STL容器学习笔记 (附类比与实例)

导语

本文档是我学习 C++ STL（Standard Template Library）中各种容器的笔记总结。为了让这些概念更生动易懂，我将结合一些生活中的类比和具体的代码实例，来帮助理解 STL 容器的底层实现、特性和适用场景。

1. 序列式容器 (Sequence Containers)

序列式容器就像一个有序的列表，里面的元素按照它们被添加的顺序排列，我们可以通过它们在列表中的位置来访问它们。

1.1 `std::vector` - 动态数组 (像一个可伸缩的储物柜)

核心概念: 动态数组，内存连续。
类比: 想象一个储物柜，一开始可能只有几层，但当你需要放更多东西时，它会自动“变大”，增加新的层数来容纳。
底层实现: 单块连续内存，通过三个指针 (_M_start, _M_finish, _M_end_of_storage) 管理。
- _M_start: 柜子的起始位置。
- _M_finish: 当前已放满物品的柜子位置。
- _M_end_of_storage: 柜子总共能容纳物品的末尾位置。
特性:
- 快速查找 (O(1)): 就像你知道物品在第几层，可以直接去拿。例如 my_vector[5]。
- 末尾添加/删除高效 (均摊 O(1)): 在柜子最上面（末尾）放东西或拿走最上面的东西很快。
- 中间添加/删除低效 (O(n)): 如果你想在中间某一层插入或移除物品，可能需要把上面的所有物品都挪一下位置，非常麻烦。
- 自动扩容: 当储物柜满了，它会找一个更大的地方（比如一个更大的储物柜），把所有东西搬过去，然后把旧的储物柜扔掉。这个搬家过程比较耗时。
适用场景: 需要快速访问任意位置的元素，且主要在末尾进行添加或删除操作。
源码关键点: _M_check_len (扩容策略), _M_insert_aux (中间插入逻辑)。

实例:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers; // 创建一个空的vector
    numbers.push_back(10);    // 末尾添加元素，像在储物柜顶层放东西
    numbers.push_back(20);
    numbers.push_back(30);

    std::cout << "Vector elements: ";
    for (int num : numbers) {
        std::cout << num << " "; // 10 20 30
    }
    std::cout << std::endl;

    std::cout << "Element at index 1: " << numbers[1] << std::endl; // 快速访问，O(1)
    // numbers.insert(numbers.begin() + 1, 15); // 在中间插入，效率较低
    return 0;
}

1.2 `std::list` - 双向环形链表 (像一条可以随意增减环节的手链)

核心概念: 双向环形链表，内存非连续。
类比: 想象一条手链，每个珠子都知道它前面和后面的珠子是谁。你可以很容易地在任何两个珠子之间加一个新珠子，或者取下一个珠子，而不需要打断手链。
底层实现: 每个节点包含数据、前驱指针 (_M_prev) 和后继指针 (_M_next)。end() 指向一个特殊的空白节点，形成环。
特性:
- 任意位置插入/删除高效 (O(1)): 就像在手链上加减珠子一样简单。
- 不支持随机访问: 你不能直接说“给我第 5 个珠子”，你只能从头（或尾）一个一个地数过去。
- 迭代器稳定: 即使你插入或删除了其他元素，指向某个元素的迭代器仍然有效（除非你删除了那个元素本身）。
适用场景: 需要频繁在任意位置进行插入和删除，对随机访问无要求。
源码关键点: _M_hook (插入节点), _M_unhook (删除节点), splice (移动节点), sort (自定义归并排序)。

实例:

#include <list>
#include <iostream>

int main() {
    std::list<int> numbers;
    numbers.push_back(10); // 末尾添加
    numbers.push_front(5); // 开头添加
    numbers.push_back(20);

    auto it = numbers.begin(); // 获取第一个元素的迭代器
    ++it; // 指向第二个元素 (10)
    numbers.insert(it, 15); // 在 10 前面插入 15，非常快！

    std::cout << "List elements: ";
    for (int num : numbers) {
        std::cout << num << " "; // 5 15 10 20
    }
    std::cout << std::endl;

    numbers.erase(++numbers.begin()); // 删除第二个元素 (15)，也非常快！
    std::cout << "List after erase: ";
    for (int num : numbers) {
        std::cout << num << " "; // 5 10 20
    }
    std::cout << std::endl;
    return 0;
}

