C++ STL 容器概览

标准模板库（STL）把常用数据结构做成容器：已经用过的 vector 是动态数组。还需要按名字查分数时用 map，需要去重且保持有序时用 set。容器负责存元素和管理内存；算法通过迭代器读写这些元素，所以 std::sort 不必为每种容器各写一份。本节在 vector 之上概览序列容器、关联容器和选用思路。

序列容器

默认优先 vector：连续存储，下标访问快，尾部 push_back 摊还为常数时间，用法见vector 容器。其它序列容器只在明确需要时再换：

map 与 set

map 按键存放键值对，键唯一，遍历时键有序。scores["Ada"] = 95 若键不存在会插入再赋值；只读时宜用 at 或 find，避免无意插入。set 只存键，重复元素会被丢掉，下面 1 只出现一次：

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

int main() {
    std::map<std::string, int> scores;
    scores["Ada"] = 95;
    scores["Lin"] = 88;

    std::set<int> ids = {3, 1, 2, 1};  // 1 只保留一次，遍历按升序
    for (int id : ids) {
        std::cout << id << " ";
    }
    std::cout << "\nAda: " << scores.at("Ada") << std::endl;
    return 0;
}

输出：

1 2 3
Ada: 95

二者底层是有序树，单次查找大约与元素个数的对数成正比。

无序容器与适配器

unordered_map / unordered_set（C++11）用哈希，平均查找更快，但遍历顺序不稳定；需要按键排序时仍用 map / set。适配器在已有容器上限制接口：stack 后进先出，queue 先进先出，priority_queue 每次取出当前最大（或按比较器指定的）元素。适配器没有 begin / end，不能用范围 for 遍历。

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    std::cout << s.top() << "\n";  // 栈顶是后放进去的 2
    s.pop();
    std::cout << s.top() << "\n";
    return 0;
}

输出：

2
1

选用简表

本节概括了常用 STL 容器。下一节介绍STL 算法概览：sort、find 等与容器配合。