四、容量相关的函数
1.size和capacity
size_t size() const { return _finish - _start;//返回的是容器中有效数据的个数 } size_t capacity() const { return _end_of_storage - _start;//返回的是容器的实际有效容量 }
2.reserve
reserve增容：
1.当 n > capacity 时，将capacity扩大到n；
2.当 n < capacity 时，不进行任何操作；
void reserve(size_t n) { if (n > capacity())//判断是否需要扩容 { //扩容 size_t sz = size(); //提前算好增容前的数据个数 T* tmp = new T[n]; //开辟n个空间 if (_start) { //数据拷贝，也不能去使用memcpy函数 for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[]_start; //释放旧空间 } _start = tmp; //指向新空间 _finish = _start + sz; _end_of_storage = _start + n; } }
对于reserve，我还需要注意两个问题：
1.对增容前的数据个数进行记录
如果不提前算好增容前的数据个数，而是在增容完后更新_start，对于_finish和_end_of_storage都会出现问题，因为增容完后，就需要释放旧空间。
2.增容前后的数据拷贝不能使用memcpy
如果使用memcpy进行数据的拷贝后，随着_start的释放，tmp作为新的_start后，当进行访问操作时，就存在非法访问
3.resize
当n<size时，是缩容，相应的数据会减少，只需要调整一下_finish的位置
当n>size时，我们还需要判断n是否大于capacity，是否增容
在resize函数中的第二个参数val，采用的是缺省（匿名对象），因为我们并不知道T是什么类型，如果是int/int*给val = 0是可以的，但是T还有可能是vector，我们给到匿名对象作为缺省值的好处在于，对于内置类型它也有自己的默认构造函数
例如: int i = int(); // i = 0 int j = int(10);// j = 10
当我们不给val传任何参数时，它会去调用自己的默认构造函数给val
void resize(size_t n, const T& val = T()) //T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期 { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish != _start + n) { *_finish = val; ++_finish; } } }
五、增删查改相关的函数
1.push_back
尾插数据时，首先需要判断容器是否已满，若满则去调用reserve
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; }
2.pop_back
在进行尾删时，需要判断容器是否为空，我们这里并没有实现vector的判空操作，可以利用_finish和_start之间的关系进行判断。
void pop_back(const T& x) { assert(_finish > _start); --_finish; }
3.insert
insert是在某个位置插入数据，插入数据就存在是否扩容，如果不需要扩容，插入数据时不会存在然后的问题；如果需要扩容，但未调整pos，会存在pos失效；
iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _end_of_storage) { //扩容会导致pos失效，需要更新一下pos size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } void test_vector4() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); vector<int>::iterator it = find(v1.begin(), v1.end(), 2); if (it != v1.end()) { //如果insert中发生了扩容，那么会导致it指向的空间被释放 //it本质就是一个野指针，这种问题，我们叫做迭代器失效 v1.insert(it, 30); } for (auto e : v1) { cout << e << " "; } cout << endl; }
当插入数据需要扩容时，扩容会将旧空间的数据拷贝到新空间，再释放旧空间，此时pos就指向了一块释放的空间，再对pos位置进行访问时，就属于野指针问题，一般我们还需要加上对pos位置的提前调整，防止迭代器失效。
insert的返回值是iterator：虽然在插入数据的过程中调整了pos，解决了内部的迭代器失效问题，但是外部的迭代器（it）还是失效的，我们需要将更新后的迭代器利用返回值的形式返回，防止需要再次使用这个迭代器时发生失效。
4.erase
erase也会存在迭代器失效的问题
iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1) = *begin; ++begin; } --_finish; return pos; } void test_vector5() { vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); //要求删除v1中所有的偶数 // g++下 vs下 // 1 2 3 4 5 --> 正常 断言报错 vector的迭代器的失效主要是在insert和erase中 // 1 2 3 4 --> 崩溃 断言报错 // 1 2 4 5 --> 结果不对 断言报错 //测试库中的erase --- 存在失效 vector<int> v2; v2.push_back(1); v2.push_back(2); v2.push_back(3); v2.push_back(4); v2.push_back(5); std::vector<int>::iterator it = v2.begin(); while (it != v2.end()) { if (*it % 2 == 0) { v2.erase(it); } ++it; } /*************************************************/ vector<int>::iterator it = v1.begin(); while (it != v1.end()) { if (*it % 2 == 0) { it = v1.erase(it);//每次跟新一下迭代器，不会存在失效了 } else { ++it; } } for (auto e : v1) { cout << e << " "; } cout << endl; }
5.swap
void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }
六、完成代码
#pragma once namespace vec { template<class T> class vector { //typedef T* iterator;//typedef也受访问限定符的限制，放在这里默认是私有的 public: typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} //v2(v1) //传统写法 /* vector(const vector<T>& v) { _start = new T[v.capacity()]; _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); memcpy(_start, v._start, v.size() * sizeof(T));//存在浅拷贝 } vector(const vector<T>& v) { _start = new T[v.capacity()]; //让v2开辟一块和v一样大小的空间 for (size_t i = 0; i < v.size(); i++) { _start[i] = v[i];//通过循环进行赋值 } //最后调整_finish和_end_of_storage的大小 _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } */ //v2(v1) //现代写法 //一个类模板的成员函数，又可以是一个函数模板 template <class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); ++first; } } vector(const vector<T>& v)//也支持vector(const vector& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { vector<T> tmp(v.begin(), v.end()); swap(tmp); //this->swap(tmp); } //v1 = v2 //vector<T>& operator=(const vector<T>& v) //传统写法 //vector& operator=(vector v)语法上也支持这样写 vector<T>& operator=(vector<T> v)//推荐写 { swap(v); return *this; } ~vector() { if (_start) { delete[] _start; _start = _finish = _end_of_storage = nullptr; } } const T& operator[](size_t i) const { assert(i < size()); return _start[i]; } T& operator[](size_t i) { assert(i < size()); return _start[i]; } 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 sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * size());存在浅拷贝 for (size_t i = 0; i < sz; i++) { //T是int，一个一个拷贝没问题 //T是自定义类型，一个个拷贝调用的是深拷贝赋值，也没问题 tmp[i] = _start[i]; } delete[]_start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } void resize(size_t n, const T& val = T()) //T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期 { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish != _start + n) { *_finish = val; ++_finish; } } } iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _end_of_storage) { //扩容会导致pos失效，需要更新一下pos size_t len = pos - _start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1) = *begin; ++begin; } --_finish; return pos; } void push_back(const T& x) { if (_finish == _end_of_storage) { //扩容 reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; } void pop_back(const T& x) { assert(_finish > _start); --_finish; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
