CPP学习笔记—标准模板库（STL）中的容器

一、什么是容器？为什么它如此重要？

简单来说，C++ 容器是用来存储和管理一组对象的类模板。它们就像是工具箱里不同种类的收纳盒：有的适合快速取放（像数组），有的适合保持物品有序（像分类文件柜），还有的适合快速查找（像带索引的卡片盒）。

使用 STL 容器的好处是巨大的：

1. 代码更简洁：你无需从零开始实现链表、哈希表等复杂数据结构。
2. 性能更优越：STL 容器经过了高度优化，性能通常比手写的要好。
3. 代码更安全：它们处理了内存管理的细节，减少了内存泄漏和越界访问的风险。
4. 互操作性强：所有容器都遵循一套统一的接口（如 begin(), end(), size()），可以与 STL 的迭代器和算法无缝协作，威力倍增。

---

二、容器的分类与概览

C++ 的容器主要分为四大类，分别是序列容器、关联容器、无序关联容器和容器适配器。

类别	容器	特点
序列容器	vector, deque, list, array	元素按线性顺序排列，可通过位置访问。
关联容器	map, set, multimap, multiset	元素根据键值自动排序，查找速度快 (O(log N))。
无序关联容器	unordered_map, unordered_set, …	元素通过哈希存储，无序，查找速度极快 (平均 O(1))。
容器适配器	stack, queue, priority_queue	提供特定接口（LIFO/FIFO），是对其他容器的封装。

---

三、序列容器 (Sequence Containers)

序列容器中的元素按严格的线性序列排序，你可以通过元素在序列中的位置来访问它们。

1. std::vector — 动态数组

vector 是最基本也是最常用的容器，是你的“默认选项”。

• 头文件: #include <vector>
• 本质: 一块在堆上分配的连续内存空间。当空间不足时，会自动重新分配一块更大的内存，并将原有元素移动过去。
• 复杂度:
  • 随机访问 (通过 [] 或 at()): O(1)
  • 尾部添加/删除 (push_back, pop_back): 均摊 O(1)
  • 中间或头部添加/删除 (insert, erase): O(N)
• 适用场景:
  • 需要快速随机访问元素。
  • 主要在容器末尾进行添加或删除操作。
  • 在大多数情况下，当你需要一个动态数组时，vector 都是最佳选择。

示例代码:

#include <iostream>
#include <vector>
#include <string>

void print_vector(const std::string& title, const std::vector<int>& v) {
    std::cout << title << ":\t[ ";
    for (int i : v) std::cout << i << " ";
    std::cout << "], size=" << v.size() << ", capacity=" << v.capacity() << std::endl;
}

int main() {
    std::vector<int> vec;
    std::vector vec2 = {1, 2, 3, 4, 5};
    std::vector<int> vec3(5);   //  初始化5个元素的vector，默认值为0
    std::vector<int> vec4(5, 2);    //  初始化5个元素的vector，默认值为2
    print_vector("Initial", vec);
    print_vector("Initial vec2", vec2);
    print_vector("Initial vec3", vec3);
    print_vector("Initial vec4", vec4);

    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    print_vector("After push_back", vec);

    // 随机访问
    std::cout << "Element at index 1: " << vec.at(1) << std::endl;

    // 在中间插入
    vec.insert(vec.begin() + 1, 15);
    print_vector("After insert", vec);

    // 删除元素
    vec.erase(vec.begin() + 2);
    print_vector("After erase", vec);

    // 删除一个区间的元素
    vec.erase(vec.begin() + 2, vec.end()); // 删除索引2到末尾的元素
    print_vector("After erase from index 2 to end", vec);

    // 弹出最后一个元素
    vec.pop_back();
    print_vector("After pop_back", vec);
}

/*
输出结果：
Initial:        [ ], size=0, capacity=0
After push_back:        [ 10 20 30 ], size=3, capacity=4
Element at index 1: 20
After insert:   [ 10 15 20 30 ], size=4, capacity=4
After erase:    [ 10 15 30 ], size=3, capacity=4
After erase from index 2 to end:        [ 10 15 ], size=2, capacity=4
After pop_back: [ 10 ], size=1, capacity=4
*/

