Ch 4: 容器与数据结构

本章目标

• 掌握 std::vector 与 list 的对比
• 掌握 std::map/unordered_map 与 dict 的对比
• 理解 std::set 的使用场景
• 学会选择合适的容器

4.1 Python list vs C++ vector

Python 列表特性

Python list 是动态数组，内部实现包括：

• 连续内存存储：元素在内存中相邻
• 动态扩容：当空间不足时，分配更大的数组并复制
• 任意类型：可以存储任何 Python 对象（实际存储的是指针）

# Python - 列表是动态数组
lst = [1, 2, 3, 4, 5]

# 添加元素
lst.append(6)         # 末尾添加
lst.insert(0, 0)      # 任意位置插入
lst.extend([7, 8])    # 批量添加

# 删除元素
lst.pop()             # 末尾删除
lst.pop(0)            # 指定位置删除
lst.remove(3)         # 删除第一个出现的值

# 切片（Python 特有）
sub = lst[1:4]        # [2, 3, 4]
reversed_lst = lst[::-1]  # 反转

# 列表推导
squares = [x**2 for x in lst]
filtered = [x for x in lst if x % 2 == 0]

C++ vector

std::vector 是 Python list 的等价物：

#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};

// 添加元素
v.push_back(6);           // 末尾添加
v.emplace_back(7);         // C++11 原位构造，更高效
v.insert(v.begin(), 0);    // 任意位置插入

// 删除元素
v.pop_back();              // 末尾删除
v.erase(v.begin());        // 指定位置删除
v.erase(std::remove_if(v.begin(), v.end(),
    [](int x) { return x == 3; }), v.end());  // 删除值=3

// 访问
int first = v.front();      // 第一个元素
int last = v.back();        // 最后一个元素
int val = v[2];            // 下标访问
int val_safe = v.at(2);   // 带边界检查

// 大小
std::size_t sz = v.size();  // 元素个数
v.resize(10);               // 改变大小
v.shrink_to_fit();         // 释放多余容量

性能对比

操作	Python list	C++ vector	原因
索引	O(1)	O(1)	两者都是连续内存
尾插	O(1) 均摊	O(1) 均摊	类似实现
中间插/删	O(n)	O(n)	需要移动元素
遍历	有 Python 对象开销	直接内存访问	C++ 无对象包装

vector 的容量管理

std::vector<int> v;

// reserve - 预分配空间，避免多次扩容
v.reserve(1000);  // 预分配 1000 元素空间

// capacity - 已分配空间
std::cout << v.capacity() << std::endl;

// 常用操作
v.clear();        // 清空所有元素
v.empty();        // 是否为空
v.max_size();    // 最大可能容量

// 批量操作
std::vector<int> v2 = {1, 2, 3};
v.insert(v.end(), v2.begin(), v2.end());  // 批量插入

4.2 Python dict vs C++ unordered_map

Python 字典特性

Python dict 是哈希表的优化实现：

# Python - 字典
d = {"apple": 1, "banana": 2}

# 访问
d["cherry"] = 3       # 添加/修改
val = d["apple"]       # 获取，不存在会抛 KeyError
val = d.get("durian", 0)  # 安全获取，默认值

# 检查
if "apple" in d:
    del d["apple"]

# 遍历
for key in d:           # 遍历键
    print(key, d[key])
for key, value in d.items():  # 遍历键值对
    print(key, value)
for value in d.values():  # 遍历值
    print(value)

# 视图对象
keys = d.keys()
values = d.values()
items = d.items()

C++ unordered_map

std::unordered_map 是 Python dict 的等价物：

#include <unordered_map>

std::unordered_map<std::string, int> d = {{"apple", 1}, {"banana", 2}};

// 访问
d["cherry"] = 3;                      // 添加/修改
int val = d["apple"];                  // 获取，不存在会插入默认值

// 安全访问
auto it = d.find("durian");
int val2 = (it != d.end()) ? it->second : 0;  // 安全获取

// C++20 contains
if (d.contains("apple")) {  // C++20
    d.erase("apple");
}

// 遍历
for (const auto& [key, value] : d) {  // C++17 结构化绑定
    std::cout << key << ": " << value << std::endl;
}