1.3 `std::deque` - 双端队列 (像一个可以两头进出的队列)

核心概念: 分段连续内存 + 中控器 (map)。
类比: 想象一个特殊的队列，你可以从前面（队首）和后面（队尾）都能快速地进出物品。它内部是由很多小盒子组成的，每个小盒子里的东西是连续的，但盒子之间不一定挨着。有一个总的目录（中控器）告诉你每个小盒子在哪里。
底层实现: 由多个固定大小的缓冲区组成，中控器管理这些缓冲区的指针。
特性:
- 两端操作高效 (O(1)): 就像从队列两头进出一样方便。
- 随机访问 (O(1)): 可以通过某种方式（虽然比 vector 复杂）快速定位到任意位置的元素。
- 中间插入/删除低效 (O(n)): 在中间插入或删除，可能需要移动很多元素，并且可能需要调整中控器和缓冲区。
适用场景: 需要在容器两端频繁进行插入和删除操作，同时需要随机访问。常作为 stack 和 queue 的默认底层容器。
源码关键点: 中控器 (_Deque_base, _Deque_impl), 复杂的迭代器 (_M_set_node 缓冲区切换)。

实例:

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;
    dq.push_back(10);  // 末尾添加
    dq.push_front(5);  // 开头添加
    dq.push_back(20);

    std::cout << "Deque elements: ";
    for (int num : dq) {
        std::cout << num << " "; // 5 10 20
    }
    std::cout << std::endl;

    std::cout << "Element at index 1: " << dq[1] << std::endl; // 随机访问，O(1)
    return 0;
}

1.4 `std::array` - 固定大小数组 (像一个固定大小的盒子)

核心概念: 固定大小的数组，内存连续。
类比: 就像一个你买来时就确定好大小的盒子，里面有多少个格子是固定的，不能增减。
底层实现: 类似于 C 风格数组，内存连续。
特性:
- 大小固定: 在编译时就确定了，运行时不能改变。
- 内存连续: 访问速度快，与 C 风格数组一样。
- 更安全: 提供 at() 方法进行边界检查，避免 C 风格数组越界访问的风险。
- STL 兼容: 可以使用 STL 算法。
适用场景: 需要固定大小的容器，性能要求高，或需要与 C API 交互。

实例:

#include <array>
#include <iostream>
#include <algorithm> // for std::sort

int main() {
    std::array<int, 5> fixed_numbers = {10, 5, 20, 15, 25}; // 大小固定为 5

    std::cout << "Array elements: ";
    for (int num : fixed_numbers) {
        std::cout << num << " "; // 10 5 20 15 25
    }
    std::cout << std::endl;

    std::sort(fixed_numbers.begin(), fixed_numbers.end()); // 可以使用 STL 算法

    std::cout << "Sorted array: ";
    for (int num : fixed_numbers) {
        std::cout << num << " "; // 5 10 15 20 25
    }
    std::cout << std::endl;

    // fixed_numbers.push_back(30); // 编译错误！std::array 大小固定
    return 0;
}

2. 关联式容器 (Associative Containers)

关联式容器不像序列式容器那样按顺序存储，而是根据元素的“键”来组织数据，并且通常是自动排序的。

2.1 `std::map` / `std::multimap` - 有序键值对 (像一个带索引的字典)

核心概念: 有序键值对存储。map 的键唯一，multimap 的键可重复。
类比: 想象一个字典，每个词（键 key）对应一个解释（值 value）。字典里的词是按字母顺序排列的。
- map 就像一个普通字典，每个词只有一个解释。
- multimap 就像一个特殊的字典，同一个词可能有多个不同的解释（例如，同一个英文单词在不同语境下有不同含义）。
底层实现: 红黑树 (Red-Black Tree)。
特性:
- 元素按 key 自动排序。
- 查找、插入、删除操作的时间复杂度为 O(log n)。
- map 的 key 不可修改，value 可修改。
- map 提供 operator[]，可以方便地通过键访问或插入值。multimap 没有 operator[]，因为一个键可能对应多个值。
适用场景: 需要根据键快速查找、插入、删除，且需要保持数据有序。
源码关键点: _M_insert_unique (map), _M_insert_equal (multimap), _Select1st (提取 key)。

