deque 是 “double-ended queue”的缩写,和 vector 一样,deque 也支持随机存取。 与 vector 不同的是,vector 是单向开口的,deque 是双向开口的,在两端进行插入和删除操作的时间复杂度为 O(1)。此外,deque 没有容量的概念,因为它是动态的以分段的连续空间组合而成,随时可 以增加一段新的空间并链接起来,换句话说,像 vector 那样“因旧空间不足而重新分配一 块更大的空间,然后再复制元素,释放空间”这样的操作不会发生在 deque 身上,也因此 deque 没有必要提供所谓的空间保留功能。
- 双端插入和删除元素效率较高.
- 指定位置插入也会导致数据元素移动,降低效率.
- 可随机存取,效率高.
1 2 3 4
|
deque<T> deqT; deque(beg, end); deque(n, elem); deque(const deque &deq);
|
deque 赋值操作
1 2 3 4
|
assign(beg, end); assign(n, elem); deque& operator=(const deque &deq); swap(deq);
|
deque 大小操作
1 2 3 4
|
deque.size(); deque.empty(); deque.resize(num); deque.resize(num, elem);
|
deque 双端插入和删除操作
1 2 3 4
|
push_back(elem); push_front(elem); pop_back(); pop_front();
|
deque 数据存取
1 2 3 4
|
at(idx); operator[]; front(); back();
|
deque 插入操作
1 2 3
|
insert(pos,elem); insert(pos,n,elem); insert(pos,beg,end);
|
deque 是分段连续的内存空间,通过中控器维持一种连续内存空间的状态, 其实现复杂性要大于 vector queue stack 等容器,其迭代器的实现也更加复杂。
在需要对 deque 容器元素进行排序的时候,建议先将 deque 容器中数据数据元素拷贝到 vector 容 器中,对 vector 进行排序,然后再将排序完成的数据拷贝回 deque 容器。
deque 删除操作
1 2 3
|
clear(); erase(beg,end); erase(pos);
|
近期评论