C++ STL 容器与数据结构详解：deque 底层迭代器、priority_queue 优先队列、堆排序原理、冒泡排序泛型实现
·
文章目录
C++ STL 容器与数据结构底层原理详解
从 deque、priority_queue 到堆和排序算法，深入理解 STL 实现细节
适合：已掌握 C++ 基础语法，想深入了解 STL 容器底层实现的同学
一、deque：vector 和 list 的折中方案
1.1 为什么需要 deque？
vector 的痛点
- 头部插入/删除效率极低：O(N)，需要整体搬移数据
- 扩容有代价：重新分配内存 + 拷贝所有元素
- 支持高效的随机访问：O(1)
list 的痛点
- 不支持随机访问：必须遍历，O(N)
- 内存碎片化：每个节点独立分配
- 缓存不友好：节点散落在堆上
deque 的折中
- 头尾插入/删除：O(1)
- 支持随机访问（虽然比 vector 慢）
- 按需分配，不需要整体扩容
1.2 deque 的底层数据结构
核心组件
┌─────────────────────────────────────────────┐
│ deque 结构 │
├─────────────────────────────────────────────┤
│ map 指针（中控阵列） │
│ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │
│ │ * │ * │ * │ * │ * │ * │ * │ * │ ... │
│ └───┴───┴───┴───┴───┴───┴───┴───┘ │
│ ↓ ↓ ↓ ↓ │
│ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │Block│ │Block│ ... │Block│ │
│ │buf[]│ │buf[]│ │buf[]│ │
│ └─────┘ └─────┘ └─────┘ │
│ ↑ ↑ ↑ │
│ start cur (finish) finish│
└─────────────────────────────────────────────┘
- Map（中控阵列）：一个指针数组，每个元素指向一个缓冲区（Block）
- Buffer（缓冲区）：固定大小的连续内存块，默认通常为 512 字节 / sizeof(T)
- start 迭代器：指向第一个缓冲区的起始元素
- finish 迭代器：指向最后一个缓冲区的末尾元素
关键成员变量
class deque {
protected:
typedef T** map_pointer; // 指向指针的指针（中控阵列）
iterator start; // 当前使用的第一个缓冲区
iterator finish; // 当前使用的最后一个缓冲区
map_pointer map; // 中控阵列指针
size_type map_size; // 中控阵列大小
};
1.3 deque 迭代器实现
迭代器结构
struct _deque_iterator {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef T* pointer;
typedef const T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;
T* cur; // 指向当前元素
T* first; // 当前缓冲区的起始位置
T* last; // 当前缓冲区的结束位置（不含）
map_pointer node; // 指向当前缓冲区在中控阵列中的位置
// 构造函数
_deque_iterator(T* x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
_deque_iterator() : cur(0), first(0), last(0), node(0) {}
};
迭代器自增操作
self& operator++() {
++cur; // 先移动到下一个位置
if (cur == last) { // 如果到达当前缓冲区末尾
set_node(node + 1); // 切换到下一个缓冲区
cur = first; // cur 指向新缓冲区的起始
}
return *this;
}
缓冲区大小计算
// 假设每个 buffer 大小为 N（通常 512 字节）
// 获取第 i 个数据的位置：
int block_index = i / N; // 第几个缓冲区
int offset_in_block = i % N; // 在该缓冲区内的偏移
// 访问：*((ptr + block_index)[offset_in_block])
// 简化：*(*(ptr + block_index) + offset_in_block)
迭代器随机访问（operator+=）
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
// 情况1：仍在当前缓冲区范围内
if (offset >= 0 && offset < difference_type(buffer_size()))
cur += n;
else {
// 情况2：需要跳到其他缓冲区
difference_type node_offset =
n > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
1.4 deque 核心操作分析
头尾插入
// 头插：O(1)
void push_front(const T& x) {
if (start.cur != start.first) {
// 当前缓冲区还有空间
--start.cur;
*start.cur = x;
} else {
// 需要扩充或新建缓冲区
insert_aux_front(x);
}
}
// 尾插：O(1)
void push_back(const T& x) {
if (finish.cur != finish.last - 1) {
// 当前缓冲区还有空间
*finish.cur = x;
++finish.cur;
} else {
// 需要扩充或新建缓冲区
insert_aux_back(x);
}
}
中间插入
iterator insert(iterator position, const value_type& x) {
if (position.cur == start.cur) {
push_front(x);
return start;
} else if (position.cur == finish.cur) {
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
} else {
return insert_aux(position, x); // 中间插入，需要搬移数据 O(N)
}
}
1.5 deque vs vector vs list 对比总结
| 特性 | vector | list | deque |
|---|---|---|---|
| 内存布局 | 连续 | 链式 | 分段连续 |
| 随机访问 | O(1) | O(N) | O(1)（略慢） |
| 头插 | O(N) | O(1) | O(1) |
| 尾插 | O(1) amortized | O(1) | O(1) |
| 中间插入 | O(N) | O(1) | O(N) |
| 扩容代价 | 高（拷贝全部） | 无 | 低（仅新增区块） |
| 缓存友好性 | 优秀 | 差 | 较好 |
| 适用场景 | 只尾插尾删 | 频繁中间插删 | 头尾频繁操作 |
二、Priority Queue：优先队列
2.1 概念与定义
优先队列是一种容器适配器，根据某种严格弱序准则，其第一个元素总是包含最大值（默认情况）。
template <class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type> >
class priority_queue;
- Container：底层容器，默认为 vector
- Compare：比较函数，默认为
less（大顶堆）
2.2 核心操作
priority_queue<int> pq; // 默认大顶堆
pq.push(5); // 插入元素
pq.push(3);
pq.push(8);
pq.top(); // 访问队头（最大值）：8
pq.pop(); // 移除队头
pq.size(); // 返回元素个数
pq.empty(); // 判断是否为空
2.3 自定义优先级
// 小顶堆（最小值优先）
priority_queue<int, vector<int>, greater<int>> min_pq;
// 自定义比较器
struct CustomCompare {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second; // 按 second 从小到大
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, CustomCompare> pq;
三、堆（Heap）：数据结构原理
3.1 堆的定义
堆是一种特殊的完全二叉树，满足以下性质：
- 大顶堆：每个节点的值 ≥ 其子节点的值
- 小顶堆：每个节点的值 ≤ 其子节点的值
3.2 数组与完全二叉树的映射
对于编号为 i 的节点（从 0 开始）：
左孩子：left = 2*i + 1
右孩子：right = 2*i + 2
父节点：parent = (i - 1) / 2
图示示例
0(9)
/ \
1(5) 2(7)
/ \ /
3(1) 4(2) 5(4)
数组表示：[9, 5, 7, 1, 2, 4]
验证映射：
- 节点0(9)的左孩子 = 2*0+1 = 1 → 5 ✓
- 节点0(9)的右孩子 = 2*0+2 = 2 → 7 ✓
- 节点1(5)的左孩子 = 2*1+1 = 3 → 1 ✓
- 节点1(5)的右孩子 = 2*1+2 = 4 → 2 ✓
- 节点2(7)的左孩子 = 2*2+1 = 5 → 4 ✓
- 节点5(4)的父节点 = (5-1)/2 = 2 → 7 ✓
3.3 堆的核心操作
向上调整（Push）
当插入新元素时，需要从新位置向上调整，维持堆性质。
void AdjustUp(vector<int>& heap, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (heap[parent] < heap[child]) { // 大顶堆：父 < 子
swap(heap[parent], heap[child]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
向下调整（Pop）
当移除堆顶元素时，需要将最后一个元素移到堆顶，然后向下调整。
void AdjustDown(vector<int>& heap, int parent, int n) {
int child = 2 * parent + 1; // 左孩子
while (child < n) {
// 找较大的孩子
if (child + 1 < n && heap[child] < heap[child + 1]) {
child++;
}
// 如果父节点已经大于等于较大孩子，则调整完毕
if (heap[parent] >= heap[child]) {
break;
}
swap(heap[parent], heap[child]);
parent = child;
child = 2 * parent + 1;
}
}
3.4 堆排序
// 建堆（从最后一个非叶子节点开始向下调整）
void BuildHeap(vector<int>& heap) {
int n = heap.size();
for (int i = (n - 2) / 2; i >= 0; i--) {
AdjustDown(heap, i, n);
}
}
// 堆排序
void HeapSort(vector<int>& heap) {
int n = heap.size();
BuildHeap(heap); // O(N)
for (int i = n - 1; i > 0; i--) {
swap(heap[0], heap[i]); // 将最大值放到末尾
AdjustDown(heap, 0, i); // 重新调整堆 O(logN)
}
}
时间复杂度：O(N log N)
空间复杂度：O(1)
稳定性：不稳定排序
四、排序算法：冒泡排序及其泛型实现
4.1 冒泡排序原理
相邻两个数两两比较，将较大的数交换到后面，每轮结束后最大值"浮"到末尾。
原始数组：[9, 1, 2, 5, 7, 4, 6, 3]
第1轮：[1, 2, 5, 7, 4, 6, 3, 9] ← 9 冒泡到末尾
第2轮：[1, 2, 5, 4, 6, 3, 7, 9] ← 7 冒泡到位
第3轮：[1, 2, 4, 5, 3, 6, 7, 9] ← 6 冒泡到位
...
4.2 基础实现
void BubbleSort(int a[], int n) {
for (int j = 0; j < n - 1; j++) { // 外层：控制轮数
for (int i = 0; i < n - 1 - j; i++) { // 内层：相邻比较
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
}
}
}
}
优化：添加提前终止标志
void BubbleSortOptimized(int a[], int n) {
for (int j = 0; j < n - 1; j++) {
bool swapped = false;
for (int i = 0; i < n - 1 - j; i++) {
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped) break; // 没有交换，说明已有序
}
}
4.3 泛型冒泡排序（使用函数对象）
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) {
return x < y; // 升序
}
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) {
return x > y; // 降序
}
};
template<class T, class Compare>
void BubbleSort(T a[], int n, Compare comp) {
for (int j = 0; j < n - 1; j++) {
for (int i = 0; i < n - 1 - j; i++) {
if (comp(a[i], a[i + 1])) { // 使用自定义比较器
swap(a[i], a[i + 1]);
}
}
}
}
// 使用示例
int a[] = {9, 1, 2, 5, 7, 4, 6, 3};
// 升序排序
BubbleSort(a, 8, Less<int>());
// 降序排序
BubbleSort(a, 8, Greater<int>());
4.4 时间复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(N) | 已有序，只需一轮扫描 |
| 平均 | O(N²) | 每次比较都可能需要交换 |
| 最坏 | O(N²) | 逆序排列 |
五、知识串联与总结
5.1 知识点关联图
┌─────────────────────────────────────────────────────────────────┐
│ STL 容器体系 │
├────────────────────────┬────────────────────────┬────────────────┤
│ 顺序容器 │ 容器适配器 │ 算法 │
├────────────────────────┼────────────────────────┼────────────────┤
│ vector ←连续内存 │ priority_queue ← 堆 │ sort │
│ list ←双向链表 │ stack ← 适配器 │ find │
│ deque ←分段连续内存 │ queue ← 适配器 │ bubble_sort │
└────────────────────────┴────────────────────────┴────────────────┘
↓ ↓ ↓
迭代器设计 堆操作 排序算法
map中控 向上/向下调整 泛型实现
5.2 核心要点速记
deque
- Map 中控阵列 + 多个 Buffer 块
- 头尾 O(1)，中间 O(N)
- 迭代器需维护 cur/first/last/node 四个指针
- 随机访问通过 i/N 和 i%N 定位
priority_queue
- 基于堆实现的容器适配器
- 默认大顶堆（less 比较）
- 只能访问和移除顶部元素
堆
- 完全二叉树的数组表示
- 左孩子 = 2i+1，右孩子 = 2i+2
- 向上调整用于插入，向下调整用于删除
冒泡排序
- 相邻比较，大数后移
- 泛型实现通过函数对象支持自定义比较
- O(N²) 复杂度，简单但效率低
六、常见问题与面试考点
Q1：deque 为什么不直接复用 vector 的扩容策略？
答：deque 的缓冲区是固定大小的，扩容时只需在 map 中新增指针指向新缓冲区，不需要像 vector 那样重新分配整块内存并拷贝所有元素。
Q2：deque 的迭代器如何实现随机访问？
答：通过 i/N 找到第几个缓冲区，i%N 找到缓冲区内的偏移量，然后直接定位到对应内存地址。
Q3：为什么 priority_queue 默认是大顶堆？
答：STL 使用 less 作为默认比较器，堆的性质是父节点 ≥ 子节点，所以堆顶始终是最大值。
Q4：堆排序的时间复杂度为什么是 O(N log N)？
答：建堆 O(N)，每次弹出堆顶后向下调整 O(log N)，共执行 N 次，总计 O(N log N)。
Q5：冒泡排序什么情况下退化为 O(N)？
答：当数组已经有序时，优化版本的冒泡排序只需一轮扫描即可确定有序，时间复杂度降为 O(N)。
七、代码附录
A. deque 迭代器完整实现框架
template <class T>
struct _deque_iterator {
typedef _deque_iterator<T> self;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;
typedef random_access_iterator_tag iterator_category;
T* cur; // 当前元素
T* first; // 缓冲区首
T* last; // 缓冲区尾（不含）
map_pointer node; // 中控阵列位置
_deque_iterator() : cur(0), first(0), last(0), node(0) {}
_deque_iterator(pointer x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
reference operator*() const { return *cur; }
pointer operator->() const { return cur; }
self& operator++() {
++cur;
if (cur == last) {
set_node(node + 1);
cur = first;
}
return *this;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
cur += n;
else {
difference_type node_offset =
n > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
static size_type buffer_size() { return 4; } // 简化示例
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
};
B. 堆排序完整实现
#include <vector>
#include <algorithm>
using namespace std;
void AdjustUp(vector<int>& heap, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (heap[parent] < heap[child]) {
swap(heap[parent], heap[child]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
void AdjustDown(vector<int>& heap, int parent, int n) {
int child = 2 * parent + 1;
while (child < n) {
if (child + 1 < n && heap[child] < heap[child + 1]) {
child++;
}
if (heap[parent] >= heap[child]) break;
swap(heap[parent], heap[child]);
parent = child;
child = 2 * parent + 1;
}
}
void HeapSort(vector<int>& nums) {
int n = nums.size();
// 建堆
for (int i = (n - 2) / 2; i >= 0; i--) {
AdjustDown(nums, i, n);
}
// 排序
for (int i = n - 1; i > 0; i--) {
swap(nums[0], nums[i]);
AdjustDown(nums, 0, i);
}
}
任何的批评与建议欢迎指出，我们共同进步！
更多推荐
12
0- 0
已为社区贡献3条内容
所有评论(0)