容器大致分为序列式容器（Sequence），关联式容器（Associative）和无序容器（Unordered），无序容器也可以归为关联式容器内。
序列式容器（Sequence）
- array：数组，是一种固定大小的结构，静态空间，配置后大小就不能改变。
- vector：动态数组，单向开口的线性连续空间，可动态配置空间，原理是每次扩容时二倍增长，再将原空间数据拷贝到新空间中。
- deque：是一种双向开口的线性连续空间，可在头和尾进行插入和删除操作。
- list：链表结构，不是线性连续空间，使用指针寻址，这里指的是双向链表。
- forward-list：单向链表
- stack/queue：栈和队列，底层都是使用双向开口的deque包装后实现的。
关联式容器（Associative）
- set/multiset：以红黑树为基础的结构，可以存放key。对于set来说key不可以重复，multiset的key可以重复。
- map/multimap：以红黑树为基础的结构，可以存放key和value，对于map来说key不可以重复，multimap的key可以重复。
- unordered set/multiset：以哈希表为基础的结构，可以存放key。对于set来说key不可以重复，multiset的key可以重复。
- unordered map/multimap：以哈希表为基础的结构，可以存放key和value，对于map来说key不可以重复，multimap的key可以重复。
vector的数据结构：
vector内部有三个迭代器，start，finish和end of storage。
start和finish指向已占用空间的首端和尾端（注意这个尾端是最后一个元素的下一位，左闭右开）
end of storage指向整块连续空间的尾部。
代码如下：
template <class T ,class Alloc=alloc>
class vector {
...
protected:
iterator start;
iterator finish;
iterator end_of_storage;
...
}
vector的大小也一目了然。一个指针4个字节（32位），所以vector在这个版本中的大小为12个字节。
这三个迭代器的存在，vector提供的其他诸如计算数据大小size,容器容量capacity的各种方法就可以很容易地实现。
template <class T,class Alloc=alloc>
class vector {
...
public:
iterator begin(){return start};//1
iterator end(){return finish};//1
size_type size() const {return size_type(end()-begin());}//2
size_type capacity() const{//3
return size(end_of_storage-begin());
}
bool empty() const {return begin()==end();}//4
reference operator[](size_type n){return *(begin()+n);}//5
reference front(){return *begin();}//6
reference back(){return *(end()-1);}//6
}
解释：
- begin()和end()的实现很直接，返回我们上面说的的start和finish迭代器（指针）。
- 数据的大小size()就是返回尾减去头的结果。这里使用finish-start更快，但是使用begin()-end()方便维护。
- 容器的容量capacity()的实现是返回指向整块空间尾部的迭代器减去开头的结果。
- 空的情况就是头与尾相等。
- 重载[]，也就是我们常用的取vector中的下标元素，返回的是解引用的结果（下标从0开始）。
- 返回第一个元素和最后一个元素的实现是使用begin()和end()解引用的结果。注意end()指向的是最后一个元素的下一位置。
vector的内存是二倍增长的，当放数据时发现空间已经满了，vector就会寻找新的二倍大小的空间，再将原来的值复制过去，然后释放原空间。
我们从push_back()这个插入新元素的操作就可以看到vector内存管理的方法：
void push_back(const T& x)
{
if(finish != end_of_storage)
{
construct(finish,x);
++finish;//移动迭代器
}
else
{
insert_aux(end(),x);
}
}
push_back()在数据没有满时将其加入，再重新调整迭代器位置。
如果满了则调用insert_aux()
再来看insert_aux()
template <class T,class Alloc>
void vector<T,Alloc>::insert_aux(iterator position,const T& x){
if(finish != end_of_storage){//1
...
++finish;
...
}
else{
const size_type old_size=size();//2
const size_type len=old_size!=0?2*old_size:1;//3
iterator new_start =data_alloctor:allocate(len);//4
iterator new_finish=new_start;
try{
new_finish=uninitialized_copy(start,position,new_start);//5
construct(new_finish,x);//6
++new_finish;//6
new_finish=uninitialized_copy(position,finish,new_finish);//7
}
catch(...){
...
}
destroy(begin(),end());//8
dellocate();
start=new_start;//9
finish=new_finish;
end_of_storage=new_start+len;
}
}
解释：
- 在insert_aux内部又做了一次判断，判断数据是否已经放满。
- 如果已经满了，那么就记录一下原来的大小old_size
- 这句很关键。如果原来的大小为0，就扩展为1；不为0就扩展为2倍大小。
- 这里才是真正分配空间的地方。得到二倍空间后，建立新的start，然后让新的finish等于它。
- 开始拷贝原来vector中的值。
- 还有要添加的元素没有放进去。这时构造新元素，再调整new_finish的位置。
- 其实到这里放入元素的操作已经可以结束了。但是insert_aux()可能还会被其他函数调用，比如insert()，这时就会有一个安插位置的概念。那么还需要把安插点后面的内容也拷贝过来。
- 释放原来的vector空间
- 调整新的迭代器的位置
需要特别注意的点
- 动态空间增加不是单纯地增加大小，而是在新空间上进行拷贝操作。
- 空间配置后所有指向原来vector的迭代器就会失效。
vector的迭代器其实就是普通指针，也就是random access iterators。
template <class T,class Alloc=alloc>
class vector{
public:
typedef T value_type;
typedef value_type * iterator;//普通指针
...
};
pop_back()
删除尾端元素实现比较简单，直接把末尾标记前移，再销毁元素。
void pop_back(){
--finish;
destory(finish);
}
erase
erase有两种用法，我们说一下清除first到last之间的元素。（注意是[first,last)左闭右开）
先看图:
基本思路就是把last后面的内容复制到first的位置，再调整新的finish位置。
iterator erase(iterator first,iterator last){
iterator i= copy(last,finish,first);//复制last到finish位置的数据到first
destroy(i,finish);
finish=finish-(last-first);//调整新的finish
return first;
}
解释：
- 关于destroy()，会在迭代器部分细说。在这里是接受first和last两个迭代器，将两个迭代器范围内的对象析构。
- 关于copy()，会在算法部分出现，就是我们上面说到的复制，但是会返回一个迭代器:result+(last-first),也就是返回复制后数据的下一个位置，这也是为什么在destroy中是从i到finish，翻译一下就是从新的finish到原来的finish。
insert
insert的用法是insert(position,n,x),即从position开始，插入n个元素，初值为x。
在实现过程中有以下几个情况：
首先是备用空间充足的情况下：
if(size_type(end_of_storage-finish)>=n)
{
T x_copy=x;
const size_type elems_after=finish-position;//计算插入点后现有的元素
iterator old_finish=finish;
...
}
插入点后现有的元素>新增元素个数，比如插入2个，而现在position后面有三个
if(elem_after>n)
{
uninitialized_copy(finish-n,finish,finish);
finish +=n;
copy_backward(position,old_finish-n,old_finish);
fill(position,position+n,x_copy);
}
图示中，第二步调用的是uninitialized_copy(),第三步调用的是copy_backward()。
当然大家都会很好奇为什么这两步要拆开拷贝，而不能一气呵成。
暂时理解为uninitialized_copy()是要将数据拷贝到未初始化的区域，比如移动两位则需要占用两位备用空间，所以要移动的范围是[finish-2,finish)
另外也不能单独调用copy_backward()，会出现没有调用构造函数就被析构的情况（uninitialized_copy()调用构造函数）
插入点之后的现有元素<=新增元素个数
比如插入3个，而现在position后面有两个
else
{
uninitialized_fill_n(finish,n-elems_after,x_copy);
finish+=n-elems_after;
uninitialized_copy(position,old_finish,finish);
finish+=elem_after;
fill(position,old_finish,x_copy);
}
先从finish开始添加n-elems_after个元素，再更新一下finish。
然后在把原来的元素拷贝到新的finish后面。
最后在将空缺位置补满。
这个也比较好理解，不管添加多少个元素（当然要满足前提条件），比如10个20个，那么插入位置后面的元素的位置都会被占用，所以先将后面的填满，再把有元素的地方替换即可。
在空间不足的情况下也会二倍增长
else{
const size_type old_size=size();//1
const size_type len = old_size+max(old_size,n);//2
iterator new_start=data_alloctor:allocte(len);//3
iterator new_finish=new_start;//3
_STL_TRY{//4
new_finish=uninitialized_copy(start,position,new_start);//5
new_finish=uninitialized_fill_n(new_finish,n,x);//6
new_finish=uninitialized_copy(position,finish,new_finish);//7
}
...
}
解释：
- 记录原来的size
- 扩充空间，有可能是旧长度的二倍，如果插入元素个数大于原来的size，那么新长度就是old_size+n
- 申请新的空间，设置新的start和finish
- 因为这块空间都没有初始化，所以都是使用uninitialized_，注意这段操作一直在为new_finish赋值，更新new_finish
- 首先将插入位置之前的数据拷贝过来。从start到position拷贝到new_start
- 再从插入点（也就是new_finish）开始填入n个x
- 将原来vector中插入点后的数据拷贝过来（position到finish）