序列式容器
所谓序列式容器，其中的元素都可序，但未必有序，C++语言本身提供了一个序列式容器array，STL另外再提供vector、list、deque、stack、queue、priority-queue等序列容器。其中stack和queue由于只是将deque改头换面而成，技术上被归类为一种配接器。下图为常用的序列式容器。
vector
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。 当空间不够的时候，往往vecotr会去申请双倍的容器空间，size指的是当前容器中的元素个数
-
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。】
- 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
用法
头文件
#include
vector声明及初始化
vector<int> vec; //声明一个int型向量
vector<int> vec(5); //声明一个初始大小为5的int向量
vector<int> vec(10, 1); //声明一个初始大小为10且值都是1的向量
vector<int> vec(tmp); //声明并用tmp向量初始化vec向量
vector<int> tmp(vec.begin(), vec.begin() + 3); //用向量vec的第0个到第2个值初始化tmp
int arr[5] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量
//说明：当然不包括arr[4]元素，末尾指针都是指结束元素的下一个元素，
//这个主要是为了和vec.end()指针统一。
vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值
vector基本操作 (1). 容量
向量大小： vec.size();
向量最大容量： vec.max_size();
更改向量大小： vec.resize();
向量真实大小： vec.capacity();
向量判空： vec.empty();
减少向量大小到满足元素所占存储空间的大小： vec.shrink_to_fit(); //shrink_to_fit
(2). 修改
多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值
末尾添加元素： vec.push_back();
末尾删除元素： vec.pop_back();
任意位置插入元素： vec.insert();
任意位置删除元素： vec.erase();
交换两个向量的元素： vec.swap();
清空向量元素： vec.clear();
(3)迭代器
开始指针：vec.begin();
末尾指针：vec.end(); //指向最后一个元素的下一个位置
指向常量的开始指针： vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容，但还是可以通过其他方式修改的，而且指针也是可以移动的。
指向常量的末尾指针： vec.cend();
(4)元素的访问
下标访问： vec[1]; //并不会检查是否越界
at方法访问： vec.at(1); //以上两者的区别就是at会检查是否越界，是则抛出out of range异常
访问第一个元素： vec.front();
访问最后一个元素： vec.back();
返回一个指针： int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组，所以可以返回一个指针指向这个数组。这是是C++11的特性。
dequeu
- STL提供3种顺序容器：vector、list、deque。vector和deque都是基于数组的，list实现链表数据结构。
- deque是double-ended queue（双头队列）。deque类在一个容器中提供了vector和list的许多好处。
- deque类能利用下标提供有效的索引访问，可以像vector一样读取与修改元素，还像list一样能有效地在前面和后面进行插入和删除操作。
- 需要增加deque的存储空间时，可以在内存块中deque两端进行分配，通常保存为这些块的指针数组。
- 对deque分配存储块之后，有些版本要删除deque时才释放这个块，这样使deque比重复分配、释放和再分配内存块时更加有效，但也更浪费内存。
- deque利用非连续内存布局，因此deque迭代器比vector和基于指针的数组中用于迭代的指针更加智能化。
- deque支持随机访问迭代器，即list可以使用下表内所有的迭代器操作。
用法
头文件
java #include<deque>
deque
//声明list类的实例list1，存放int值，生成了一个长度为0的空list，容量capacity为0
deque<int>de;
//声明一个list类型的二维链表list1
deque<deque<int>>de;
//声明一个list类型的一维链表list1,并将{1,2,3,4}赋值给list1
deque<int>de = { 1,2,3,4 };
//生成一个链表list1，将list2复制给list1
deque<int>de = de1;
deque<int>de(de1);
deque<int>de(de1.begin(), de1.end());
//生成一个链表list1，将数组a的a[0]到a[4]的内容复制给list1
deque<int>de(a, a + 5);
deque<int>de(&a[0], &a[4]);
//生成一个链表list1，将大小设为10，且每个元素都为设置为0(默认)
deque<int>de(10);
//生成一个链表list1，将大小设为10，且每个元素都为设置为5
deque<int>de(10, 5);
//将list1清空，然后添加2个元素，每个元素都赋值为10
de.assign(2, 10);
//声明二维链表list1,将两个一维链表赋值给list1
deque<deque<int>>de;
deque<int>de1 = { 1,2,3,4 };
deque<int>de2 = { 2,4,6,8 };
de.push_back(de1);
de.push_back(de2);
(2)迭代器
//开始指针（正向）
de.begin()
//结束指针（正向），指向de最后一个元素的后一位
de.end()
//开始指针（逆向）
de.rbegin()
//结束指针（逆向），指向de最后一个元素的后一位
de.rend()
//常量开始指针（正向），不能通过该指针来修改所指内容
de.cbegin()
//常量结束指针（正向），不能通过该指针来修改所指内容，指向de最后一个元素的后一位
de.cend()
(3)输出
//迭代器，顺序访问
for (deque<int>::iterator p = nums.begin(); p != nums.end(); p++)
cout << *p << " ";
//输出迭代器，copy算法
ostream_iterator<int> output(cout, " ");
copy(de.begin(),de.end(),output);
cout<<endl;
// 迭代器，逆序访问
for(deque<int>::reverse_iterator p = nums.rbegin(); p != nums.rend(); p++)
cout << *p << " ";
//若是二维deque，注意传入参数是按值传递（不是&nums）因此在函数里对向量的修改不影响真正的向量的元素。顺序访问
void display_deque_two(deque<deque<int>> nums) {
while (!nums.empty()) {
for (deque<int>::iterator p = nums.front().begin(); p != nums.front().end(); p++)
cout << *p << " ";
cout << endl;
nums.erase(nums.begin());
}
}
//还有一个基础的类似二维数组a[ ][ ]的输出方法，用下标运算符[ ]来输出，顺序访问
void display_deque_two(deque<deque<int>> nums) {
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums[i].size(); j++) {
cout << nums[i][j] << " ";
}
cout << endl;
}
}
list
相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间因此，list对于空间不浪费，插入和删除的时间复杂度为o(1)。
list迭代器正确的递增、递减、取值、成员取用操作是指，递增指向下一个节点，递减指向上一个节点，取值取的是节点的数据值，成员取用时取用的是节点的成员。STL list是一个双向链表迭代器具备前移、后移的能力。list有一个重要性质：插入和结合操作都不会有list迭代器失效，这在vector是不成立的，因为vector的插入操作可能造成原来的重新配置，导致原有的迭代器全部失效。list的元素删除操作也只有指向删除元素的那个迭代器失效，其他迭代器不受影响。
list 的 erase操作
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
if( WillDelete( *itList) )
{
itList = List.erase( itList);
}
else
itList++;
}
list的操作
list<int> l;
push_front(); //在list头部添加一个元素
push_back(); //在list尾部添加一个元素
pop_back(); //删除最后一个元素
pop_front(); //删除第一个元素
clear(); //删除链表
empty(); //如果list为空返回true
size(); //返回list中元素的个数
max_size(); //返回容器能容纳的最大数量
remove(val); //删除值为val的元素
sort(); //排序，默认升序
reverse();
list的设计
template <class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
// 至于为什么不使用默认参数, 这个是因为有一些编译器不能提供推导能力,
// 而作者又不想维护两份代码, 故不使用默认参数
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator<T, T&, T*> iterator; // STL标准强制要求
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node; //迭代器内部当然要有一个普通指针，指向list的节点
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
// 在STL算法中需要迭代器提供支持
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 以下对迭代器取值（dereference）,取的是节点的数据值
reference operator*() const { return (*node).data; }
// 以下是迭代器的成员存取运算子的标准做法
pointer operator->() const { return &(operator*()); }
// 前缀自加，对迭代器累加1，就是前进一个节点
self& operator++()
{
node = (link_type)((*node).next);
return *this;
}
// 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本
self operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
// 前缀自减
self& operator--()
{
node = (link_type)((*node).prev);
return *this;
}
self operator--(int)
{
self tmp = *this;
--*this;
return tmp;
}
};
