【探索C++容器：vector的使用和模拟实现】（二）：https://developer.aliyun.com/article/1425781
当我们的程序运行到了39行，此时38行的代码已经运行完了，但是此时_finish还是为空指针，所以就可以断定是这一步出现了问题。
从上图我们就可以发现当我们执行_start = temp;之后，此时_start就也指向了tmp所指向的那一块空间，而此时_finish还是指向旧空间的地方，我们的size函数是使用的_finish - _start，此时_start的地址已经发生变化，_finish - _start之间相减就是未知数，所以此时程序就会报错，capacity同样如此。
void reserve(size_t n) { if(n > capacity()) { T* temp = new T[n]; size_t oldsize = size();//保存旧空间有效元素的个数 if(_start) { //这里不需要拷贝n个，只需oldsize个，因为有效元素个数为oldsize memcpy(temp,_start,oldsize*sizeof(T)); delete[] _start; } _start = temp; _finish = _strat + oldsize; _end_of_storage = _start + n; } }
运行结果：
上面为了打印输出，我们使用的是迭代器的方式，我们前面也讲到打印一共有三种方法，现在我们已经使用了一种，还有两种是范围for和[]操作符重载。范围for前面我们也已经提到它底层就是通过迭代器实现的，它是一种傻瓜式的替换，我们来看一下范围for输出结果
void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for(auto e : v) { cout << e << " "; } cout << endl; } int main() { yu::test_vector3(); return 0; }
运行结果：
vector尾插尾删的效率非常高效，但是头部或者中间插入删除效率比较一般，尽量少用，但是vector的最大优势还是随机访问。
c语言阶段学习的顺序表的随机访问是具有局限性的，是只读的，不能对内部元素进行修改。但是我们这里也可以修改，使用返回指针 + 解引用操作才可以。
int SLAT(SL* ps, int pos) { //可以获得当前位置的元素 //返回的是顺序表pos位置元素的拷贝 //但是不能对元素进行修改 } SL s; SLAT(&s, i);
c++为了解决这个问题提供了运算符重载[]和at函数，这里着重实现运算符重载，它通过传引用返回，直接可以对元素进行修改。
//此时没有加const，可读可写 T& operator[] (size_t pos)//传引用返回 { assert(pos < size()); return _start[pos]; } void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); for(int i = 0; i < v.size(); ++i) { //v.operator[](i) == v[i] cout << v[i] << " "; } cout << endl; } int main() { yu::test_vector3(); return 0; }
我们来看一下范围for输出结果
运行结果：
有了上述三种形式输出打印，此时就可以完全实现print_vector函数了，那我们就来使用范围for吧。
很奇怪，这里为什么报错了？这是因为print_vector的参数是const类型的，而我们没有实现const版本的迭代器，此时才会报错。
const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } void print_vector(const vector<int>& v) { for(auto e : v) { cout << e << " "; } cout << endl; }
此时我们再去运行一下，就没有错误了。然后我们再来实现一下尾删pop_back函数，这里比较简单，vector是不支持在单独的头插头删函数的，所以我们这里也就不实现了。
void pop_back() { assert(size() > 0); --_finish; }
此时我们再实现一下在任意位置之前插入的函数insert。
// 在pos位置插入 void insert(iterator pos,const T& x) { assert(pos >= _start && pos <= _finish); // 检查扩容 if(_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } // 把pos后面的数据移走，再把x放到pos位置 memmove(pos + 1,pos,sizeof(T)*(_finish - pos)); *pos = x; ++_finish; } void test_vector2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.insert(v.begin(), 100); print_vector(v); } int main() { yu::test_vector2(); return 0; }
运行结果：
我们再头插一个数据，看看结果如何？
此时我们头插第一个数据没有问题，为什么插入再次头插程序就崩溃了呢？我们调式一下
发现是memmove函数发生崩溃了，为什么？这里本质是一直迭代器失效，pos失效了，扩容后出现问题了。
根据上面的图我们可以知道此时的pos仍然指向旧空间的位置，没有随着新空间的开辟而变化，所以当扩容之后，此时pos指向的就是随机地址，此时访问也肯定会出错，要想解决，我们就要更新pos。
// 在pos位置插入 void insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); // 检查扩容 if (_finish == _end_of_storage) { //记录pos到_start的距离 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); //如果发生扩容 pos = _start + len; } // 把pos后面的数据移走，再把x放到pos位置 memmove(pos + 1, pos, sizeof(T) * (_finish - pos)); *pos = x; ++_finish; }
运行结果：
erase接口的实现
void erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator it = pos + 1; while (it < _finish) { *(it - 1) = *it ; ++it; } --_finish; } void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); print_vector(v); v.erase(v.begin()); print_vector(v); v.erase(v.begin() + 3); print_vector(v); } int main() { yu::test_vector6(); return 0; }
运行结果：
resize接口的实现 - 不缩容
我们先来看一下resize的第二个参数T val = T()，这使一个缺省值，如果我们没有传参的时候，T()是一个匿名对象，它使用类型T的默认构造函数来初始化元素，比如我们的string类，它就会去调用string类的默认构造函数，此时会给val初始化一个带null字符'\0'的空串，对于内置类型，在C++中它也有默认构造函数，如果内置类型是int，它就会初始化为0，是double，就会初始化为0.0。
void resize(size_t n, T val = T()) { if (n > size()) { reserve(n); //这里就包含了两种情况 /* 1.resize(8),此时n<capacity(),进入reserve函数啥事不干 2.resize(15)，此时n>capacity(),进入reserve函数扩容 */ while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } } void test_vector4() { vector<int> v; v.reserve(10); v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); print_vector(v); v.resize(8); print_vector(v); v.resize(15, 1); print_vector(v); v.resize(3); print_vector(v); } int main() { yu::test_vector4(); return 0; }
运行结果：
内置类型我们已经验证过了会调用默认的构造函数初始化val，我们再来看看自定义类型
void test_vector5() { vector<string> v; v.reserve(10); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); v.push_back("xxxx"); print_vector(v); v.resize(8); print_vector(v); v.resize(15, "yyyy"); print_vector(v); v.resize(3); print_vector(v); }
运行结果：
但是程序这里崩溃了，原因暂时先不说，我们可以观察到上面的现象就行。我们再看一下拷贝构造和赋值拷贝。
void test_vector3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); print_vector(v); // 拷贝构造 vector<int> v1 = v; print_vector(v); print_vector(v1); } int main() { yu::test_vector3(); return 0; }
运行结果：
此时我们的程序崩溃了，因为我们此时的程序没有写拷贝构造函数，此时使用的是编译器生成的默认拷贝构造函数，而它是浅拷贝，析构两次，所以程序此时就会报错。
vector(const vector<T>& v) { //开辟同样大小的空间，然后拷贝数据 _start = new T[v.capacity()]; memcpy(_start, v._start, sizeof(T) * v.size()); _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }
运行结果：
同时我们这里也可以换一种写法
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { for (auto e : v) { push_back(e); } }
我们直接通过尾插push_back函数完成拷贝构造，push_back函数会帮我们改变_start , _finish和_end_of_storage。上面我们必须要对_start , _finish和_end_of_storage进行初始化成nullptr，否则就可能是随机值，会出现错误。同时我们这里还可以简化，根据C++11，我们可以给成员变量给上缺省值。
private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; vector(const vector<T>& v) { for (auto e : v) { push_back(e); } }
我们这里还可以优化，看看下面的代码
vector(const vector<T>& v) { reserve(v.capacity()); for (const auto& e : v) { push_back(e); } }
此时提前开辟好空间，防止后面会反复开辟空间消耗时间，同时这里使用传引用拷贝，能节省很大开销。然后我们再来实现一下赋值拷贝，这里就不写传统写法的那个开空间拷贝了，这里直接使用现代写法。
void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } // 赋值拷贝现代写法 // v2 = v1,v是v1的拷贝 // 这个参数不能传引用 vector<T>& operator=(vector<T> v) { swap(v); return *this; }
【探索C++容器：vector的使用和模拟实现】（四）：https://developer.aliyun.com/article/1425787