2. std::deque — 双端队列

deque (double-ended queue) 是一个在两端操作都非常高效的序列。

• 头文件: #include <deque>
• 本质: 由多个独立的小内存块（chunks）和一箇中控的映射结构组成，非连续内存。
• 复杂度:
  • 随机访问: O(1) (但比 vector 慢，需要两次指针解引用)
  • 头部和尾部添加/删除 (push_front, pop_front, push_back, pop_back): O(1)
  • 中间添加/删除: O(N)
• 适用场景:
  • 需要在容器的两端进行频繁的插入和删除操作。
  • 例如，实现一个任务队列，既可以从队首取任务，也可以在队尾或队首添加新任务。

示例代码:

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

void print_deque(const std::string& title, const std::deque<int>& d) {
    std::cout << title << ":\t[ ";
    for (int i : d) std::cout << i << " ";
    std::cout << "], size=" << d.size() << std::endl;
}

int main() {
    std::deque<int> deq = {10, 20, 30};
    print_deque("Initial", deq);

    deq.push_back(40);
    print_deque("After push_back(40)", deq);

    deq.push_front(5);
    print_deque("After push_front(5)", deq);

    deq.pop_front();
    print_deque("After pop_front()", deq);
}

/*
输出结果：
Initial:        [ 10 20 30 ], size=3
After push_back(40):    [ 10 20 30 40 ], size=4
After push_front(5):    [ 5 10 20 30 40 ], size=5
After pop_front():      [ 10 20 30 40 ], size=4
*/

3. std::list — 双向链表

list 专为在任意位置进行快速插入和删除而设计。

• 头文件: #include <list>
• 本质: 一个双向链表，每个节点包含元素值以及指向前一个和后一个节点的指针。
• 复杂度:
  • 随机访问: O(N) (不支持 [] 或 at())
  • 任意位置添加/删除: O(1) (前提是已有指向该位置的迭代器)
• 适用场景:
  • 当程序需要对序列进行大量、频繁的非头部非尾部的插入和删除操作时。
  • 对元素的随机访问需求不高。

示例代码:

#include <iostream>
#include <list>
#include <string>

void print_list(const std::string& title, const std::list<int>& l) {
    std::cout << title << ":\t[ ";
    for (int i : l) std::cout << i << " ";
    std::cout << "], size=" << l.size() << std::endl;
}

int main() {
    std::list<int> myList = {10, 20, 40};
    print_list("Initial", myList);

    auto it = myList.begin();
    ++it; // it 指向 20
    myList.insert(it, 15); // 在 20 前插入 15
    print_list("After insert", myList);

    it = myList.begin();
    ++it; ++it; // it 指向 20
    myList.erase(it);
    print_list("After erase", myList);
}

/*
输出结果：
Initial:        [ 10 20 40 ], size=3
After insert:   [ 10 15 20 40 ], size=4
After erase:    [ 10 15 40 ], size=3
*/

4. std::array — 固定大小数组

std::array 是对 C 风格静态数组的轻量级、类型安全的封装。

• 头文件: #include <array>
• 本质: 一块在栈上或静态存储区分配的固定大小的连续内存空间。它的大小在编译时就必须确定，之后不能改变。它本质上就是对 C 语言数组 T arr[N] 的一个包装。
• 复杂度:
  • 随机访问 (通过 [] 或 at()): O(1)
  • 不支持任何改变其大小的操作（如 push_back, insert, erase 等）。
• 适用场景:
  • 当你需要一个大小在编译时就已知的固定长度数组时。
  • 相比 C 风格数组，std::array 提供了容器的通用接口（如 size(), begin(), end(), empty()），可以无缝地与 STL 算法（如 std::sort）配合使用。
  • 它不会退化为指针，作为函数参数传递时会传递整个数组（或其引用），保留了大小信息，更加安全。

示例代码:

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

// 函数可以安全地接收 std::array，并知道其大小
void print_array(const std::array<int, 5>& arr) {
    std::cout << "Array contents: [ ";
    for (int element : arr) {
        std::cout << element << " ";
    }
    std::cout << "], size=" << arr.size() << std::endl;
}

