Ch 17: 其他标准容器

本章目标

• 理解各容器的底层数据结构和性能特征
• 掌握 std::array 的用法和与 C 数组的区别
• 学会在不同场景下选择合适的容器
• 理解 deque vs vector 的区别
• 理解 set vs unordered_set 的选择
• 掌握 list 和 forward_list 的使用场景

17.1 容器总览

选择决策树

需要存储元素？
├── 固定大小（编译时已知） → std::array
├── 大小可变
│   ├── 默认使用 → std::vector
│   ├── 需要两端 O(1) 插入删除 → std::deque
│   ├── 需要有序遍历 → std::set
│   ├── 需要唯一键 + 快速查找 → std::unordered_set
│   ├── 需要键值对 → std::map / std::unordered_map
│   ├── 需要频繁中间插入删除 → std::list
│   └── 需要 FIFO → std::queue

性能对比表

容器	随机访问	头部插入	尾部插入	中间插入	搜索
vector	O(1)	O(n)	O(1) 均摊	O(n)	O(n)
deque	O(1)	O(1)	O(1)	O(n)	O(n)
list	O(n)	O(1)	O(1)	O(1)	O(n)
array	O(1)	N/A	N/A	N/A	O(n)
set	N/A	O(log n)	O(log n)	O(log n)	O(log n)
unordered_set	N/A	O(1) 均摊	O(1) 均摊	O(1) 均摊	O(1) 均摊

Python 对照

Python	C++	说明
list	vector	动态数组，默认选择
list（固定大小）	array	固定大小数组
collections.deque	deque	双端队列
无直接对应	list	双向链表
set	unordered_set	无序集合
set（有序）	set	有序集合
无	forward_list	单向链表
dict	unordered_map	哈希表

17.2 std::array 详解

基础用法

#include <array>
#include <iostream>

int main() {
    // 固定大小，编译时确定
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 访问方式
    arr[0];           // 不检查边界
    arr.at(0);        // 检查边界，越界抛 std::out_of_range
    arr.front();      // 第一个元素
    arr.back();       // 最后一个元素

    // 大小信息
    arr.size();       // 5（编译时已知）
    arr.empty();      // false
    arr.max_size();   // 5（与 size 相同）

    // 遍历
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    // 支持迭代器
    for (auto it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    return 0;
}

vs C 风格数组

#include <array>
#include <iostream>
#include <algorithm>

int main() {
    // C 风格数组
    int c_arr[5] = {1, 2, 3, 4, 5};

    // C 数组传递给函数时会退化为指针
    // void process(int* arr);  // arr 丢失了大小信息

    // std::array 保留大小信息
    std::array<int, 5> cpp_arr = {1, 2, 3, 4, 5};

    // 安全操作
    std::sort(cpp_arr.begin(), cpp_arr.end());  // 有迭代器
    // cpp_arr.data() 返回底层指针（用于 C 互操作）

    // 边界安全
    // c_arr[10];   // ❌ 未定义行为，无检查
    // cpp_arr.at(10);  // ❌ 抛出 std::out_of_range

    // 多维数组
    std::array<std::array<int, 3>, 2> matrix = {{
        {1, 2, 3},
        {4, 5, 6}
    }};

    std::cout << matrix[1][2] << std::endl;  // 6

    return 0;
}

初始化行为

#include <array>
#include <iostream>

int main() {
    // 默认初始化（不定值！）
    std::array<int, 5> a1;  // 未初始化，可能是任意值

    // 值初始化为 0
    std::array<int, 5> a2{};  // 所有元素为 0
    std::array<int, 5> a3 = {};  // 同上

    // 聚合初始化
    std::array<int, 5> a4 = {1, 2, 3};  // {1, 2, 3, 0, 0}
    std::array<int, 5> a5 = {1, 2, 3, 4, 5};  // 完整初始化

    // C++20 可以用 std::to_array（编译时转换）
    // auto arr = std::to_array({1, 2, 3});  // std::array<int, 3>

    return 0;
}

实际应用场景

#include <array>
#include <iostream>
#include <algorithm>
#include <numeric>

// 场景 1：查找表（编译时大小固定）
std::array<int, 26> create_letter_count() {
    std::array<int, 26> counts = {};
    // ...
    return counts;
}

// 场景 2：固定大小的缓冲区
using Buffer = std::array<uint8_t, 1024>;

// 场景 3：坐标系统
struct Point3D {
    std::array<double, 3> coords;
};

Point3D p1{{{1.0, 2.0, 3.0}}};  // 初始化

// 场景 4：查找表
std::array<int, 128> char_to_index;  // ASCII 字符映射

int main() {
    // 计算统计量
    std::array<int, 5> values = {3, 1, 4, 1, 5};

    auto [min_it, max_it] = std::minmax_element(values.begin(), values.end());
    std::cout << "Min: " << *min_it << ", Max: " << *max_it << "\n";

    int sum = std::accumulate(values.begin(), values.end(), 0);
    std::cout << "Sum: " << sum << "\n";

    // 检查是否包含
    bool has_3 = std::find(values.begin(), values.end(), 3) != values.end();

    return 0;
}

17.3 std::deque 详解

什么是 deque

# Python - collections.deque
from collections import deque

dq = deque()
dq.append(1)        # 右端添加
dq.appendleft(0)    # 左端添加
dq.pop()            # 右端弹出
dq.popleft()        # 左端弹出
dq[0]               # 访问头部
dq[-1]              # 访问尾部

C++ deque 基本操作

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    // 两端操作
    dq.push_back(1);      // {1}
    dq.push_front(0);     // {0, 1}
    dq.push_back(2);      // {0, 1, 2}

    // 访问
    std::cout << dq.front() << std::endl;  // 0
    std::cout << dq.back() << std::endl;   // 2
    std::cout << dq[1] << std::endl;       // 1

    // 删除
    dq.pop_front();       // {1, 2}
    dq.pop_back();        // {1}

    // 在中间插入（O(n)，但两端 O(1)）
    dq.insert(dq.begin() + 1, 5);  // {1, 5, 2}

    // 大小
    std::cout << dq.size() << std::endl;  // 3

    return 0;
}

