从零实现C++ Vector容器
·
一、vector的模拟实现讲解
1. vector的成员变量
//类模板
template<class T>
class vector
{
private:
iterator _start = nullptr;//指向空间的起始位置
iterator _finish = nullptr;//指向存储位置的末尾
iterator _end_of_storage = nullptr;//指向空间位置的末尾
};
2. vector的构造函数
vector()
{
}
在成员变量声明的位置给了缺省值，这里就可以不用再一次初始化。之所以这样做，是因为拷贝构造函数也要对成员进行初始化，如果不在声明位置给缺省值，那么拷贝构造函数也要写初始化列表，这样代码就冗余了。
那么，这时候可能就有人问了，我们不写无参的构造函数不就好了吗？创建对象时，不一定需要传递参数，所以需要无参的构造函数。拷贝构造函数也是构造函数，如果不显示写无参的构造函数，那么编译器也不会再自动生成默认构造函数。
3. reserve
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
//memcpy进行浅拷贝，当T实例化为string类型时(内部有指向的资源时)，就会存在多次析构的问题
//memcpy(tmp, _start, sizeof(T) * oldSize);
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}
这里不能使用memcpy拷贝数据，因为memcpy是浅拷贝，如果vector存的是内置类型，那没关系。可是如果存的是string对象（或者是其它的自定义类型对象），那么大概率是有问题的。浅拷贝会使两个vector对象中的string指向同一个字符串，那么，在析构时，就会对同一个空间进行多次析构，造成野指针问题。一个vector对象释放也会影响另一个vector对象的内容。
vector<string>对象里的
tmp（新开辟的空间）里的
可以看到，_Ptr指向的空间地址是一样的，所以析构时肯定有问题。因此，需要写一个深拷贝，不能使用memcpy函数。像上面代码一样就可以实现深拷贝了。这是调用了string库里面的赋值运算符重载函数，库里面实现的就是深拷贝。
4. push_back
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
//扩容
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = val;
++_finish;
}
当存储空间满了，就需要扩容，容量初始值为0，所以需要判断一下，为0就开4个空间，否则开2倍空间。
5. pop_back
//尾删
void pop_back()
{
assert(_finish > _start);
--_finish;
}
6.operator[]
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n)const
{
assert(n < size());
return _start[n];
}
像数组一样访问就可以了。
7.resize
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
当 n < size时，删除数据，反之，直接开辟新空间，在插入数据。
这里将两种情况合并为一种情况，本来应该是 n > size && n < capacity，直接插入数据即可，当 n > capacity时，才需要开辟空间并插入数据。
8. operator=
vector& operator=(const vector& v)
//vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
return *this;
}
为了防止自己给自己赋值的情况，所以需要判断this指针与vector对象的地址是否一样。不一样，说明是两个vector对象，释放掉旧空间，将指针变量置空，开辟新空间，再插入数据。
这里之所以要对指针变量置空，是因为如果vector存的是自定义类型，例如string，那么，在delete释放空间时，调用的是string的析构，不会将指针变量置空，所以，我们需要手动将指针变量置空。
这是传统写法，下面看现代写法是如何实现的。
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//拷贝构造函数+swap完成赋值重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
最大的区别就在于，赋值运算符重载函数的参数不再是已存在vector对象的引用，而是一个全新的vector对象。这就意味着，在调用赋值运算符重载之前，需要先调用拷贝构造函数初始化赋值运算符重载的函数参数，再进行资源上的交换，就完成了赋值重载。
赋值函数参数是一个局部对象，出了函数作用域就会被销毁，所以，直接利用交换函数，交换资源，就可以完成赋值，而这个局部对象会被销毁，进而释放掉旧资源。
9. insert
测试用例
这样写是不对的。那么这是为什么呢？
扩容前
扩容后
可以看到，扩容后，迭代器的位置已经不再有效，这种情况叫做迭代器失效。再去执行下面的操作就会出错，就相当于野指针了，vector的底层是数组，可以用原生指针模拟迭代器的行为。
这是因为扩容后导致的迭代器的插入位置不对，所以，需要扩容后更新迭代器的插入位置。就要按照下面这样去写。
//迭代器失效
void insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
//扩容前计算迭代器的相对位置
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
//扩容后，更新迭代器的插入位置
pos = _start + len;
}
//挪动数据
iterator it = _finish - 1;
while (it >= pos)
{
*(it + 1) = *it;
--it;
}
*pos = val;
++_finish;
}
10. erase
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
迭代器失效的第二个原因：vs下会强制检查。
我们用一段程序来说明问题。
可以看到，这样删除所有的偶数是有问题的。那么，为什么呢？用一幅图来说明原因。
这样判断在移除偶数之后，_finish–，it1++，会导致偶数后面一个错过判断，从而发生错误。所以应该删除偶数之后，继续从当前位置判断，不应该让it1++。
当然了，这里插入的数据恰好让it1最后等于了_finish，结束循环。也有可能让it1与_finish最后也错过了，再去解引用就会出现野指针。
这个测试用例就会越界。
这样就正确了。但是我们还没有验证迭代器失效的原因呢？验证这个答案，我们需要使用C++提供的vector才可以。
结论：insert，erase以后，不同平台实现有差异，统一认为迭代器失效。失效的迭代器，需要更新以后才能使用。
11. 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
12. 拷贝构造
//v3(v1)
vector(const vector& v)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
13. size,capacity
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
指针 - 指针就可以得到存储的个数和空间的容量。
二、完整代码
. vector.h
#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<assert.h>
using namespace std;
namespace LC
{
//类模板
template<class T>
class vector
{
typedef T* iterator;
typedef const T* const_iterator;
public:
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
vector()
{
}
//v3(v1)
vector(const vector& v)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
//memcpy进行浅拷贝，当T实例化为string类型时(内部有指向的资源时)，就会存在多次析构的问题
//memcpy(tmp, _start, sizeof(T) * oldSize);
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
//扩容
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = val;
++_finish;
}
void pop_back()
{
assert(_finish > _start);
--_finish;
}
T& operator[](size_t n)
{
assert(n < size());
return _start[n];
}
const T& operator[](size_t n)const
{
assert(n < size());
return _start[n];
}
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
//vector& operator=(const vector& v)
////vector<T>& operator=(const vector<T>& v)
//{
// if (this != &v)
// {
// delete[] _start;
// _start = _finish = _end_of_storage = nullptr;
// reserve(v.capacity());
// for (const auto& e : v)
// {
// push_back(e);
// }
// }
// return *this;
//}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//拷贝构造函数+swap完成赋值重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//迭代器失效
void insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator it = _finish - 1;
while (it >= pos)
{
*(it + 1) = *it;
--it;
}
*pos = val;
++_finish;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
. test.cc
#define _CRT_SECURE_NO_WARNINGS
#include"vector.h"
void TestVector1()
{
LC::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
cout << v1[3] << endl;
LC::vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(30);
v2.push_back(40);
v2.push_back(50);
v1 = v2;
for (auto& e : v1)
{
cout << e << " ";
}
cout << endl;
LC::vector<int> v3 = v1;
for (auto& e : v3)
{
cout << e << " ";
}
cout << endl;
LC::vector<string> v4;
cout << typeid(v4).name() << endl;
}
void TestVector2()
{
LC::vector<string> v1;
v1.push_back("111111111111111111111111");
v1.push_back("111111111111111111111111");
v1.push_back("111111111111111111111111");
v1.push_back("111111111111111111111111");
//v1.push_back("111111111111111111111111");
for (auto& e : v1)
{
cout << e << " ";
}
cout << endl;
LC::vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(30);
v2.push_back(40);
//扩容导致的迭代器失效
//insert以后，默认迭代器都失效了
v2.insert(v2.begin(), 60);
for (auto& e : v2)
{
cout << e << " ";
}
cout << endl;
}
void TestVector3()
{
LC::vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(30);
v2.push_back(40);
int i = 0;
cin >> i;
//auto it = v2.begin() + i;
////形参的改变不影响实参
//v2.insert(it, 66);
auto it = v2.begin();
//形参的改变不影响实参
v2.insert(it + i, 66);
//cout << *it << endl;
for (auto& e : v2)
{
cout << e << " ";
}
cout << endl;
//删除所有的偶数
//auto it = v2.begin();
auto it1 = v2.begin();
while (it1 != v2.end())
{
if (*it1 % 2 == 0)
{
it1 = v2.erase(it1);
}
else
{
++it1;
}
}
}
int main()
{
TestVector1();
return 0;
}
更多推荐
34
0- 0
已为社区贡献5条内容
所有评论(0)