深入学习STL系列（4）--deque
Ø deque
vector是单向开口的连续线性容器，deque是双向开口的连续线性容器，也就说可以在头尾两端分别做元素的插入和删除操作，vector也可以在头部利用insert进行插入操作，但其效率极差，无法接受。deque与vector的最大差别，一在于deque允许常数时间内队头部进行插入和移除操作，二在于deque没有容量（capacity）的概念，因为它是以分段的连续空间组合而成，所以不会像vector那样“因旧空间不足而重新分配一块新的空间，然后复制元素，再释放旧空间”。
此外，和vector不同，deque的迭代器不是普通指针，所以会影响运算效率。因此，除非必要，否则我们尽量选择vector。对于deque的排序，可以先将其复制到vector中进行排序后，再拷贝回deque。
图2 deque结构示意图
---创建deque---
deque<int> id; //方式1，构建一个空的容器对象
deque <int> id(2); //方式2，构建一个包含2个默认初始化值的容器对象
deque <int> id(2, 9); //方式3，构建一个包含2个值为9的容器对象
int a[4] = { 1, 2, 3, 4 };
deque <int> id(a, a+3); //方式4，利用数组指针构建容器对象（也可以利用其它容器迭代器）
deque <int> id2(id); //方式5，利用其它vector对象构建容器对象
deque <int> id3 = id; //方式5的另一种写法
---插入操作---
id.push_front(0); //方式1，在队首插入一个元素
id.push_back(1); //方式2，在队尾插入一个元素
id.emplace_front(3); //方式3，在队首插入一个元素
id.emplace_back(2); //方式4，在队尾插入一个元素
id.emplace(id.begin() + 2, 4); //方式5，在指定位置插入一个元素
id.insert(id.begin()++, 5); //方式6，在指定位置插入一个元素
inta[] = { 11, 22, 33 };
id.insert(id.begin(), a, a+2); //方式7，在指定位置插入多个元素
---删除操作---
id.erase(id.begin()); //方式1，删除指定位置的1个元素
id.erase(id.begin(),id.begin() + 2); //方式2，删除指定位置的多个元素
id.pop_front(); //方式3，删除队首元素
id.pop_back(); //方式4，删除队尾元素
id.clear(); //方式5，清空所有元素
---查看操作---
id[1]; //方式1，查看指定位置的元素（注意防止越界访问）
id.at(1); //方式2，查看指定位置的元素（从0计数，注意防止越界访问）
id.front(); //方式3，查看头部的元素
id.back(); //方式4，查看尾部的元素
*id.begin(); //方式5，使用迭代器查看元素
---遍历操作---
//从前往后遍历
for(deque <int>::iteratoriter = id.begin(); iter++; iter!= id.end()){
//dosomething
}
//从后往前遍历
for(deque<int>::iteratoriter = id.rbegin(); iter++; iter!= id.rend()){
//dosomething
}
//利用for_each进行遍历
for_each(id.begin(), id.end(),dosomething);
---其它操作---
id.empty(); //判断容器是否为空
id.size(); //返回容器的size（大小）
id.resize(10); //调整容器的size为10，如果原值大于10，则删除元素
id.assign(5,2); //清空所有元素，并插入5个值为2的元素
id.assign(iter1,iter2);//清空所有元素，并根据迭代器（或数组指针）进行赋值
id.swap(id2); //两个容器互相交换内容
id. shrink_to_fi();//请求容器减小容量使其足够用来存放所有有效元素
---注意事项---
当执行插入删除操作时，因为元素的位置会有可能发生变动，迭代器将会失效。