#include<vector>
vector占用一块连续分配的内存，一种可以存储任意类型的动态数组，与array不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。
属性：
// alloc是SGI STL的空间配置器
template <class T, class Alloc = alloc>
class vector
{
public:
// vector的嵌套类型定义,typedefs用于提供iterator_traits<I>支持
typedef T value_type;//数据类型
typedef value_type* pointer;//指针
typedef value_type* iterator;
typedef value_type& reference;//引用
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
// 这个提供STL标准的allocator接口
typedef simple_alloc <value_type, Alloc> data_allocator;//simple_alloc是SGI STL的空间配置器
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示实际分配内存空间的尾
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数据结构如下，通过三个迭代器start, finish, end_of_storage的系列public接口，可很好地完成数据存储、溢出判断(iter >= iv.end())、大小、容量(容量与大小不等，以免不断申请空间耗费资源)、重载操作符[]、判空、最前元素、最后元素等等。
vector 原始对象本身大小为12（32位）对应3个指针。
iterator start; // 表示目前使用空间的头
iterator finish; // 表示目前使用空间的尾
iterator end_of_storage; // 表示实际分配内存空间的尾
在VS中可用sizeof(vector)来输出查看。
vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素，vector动态增加大小时，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。
size==capacity
- size:实际所包含的元素个数
- capacity:容器的容量,指的是在不分配更多内存的情况下，容器可以保存的最多元素个数
- 1、完全弃用现有的内存空间，成倍申请更大的内存空间；
- 2、将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
- 3、最后将旧的内存空间释放。
面试热点：
vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效。
start不再指向相同的地址，扩大空间是新请新的更大的空间，因而不仅是start迭代器，其它指向空间变化前vector的迭代器都将失效
void push_back(const T& x)
{
// 内存满足条件则直接追加元素, 否则需要重新分配内存空间
if (finish != end_of_storage)
{
construct(finish, x);
++finish;
}
else
insert_aux(end(), x);
}
iterator insert(iterator position, const T& x)
{
size_type n = position - begin();
if (finish != end_of_storage && position == end())//尾部插入，等同push_back,并且容量没满
{
construct(finish, x);
++finish;
}
else
insert_aux(position, x);
return begin() + n;//返回插入位置的迭代器
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x)
{
if (finish = != end_of_storage) // 还有备用空间
{
construct(finish, *(finish - 1)); // 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值
++finish; // 调整finish
// 把[position,finish - 2]的元素后移一位
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 ? 2 * ols_size : 1;
// 以上配置原则，如果原大小为0，则配置1（个元素）
// 如果原大小不为0，则配置原大小的两倍
// 前半段用来放置源数据，后半段准备用来放置新数据
iterator new_start = data_allocator::allocate(len); // 实际配置
iterator new_finish = new_start;
try {
// 将原 vector 的内容拷贝到新的 vector
// uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
// 迭代器 first 指向输入端的起始位置, 迭代器 last 指向输入端的结束位置(前闭后开区间)
// 迭代器 result 指向输出端(欲初始化空间)的起始位置
new_finish = uninitialized_copy(start, position, new_start);
// 为新元素设定初值x
construct(new_finish, x);
// 调整finish
++new_finish;
// 将安插点的原内容也拷贝过来
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch (...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
// 析构并释放原 vector
destory(begin(), end());
deallocate();
// 调整迭代器, 指向新 vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
// 将[first,last]按倒序赋值给[first - (result-last), last - (result-last)]
// (result-last)大于0时，相当于将元素[first,last]后移(result-last)位
// (result-last)小于0时，相当于将元素[first,last]前移(result-last)位
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result )
{
while (last != first) *(--result) = *(--last);
return result;
}
参考
vector():创建一个空vector
vector(int nSize):创建一个vector,元素个数为nSize
vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
vector(const vector&):复制构造函数
vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中
实例：
//int型vector
vector<int> vecInt;
//float型vector
vector<float> vecFloat;
//嵌套vector
vector<vector<int>> vec;
//结构体或类 类型的vector
class A
{
//空类
};
vector<A> vecA
struct B
{空结构体}
vector<B> vecB
//使用构造函数的初始化
//int型vector,包含3个元素
vector<int> vecIntA(3);
//int型vector,包含3个元素且每个元素都是9
vector<int> vecIntB(3,9);
//复制vecIntB到vecIntC
vector<int> vecIntC(vecIntB);
//复制数组中begin-end这段区间上的值到vector中
int iArray[]={2,4,6};
vector<int> vecIntD(iArray,iArray+3);
void push_back(const T& x):向量尾部增加一个元素X //使用vector函数添加数
//使用迭代器添加数
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
//push_back在尾部插入数字1
vector<int> vecIntA;
vecIntA.push_back(1);
//使用迭代器在第一个位置插入数值888
vector<int> vecIntB;
vector<int>::iterator it;
vecIntB.insert(it=vecIntB.begin(),888);
//使用迭代器在第一个位置前插入数值3个888
vector<int> vecIntC;
vector<int>::iterator it;
vecIntC.insert(it=vecIntC.begin(),3,888);
iterator erase(iterator it):删除向量中迭代器指向元素
iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
void pop_back():删除向量中最后一个元素
void clear():清空向量中所有元素
//删除最后一个元素
vecIntA.pop_back();
//删除第四个位置的元素
vector<int> vecIntA;
vecIntA.erase(vecIntA.begin()+4);
//删除第2-5个元素
vecIntA.erase(vecIntA.begin()+1,vecIntA.begin()+5);
判断容器是否为空：vec.empty（）
传回第一个数据：vec.front();
清空：vec.clear()；
向量数量：vec.size()；
#include<algorithm>,
reverse(vec.begin(),vec.end());
#include<algorithm>
sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大)。
可以通过重写排序比较函数按照降序比较，如下：
//定义排序比较函数：
bool Comp(const int &a,const int &b)
{
return a>b;
}
调用时:
sort(vec.begin(),vec.end(),Comp)，这样就降序排序。
源码参考
1、https://www.cnblogs.com/sooner/p/3273395.html
2、https://blog.csdn.net/wizardtoh/article/details/82532236
3、https://blog.csdn.net/u011028345/article/details/60475566
4、《STL源码剖析》