实例:

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<std::string, int> word_counts; // 键是单词(string)，值是计数(int)
    word_counts["apple"] = 3; // 插入或更新
    word_counts["banana"] = 2;
    word_counts.insert({"orange", 5}); // 另一种插入方式

    std::cout << "Word counts (sorted by key):" << std::endl;
    for (const auto& pair : word_counts) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 输出会按字母顺序排列：apple: 3, banana: 2, orange: 5

    std::cout << "Count of apple: " << word_counts["apple"] << std::endl; // O(log n) 查找
    // std::cout << "Count of grape: " << word_counts["grape"] << std::endl; // 如果 grape 不存在，会自动插入 grape: 0

    std::multimap<int, std::string> student_scores; // 键是分数，值是学生姓名
    student_scores.insert({90, "Alice"});
    student_scores.insert({90, "Bob"}); // 分数相同，允许重复
    student_scores.insert({85, "Charlie"});

    std::cout << "Scores (sorted by score):" << std::endl;
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 输出会按分数排序：85: Charlie, 90: Alice, 90: Bob
    return 0;
}

2.2 `std::set` / `std::multiset` - 红黑树实现 (像一个自动排序的去重集合)

核心概念: 有序元素存储。set 的元素唯一，multiset 的元素可重复。
类比: 想象一个自动排序的集合，你往里面放东西，它会自动帮你排好序，并且如果放了重复的东西，它只会保留一个（set）或保留所有（multiset）。
底层实现: 红黑树 (Red-Black Tree)。
特性:
- 元素按自身值自动排序。
- 查找、插入、删除操作的时间复杂度为 O(log n)。
- 元素本身是 const 的，不可修改。
适用场景: 需要存储唯一（或可重复）的有序元素，并进行快速查找。

实例:

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

int main() {
    std::set<std::string> unique_words; // 存储不重复的单词
    unique_words.insert("hello");
    unique_words.insert("world");
    unique_words.insert("hello"); // 重复插入，会被忽略

    std::cout << "Unique words (sorted):" << std::endl;
    for (const auto& word : unique_words) {
        std::cout << word << std::endl; // hello, world (按字母序)
    }

    std::multiset<int> numbers_with_duplicates; // 存储可能重复的数字
    numbers_with_duplicates.insert(10);
    numbers_with_duplicates.insert(5);
    numbers_with_duplicates.insert(10); // 重复插入，会被保留

    std::cout << "Numbers with duplicates (sorted):" << std::endl;
    for (int num : numbers_with_duplicates) {
        std::cout << num << " "; // 5 10 10
    }
    std::cout << std::endl;
    return 0;
}

2.3 `std::unordered_map` / `std::unordered_multimap` - 哈希表实现 (像一个快速查找的电话簿)

核心概念: 无序键值对存储。unordered_map 的键唯一，unordered_multimap 的键可重复。
类比: 想象一个电话簿，你输入名字（键 key），它能飞快地告诉你对应的电话号码（值 value）。它不按名字排序，而是通过一种“魔法”（哈希函数）直接找到你要找的号码。
底层实现: 哈希表 (Hash Table)。
特性:
- 元素无序。
- 平均查找、插入、删除操作的时间复杂度为 O(1)。
- 最坏情况下（哈希冲突严重）为 O(n)。
- unordered_map 提供 operator[]，unordered_multimap 不提供。
适用场景: 需要极快的查找、插入、删除速度，且不关心元素顺序。
源码关键点: 哈希函数 (std::hash), 冲突解决机制 (链表法), _Hashtable_traits (控制唯一性、迭代器类型)。

实例:

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> fast_lookup;
    fast_lookup["apple"] = 3;
    fast_lookup["banana"] = 2;
    fast_lookup["orange"] = 5;

    std::cout << "Fast lookup for banana: " << fast_lookup["banana"] << std::endl; // 平均 O(1) 查找

    // 插入一个不存在的键，会自动创建并初始化值为0
    std::cout << "Lookup for grape (before insert): " << fast_lookup["grape"] << std::endl; // 0
    std::cout << "Size after potential insert: " << fast_lookup.size() << std::endl;

    return 0;
}

