序列式容器:
vector是单向开口的连续线性空间,deque是一种双向开口的连续线性空间。所谓双向开口,意思就是可以在头尾两端分别做元素的插入和删除操作。
deque和vector的最大差异:
在于deque允许常数时间内对头端进行插入和移除操作。
在于deque没有所谓的容量的概念,因为它是以动态的分段连续空间组合而成,随时可以增加一段空间并链接起来。
deque是一段一段的定量连续空间组成的,需要维护这些定量空间所需要的内部数据结构肯定是要比vector复杂许多,所以,当对deque进行排序操作时候,为了提高效率,可将deque完整的复制到一个vector身上,将vector进行排序之后,再复制回deque。
代码示例:
#include"Test.h" #include<vector> #include<list> #include<array> #include<stack> #include<deque> #include<queue> #include<algorithm>//为了使用find、sort等方法 void main() { setlocale(LC_ALL, "chs");//识别中文 deque<int> v1(5, 0); v1.push_back(1); v1.push_back(2); v1.push_front(5); v1.front(); v1.back(); deque<int>::iterator v2 = find(v1.begin(), v1.end(), 5); v1.insert(v2,4); v2 = find(v1.begin(), v1.end(), 2); v1.erase(v2); sort(v1.begin(), v1.end());//这样排序效率不高 for (deque<int>::iterator v5 = v1.begin(); v5 != v1.end();v5++) { cout << *v5 << endl; } vector<int> v3(v1.begin(), v1.end()); sort(v3.begin(), v3.end());//使用这样的方法对deque排序 //v2.size(); v1.clear(); getchar(); }
“Time is the only true unit of measure.”
参考书籍:
《STL源码剖析》