deque vs vector

#include <deque>
#include <vector>
#include <iostream>
#include <chrono>

int main() {
    // vector：内存连续，尾部插入 O(1)
    //       中间插入 O(n)，头部插入 O(n)
    // deque：分块内存，两端插入 O(1)，中间 O(n)
    //       随机访问 O(1)，但比 vector 稍慢

    std::vector<int> v;
    std::deque<int> dq;

    // 性能测试：尾部追加
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        v.push_back(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Vector push_back: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        dq.push_back(i);
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Deque push_back: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    // 性能测试：头部追加
    v.clear();
    dq.clear();

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) {
        v.insert(v.begin(), i);  // O(n)，慢
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Vector push_front (10k): "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) {
        dq.push_front(i);  // O(1)，快
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Deque push_front (10k): "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    return 0;
}

实际应用场景

#include <deque>
#include <iostream>
#include <string>

// 场景 1：任务队列（FIFO）
class TaskQueue {
private:
    std::deque<std::string> tasks_;

public:
    void add_task(const std::string& task) {
        tasks_.push_back(task);
    }

    std::string get_next_task() {
        if (tasks_.empty()) return "";
        std::string task = tasks_.front();
        tasks_.pop_front();
        return task;
    }

    bool empty() const { return tasks_.empty(); }
    std::size_t size() const { return tasks_.size(); }
};

// 场景 2：滑动窗口
class SlidingWindow {
private:
    std::deque<int> window_;
    std::size_t max_size_;

public:
    explicit SlidingWindow(std::size_t size) : max_size_(size) {}

    void add(int value) {
        window_.push_back(value);
        if (window_.size() > max_size_) {
            window_.pop_front();
        }
    }

    double average() const {
        if (window_.empty()) return 0.0;
        long long sum = 0;
        for (int x : window_) sum += x;
        return static_cast<double>(sum) / window_.size();
    }

    std::size_t size() const { return window_.size(); }
};

// 场景 3：撤销/重做历史
class History {
private:
    std::deque<std::string> undo_stack_;
    std::deque<std::string> redo_stack_;
    static const std::size_t MAX_HISTORY = 100;

public:
    void record(const std::string& action) {
        undo_stack_.push_back(action);
        redo_stack_.clear();
        if (undo_stack_.size() > MAX_HISTORY) {
            undo_stack_.pop_front();
        }
    }

    std::string undo() {
        if (undo_stack_.empty()) return "";
        std::string action = undo_stack_.back();
        undo_stack_.pop_back();
        redo_stack_.push_back(action);
        return action;
    }

    std::string redo() {
        if (redo_stack_.empty()) return "";
        std::string action = redo_stack_.back();
        redo_stack_.pop_back();
        undo_stack_.push_back(action);
        return action;
    }
};

int main() {
    // 测试任务队列
    TaskQueue queue;
    queue.add_task("Task 1");
    queue.add_task("Task 2");
    std::cout << "Next: " << queue.get_next_task() << "\n";

    // 测试滑动窗口
    SlidingWindow window(3);
    window.add(10);
    window.add(20);
    window.add(30);
    std::cout << "Average (3 elements): " << window.average() << "\n";
    window.add(40);
    std::cout << "Average (3 elements, new): " << window.average() << "\n";

    return 0;
}

17.4 std::list 详解

链表 vs 数组

# Python 没有内置链表，但可以用列表模拟
# 列表在中间插入/删除是 O(n)

lst = [1, 2, 3, 4, 5]
lst.insert(2, 99)  # O(n)，需要移动元素
lst.pop(2)         # O(n)

#include <list>
#include <iostream>

int main() {
    // 双向链表
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 任意位置插入/删除 O(1)（需要迭代器）
    auto it = lst.begin();
    ++it;  // 指向第二个元素

    lst.insert(it, 99);   // 在第二个位置前插入 {1, 2, 99, 3, 4, 5}
    lst.erase(it);        // 删除第二个（99）{1, 2, 3, 4, 5}

    // splice - 高效移动整个链表
    std::list<int> lst1 = {1, 2, 3};
    std::list<int> lst2 = {4, 5, 6};

    // 将 lst2 的全部移动到 lst1 末尾
    lst1.splice(lst1.end(), lst2);
    // lst1 = {1, 2, 3, 4, 5, 6}
    // lst2 = 空

    // 排序（链表有自己的 sort，更高效）
    lst1.sort();  // O(n log n)

    // 合并（合并两个已排序链表）
    std::list<int> a = {1, 3, 5};
    std::list<int> b = {2, 4, 6};
    a.merge(b);  // a = {1, 2, 3, 4, 5, 6}

    // 去重
    lst1.unique();  // 删除连续重复元素

    return 0;
}

迭代器失效规则

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 获取迭代器
    auto it = lst.begin();
    ++it;  // 指向 2

    // ✅ 删除元素不会使其他迭代器失效（除了被删除的）
    lst.erase(it);  // 删除 2
    // it 现在失效，不能使用

    // ✅ 插入不会使任何迭代器失效
    it = lst.begin();
    ++it;
    lst.insert(it, 99);  // 不会使 it 失效

    // ✅ list 是双向迭代器，支持 --
    auto rit = lst.end();
    --rit;  // 指向最后一个元素

    return 0;
}

