引言
关于STL容器的学习，我们来到了运用最广泛、最常见的vector。有了之前关于string的学习，我们对容器设计有了一个大概的了解，而今天在熟悉的基础上去探求vector相比于string有哪些异同，同时迎来更多的新挑战……
一、成员变量
vector类中包含了
- _start（指向有效空间的头）
- _finish（指向有效空间的尾）
- _end_of_storage（指向可用空间的尾）
细节：
- 三个成员变量均迭代器（此刻即指针）
- 使用缺省值，不必写多份初始化列表
template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; };
二、默认成员函数
2.1 constructor
无参构造
vector() {}
带参构造
细节：
- 分别重载 size_t 和 int 类型，防止参数匹配时，匹配到迭代器区间构造，从而导致间接寻址错误
- 初始化的val的缺省值，是匿名构造的对象
vector(size_t n, const T& val = T()) { reserve(n); for (size_t i = 0; i < n; ++i) { _start[i] = val; } _finish = _start + n; } vector(int n, const T& val = T()) { reserve(n); for (int i = 0; i < n; ++i) { _start[i] = val; } _finish = _start + n; }
迭代器区间构造
细节：
- 使用类模板，可以传任意类型的迭代器
- 迭代器访问，条件最好使用不等于（！=）
template <class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } }
2.2 destructor
~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; }
2.3 copy constructor
近代写法
细节：
- 先开辟一维空间
- 再用赋值重载，进行深拷贝（不能用memcpy，它是浅拷贝）
vector(const vector<T>& x) { _start = new T[x.capacity()]; for (size_t i = 0; i < x.size(); ++i) { _start[i] = x._start[i]; } _finish = _start + x.size(); _end_of_storage = _start + x.capacity(); }
现代写法
细节：
- 用迭代器区间构造，构造出临时对象
- 再使用vector中的swap，交换*this和tmp的值，完成拷贝构造
vector(const vector<T>& x) { vector<T> tmp(x.begin(), x.end()); swap(tmp); }
2.4 operator=
近代写法
细节：大体与拷贝构造相同
vector<T>& operator=(const vector<T>& x) { if (this != &x) { _start = new T[x.capacity()]; for (size_t i = 0; i < x.size(); ++i) { _start[i] = x._start[i]; } _finish = _start + x.size(); _end_of_storage = _start + x.capacity(); } return *this; }
现代写法
细节：
- 传参变成传值，这样就会拷贝构造出一个临时对象
- 再使用vector中的swap，交换*this和tmp的值，完成赋值重载
vector<T>& operator=(vector<T> x) { swap(x); return *this; }
三、迭代器
3.1 begin
迭代器的实现和编译器有关，不同的编译器有不同的实现方式。这里用指针来实现迭代器。
同时，重载了普通迭代器和const迭代器。
iterator begin() { return _start; } const_iterator begin() const { return _start; }
3.2 end
迭代器遵循左闭右开的原则，begin指向首元素，end指向末元素的下一位。
iterator end() { return _finish; } const_iterator end() const { return _finish; }
悄悄告诉你：范围for的底层实现，就是运用了迭代器。
四、元素访问
4.1 operator[ ]
为了方便的访问元素，我们重载了[ ]运算符。同时，也分为普通版本和const版本，对应不同vector类的权限。
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
五、容量
5.1 size
获取当前有效数据个数
细节：const修饰，保证普通和const类型vector类都能访问
size_t size() const { return _finish - _start; }
5.2 capacity
获取当前最大有效容量
细节：同上
size_t capacity() const { return _end_of_storage - _start; }
看了上面size和capacity的实现，是不是就瞬间明白_start、_finish和_end_of_storage的含义了？
悄悄告诉你：其实当你不懂成员变量的含义时，可以先看看size和capacity的实现。
5.3 reserve
改变当前最大容量
细节：
- 只扩容，不缩容
- 用赋值重载，进行深拷贝
- 更新成员变量时（如果按照顺序更新），先保存size的大小，防止_finish失效。因为如果为_finish = tmp + size()，等价于_finish = tmp + _finish - _start，而_start已经更新了，所以size()计算的大小失效，最终_finish并没有更新。
void reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; if (_start) { for (size_t i = 0; i < size(); ++i) { tmp[i] = _start[i]; } delete[] _start; } size_t sz = size(); _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } }
5.4 resize
改变当前有效数据个数
细节：
- 如果n<size，则减少有效个数，如果n>size，则填充指定值，直至达到n个
- 运用赋值重载，实现深拷贝
void resize(size_t n, T val = T()) { if (n > size()) { reserve(n); for (size_t i = size(); i < n; ++i) { _start[i] = val; } } _finish = _start + n; }
5.5 empty
判断是否为空
细节：const修饰，保证普通和const类型vector类都能访问
bool empty() const { return _start == _finish; }
六、修改
6.1 push_back
尾插
细节：需要扩容时，判断容量是否为空
void push_back(const T& val) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } *_finish = val; ++_finish; }
6.2 pop_back
尾删
细节：断言vector不为空，才进行删除
void pop_back() { assert(!empty()); --_finish; }
6.3 insert
指定位置插入
细节：
- 断言判断pos的合法性
- 扩容前，先保存pos的相对位置，扩容后，刷新pos，防止迭代器失效
- 返回指向新插入元素的迭代器，防止迭代器失效
iterator 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 end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = val; ++_finish; return pos; }
6.4 erase
指定位置删除
细节：
- 断言判断pos的合法性
- 返回指向删除元素的后一位的迭代器，防止迭代器失效
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator start = pos + 1; while (start < _finish) { *(start - 1) = *start; ++start; } --_finish; return pos; }
上述有两种迭代器失效：
- 野指针
- 指向含义改变
关于迭代器失效，我们统一认为，进行过插入或删除操作的迭代器pos，已经失效，不能再使用。只有接收其返回值，刷新pos，才能重新使用。
6.5 swap
交换两个vector类的值
细节：使用std库中的swap函数，交换各个成员变量的值
void swap(vector<T>& x) { std::swap(_start, x._start); std::swap(_finish, x._finish); std::swap(_end_of_storage, x._end_of_storage); }
总结
我们在有了学习string的基础后，学习vector的成本降低了不少，函数名和用法大体相同。但是，我们依旧遇到了新的问题与挑战，如多层深拷贝，迭代器失效等。我与C++的故事，仍在无声地诉说……
真诚点赞，手有余香
