C++deque双向队列

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++deque双向队列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1743字，纯文字阅读大概需要3分钟。

内容图文

1、简介

　　deque 也是顺序容器的一种，同时也是一个可变长数组。要使用 deque，需要包含头文件 deque。所有适用于 vector 的操作都适用于 deque。
　　在 deque 中，随机存取任何元素都能在常数时间内完成（但慢于vector）。它相比于 vector 的优点是，vector 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而 deque 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。它有两种 vector 没有的成员函数：
　　void push_front (const T & val); //将 val 插入容器的头部
　　void pop_front(); //删除容器头部的元素

2、deque的中控器

　　deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。
　　deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。

　　deque采用一块所谓的map(注意,不是STL的map容器)作为主控。这里所谓map是一小块连续空间 ，其中每个元素(此处称为一个节点, node)都是指针，指向另一段(较大的) 连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。

3、数据结构

template <class T, class Allod alloc, size_t Bufsiz = 0>

class deque {

public:
　　typedef T value_type;
　　typedef value_type* pointer;
　　...

protected:
　　typedef pointer* map pointer;

protected:
　　map_pointer map;//指向map，map是块连续空间，其内的每个元素都是一个指针，指向一块缓冲区
　　size_type map_size;//map可容纳多少指针

　　...

}

4、构造和内存管理

　　如果申请的map空间不够时，也需要重新配置更大的空间，将原来map里的指针拷贝过来，最后释放原来的空间。

5、和vector的区别

　　vector是单向开口的连续线性空间， dequeu是一种双向开口的连续线性定 ；
　　deque允许于常数时间内对起头端进行元素的插入或移除操作 ；
　　deque没有所谓容量(capacity)观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来

内容总结

以上是互联网集市为您收集整理的C++deque双向队列全部内容，希望文章能够帮你解决C++deque双向队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端