首页 > 专利学习

c++双端队列deque之（头部、尾部）插入元素删除元素

c++双端队列deque之（头部、尾部）插⼊元素删除元素头⽂件 #include <deque>

和vector⽤法基本相同

没有 capacity() reserve()

有了push_back(),pop_back()

烫发杠子//insert elements in first a.push_front(some_element)

//insert elements at last a.push_back(some_element);

//pop element at first a.pop_front(some_element);

//pop element at last a.pop_back(some_element);

#include <iostream>

#include <string>

#include <deque>

#include <algorithm>

#include <vector>

#include <iterator>

using namespace std;

int main()

{

vector<int> v_int = {1,2,3,4};

无热胆饮水机deque<int> d_int;

d_int.push_back(1);

d_int.push_back(2);

d_int.push_back(1001);

d_int.push_back(1002);

d_int.push_front(-1);

d_int.push_front(-2);

d_int.push_front(-3);

d_int.push_front(-4);

for(size_t i = 0;i != d_int.size() ; ++i)

{

电源延时器cout << "a[" << i << "] = " << d_int[i] << endl;

//cout << v_int[i] << endl;

}

cout << "iterator 's output:" << endl;

d_int.pop_front();

压模

d_int.pop_back();

//cout << del_1 << endl;

//cout << del_2 << endl;

for(deque<int>::iterator i = d_int.begin(); i != d() ;++ i )

cout << *i <<endl;

return 0;

}

6、双端队列deque

所谓的deque是”double ended queue”的缩写，双端队列不论在尾部或头部插⼊元素，都⼗分迅速。⽽在中间插⼊元素则会⽐较费时，因为必须移动中间其他的元素。双端队列是⼀种随机访问的数据类型，提供了在序列两端快速插⼊和删除操作的功能，它可以在需要的时候改变⾃⾝⼤⼩，完成了标准

的C++数据结构中队列的所有功能。

Vector是单向开⼝的连续线性空间，deque则是⼀种双向开⼝的连续线性空间。deque对象在队列的两端放置元素和删除元素是⾼效的，⽽向量vector只是在插⼊序列的末尾时操作才是⾼效的。deque和vector的最⼤差异，⼀在于deque允许于常数时间内对头端进⾏元素的插⼊或移除操作，⼆在于deque没有所谓的capacity观念，因为它是动态地以分段连续空间组合⽽成，随时可以增加⼀段新的空间并链接起来。换句话说，像vector那样“因旧空间不⾜⽽重新配置⼀块更⼤空间，然后复制元素，再释放旧空间”这样的事情在deque中是不会发⽣的。也因此，deque没有必要提供所谓的空间预留（reserved）功能。

虽然deque也提供Random Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可同⽇⽽语，这当然涉及到各个运算层⾯。因此，除⾮必要，我们应尽可能选择使⽤vector⽽⾮deque。对deque进⾏的排序操作，为了最⾼效率，可将deque先完整复制到⼀个vector⾝上，将vector排序后（利⽤STL的sort算法），再复制回deque。

deque是⼀种优化了的对序列两端元素进⾏添加和删除操作的基本序列容器。通常由⼀些独⽴的区块组成，第⼀区块朝某⽅向扩展，最后⼀个区块朝另⼀⽅向扩展。它允许较为快速地随机访问但它不像vector⼀样把所有对象保存在⼀个连续的内存块，⽽是多个连续的内存块。并且在⼀个映射结构中保存对这些块以及顺序的跟踪。

1、声明deque容器

#include<deque> // 头⽂件

deque<type> deq; // 声明⼀个元素类型为type的双端队列que

deque<type> deq(size); // 声明⼀个类型为type、含有size个默认值初始化元素的的双端队列que

deque<type> deq(size, value); // 声明⼀个元素类型为type、含有size个value元素的双端队列que

deque<type> deq(mydeque); // deq是mydeque的⼀个副本(是真的不？那上⾯怎么解释)

deque<type> deq(first, last); // 使⽤迭代器first、last范围内的元素初始化deq

2、deque的常⽤成员函数

deque<int> deq;

deq[ ]：⽤来访问双向队列中单个的元素。

deq.front()：返回第⼀个元素的引⽤。

deq.back()：返回最后⼀个元素的引⽤。

deq.push_front(x)：把元素x插⼊到双向队列的头部。

deq.pop_front()：弹出双向队列的第⼀个元素。

deq.push_back(x)：把元素x插⼊到双向队列的尾部。

deq.pop_back()：弹出双向队列的最后⼀个元素。

3、deque的⼀些特点

⽀持随机访问，即⽀持[ ]以及at()，但是性能没有vector好。

可以在内部进⾏插⼊和删除操作，但性能不及list。

deque两端都能够快速插⼊和删除元素，⽽vector只能在尾端进⾏。

deque的元素存取和迭代器操作会稍微慢⼀些，因为deque的内部结构会多⼀个间接过程。

deque迭代器是特殊的智能指针，⽽不是⼀般指针，它需要在不同的区块之间跳转。

紧急切断装置so.csdn/api/v3/search?p=1&t=all&q=

deque可以包含更多的元素，其max_size可能更⼤，因为不⽌使⽤⼀块内存。

deque不⽀持对容量和内存分配时机的控制。

在除了⾸尾两端的其他地⽅插⼊和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显⽰不需要复制所有元素。

deque的内存区块不再被使⽤时，会被释放，deque的内存⼤⼩是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。

deque不提供容量操作：capacity()和reverse()，但是vector可以。

本文发布于:2024-09-21 11:06:19，感谢您对本站的认可！

本文链接：https://www.17tex.com/tex/1/164393.html

上一篇：大话多旋翼飞行器—生物视觉导航

下一篇：全球VR行业技术标准及市场概况

标签：元素队列空间操作删除需要双端

留言与评论（共有 0 条评论）