int main() {
    // 声明一个包含 5 个整数的 array
    std::array<int, 5> myArray = {30, 10, 50, 20, 40};

    std::cout << "Initial state:" << std::endl;
    print_array(myArray);

    // 随机访问
    myArray[0] = 35;
    std::cout << "Element at index 2: " << myArray.at(2) << std::endl;

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

    std::cout << "\nAfter sorting:" << std::endl;
    print_array(myArray);

    // 填充所有元素为 0
    myArray.fill(0);
    std::cout << "\nAfter filling with 0:" << std::endl;
    print_array(myArray);

    // 编译错误示例：
    // myArray.push_back(100); // 错误！std::array 没有 push_back 方法
    // std::array<int, some_runtime_variable> runtimeArray; // 错误！大小必须是编译时常量
}

/*
输出结果：
Initial state:
Array contents: [ 30 10 50 20 40 ], size=5
Element at index 2: 50

After sorting:
Array contents: [ 10 20 35 40 50 ], size=5

After filling with 0:
Array contents: [ 0 0 0 0 0 ], size=5
*/

---

四、关联容器 (Associative Containers)

关联容器中的元素根据它们的键自动排序，提供了高效的查找能力。

1. std::map — 有序键值对

• 头文件: #include <map>
• 本质: 通常是红黑树 (一种自平衡二叉搜索树)。存储 std::pair<const Key, T> 类型的键值对，键是唯一的，并根据键自动排序。
• 复杂度:
  • 插入、删除、查找 (insert, erase, find, count): O(log N)
• 适用场景:
  • 需要存储唯一的键值对，并希望它们根据键自动排序。
  • 需要高效地根据键查找、更新或删除对应的值。
  • 例如，存储字典、配置文件、学生ID和姓名的映射等。

示例代码:

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

int main() {
    std::map<std::string, int> student_ages;

    student_ages["Alice"] = 21;
    student_ages.insert(std::make_pair("Bob", 22));
    student_ages.emplace("Charlie", 20);

    std::cout << "Bob's age is: " << student_ages.at("Bob") << std::endl;

    // 遍历 map，元素会按键的字母顺序输出
    std::cout << "All students:\n";
    for (const auto& pair : student_ages) {
        std::cout << " - " << pair.first << " is " << pair.second << " years old.\n";
    }

    student_ages.erase("Alice");
    std::cout << "Number of students after erasing Alice: " << student_ages.size() << std::endl;
}

/*
输出结果：
Bob's age is: 22
All students:
 - Alice is 21 years old.
 - Bob is 22 years old.
 - Charlie is 20 years old.
Number of students after erasing Alice: 2
*/

2. std::set — 有序唯一集合

• 头文件: #include <set>
• 本质: 同样是红黑树。只存储键，没有值。可以看作是一种只有键的 map。元素是唯一的，并自动排序。
• 复杂度:
  • 插入、删除、查找: O(log N)
• 适用场景:
  • 需要存储一组唯一的元素，并保持它们有序。
  • 需要快速判断一个元素是否存在于集合中。
  • 例如，存储不重复的用户ID、统计文章中出现的不同单词等。

示例代码:

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

int main() {
    std::set<std::string> unique_words;

    unique_words.insert("hello");
    unique_words.insert("world");
    unique_words.insert("hello"); // 重复插入会被忽略

    std::cout << "Unique words count: " << unique_words.size() << std::endl;

    if (unique_words.count("world")) {
        std::cout << "'world' is in the set." << std::endl;
    }

    // 遍历 set，元素会按字母顺序输出
    std::cout << "Words in set:\n";
    for (const auto& word : unique_words) {
        std::cout << " - " << word << std::endl;
    }
}

/*
输出结果：
Unique words count: 2
'world' is in the set.
Words in set:
 - hello
 - world
*/

3. std::multimap — 有序多重映射

在 std::map 和 std::set 的基础上，STL 提供了它们的多键版本，允许存储重复的键。multimap 是 map 的变体，它允许存储具有相同键的多个键值对。

