C++常见STL使用

需要注意的是，Python 是动态类型语言，一个列表里可以同时放数字和字符串；而 C++ 是静态类型语言，在使用这些数据结构时，必须提前指定里面存储的数据类型（通过泛型 <Type> 来实现）。

以下是这 8 种数据结构在 C++ 中的对应实现及代码示例：

1. 列表 (List) ➡️ C++ std::vector

• 对应关系：Python 的 list 在 C++ 中最完美的替代品是 std::vector（动态数组）。C++ 中虽然也有 std::list，但那是双向链表，由于内存不连续，查询速度慢，日常开发中远不如 vector 常用。

• 头文件：#include <vector>

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 定义与初始化 (必须指定类型为 int)
    vector<int> my_list = {10, 20, 30};

    // 追加元素 (相当于 append)
    my_list.push_back(40);

    // 插入元素 (在索引 1 的位置插入 15)
    my_list.insert(my_list.begin() + 1, 15);

    // 访问与修改
    cout << my_list[0] << endl; // 输出: 10
    my_list[0] = 99;            // 修改第一个元素

    // 遍历
    for (int item : my_list) {
        cout << item << " ";
    }
    return 0;
}

2. 字典 (Dictionary) ➡️ C++ std::unordered_map / std::map

• 对应关系：Python 底层基于哈希表，对应的 C++ 实现是 std::unordered_map（无序，查询$O(1)$）。C++ 还有一个 std::map（基于红黑树，按键排序，查询$O(\log N)$）。

• 头文件：#include <unordered_map>

C++

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

using namespace std;

int main() {
    // 定义与初始化 <键类型, 值类型>
    unordered_map<string, int> student = {
        {"Alice", 20},
        {"Bob", 22}
    };

    // 访问元素
    cout << student["Alice"] << endl; 

    // 安全访问 (相当于 python 的 get)
    if (student.count("Charlie") > 0) {
        cout << student["Charlie"] << endl;
    }

    // 增加或修改
    student["Alice"] = 21;       // 修改
    student["David"] = 19;       // 新增

    // 遍历 (C++11 语法)
    for (const auto& pair : student) {
        cout << pair.first << ": " << pair.second << endl;
    }
    // C++17 结构化绑定语法（更像 Python）
    // for (auto const& [key, value] : student) { ... }
    return 0;
}

3. 集合 (Set) ➡️ C++ std::unordered_set / std::set

• 对应关系：同字典一样，Python 的 set 对应 C++ 的 std::unordered_set（哈希表去重）。

• 头文件：#include <unordered_set>

C++

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    // 定义与自动去重
    unordered_set<int> my_set = {1, 2, 2, 3, 4, 4};

    // 添加与删除
    my_set.insert(5);
    my_set.erase(1); // 删除 1

    // 检查元素是否存在
    if (my_set.count(3) > 0) {
        cout << "3 is in the set" << endl;
    }
    return 0;
}
// 注意：C++ 的 set 没有重载 &, | 操作符直接求交并集，需要用到 <algorithm> 里的 std::set_intersection 等函数。

4. 字符串 (String) ➡️ C++ std::string

• 重大区别：Python 的字符串是不可变的，而 C++ 的 std::string 是可变的（你可以直接修改原字符串中的某个字符 text[0] = 'a'，这在 Python 中是报错的）。

• 头文件：#include <string>

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    string text = "C++ is awesome";

    // 索引与修改 (可直接修改)
    cout << text[0] << endl; // 输出: C
    text[0] = 'c';           // 变成 "c++ is awesome"

    // 切片 (相当于 text[0:3]) -> substr(起始位置, 长度)
    cout << text.substr(0, 3) << endl; // 输出: c++

    // 拼接
    text += "!!!";
    return 0;
}

5. 栈 (Stack) ➡️ C++ std::stack

• 对应关系：C++ 提供了专门的容器适配器 std::stack。

• 头文件：#include <stack>

