文章目录
vector的迭代器vector的数据结构vector的构造与内存管理
构造扩充空间其它操作
inserterase
C++语言本身提供了一个序列式容器array，array是静态空间，一旦配置了就不能改变，类似于C语言的数组。
vector的数据安排以及操作方式与array很像，但vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
vector的迭代器
vector的嵌套型别定义如下：
template class vector {public: typedef T value_type; typedef value_type *pointer; typedef value_type *iterator; // vector的迭代器是普通指针 typedef value_type &reference; typedef size_t size_type; typedef ptrdiff_t difference_type;};
alloc是SGI STL的空间配置器。
vector维护的是一个连续线性空间，因此不论其元素型别如何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator*、operator->、operator++、operator--、operator+=、operator-=，普通指针天生都具备，所以vector提供的是Random Access Iterators。
vector::iterator ivite; // ivite的类型是int*vector::iterator svite; // svite的类型是Shape*
vector的数据结构
vector采用线性连续空间存储数据，它以两个迭代器start和finish分别指向配置得来的连续空间中已被使用的范围，并以迭代器end_of_storage指向整个配置空间的尾端。
template class vector {protected: iterator start; // 目前使用空间的头 iterator finish; // 目前使用空间的尾 iterator end_of_storage; // 目前可用空间的尾};
当finish等于end_of_storage时，便是满载。下次再新增元素时，整个vector就得另觅居所。
如图所示，vector里保存了6个整型，已配置但未使用的空间里可以再存放两个元素。
使用这三个迭代器，便可轻松访问vector的元素，获取vector的容量和大小。
template class vector {public: iterator begin() { return start; } iterator end() { return finish; } size_type size() const { return size_type(end() - begin()); } size_type capacity() const { return size_type(end_of_storage - begin()); } bool empty() const { return begin() == end(); } reference operator[](size_type n) { return *(begin() + n); } reference front() { return *begin(); } reference back() { return *(end() - 1); }};
增加新元素时，如果超过当前的容量，则容量会扩充至两倍，如果两倍容量不足，就扩张至足够大的容量。
容量的扩张必须经历“重新配置、元素移动、释放原空间”等过程，工程浩大。
vector的构造与内存管理
vector默认使用alloc作为空间配置器，并据此定义了一个data_allocator，可以更方便地以元素大小为配置单位。
template class vector {protected: typedef simple_alloc data_allocator;};
simple_alloc的实现如下：
template class simple_alloc {public: static T *allocate(size_t n) { return n == 0 ? nullptr : (T*)Alloc::allocate(n * sizeof(T)); } static T *allocate() { return (T*)Alloc::allocate(sizeof(T)); } static void deallocate(T *p, size_t n) { if (n) { Alloc::deallocate(p, n * sizeof(T)); } } static void deallocate(T *p) { Alloc::deallocate(p, sizeof(T)); }};
于是，data_allocator::allocate(n)表示配置n个元素空间。
构造
vector提供了许多constructors，其中一个允许指定元素个数及初值。
template class vector {public: vector(size_type n, const T &value) { fill_initialize(n, value); } void fill_initialize(size_type n, const T &value) { start = allocate_and_fill(n, value); finish = start + n; end_of_storage = finish; } iterator allocate_and_fill(size_type n, const T &value) { iterator result = data_allocator::allocate(n); uninitialized_fill_n(result, n, value); return result; }};
uninitialized_fill_n会根据参数的型别特性决定使用fill_n或反复调用construct来完成任务。详见【空间配置器】内存基本处理工具
扩充空间
使用push_back将新元素插入vector尾端时，如果此时有备用空间，就直接构造元素，否则就需要扩充空间。
template class vector {public: void push_back(const T &value) { if (finish != end_of_storage) { construct(finish, value); ++finish; } else { insert_aux(end(), value); } } void insert_aux(iterator position, const T &x) { if (finish != end_of_storage) { // 有备用空间 construct(finish, *(finish - 1)); ++finish; T x_copy = x; copy_backward(position, finish - 2, finish - 1); *position = x_copy; } else { // 无备用空间 const size_type old_size = size(); const size_type len = old_size == 0 ? 1 : 2 * old_size; // 计算新空间的大小 iterator new_start = data_allocator::allocate(len); // 配置新空间 iterator new_finish = new_start; try { // 把旧空间中position前的数据拷贝到新空间 new_finish = uninitialized_copy(start, position, new_start); // 构造新增的元素 construct(new_finish, x); ++new_finish; // 把旧空间中position后的数据拷贝到新空间 new_finish = uninitialized_copy(position, finish, new_finish); } catch(const std::exception& e) { // commit or rollback destroy(new_start, new_finish); data_allocator::deallocate(new_start, len); throw; } // 析构旧对象、释放旧空间 destroy(begin(), end()); deallocate(); // 调整迭代器 start = new_start; finish = new_finish; end_of_storage = start + len; } }};
所谓动态增加大小，是指以原大小的两倍另外配置一块更大的空间，将原内容拷贝过来，然后再构造新元素，最后释放原空间。此时，指向原空间的迭代器会失效。
其它操作
vector是线性连续存储元素的，所以当在finish前的某个位置posiion处增删元素时，都会引起position后面元素的一轮拷贝。
insert
template class vector {public:void insert(iterator position, size_type n, const T &x);};
在position所指的位置上加上n个值为x的元素，原来的position之后的元素要后移n个位置。
erase
template class vector {public:iterator erase(iterator first, iterator last);};
将[first, last)区间内的元素删除，last及其之后的元素前移last - first个位置。
比如有如下的vector：
执行insert(begin() + 2, 2, 7);语句后，会变成这个样子：
再执行erase(begin() + 1, begin() + 4);后，是这个样子：