目录
deque（双端队列）
内存结构
验证地址不连续
使用详解
构造函数
元素访问
容量操作
修改
迭代器
迭代器失效
code实例
实现一个简单的deque
deque（双端队列）
std::deque（双端队列）是 C++ 标准模板库（STL）中的一个容器，支持在队列的两端高效地插入和删除元素。它的名字来源于 "Double-Ended Queue"。动态大小：deque可以根据需要动态调整大小。随机访问：支持通过下标访问元素，时间复杂度为 O(1)。非连续存储：deque的元素在内存中不一定是连续存储的，这使得它在两端的插入和删除操作更高效。与 std::vector 不同std::deque的底层实现通常基于分段连续内存，这使得它在两端操作时具有更高的效率。
内存结构
底层原理：std::deque 的底层实现通常是一个分段连续内存的结构。它由多个固定大小的内存块（称为缓冲区或块）组成，这些内存块通过一个中央控制器（通常是数组或指针数组）管理。分段连续内存：std::deque 的内存不是完全连续的，而是由多个连续的内存块组成。每个内存块可以存储固定数量的元素。中央控制器（如指针数组）记录了这些内存块的地址。
优点：在两端插入和删除元素的时间复杂度为 O(1)。不需要像 std::vector 那样在扩容时复制所有元素。缺点：随机访问的时间复杂度为 O(1)，但由于内存不连续，实际性能可能略低于std::vector。
内部实现：缓冲区大小：每个缓冲区的大小是固定的，通常是 512 字节或 1024 字节。缓冲区的大小由实现定义，用户无法直接控制。中央控制器：中央控制器是一个数组，存储了指向各个缓冲区的指针。通过中央控制器，std::deque 可以快速定位任意元素。
迭代器：std::deque 的迭代器是一个随机访问迭代器。迭代器需要记录当前元素所在的缓冲区以及元素在缓冲区中的位置。
验证地址不连续
#include <iostream>
#include <deque>
#include <vector>int main() {std::deque<int> dq;std::vector<int> r;// 添加元素并观察内存地址for (int i = 0; i < 10; ++i) {dq.push_back(i);r.push_back(i);}// 在前端添加元素并观察内存地址for (int i = 10; i < 15; ++i) {dq.push_front(i);r.insert(r.begin(),i);}// 输出所有元素的地址std::cout << "All elements in deque:" << std::endl;for (const auto& elem : dq) {std::cout << "Element: " << elem << ", Address: " << &elem << std::endl;}std::cout << "All elements in vector:" << std::endl;for (const auto& elem : r) {std::cout << "Element: " << elem << ", Address: " << &elem << std::endl;}return 0;
}
All elements in deque:
Element: 14, Address: 0x1f84b78164c --- Element: 10, Address: 0x1f84b78165c
Element: 0, Address: 0x1f84b781250 --（连续段）----Element: 9, Address: 0x1f84b781274
All elements in vector:
Element: 14, Address: 0x1f84b786f70 ---连续空间）-Element: 9, Address: 0x1f84b786fa8
使用详解
构造函数
| deque() | 默认构造函数，创建一个空的 deque |
| deque(size_type count) | 创建包含 count 个默认初始化元素的 deque |
| deque(size_type count, const T& value) | 创建包含 count 个值为 value 的元素的 deque |
| deque(const deque& other) | 拷贝构造函数 |
| deque(initializer_list<T> init) | 使用初始化列表创建 deque |
元素访问
| front(): 返回第一个元素的引用 | back(): 返回最后一个元素的引用 |
| at(size_type pos): 返回指定位置 pos 处的元素的引用，并进行边界检查 | |
| operator[](size_type pos): 返回指定位置 pos 处的元素的引用，不进行边界检查 | |
容量操作
| empty(): 检查 deque 是否为空 | size(): 返回 deque 中的元素数量 |
| max_size(): 返回 deque 可以容纳的最大元素数量 | shrink_to_fit(): 请求移除未使用的容量（C++11 起 |
修改
| clear(): 清除 deque 中的所有元素 | erase(iterator pos): 删除指定位置 pos 处的元素 |
| pop_back(): 删除 deque 的最后一个元素 | pop_front(): 删除 deque 的第一个元素 |
| swap(deque& other): 交换两个 deque 的内容 | resize(size_type count): 改变 deque 的大小为 count |
| insert(iterator pos, const T& value): 在指定位置 pos 插入元素 value | |
| push_back(const T& value): 在 deque 的末尾添加元素 value | |
| push_front(const T& value): 在 deque 的开头添加元素 value | |
迭代器
| begin(), end(): 返回指向第一个元素和最后一个元素之后位置的迭代器 |
| rbegin(), rend(): 返回反向迭代器。 |
| cbegin(), cend(), crbegin(), crend(): 返回常量迭代器。 |
迭代器失效
| 操作 | 失效 |
|---|---|
| 所有只读操作 | 决不 |
| std::swap | 尾后迭代器可能失效（由实现定义） |
| shrink_to_fit、clear、insert、emplace、push_front、push_back、emplace_front、emplace_back | 始终 |
| erase | 如果在起始擦除——只有被擦除元素 如果在末尾擦除——只有被擦除元素和尾后迭代器 |
| resize | 如果新尺寸小于旧尺寸——只有被擦除元素和尾后迭代器 如果新尺寸大于旧尺寸——所有迭代器均失效 |
| pop_front、pop_back | 到被擦除元素的迭代器。 尾后迭代器可能失效（实现定义）(C++11 前) |
code实例
#include <deque>
#include <iostream>int main() {//构造函数std::deque<int> d1; // 空 dequestd::deque<int> d2(5); // 包含 5 个默认初始化元素的 dequestd::deque<int> d3(5, 10); // 包含 5 个值为 10 的元素的 dequestd::deque<int> d = {1, 2, 3, 4, 5}; // 使用初始化列表创建 deque//元素std::cout << "d[2]: " << d[2] << std::endl; // 输出: 3std::cout << "d.at(3): " << d.at(3) << std::endl; // 输出: 4std::cout << "d.front(): " << d.front() << std::endl; // 输出: 1std::cout << "d.back(): " << d.back() << std::endl; // 输出: 5//容量std::cout << "d.empty(): " << d.empty() << std::endl; // 输出: 0 (false)std::cout << "d.size(): " << d.size() << std::endl; // 输出: 5std::cout << "d.max_size(): " << d.max_size() << std::endl; // 输出: 一个很大的数//修改d.push_back(6); // d: {1, 2, 3, 4, 5, 6}d.push_front(0); // d: {0, 1, 2, 3, 4, 5, 6}d.pop_back(); // d: {0, 1, 2, 3, 4, 5}d.pop_front(); // d: {1, 2, 3, 4, 5}d.insert(d.begin() + 2, 10); // d: {1, 2, 10, 3, 4, 5}d.erase(d.begin() + 3); // d: {1, 2, 10, 4, 5}//迭代器for (auto it = d.begin(); it != d.end(); ++it) {std::cout << *it << " "; // 输出: 1 2 10 4 5}for (auto it = d.rbegin(); it != d.rend(); ++it) {std::cout << *it << " "; // 输出: 5 4 10 2 1}return 0;
}实现一个简单的deque
#include <iostream>
#include <vector>class SimpleDeque {
private:std::vector<int*> blocks; // 存储内存块的指针size_t block_size = 4; // 每个内存块的大小size_t start = 0; // 第一个元素的位置size_t end = 0; // 最后一个元素的位置public:SimpleDeque() {blocks.push_back(new int[block_size]);}~SimpleDeque() {for (auto block : blocks) {delete[] block;}}void push_back(int value) {if (end == block_size * blocks.size()) {blocks.push_back(new int[block_size]);}blocks[end / block_size][end % block_size] = value;end++;}void push_front(int value) {if (start == 0) {blocks.insert(blocks.begin(), new int[block_size]);end += block_size;start += block_size;}start--;blocks[start / block_size][start % block_size] = value;}int at(size_t index) {if (index >= end - start) {throw std::out_of_range("Index out of range");}return blocks[(start + index) / block_size][(start + index) % block_size];}size_t size() const {return end - start;}
};int main() {SimpleDeque dq;dq.push_back(1);dq.push_back(2);dq.push_front(0);dq.push_front(-1);for (size_t i = 0; i < dq.size(); ++i) {std::cout << dq.at(i) << " "; // 输出: -1 0 1 2}std::cout << std::endl;return 0;
}
