图解std::deque
时间: 2024-06-13 12:02:44 浏览: 7
`std::deque`(双端队列)是C++标准库中的一个容器,它提供了类似于数组的随机访问和类似于链表的动态大小能力。图解`std::deque`通常会展示其内部结构,包括以下几个关键特点:
1. **两端**:deque在两端进行操作,支持快速的插入和删除,这使得它在数据的末尾或开头添加元素非常高效。
2. **动态大小**:deque可以自动调整大小以适应元素的数量变化,不需要预先知道所有的元素数量。
3. **分块存储**:deque通常被实现为一系列连续的内存块,每个块有自己的头尾指针。这样可以同时支持快速的随机访问和高效的边界操作。
4. **双向**:既可以从头部(front)也可以从尾部(back)添加或删除元素,这得益于其内部的双向链接。
下面是一个简单的图解概念示例:
```
+--+
| | |
| | // 当只有一个元素时,看起来像链表
| | |
+-----------------------+
| | |
| | // 当有多个元素时,每个元素包含前一个和后一个的引用
| | |
+---------+
```
在这个图中,每个方块代表一个内存块,箭头表示了元素之间的连接。当需要添加或删除元素时,deque可能会扩展或收缩这些内存块。
相关问题
std::deque
std::deque是C++标准库中的一种容器,它是双向开口的连续线性空间。与std::vector相比,std::deque在头部操作的效率更高,因为它可以在头尾两端进行元素的插入和删除操作。而std::vector在头部操作时效率较低。
std::deque与std::vector的不同之处在于内部实现方式。std::vector使用单个数组来存储元素,需要偶尔重新分配内存以进行增长。而std::deque是动态的以分段的内存块组合而成,可以随时增加一段新的内存空间拼接起来。这样的实现方式使得std::deque在某些情况下扩容的代价更低,特别是对于非常长的序列。
需要注意的是,由于std::deque的内部实现方式,它不能保证其中所有元素存储在相邻的存储区域。因此,通过指针偏移操作来访问std::deque中的元素可能会导致访问出错。
下面是一个使用std::deque的简单示例:
```cpp
#include <iostream>
#include <deque>
int main() {
std::deque<int> deque1;
// 在尾部插入元素
deque1.push_back(1);
deque1.push_back(2);
deque1.push_back(3);
// 在头部插入元素
deque1.push_front(0);
// 遍历输出元素
for (int i : deque1) {
std::cout << i << " ";
}
std::cout << std::endl;
// 在头部删除元素
deque1.pop_front();
// 在尾部删除元素
deque1.pop_back();
// 遍历输出元素
for (int i : deque1) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
```
输出结果为:
```
0 1 2 3
1 2
```
std::deque和std::queue
std::deque是C++ STL的双端队列容器,支持在队列头尾进行插入和删除操作,可以当做栈、队列或双向队列使用。std::queue是基于std::deque实现的队列容器,支持在队列尾进行插入,在队列头进行删除操作。以下是std::deque和std::queue的例子:
1. 在std::deque的队尾插入元素、在队头插入元素、删除队头元素[^1]
```c++
std::deque<int> myDeque({ 1, 2, 3 });
myDeque.push_back(4); // 在队尾插入元素
myDeque.push_front(0); // 在队头插入元素
myDeque.pop_front(); // 删除队头元素
```
2. 使用std::queue在队尾插入元素、在队头删除元素
```c++
std::queue<int> myQueue({ 1, 2, 3 });
myQueue.emplace(4); // 在队尾插入元素
myQueue.push(5); // 在队尾插入元素
myQueue.pop(); // 删除队头元素
```
参考资料:
: C++ STL queue和deque容器用法详解。https://www.jianshu.com/p/102f7f8839b0
[^2]: C++ STL之queue和deque用法详解。https://blog.csdn.net/shrek11/article/details/86619842
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)