• 头文件: #include <map>
• 本质: 与 std::map 一样，通常是红黑树。它存储的也是 std::pair<const Key, T>，但允许键 (Key) 重复。所有元素仍然会根据键自动排序。
• 复杂度:
  • 插入 (insert): O(log N)
  • 删除 (erase): O(log N + k)，其中 k 是被删除的元素数量。
  • 查找 (find, count, equal_range): O(log N)
• 适用场景:
  • 需要表示**“一对多”**的关系。
  • 例如，一个字典中一个单词可以有多个释义；一个学生可以注册多门课程；一个作者可以有多本著作。在这些场景下，键（单词、学生、作者）是相同的，但值（释义、课程、著作）不同。

示例代码:

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

int main() {
    std::multimap<std::string, std::string> student_courses;

    // 添加选课记录，Alice 选了三门课
    student_courses.insert({"Alice", "Math101"});
    student_courses.insert({"Bob", "CS101"});
    student_courses.insert({"Alice", "Physics201"});
    student_courses.insert({"Charlie", "History101"});
    student_courses.insert({"Alice", "Chem101"});

    // 查询某个键的数量
    std::cout << "Alice is enrolled in " << student_courses.count("Alice") << " courses." << std::endl;

    // 查找并打印 Alice 的所有课程
    // 使用 equal_range 是最高效且最标准的方式
    std::cout << "\nCourses for Alice:" << std::endl;
    auto range = student_courses.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << " - " << it->second << std::endl;
    }

    // 遍历整个 multimap，键相同的元素会相邻出现
    std::cout << "\nAll enrollments:" << std::endl;
    for (const auto& pair : student_courses) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }
}

/*
输出结果：
Alice is enrolled in 3 courses.

Courses for Alice:
 - Math101
 - Physics201
 - Chem101

All enrollments:
Alice -> Math101
Alice -> Physics201
Alice -> Chem101
Bob -> CS101
Charlie -> History101
*/

4. std::multiset — 有序多重集合

multiset 是 set 的变体，它允许存储多个相同的元素。

• 头文件: #include <set>
• 本质: 与 std::set 一样，是红黑树。它允许存储重复的元素，并且所有元素都会自动排序。
• 复杂度:
  • 插入 (insert): O(log N)
  • 删除 (erase): O(log N + k)，其中 k 是被删除的元素数量。
  • 查找 (find, count): O(log N)
• 适用场景:
  • 需要存储一个可以有重复值的有序集合。
  • 例如，存储一场比赛的所有得分（可能会有同分）；对一组数字进行排序并保留所有重复项；或者需要快速统计集合中某个特定值的出现次数。

示例代码:

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

void print_multiset(const std::string& title, const std::multiset<int>& ms) {
    std::cout << title << ":\t[ ";
    for (int score : ms) {
        std::cout << score << " ";
    }
    std::cout << "]" << std::endl;
}

int main() {
    std::multiset<int> scores;

    scores.insert(88);
    scores.insert(95);
    scores.insert(73);
    scores.insert(88); // 允许插入重复的 88
    scores.insert(95);

    print_multiset("All scores (sorted)", scores);

    // 查询某个分数的数量
    int score_to_find = 88;
    std::cout << "The score " << score_to_find << " appears "
              << scores.count(score_to_find) << " times." << std::endl;

    // 删除所有等于 95 的分数
    scores.erase(95);
    print_multiset("After erasing all 95s", scores);
}

/*
输出结果：
All scores (sorted):    [ 73 88 88 95 95 ]
The score 88 appears 2 times.
After erasing all 95s:  [ 73 88 88 ]
*/

---

五、无序关联容器 (Unordered Associative Containers)

C++11 引入，基于哈希表实现，提供平均常数时间的查找性能，但元素无序。

1. std::unordered_map — 哈希映射

• 头文件: #include <unordered_map>
• 本质: 哈希表。存储唯一的键值对，但元素之间没有特定的顺序，其存储位置由键的哈希值决定。
• 复杂度:
  • 插入、删除、查找: 平均 O(1), 最坏 O(N) (哈希冲突严重时)
• 适用场景:
  • 当你需要 map 的功能（键值对存储和快速查找），但不关心元素的顺序时。
  • 在性能至关重要的场景下，它通常是比 map 更快的选择。

示例代码:

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