2.4 `std::unordered_set` / `std::unordered_multiset` - 哈希表实现 (像一个快速查找的集合)

核心概念: 无序元素存储。unordered_set 的元素唯一，unordered_multiset 的元素可重复。
类比: 想象一个快速查找的集合，你往里面扔东西，它能飞快地告诉你某个东西在不在里面。它也不关心顺序。
- unordered_set 就像一个快速查找的集合，不允许重复。
- unordered_multiset 就像一个快速查找的集合，允许重复。
底层实现: 哈希表 (Hash Table)。
特性:
- 元素无序。
- 平均查找、插入、删除操作的时间复杂度为 O(1)。
- 最坏情况下为 O(n)。
适用场景: 需要极快的查找、插入、删除速度，且不关心元素顺序，且只需要存储元素本身。

实例:

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> unique_numbers;
    unique_numbers.insert(10);
    unique_numbers.insert(5);
    unique_numbers.insert(10); // 重复插入，会被忽略

    if (unique_numbers.count(5)) { // 快速查找，平均 O(1)
        std::cout << "5 is in the set." << std::endl;
    }
    if (!unique_numbers.count(15)) {
        std::cout << "15 is not in the set." << std::endl;
    }
    return 0;
}

总结

STL 容器提供了丰富的数据结构选择，理解它们的底层实现和性能特点，能够帮助我们写出更高效、更健壮的代码。

序列容器适合按顺序访问和操作数据。
- vector: 像一个可伸缩的储物柜，适合末尾操作和快速随机访问。
- list: 像一条可随意增减环节的手链，适合任意位置的插入删除。
- deque: 像一个两头都能进出的队列，适合两端操作和随机访问。
- array: 像一个固定大小的盒子，性能高，大小固定。
关联容器适合根据键或值进行快速查找和管理。
- map/multimap: 像带索引的字典，有序，基于红黑树。
- set/multiset: 像自动排序的去重集合，有序，基于红黑树。
- unordered_map/unordered_multimap: 像快速查找的电话簿，无序，基于哈希表。
- unordered_set/unordered_multiset: 像快速查找的集合，无序，基于哈希表。
选择容器时，需要考虑:
- 访问方式: 是否需要随机访问？ (vector, deque, array 支持；list 不支持)
- 增删操作: 插入/删除操作的频率和位置？ (list 在任意位置高效；vector 末尾高效；deque 两端高效；map/set O(log n)；unordered_map/unordered_set 平均 O(1))
- 顺序要求: 是否需要元素有序？ (map/set 有序；vector/list/deque 顺序由插入决定；unordered_map/unordered_set 无序)
- 唯一性: 键/元素是否唯一？ (使用 map/set/unordered_map/unordered_set；若允许重复，则用 multi 版本)
- 性能: 对速度要求极高且不关心顺序，优先考虑 unordered_ 系列；对速度要求高且需要有序，考虑 map/set；需要固定大小且性能极致，考虑 array。

这只是对 STL 容器的初步学习笔记，深入理解还需要结合源码和实际编程练习。

STL容器学习笔记 (附类比与实例)

导语

1. 序列式容器 (Sequence Containers)

1.1 std::vector - 动态数组 (像一个可伸缩的储物柜)

1.2 std::list - 双向环形链表 (像一条可以随意增减环节的手链)

1.3 std::deque - 双端队列 (像一个可以两头进出的队列)

1.4 std::array - 固定大小数组 (像一个固定大小的盒子)

2. 关联式容器 (Associative Containers)

2.1 std::map / std::multimap - 有序键值对 (像一个带索引的字典)

2.2 std::set / std::multiset - 红黑树实现 (像一个自动排序的去重集合)

2.3 std::unordered_map / std::unordered_multimap - 哈希表实现 (像一个快速查找的电话簿)

2.4 std::unordered_set / std::unordered_multiset - 哈希表实现 (像一个快速查找的集合)

总结