forward_list 单向链表

#include <forward_list>
#include <iostream>

int main() {
    // 单向链表 - 更省内存，但只能前向遍历
    std::forward_list<int> flst = {1, 2, 3, 4, 5};

    // 没有 push_back，只有 push_front
    flst.push_front(0);

    // 在某个元素后插入
    auto it = flst.begin();  // 指向 0
    ++it;                    // 指向 1
    flst.insert_after(it, 99);  // 在 1 后插入 99

    // erase_after - 删除某个元素后的元素
    flst.erase_after(it);  // 删除 99

    // 没有 end() 直接访问，需要 advance
    // flst.end() 存在但不能直接用
    auto eit = flst.begin();
    std::advance(eit, 2);  // 移动到第三个元素

    return 0;
}

list vs vector 选择

场景	推荐容器	原因
默认首选	vector	缓存友好，性能好
频繁在中间插入删除	list	O(1) 插入删除
频繁在头部插入删除	deque	O(1) 两端操作
需要迭代器稳定（不随插入删除失效）	list	迭代器不失效
大数据量遍历	vector	缓存命中率高
内存受限	forward_list	最小内存开销

17.5 std::set 详解

set 基础

# Python set
s = {3, 1, 4, 1, 5, 9, 2, 6}
# 自动去重和排序：{1, 2, 3, 4, 5, 6, 9}

s.add(7)
s.remove(3)  # 不存在会抛异常
s.discard(3)  # 不存在不抛异常

if 5 in s:
    print("Found")

#include <set>
#include <iostream>

int main() {
    // 有序集合（红黑树实现）
    std::set<int> s = {3, 1, 4, 1, 5, 9, 2, 6};
    // 自动排序：{1, 2, 3, 4, 5, 6, 9}

    // 插入
    s.insert(7);           // O(log n)

    // 删除
    s.erase(3);            // 删除元素 3

    // 查找
    auto it = s.find(5);   // O(log n)
    if (it != s.end()) {
        std::cout << "Found: " << *it << "\n";
    }

    // 检查存在
    if (s.count(5)) {  // 0 或 1
        std::cout << "5 exists\n";
    }

    // 下界和上界
    auto lower = s.lower_bound(4);  // >= 4 的第一个
    auto upper = s.upper_bound(4); // > 4 的第一个

    // 遍历（有序）
    for (int x : s) {
        std::cout << x << " ";  // 1 2 4 5 6 7 9
    }
    std::cout << "\n";

    return 0;
}