int main() {
    std::unordered_map<std::string, std::string> capital_cities;

    capital_cities["China"] = "Beijing";
    capital_cities["France"] = "Paris";
    capital_cities.emplace("Japan", "Tokyo");

    std::cout << "The capital of France is: " << capital_cities["France"] << std::endl;

    // 遍历顺序是不确定的
    std::cout << "All entries:\n";
    for (const auto& pair : capital_cities) {
        std::cout << " - " << pair.first << ": " << pair.second << std::endl;
    }
}

/*
输出结果：
The capital of France is: Paris
All entries:
 - Japan: Tokyo
 - France: Paris
 - China: Beijing
*/

2. std::unordered_set — 哈希集合

• 头文件: #include <unordered_set>
• 本质: 哈希表。存储唯一的元素，无序。
• 复杂度:
  • 插入、删除、查找: 平均 O(1), 最坏 O(N)
• 适用场景:
  • 需要快速地判断一个元素是否存在于一个集合中，且完全不关心顺序。
  • 例如，用作访问记录，快速检查某个IP地址今天是否已经访问过。

示例代码:

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<int> visited_ids;

    visited_ids.insert(101);
    visited_ids.insert(205);
    visited_ids.insert(101); // 再次插入，被忽略

    if (visited_ids.find(205) != visited_ids.end()) {
        std::cout << "ID 205 has been visited." << std::endl;
    }

    std::cout << "Total unique visited IDs: " << visited_ids.size() << std::endl;
}

/*
输出结果：
ID 205 has been visited.
Total unique visited IDs: 2
*/

---

六、容器适配器 (Container Adapters)

它们不是独立的容器，而是对现有序列容器（默认为 std::deque）的接口进行封装，以提供特定的行为模式。

1. std::stack — 栈

• 头文件: #include <stack>
• 本质: 封装了其他容器（默认 std::deque）的后进先出 (LIFO) 接口。
• 复杂度:
  • push, pop, top: O(1) (依赖于底层容器的 push_back, pop_back, back 操作)
• 适用场景:
  • 需要后进先出行为的任何地方。
  • 例如，函数调用栈、括号匹配、表达式求值等。

示例代码:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << "Top element: " << s.top() << std::endl; // 3
    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl; // 2

    std::cout << "Stack is " << (s.empty() ? "empty" : "not empty") << std::endl;
}

/*
输出结果：
Top element: 3
Top element after pop: 2
Stack is not empty
*/

2. std::queue — 队列

• 头文件: #include <queue>
• 本质: 封装了其他容器（默认 std::deque）的先进先出 (FIFO) 接口。
• 复杂度:
  • push, pop, front, back: O(1) (依赖于底层容器的 push_back, pop_front, front, back 操作)
• 适用场景:
  • 需要先进先出行为的任何地方。
  • 例如，任务队列、广度优先搜索 (BFS)、打印机缓冲池等。

示例代码:

#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> q;
    q.push("First");
    q.push("Second");
    q.push("Third");

    std::cout << "Front of queue: " << q.front() << std::endl; // First
    q.pop();
    std::cout << "Front after pop: " << q.front() << std::endl; // Second
}

/*
输出结果：
Front of queue: First
Front after pop: Second
*/

3. std::priority_queue — 优先队列

• 头文件: #include <queue>
• 本质: 封装了其他容器（默认 std::vector）并使用堆 (heap) 算法来维护的结构。每次取出的都是当前队列中优先级最高的元素。
• 复杂度:
  • push: O(log N)
  • pop: O(log N)
  • top: O(1)
• 适用场景:
  • 需要不断处理当前集合中最大（或最小）的元素。
  • 例如，事件调度、Dijkstra算法、A*搜索算法等。

示例代码 (默认最大堆):

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // for std::greater

int main() {
    // 最大堆 (默认)
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(100);
    max_heap.push(20);
    std::cout << "Max element: " << max_heap.top() << std::endl; // 100

    // 最小堆 (需要提供比较函数)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(100);
    min_heap.push(20);
    std::cout << "Min element: " << min_heap.top() << std::endl; // 20
}

/*
输出结果：
Max element: 100
Min element: 20
*/