C++

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    stack<string> s;

    // 压栈
    s.push("A");
    s.push("B");
    s.push("C");

    // 查看栈顶元素 (但不移除)
    cout << s.top() << endl; // 输出: C

    // 出栈 (注意：C++ 的 pop() 不返回值，只负责弹出)
    s.pop();

    cout << s.top() << endl; // 输出: B
    return 0;
}

6. 队列 (Queue) ➡️ C++ std::queue

• 对应关系：相当于 Python 的 deque 限制了只能单向进出。

• 头文件：#include <queue>

C++

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    queue<string> q;

    // 入队 (加在尾部)
    q.push("Alice");
    q.push("Bob");

    // 查看队首元素
    cout << q.front() << endl; // 输出: Alice

    // 出队 (从头部弹出，不返回值)
    q.pop();

    cout << q.front() << endl; // 输出: Bob
    return 0;
}

7. 堆 (Heap) ➡️ C++ std::priority_queue

• 对应关系：C++ 中叫做优先队列。

• 重大区别：Python 的 heapq 默认是小顶堆（最小的先出），而 C++ 的 priority_queue 默认是大顶堆（最大的先出）。

• 头文件：#include <queue>

C++

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

using namespace std;

int main() {
    // 默认是大顶堆 (Max-Heap)
    priority_queue<int> max_pq;
    max_pq.push(5);
    max_pq.push(9);
    max_pq.push(1);
    cout << max_pq.top() << endl; // 输出: 9 (最大的)

    // 如果要改成跟 Python 一样的小顶堆 (Min-Heap)，写法比较长：
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(5);
    min_pq.push(9);
    min_pq.push(1);
    cout << min_pq.top() << endl; // 输出: 1 (最小的)
    
    // 弹出堆顶
    min_pq.pop(); 
    return 0;
}

8. 元组 (Tuple) ➡️ C++ std::tuple / std::pair

• 对应关系：如果只有两个元素，C++ 程序员通常使用更简单的 std::pair；如果是多个元素，则使用 C++11 引入的 std::tuple。

• 头文件：#include <tuple> 或 #include <utility> (针对 pair)

C++

#include <iostream>
#include <tuple>
#include <utility> // for std::pair
#include <string>

using namespace std;

