所谓序列式容器，其中的元素都可序，但未必有序，C++本身提供了一个序列式容器array，STL另外提供了vector、list、deque、stack、queue、priority-queue等序列式容器，其中stack和queue由于只是将deque改头换面，技术上归类为一种配接器（adapater）。
数组
1、vector是动态空间，随着元素增加，它的内部机制会自行扩充以容纳新的元素。
2、array是静态空间，一旦配置无法改变。
3、两者均为线性内存连续空间。
//扩大内存空间
#include<iostream>
#include<vector>
int main(){
int a[5];
int b[10];
for (int i = 0; i < 5; i++)
{b[i] = a[i]}
//vector
vector<int> vec{1,2,3};
cout<< vec.size() << endl; //size表示元素个数
cout << vec.capacity() << endl; //capacity表示占用的空间
vec.push_back(4);
vec.push_back(5);
cout << vec.size() << endl; //5
cout<< vec.capacity() << endl; //6
}
1、为了降低空间配置时的速度成本，vector的实际配置的大小可能比客户端需求量更大一些，以备将来可能使用到。
2、vector空间满载，将会进行“配置新空间/数据移动/释放旧空间”，时间成本很高，因此vecto配置新空间时，一般以旧空间的两倍来扩充。
3、空间配置：如果原来的大小为0，则配置capacity为1，否则为原来的两倍大小。
1、vector维护的是一个连续性空间，普通指针即可满足要求，提供随机存取迭代器。
2、因vector满载需要进行“配置新空间/数据移动/释放旧空间”操作，因而vector迭代器会失效。
1、clear()函数：清除所有的元素，但容量不改变，即size=0，capacity！=0
2、下面演示程序可知：当push_back和pop_back时的size大小（元素个数）改变，而capacity的大小只有在分配新空间时才改变。
3、因vector容量只增不减，所以对于释放vector占有的内存有必要了解。
方法一：与临时变量swap()
方法二：clear() + shink_to_fit()，先清除所有的元素，再将容量大小调整为元素大小即可。
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> vec{1,2,3,4,5};
vector<int>().swap(vec); //方法1：和临时变量进行swap()
vec.size();//0
vec.capacity()//0
vec.clear(); //方法2：先清除所有元素，再将容量大小调整元素大小
vec.shrink_to_fit();
}
vector的优缺点：
优点：随机存取。时间复杂度O（1）。
缺点：插入和删除的复杂度O（n)，需要对元素进行移动。
list是一个环状双向链表，所以它只需要一个指针，就可以完整的表现整个链表。
只要刻意在环状链表的结尾加上一个空白节点，便可以满足“前闭后开”区间。
list不像vector是连续存储空间，需要预留空间来节省“配置新空间/数据移动/释放旧空间”操作的成本。因而容量大小等于元素个数。
每次配置一个节点大小，当元素删除时，相应空间一并删除。
list不能像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。
list是一个环状双向链表，迭代器必须具备前移、后移的能力，所以list提供双向迭代器。
分配一个节点，“插入…之前”
优点：无预留空，插入和删除在常数时间内完成。
缺点：不能进行随机存取，时间复杂度为O(n).
vector是单向开口的连续线性空间，deque是双向开口的连续线性空间
deque允许常数时间内对起头端的元素进行插入和删除。vector需要将头端的元素整体前移或后移，时间复杂度是O(N)，效率极差。
deuqe没有所谓的容量概念，它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并连接起来。
deque采用一段所谓的map（不是map容器）作为主控，这里所谓的map是一小块连续空间，其中每个元素都是指针，指向另一段（较大的）连续空间，称为缓冲区，缓冲区是deque的存储空间主体。
deque的连续空间是假象，是由一段一段的定量连续空间构成。
map其实是一个T**，也就是一个指针，所指之物是一个指针，指向型别为T的一块空间。
deque的迭代器包含四个指针：
cur迭代器指向缓冲区的现行元素
first指向缓冲区的头部
last指向缓冲区的尾
node指向管控中心
当map指向的缓冲区容量满载时，需要对map进行扩充，扩充过程，配置更大的，拷贝原来的，释放原来的，因此deque的迭代器会失效。
deque的中控器，缓冲器，迭代器相互关系：
deque在尾端添加元素，引发新缓冲区的配置。
deque在最前端添加元素，引发新缓冲区的配置。
class deque{
iterator strat; //指向第一个节点
iterator finish; //指向最后一个节点
map_pointer map; //(T **类型）指向map是一块连续空间，每个元素是一个指针，指向一个缓冲区
size_type map_size; //map内的指针数量
}
reference operator[](size_type n)
{ return start[difference_type(m)];}
reference front()
{ return * start;}
reference back()
{ iterator tmp = finish;
--tmp;
return *tmp;}
size_type size()cosnt
{ return finsh-start;}
bool empty() const
{ return finish == start;}
reference operator*() const
{ return *cur;}
pointer operator->()const
{ return &(operator*());}
//两个iterator之间的距离相当于：（1）两个迭代器之间buffer的总长度+（2）迭代器1到尾部的长度+（3）x到迭代器2头的长度
difference_type operator-(const self&x) const
{
return difference_type(buffer_size()) *(node - x.node - 1) + (cur - first) +(x.last - x.cur);
}
self& operator++()
{++cur;
if(cur == last){
set_node(node+ 1); //如果到达尾部则跳跃至下一节点的起点
cur = first;
}
return *this;
}
// 后置++ 和--同理
self& operator+=(difference_type n)
{
difference_type offset = n+ (cur-first);
if(offsrt >=0 && offset < buffer_size()) // 在同一个缓冲区中
{ cur +=n;
}
else{ //不在同一个缓冲区中
difference_type node_offset = offset >0? offset/buffer_size():(-offset-1)/buffer_size() - 1;
}
set_node(node+node_offset);
cur = first+(offset- node_offset * buffer_size());
return * this;
}
// +， -= [(difference_type)n]操作中使用+= 实现
1、可随机存取，时间复杂度为O(1)。可在头部和尾部进行插入操作，相对于vector的头插效率更高。
2、插入和删除的时间复杂度为O(N)，（头插删和尾插删是O(1)）若插入位置之前的个数较少，则前面元素 前移，否则后面元素后移。
template<class T, class Sequence=deque<T>>
class queue{
protecred:
Sequence c; //底层容器
public:
bool empty()const{return c.empty();}
size_type size() const{return c.size();}
reference front() {return c.front();}
const_reference front() const {return c.front()};
reference back() {return c.back();}
const_reference back() const {return c.back();}
void push(const value_type &x) {c.push_back(x);}
void pop() {c.pop_front();}
}
可以用list和deque实现queue，不可以用map、set、vector实现。
template<class T, class Sequence=deque<T>>
class stack{
protecred:
Sequence c; //底层容器
public:
bool empty()const{return c.empty();}
size_type size() const{return c.size();}
reference top() {return c.back();}
const_reference top() const {return c.back()};
void push(const value_type &x) {c.push_back(x);}
void pop() {c.pop_back();}
};
可以用list、deque和vetor实现stack，不可以用map和set。
queue和stack都不提供迭代器，因为这两种容器不允许遍历元素。