自定义比较函数

#include <set>
#include <string>
#include <iostream>

// 方式 1：自定义类 + operator<
struct Person {
    std::string name;
    int age;

    bool operator<(const Person& other) const {
        return age < other.age;  // 按年龄排序
    }
};

// 方式 2：自定义比较函数
struct PersonCmp {
    bool operator()(const Person& a, const Person& b) const {
        return a.name < b.name;  // 按名字排序
    }
};

int main() {
    // 使用 operator<
    std::set<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    for (const auto& p : people) {
        std::cout << p.name << ": " << p.age << "\n";
        // 按年龄排序输出
    }

    // 使用自定义比较函数
    std::set<Person, PersonCmp> people_by_name = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    for (const auto& p : people_by_name) {
        std::cout << p.name << ": " << p.age << "\n";
        // 按名字排序输出
    }

    return 0;
}

multiset（允许重复）

#include <set>
#include <iostream>

int main() {
    // 允许重复元素的 set
    std::multiset<int> ms = {3, 1, 4, 1, 5, 9, 2, 6, 4};

    // count - 统计出现次数
    std::cout << "4 appears " << ms.count(4) << " times\n";  // 2

    // 遍历（有序）
    for (int x : ms) {
        std::cout << x << " ";  // 1 1 2 3 4 4 5 6 9
    }
    std::cout << "\n";

    // lower_bound/upper_bound 返回范围
    auto range = ms.equal_range(4);  // 4 的范围
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Found: " << *it << "\n";
    }

    // erase - 删除所有匹配的
    ms.erase(4);  // 删除所有 4

    return 0;
}

17.6 std::unordered_set 详解

无序集合

#include <unordered_set>
#include <iostream>

int main() {
    // 无序集合（哈希表实现）
    std::unordered_set<int> us = {3, 1, 4, 1, 5, 9, 2, 6};

    // 插入 O(1)
    us.insert(7);

    // 查找 O(1) 平均
    if (us.find(5) != us.end()) {
        std::cout << "Found 5\n";
    }

    // 删除 O(1) 平均
    us.erase(3);

    // bucket 信息
    std::cout << "Bucket count: " << us.bucket_count() << "\n";

    // 遍历顺序不确定
    std::cout << "Elements: ";
    for (int x : us) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    return 0;
}

unordered_set vs set

#include <set>
#include <unordered_set>
#include <chrono>
#include <iostream>