int main() {
    // 1. 使用 Pair (仅限两个元素)
    pair<int, string> p = {10, "Apple"};
    cout << p.first << ", " << p.second << endl;

    // 2. 使用 Tuple (任意数量元素)
    tuple<int, double, string> t = make_tuple(1, 3.14, "hello");

    // 访问 Tuple 元素 (需要使用 std::get<索引>)
    cout << get<0>(t) << endl; // 输出: 1

    // C++17 的解包 (Structured Binding，极其类似 Python)
    auto [x, y, z] = t;
    cout << z << endl; // 输出: hello

    return 0;
}
```</Type>

9. 数组容器 ➡️ C++ std::array

• 特点：固定大小的数组。它封装了 C 风格的裸数组（如 int arr[5];），提供了 STL 的迭代器接口和更安全的边界检查（通过 .at() 方法）。由于大小固定，它的元素是在栈（Stack）上分配的，性能极高，没有动态内存分配的开销。

• 适用场景：当你知道数据量是固定的，且永远不会改变时使用，性能优于 std::vector。

• 头文件：#include <array>

C++

#include <iostream>
#include <array>

using namespace std;

int main() {
    // 定义一个大小为 5 的整型数组
    array<int, 5> arr = {1, 2, 3, 4, 5};

    // 访问元素
    cout << arr[0] << endl;       // 正常访问，越界不报错（行为未定义）
    cout << arr.at(1) << endl;    // 安全访问，越界抛出 std::out_of_range 异常

    // 常用操作
    cout << arr.size() << endl;   // 输出: 5
    cout << arr.front() << endl;  // 输出: 1
    cout << arr.back() << endl;   // 输出: 5

    // 遍历
    for(int val : arr) {
        cout << val << " ";
    }
    return 0;
}

10. 正向链表 ➡️ C++ std::forward_list

• 特点：单向链表。它比双向链表（std::list）更轻量级，因为每个节点只保留指向下一个节点的指针。这意味着你只能从头向后遍历，不能向前遍历。它没有提供 .size() 方法（因为计算大小需要遍历一遍，复杂度是$O(N)$，STL 设计者为了强调效率而故意去掉了这个接口）。

• 适用场景：对内存占用极其敏感，且只需要单向遍历和在头部（或已知节点后）插入/删除的场景。

• 头文件：#include <forward_list>

C++

#include <iostream>
#include <forward_list>

using namespace std;

int main() {
    forward_list<int> flist = {10, 20, 30};

    // 在头部插入元素 (时间复杂度 O(1))
    flist.push_front(5);

    // 在指定位置后插入元素 (由于是单向，只能在某个元素 "之后" 插入)
    auto it = flist.begin();
    flist.insert_after(it, 15); // 在第一个元素后插入 15

    // 遍历
    for (int val : flist) {
        cout << val << " "; // 输出: 5 15 10 20 30 
    }
    return 0;
}

11. 位集合 ➡️ C++ std::bitset

• 特点：专门用于存储和操作位（bit）的定长容器。相当于一个只能存 0 和 1 的超级数组，但它的底层做了极其优秀的内存压缩（1个字节存 8 个布尔值）。它支持所有位运算符（&, |, ^, ~, <<, >>）。

• 适用场景：状态压缩、位运算优化、布隆过滤器（Bloom Filter）的底层实现、处理大量的真/假状态。

• 头文件：#include <bitset>

C++

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    // 定义一个 8 位的位集合，初始化为二进制 1010
    bitset<8> b1(string("1010")); 
    // 或者用整数初始化
    bitset<8> b2(12); // 12 的二进制是 00001100

    // 访问特定位
    cout << b1[1] << endl; // 输出: 1 (注意，索引是从右往左数的，即第 1 位)

    // 常用方法
    cout << b1.count() << endl; // 输出: 2 (统计二进制中 1 的个数)
    cout << b1.any() << endl;   // 输出: 1 (是否有任意一位是 1)
    cout << b1.none() << endl;  // 输出: 0 (是否全为 0)

    // 位运算
    bitset<8> b3 = b1 & b2;     // 按位与
    cout << b3 << endl;         // 输出: 00001000

    // 翻转
    b1.flip();                  // 全部取反
    cout << b1 << endl;         // 输出: 11110101

    return 0;
}

12. 多重集合 / 多重字典 ➡️ C++ std::multiset / std::multimap

• 特点：它们分别是 std::set 和 std::map 的变体。唯一的区别是：它们允许键（Key）重复。底层同样基于红黑树，是有序的。

• 适用场景：

  • multiset：经常用于作为有序的数组，且需要频繁插入/删除/求最值（比优先队列更灵活，因为可以删除任意元素）。

  • multimap：用于一对多的映射关系。

• 头文件：#include <set> 或 #include <map>

C++

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> mset = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // 插入元素
    mset.insert(1); // 允许重复插入

    // 统计某个元素出现的次数
    cout << mset.count(1) << endl; // 输出: 3

    // 遍历 (由于底层是红黑树，输出是有序的)
    for (int val : mset) {
        cout << val << " "; // 输出: 1 1 1 2 3 4 5 5 6 9 
    }
    cout << endl;

    // ⚠️ 陷阱：删除操作
    // 如果直接 erase(1)，会把所有等于 1 的元素全删掉！
    // mset.erase(1); 
    
    // 如果只想删掉一个 1，需要用迭代器：
    auto it = mset.find(1); // find 会找到第一个匹配的元素
    if (it != mset.end()) {
        mset.erase(it);     // 只删掉这一个迭代器指向的元素
    }

    return 0;
}