for (auto it = d.begin(); it != d.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// 获取键值对容器
std::vector<std::pair<const std::string, int>> items(d.begin(), d.end());

map vs unordered_map

C++ 提供了两种映射容器：

#include <map>
#include <unordered_map>

// std::map - 有序（按 key 排序）- 红黑树实现
std::map<std::string, int> ordered = {
    {"banana", 2},
    {"apple", 1},
    {"cherry", 3}
};
// 遍历顺序：apple, banana, cherry（按字母排序）

// 边界操作
auto lb = ordered.lower_bound("b");   // 第一个 >= "b"
auto ub = ordered.upper_bound("b");   // 第一个 > "b"

// std::unordered_map - 无序 - 哈希表实现
std::unordered_map<std::string, int> hash = {
    {"banana", 2},
    {"apple", 1},
    {"cherry", 3}
};
// 遍历顺序不确定

// 性能对比
// map: O(log n) 查找/插入/删除，有序遍历
// unordered_map: O(1) 平均查找/插入/删除，无序

选择建议

场景	推荐容器
需要有序遍历	std::map
只关心快速查找	std::unordered_map
自定义比较/排序	std::map
内存敏感	std::unordered_map

4.3 Python set vs C++ set

Python 集合

# Python - 集合（无序、唯一）
s = {1, 2, 3, 2, 1}  # {1, 2, 3}

# 操作
s.add(4)
s.remove(2)      # 不存在会抛 KeyError
s.discard(10)    # 不存在不抛异常
s.pop()          # 任意删除一个

# 集合运算
s1 = {1, 2, 3}
s2 = {3, 4, 5}
union = s1 | s2          # 并集
intersection = s1 & s2  # 交集
difference = s1 - s2    # 差集
sym_diff = s1 ^ s2     # 对称差集

# 检查
2 in s1
s1.issubset(s2)
s1.issuperset(s2)

C++ set

#include <set>

// std::set - 有序唯一集合
std::set<int> s = {1, 2, 3, 2, 1};  // {1, 2, 3}

// 操作
s.insert(4);
s.erase(2);
auto it = s.find(2);
if (it != s.end()) s.erase(it);

// 集合运算（需要算法库）
std::set<int> s1 = {1, 2, 3};
std::set<int> s2 = {3, 4, 5};

// 并集
std::set<int> result;
std::set_union(s1.begin(), s1.end(),
               s2.begin(), s2.end(),
               std::inserter(result, result.begin()));
// result: {1, 2, 3, 4, 5}

// 交集
result.clear();
std::set_intersection(s1.begin(), s1.end(),
                       s2.begin(), s2.end(),
                       std::inserter(result, result.begin()));
// result: {3}

// unordered_set - 无序版本
std::unordered_set<int> us = {1, 2, 3};  // O(1) 查找

4.4 元组与结构体

Python 元组和 dataclass

# Python 元组（不可变）
t = (1, "hello", 3.14)
a, b, c = t  # 解包

# 命名元组
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)
print(p.x, p.y)  # 1 2

# dataclass（Python 3.7+）
from dataclasses import dataclass
@dataclass
class Point:
    x: int
    y: int
    def distance_from_origin(self):
        return (self.x**2 + self.y**2)**0.5

C++ tuple 和 struct

#include <tuple>

// 元组
std::tuple<int, std::string, double> t = {1, "hello", 3.14};
auto [a, b, c] = t;  // C++17 结构化绑定

// 访问元素
int x = std::get<0>(t);
std::string y = std::get<1>(t);

// std::pair - 两个元素的元组
std::pair<int, std::string> p = {1, "one"};
auto [key, value] = p;

// 结构体
struct Point {
    int x;
    int y;
};

Point pt{1, 2};
pt.x = 3;
pt.y = 4;

// 结构体初始化（C++20）
struct Point3D {
    int x = 0;
    int y = 0;
    int z = 0;
};

Point3D p3d{.x = 1, .y = 2, .z = 3};  // C++20 指定初始化

4.5 栈与队列

Python collections

from collections import deque, Counter, OrderedDict

# 栈（LIFO）
stack = deque()
stack.append(1)    # push
stack.append(2)
stack.pop()        # pop，返回 2

# 队列（FIFO）
queue = deque()
queue.append(1)    # enqueue
queue.append(2)
queue.popleft()    # dequeue，返回 1

# 有序字典（记住插入顺序）
od = OrderedDict()
od["first"] = 1
od["second"] = 2

# 计数器
cnt = Counter("abracadabra")
print(cnt.most_common(3))  # [('a', 5), ('b', 2), ('r', 2)]

C++ 容器适配器

#include <stack>
#include <queue>
#include <deque>

// 栈（LIFO）
std::stack<int> s;
s.push(1);
s.push(2);
int top = s.top();
s.pop();

// 队列（FIFO）
std::queue<int> q;
q.push(1);
q.push(2);
int front = q.front();
q.pop();

// 优先队列（最大元素在顶部）
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.top();  // 4

// deque - 双端队列
std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_back();
dq.pop_front();

// deque 可以用作栈或队列的底层容器
std::stack<int, std::deque<int>> s2;  // 指定底层容器

4.6 容器选择指南

选择决策树

需要有序遍历？
├── 是 → 需要键值对？→ 是 → std::map
│         └── 否 → std::set
└── 否 → 需要唯一性？
          ├── 是 → 需要快速查找？→ 是 → std::unordered_set
          │         └── 否 → std::set
          └── 否 → 需要两端的操作？
                  ├── 是 → std::deque
                  └── 否 → std::vector

性能特点

容器	插入	访问	查找	删除	特点
vector	末尾 O(1)	O(1)	O(n)	O(n)	连续内存，默认首选
deque	两端 O(1)	O(1)	O(n)	O(n)	分段连续
list	O(1)	O(n)	O(n)	O(1)	双向链表
set	O(log n)	-	O(log n)	O(log n)	红黑树
unordered_set	O(1) 平均	-	O(1) 平均	O(1) 平均	哈希表
map	O(log n)	-	O(log n)	O(log n)	红黑树
unordered_map	O(1) 平均	-	O(1) 平均	O(1) 平均	哈希表

章节总结

• std::vector 是 Python list 的等价物，是大多数场景的默认选择
• std::unordered_map 是 Python dict 的等价物，追求查找性能
• std::map 提供有序遍历
• std::set 是 Python set 的等价物
• 选择容器要考虑操作的时间复杂度

---

下章预告：ch05 迭代器与算法。