vector的介绍
vector是一个可变的数组序列容器。
1.vector的底层实际上就是一个数组。因此vector也可以采用连续存储空间来存储元素。也可以直接用下标访问vector的元素。我们完全可以把它就当成一个自定义类型的数组使用。
2.除了可以直接用下标访问元素，vector还支持动态开辟空间以提高其灵活度。这也是vector与数组最大的区别之一。
3.为了减少不断插入元素带来的扩容消耗问题，vector会分配一些额外的空间以适应可能的增长，因此实际开辟的空间需要比已存在元素占有空间要大。vector的底层采用每次扩容原来空间的1.5或者2倍（不同编译器的扩容策略可能不同）。
4.由于底层是用数组实现的，不可避免地也具有数组的缺点，即除了尾插的插入、删除的效率低下。
vector的使用
关于vector的使用在cplusplus上一览无余。我接下来介绍常用的一些接口。
vector的定义
vector一共有4个构造函数，分别对应不同的构造场景。
1.
vector().无参构造2.
vector(size_type n,const value_type& val=value_type()).构造并且初始化n个元素的值为value.3.
vector(const vector& x).拷贝构造4.
vector(InputIterator first,InputIterator last).迭代器初始化构造#include <iostream> #include <vector> int main() { // constructors used in the same order as described above: std::vector<int> first; // 无参构造 std::vector<int> second(4, 100); // 构造的同时初始化4个元素都为100 std::vector<int> third(second.begin(), second.end()); // 迭代器初始化构造 std::vector<int> fourth(third); // 拷贝构造 //迭代器初始化构造示例 int myints[] = { 16,2,77,29 }; std::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); std::cout << "The contents of fifth are:"; for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; }
vector迭代器的使用
其中rbegin和rend是反向迭代器reverse_iterator类型，rbegin指向的是vecotr对象的最后一个元素，遍历方式和begin一样，只不过反向迭代器++的时候是往前移动。rend则指向vector第一个元素。
带c表示用const修饰了thsi指针。比如cbegin和cend都用const修饰迭代器指向的内容，即不可以修改迭代器指向元素的值。
const_iterator cbegin() const noexcept; • 1
vector空间增长问题
跟vector空间有关的成员函数有
1.size（）返回当前元素个数
2.max_size（）返回vector最多能容纳元素的个数
3.关于resize
void resize (size_type n, value_type val = value_type()); • 1
resize可以调整vector的元素个数为n。
如果n<size(),删除后面的元素.
如果n>size(),增加元素个数到n,新增元素的值为val。
值得注意的是，如果n>size()并且大于capacity(),则会先扩容到n。
4.capacity()返回当前容量大小。vs下capacity是按1.5倍增长的，g++是按2倍增长的。
5.reserve()
void reserve (size_type n);
reserve(n)要求扩容到至少可以容纳n个元素。
6.shrink_to_fit()要求缩容到合适的容量。这个函数一般不常用。
vector扩容机制
用以下代码观察vs下的vector的扩容机制
int main() { vector<int>A; int t = A.capacity(); for (int i = 0; i < 20; i++) { A.push_back(i); if (A.capacity() != t) {//每次容量发生改变就打印并输出 cout << A.capacity() << endl; t = A.capacity(); } } }
每次扩容都是1.5倍，向下取整。
同样的代码，来看g++环境下的扩容机制：
每次扩容都是原来的2倍！
vector的增删查改
assign：
range(1)版本的assign函数可以用迭代器给vector对象重新赋值。会覆盖原来的内容，相当于赋值操作。
fill(2)版本的assign函数可以赋值给调用对象n个value的值。
push_back：尾插一个元素
pop_back:弹出最后一个元素
insert:
single element（1）版本，在迭代器position指向的位置处插入一个val.
fill（2）版本，可以在迭代器position指向的位置处插入n个值为val的元素。
range（3）版本，在position指向的位置处，插入一段首尾迭代器指向的所有元素。
erase:
可以删除position指向位置的元素，或者删除first-last所有指向元素。
swap：交换两个vector对象。
clear:清空vector对象的所有元素，并不会清空容量。
emplace:
可以在position指向位置处插入一个以args为参数构造出来的新元素，并返回插入成功后指向该位置的迭代器。
emplace_back:作用跟empace函数类似，只不过是尾插。
迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
简单来说就是我们在扩容的时候会开辟新空间，如果原来的迭代器没有被更新，还是指向原来的地址，那么就会造成程序崩溃。也有可能是在
具体有以下几种情况造成迭代器失效：
- 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
- 指定位置元素的删除操作–erase
erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代
器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是
没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效
了。
3.与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。
迭代器失效解决办法：使用之前更新迭代器。
vector的模拟实现
vector.h包含了类的声明与定义。我这里没有分离。
#define _CRT_SECURE_NO_WARNINGS 1 #include<assert.h> #include<string> #include<algorithm> #include<iostream> namespace bit { template<class T> class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; template<class T> friend void Swap(vector<T>& A, vector<T>& B); iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const{ return _start; } const_iterator end() const { return _finish; } // construct and destroy vector() { _start = _finish = _endOfStorage = nullptr; } vector(int n, const T& value = T()) { reserve(n); for (size_t i = 0; i < n; i++)push_back(value); } template<class inputiterator> vector(inputiterator first, inputiterator last) { size_t n = last - first; reserve(n); memcpy(_start, first, n * sizeof(T)); _finish = _start + n; _endOfStorage = _start + n; } vector(const vector<T>& v) { reserve(v.capacity()); for (auto& it : v) { push_back(it); } } vector<T>& operator= (vector<T> v) { reserve(v.capacity()); memcpy(_start, v._start, v.size() * sizeof(T)); _finish = _start + v.size(); return *(this); } ~vector() { delete[] _start; _start = _finish = _endOfStorage = nullptr; } // capacity size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } void reserve(size_t n) { if (n>capacity()) { T* temp = new T[n]; size_t sz = size(); // memcpy(temp, _start, sz * sizeof(T)); for (size_t i = 0; i < sz; i++) { temp[i] = _start[i]; } delete[] _start; _start = temp; _finish = _start + sz; _endOfStorage = _start + n; } } void resize(size_t n, const T& value = T()) { if (n > size()) { reserve(n); T* begin = _start + size(); while (begin < _start + n) { *begin = value; begin++; } } else { _finish = _start + n; } } ///access/// T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; } ///modify/ void push_back(const T& x) { if (size() == capacity()) { reserve(capacity()==0?4:capacity()*2); } *_finish = x; _finish++; } void pop_back() { assert(size() > 0); _finish--; } void Swap(vector<T>& v) { std::swap(v._start, _start); std::swap(v._finish, _finish); std::swap(v._endOfStorage, _endOfStorage); } bool empty() { return size() == 0; } iterator insert(iterator pos, const T& x) { assert(pos <= _finish&&pos>=_start); size_t len = pos - _start; reserve(size() + 1); pos = _start + len; iterator end = _finish-1; while (end >= pos) { *(end+1) = *end; end--; } *pos = x; _finish++; return _start; } iterator erase(iterator pos) { assert(pos < _finish && pos >= _start); iterator begin = pos+1; while (begin <_finish) { *(begin - 1) = *(begin); begin++; } _finish--; return _start; } private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾 }; template<class T> void Swap(vector<T>& A, vector<T>& B) { std::swap(A._start, B._start); std::swap(A._finish, B._finish); std::swap(A._endOfStorage, B._endOfStorage); } }
这里值得注意的是，如果对象中涉及到资源管理时（比如用reserve扩容），千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
比如vector<string>,在扩容拷贝原来的数据的时候就不能使用memcpy,因为memcpy对于string底层的指针只是值拷贝。也就意味着，新空间里的string指针和旧空间里的指针指向的空间是一样的。