int main() {
    const int N = 100000;

    // 测试插入性能
    std::set<int> ordered;
    std::unordered_set<int> unordered;

    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        ordered.insert(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "set insert: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        unordered.insert(i);
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "unordered_set insert: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    // 测试查找性能
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        volatile bool found = ordered.find(i) != ordered.end();
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "set find: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        volatile bool found = unordered.find(i) != unordered.end();
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "unordered_set find: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    return 0;
}

unordered_multiset

#include <unordered_set>
#include <iostream>

int main() {
    // 允许重复的无序集合
    std::unordered_multiset<int> ums = {1, 2, 3, 1, 2, 3, 1};

    std::cout << "Count of 1: " << ums.count(1) << "\n";  // 3

    // 删除一个
    auto it = ums.find(1);
    if (it != ums.end()) {
        ums.erase(it);  // 删除一个 1
    }

    std::cout << "Count of 1 after erase: " << ums.count(1) << "\n";  // 2

    return 0;
}

17.7 容器适配器

std::stack

#include <stack>
#include <iostream>

int main() {
    std::stack<int> st;

    st.push(1);  // {1}
    st.push(2);  // {1, 2}
    st.push(3);  // {1, 2, 3}

    std::cout << "Top: " << st.top() << std::endl;  // 3

    st.pop();    // {1, 2}
    std::cout << "Top after pop: " << st.top() << std::endl;  // 2

    std::cout << "Size: " << st.size() << std::endl;  // 2

    // 用 vector 实现 stack
    std::stack<int, std::vector<int>> st2;

    return 0;
}

std::queue

#include <queue>
#include <iostream>

int main() {
    std::queue<int> q;

    q.push(1);  // {1}
    q.push(2);  // {1, 2}
    q.push(3);  // {1, 2, 3}

    std::cout << "Front: " << q.front() << std::endl;  // 1
    std::cout << "Back: " << q.back() << std::endl;    // 3

    q.pop();    // {2, 3}
    std::cout << "Front after pop: " << q.front() << std::endl;  // 2

    return 0;
}

std::priority_queue

#include <queue>
#include <iostream>
#include <vector>

int main() {
    // 最大堆（默认）
    std::priority_queue<int> pq;

    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "Top (max): " << pq.top() << std::endl;  // 50

    pq.pop();  // 删除 50
    std::cout << "Top after pop: " << pq.top() << std::endl;  // 30

    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

    min_pq.push(30);
    min_pq.push(10);
    min_pq.push(50);
    min_pq.push(20);

    std::cout << "Top (min): " << min_pq.top() << std::endl;  // 10

    return 0;
}

17.8 完整示例：文本编辑器

#include <deque>
#include <list>
#include <string>
#include <iostream>
#include <memory>

// 文本编辑器（类似撤销/重做功能）
class TextEditor {
private:
    std::deque<std::string> undo_stack_;
    std::deque<std::string> redo_stack_;
    std::string current_text_;
    std::size_t max_history_;

public:
    explicit TextEditor(std::size_t max_history = 100)
        : max_history_(max_history) {}

    void type(const std::string& text) {
        undo_stack_.push_back(current_text_);
        if (undo_stack_.size() > max_history_) {
            undo_stack_.pop_front();
        }
        current_text_ += text;
        redo_stack_.clear();
    }

    void backspace(std::size_t chars = 1) {
        if (chars > current_text_.size()) {
            chars = current_text_.size();
        }
        undo_stack_.push_back(current_text_);
        current_text_.resize(current_text_.size() - chars);
        redo_stack_.clear();
    }

    std::string undo() {
        if (undo_stack_.empty()) return current_text_;
        redo_stack_.push_back(current_text_);
        current_text_ = undo_stack_.back();
        undo_stack_.pop_back();
        return current_text_;
    }

    std::string redo() {
        if (redo_stack_.empty()) return current_text_;
        undo_stack_.push_back(current_text_);
        current_text_ = redo_stack_.back();
        redo_stack_.pop_back();
        return current_text_;
    }

    const std::string& content() const { return current_text_; }

    bool can_undo() const { return !undo_stack_.empty(); }
    bool can_redo() const { return !redo_stack_.empty(); }
};

// 链表实现的朋友列表
class FriendList {
private:
    std::list<std::string> friends_;

public:
    void add_friend(const std::string& name) {
        friends_.push_back(name);
    }

    void remove_friend(const std::string& name) {
        friends_.remove(name);
    }

    bool is_friend(const std::string& name) const {
        return std::find(friends_.begin(), friends_.end(), name) != friends_.end();
    }

    void sort_alphabetically() {
        friends_.sort();
    }

    void print() const {
        for (const auto& f : friends_) {
            std::cout << "- " << f << "\n";
        }
    }
};

int main() {
    // 测试文本编辑器
    TextEditor editor;

    editor.type("Hello ");
    editor.type("World!");
    std::cout << "Content: " << editor.content() << "\n";

    editor.backspace(6);
    std::cout << "After backspace: " << editor.content() << "\n";

    editor.undo();
    std::cout << "After undo: " << editor.content() << "\n";

    editor.redo();
    std::cout << "After redo: " << editor.content() << "\n";

    std::cout << "\n=== Friend List ===\n";

    FriendList friends;
    friends.add_friend("Charlie");
    friends.add_friend("Alice");
    friends.add_friend("Bob");

    friends.sort_alphabetically();
    friends.print();

    return 0;
}

章节总结

容器	底层结构	特点
array<T, N>	固定数组	编译时大小，边界安全
vector<T>	动态数组	默认首选，末尾 O(1)
deque<T>	分块数组	两端 O(1)
list<T>	双向链表	中间插入 O(1)，迭代器稳定
forward_list<T>	单向链表	最小内存开销
set<T>	红黑树	有序，O(log n)
unordered_set<T>	哈希表	无序，O(1) 平均
multiset<T>	红黑树	有序，允许重复
stack<T>	适配器	LIFO
queue<T>	适配器	FIFO
priority_queue<T>	堆	最大/最小元素优先

选择原则：

• 默认用 vector
• 需要两端操作 → deque
• 需要有序遍历 → set
• 需要快速查找 → unordered_set
• 需要频繁中间插入删除 → list

---

下章预告：ch18 学习迭代器和标准库算法。