C++ STL 标准模板库

STL(Standard Template Library)是 C++ 标准库的核心——一组高质量的容器(vector/map)、算法(sort/find)、迭代器(iterator)。学会 STL,你写 C++ 的效率会提升 10 倍——大部分数据结构和算法都不用自己实现了。

一、STL 三大件

STL 由三个核心组件构成:

• 容器(containers):存储数据的"箱子"。如 vector(动态数组)、map(键值对)、set(集合)。
• 算法(algorithms):操作数据的函数。如 sort(排序)、find(查找)、count(计数)。
• 迭代器(iterators):连接容器和算法的"桥梁",类似指针,用于遍历容器。

设计哲学:算法不直接操作容器,而是通过迭代器。这样 sort 既能排序 vector,也能排序 list(部分),还能排序原生数组。

二、vector:动态数组(最常用)

vector 是 STL 中使用频率最高的容器,功能类似 Python 的 list:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // vector:动态数组,自动扩容,STL 最常用的容器
    vector<int> v1;                      // 空 vector
    vector<int> v2(5);                   // 5 个 0
    vector<int> v3(5, 7);                // 5 个 7
    vector<int> v4 = {1, 2, 3, 4, 5};    // 列表初始化(C++11)

    // 添加元素
    v1.push_back(10);                    // 尾部添加
    v1.push_back(20);
    v1.push_back(30);

    // 访问元素
    cout << v1[0] << endl;               // 10(不检查越界)
    cout << v1.at(1) << endl;            // 20(at 会检查越界,抛异常)
    cout << v1.front() << endl;          // 10(首元素)
    cout << v1.back() << endl;           // 30(尾元素)

    // 大小相关
    cout << v1.size() << endl;           // 3
    cout << v1.empty() << endl;          // 0(false)

    // 遍历
    for (int x : v1) cout << x << " ";   // 10 20 30
    cout << endl;

    // 删除
    v1.pop_back();                       // 删尾部
    v1.clear();                          // 清空
    return 0;
}

vector 的核心特点:

• 动态扩容:容量不够自动翻倍扩容,push_back 平均 O(1)。
• 连续内存:元素在内存中连续,缓存友好,随机访问 O(1)。
• 尾部操作快:push_back/pop_back 都是 O(1)。
• 中间/头部操作慢:insert/erase 在中间是 O(n),要移动元素。
• 知道大小:.size() O(1)(C 数组退化成指针后就没法知道大小了)。

记住:能用 vector 就用 vector。除非有特殊需求(频繁头插用 deque、频繁中间插删用 list),其他容器的复杂度优势往往抵不过 vector 的缓存友好性。

三、map:有序键值对

map 是 C++ 的"字典"/"哈希表"之一,提供 key-value 映射:

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    // map:红黑树实现,键自动排序,查找 O(log n)
    map<string, int> ages;
    ages["Alice"] = 20;
    ages["Bob"] = 25;
    ages["Carol"] = 22;

    // 插入/修改
    ages["Alice"] = 21;                  // 修改
    ages.insert({"Dave", 30});           // 插入

    // 查找
    cout << ages["Bob"] << endl;         // 25([] 不会找不到,会插入默认值)
    auto it = ages.find("Eve");          // find 返回迭代器
    if (it == ages.end()) {
        cout << "Eve not found" << endl;
    }

    // 遍历(按键排序)
    for (const auto& p : ages) {
        cout << p.first << " -> " << p.second << endl;
    }

    // unordered_map:哈希表实现,查找 O(1),不排序
    unordered_map<string, int> cache;
    cache["x"] = 1;
    cache["y"] = 2;
    cout << cache.size() << endl;        // 2
    return 0;
}

map vs unordered_map:

• map:红黑树实现,key 自动排序。查找/插入/删除 O(log n)。需要按 key 顺序遍历时用。
• unordered_map:哈希表实现,无序。查找/插入/删除平均 O(1)。纯查找场景首选,比 map 快几个数量级。
• [] 的坑:m["不存在的 key"] 会插入一个默认值!只想查询要用 m.find() 或 m.count()(C++20 有 m.contains())。

四、set:有序集合

set 类似数学里的"集合"——存一组不重复的元素,自动排序:

#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

int main() {
    // set:自动排序、去重的集合
    set<int> s = {5, 3, 1, 4, 1, 5};     // 重复元素被去重
    for (int x : s) cout << x << " ";
    cout << endl;                        // 1 3 4 5(排序+去重)

    // 插入/删除
    s.insert(2);
    s.erase(3);

    // 查找
    if (s.count(4)) {                    // count 返回 0 或 1
        cout << "found 4" << endl;
    }

    // unordered_set:哈希实现,更快但不排序
    unordered_set<int> us = {5, 3, 1, 4};
    cout << us.size() << endl;           // 4

    // 选择建议:
    // - 需要排序/范围查询:用 set/map(红黑树)
    // - 只判断存在/快速查找:用 unordered_set/unordered_map(哈希)
    return 0;
}

set 的常见用途:去重、判断元素是否存在、维护有序集合。需要去重时,set 是天然选择。

五、string:字符串

严格说 string 不算 STL,但日常用得最多:

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string s = "Hello, World!";

    cout << s.length() << endl;          // 13
    cout << s.substr(0, 5) << endl;      // Hello(从 0 开始 5 个字符)
    cout << s.find("World") << endl;     // 7(找到返回下标)
    cout << (s.find("xyz") == string::npos) << endl;  // 1(找不到)

    // 拼接
    string s1 = "abc";
    s1 += "def";
    s1 = s1 + "ghi";
    cout << s1 << endl;                  // abcdefghi

    // 比较
    cout << ("abc" == "abc") << endl;    // 1
    cout << ("abc" < "abd") << endl;     // 1(字典序)

    // 字符串转数字 / 数字转字符串
    int n = stoi("42");
    double d = stod("3.14");
    string s42 = to_string(42);

    // 字符串流:用于复杂字符串拼接/解析
    stringstream ss;
    ss << "name=" << "Alice" << ", age=" << 20;
    cout << ss.str() << endl;            // name=Alice, age=20
    return 0;
}

string 关键方法:length/size(长度)、substr(子串)、find(查找)、+(拼接)、==(比较)、stoi/stod(转数字)、to_string(数字转字符串)。配合 stringstream 处理复杂字符串拼接。

六、algorithm:算法库

algorithm 头文件提供了大量通用算法,大部分都需要迭代器范围:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>    // accumulate
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // 排序(默认升序)
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << endl;                        // 1 2 3 5 7 8 9

    // 降序
    sort(v.begin(), v.end(), greater<int>());
    // 或用 lambda:sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

    // 查找
    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) cout << "found at " << (it - v.begin()) << endl;

    // 计数
    vector<int> nums = {1, 2, 3, 2, 2, 4};
    cout << count(nums.begin(), nums.end(), 2) << endl;   // 3

    // 最值
    cout << *max_element(v.begin(), v.end()) << endl;     // 9
    cout << *min_element(v.begin(), v.end()) << endl;     // 1

    // 累加
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << sum << endl;                 // 35

    // 遍历(可以修改)
    for_each(v.begin(), v.end(), [](int& x){ x *= 2; });
    return 0;
}

algorithm 的几个特点:

• 通用:同一个 sort 既能排 vector,也能排原生数组。
• 高效:STL 算法经过高度优化,通常比自己手写快。
• 可定制:大多数算法接受 lambda 作为回调。

七、algorithm 高级用法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 拷贝满足条件的元素到新容器
    vector<int> evens;
    copy_if(v.begin(), v.end(), back_inserter(evens),
            [](int x){ return x % 2 == 0; });
    for (int x : evens) cout << x << " ";   // 2 4 6 8 10
    cout << endl;

    // 条件判断
    bool allPos = all_of(v.begin(), v.end(), [](int x){ return x > 0; });
    bool anyBig = any_of(v.begin(), v.end(), [](int x){ return x > 5; });
    bool noneNeg = none_of(v.begin(), v.end(), [](int x){ return x < 0; });
    cout << allPos << " " << anyBig << " " << noneNeg << endl;   // 1 1 1

    // 删除所有偶数(erase-remove 惯用法)
    v.erase(remove_if(v.begin(), v.end(),
                      [](int x){ return x % 2 == 0; }),
            v.end());
    for (int x : v) cout << x << " ";   // 1 3 5 7 9
    cout << endl;

    // C++20 引入了 ranges,语法更简洁
    // auto evens = v | views::filter([](int x){ return x%2==0; });
    return 0;
}

几个高频用法:

• copy_if:筛选满足条件的元素到新容器。
• all_of/any_of/none_of:判断所有/任一/无元素满足条件。
• erase-remove 惯用法:真正删除满足条件的元素(remove 只是"搬"到末尾)。
• transform:对每个元素做变换。

C++20 引入了 ranges,语法更简洁(v | views::filter | views::transform),是新代码的趋势。

八、迭代器(iterator)

迭代器是连接容器和算法的桥梁,行为类似指针:

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // 迭代器:类似指针,指向容器中的元素
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";              // 解引用获取元素
    }
    cout << endl;

    // auto 简化
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 现代写法:range-for(语法糖,内部用迭代器)
    for (int x : v) cout << x << " ";
    cout << endl;

    // 迭代器分类(了解):
    // - 输入迭代器:只读,单向前进(istream_iterator)
    // - 输出迭代器:只写,单向前进(back_inserter)
    // - 前向迭代器:读写,单向前进(forward_list)
    // - 双向迭代器:前进后退(list, set, map)
    // - 随机访问迭代器:跳跃访问(vector, deque, array)
    return 0;
}

迭代器的核心操作:

• begin():指向首元素。
• end():指向尾元素的下一个(不存在的位置),作为结束标志。
• *it:解引用,获取元素。
• ++it:前进到下一个。
• it->member:访问元素的成员。

现代 C++ 推荐用 range-for,几乎不需要手写迭代器。但理解迭代器对读懂 STL 错误信息很重要。

九、容器选型参考

面对一堆容器不知道选哪个?参考下面这张表:

// STL 容器选型参考(按使用频率):
//
// 1. 顺序容器:
//    vector       动态数组,尾插/尾删 O(1),其他 O(n)  ★★★★★
//    string       字符数组,接口和 vector 类似        ★★★★★
//    array        定长数组(C++11),替代 C 数组        ★★★
//    deque        双端队列,头尾都 O(1)               ★★★
//    list         双向链表,任意位置 O(1) 插删        ★★
//    forward_list 单向链表                            ★
//
// 2. 关联容器(基于红黑树,有序):
//    map          键值对,按 key 排序                 ★★★★
//    set          集合,按值排序                      ★★★
//    multimap     允许重复 key 的 map                 ★
//    multiset     允许重复值的 set                    ★
//
// 3. 无序关联容器(基于哈希,C++11):
//    unordered_map   ★★★★ (查找 O(1))
//    unordered_set   ★★★
//
// 4. 容器适配器(基于其他容器):
//    stack        栈(LIFO)
//    queue        队列(FIFO)
//    priority_queue 优先队列(堆)
//
// 默认选择:
// - 数组用 vector
// - 字符串用 string
// - 键值对/查找用 unordered_map
// - 需要排序用 map

简化决策:

• 默认用 vector:99% 的"我需要一个数组"场景。
• 键值对用 unordered_map:比 map 快,除非要排序。
• 去重/查找用 unordered_set:同理。
• 字符串用 string:永远不要用 char 数组(除非调用 C API)。

十、性能与陷阱

STL 用得爽,但有几个坑:

• 迭代器失效:vector 扩容后,之前的迭代器/指针/引用都失效。push_back 后再用旧迭代器等于访问已释放内存。
• map 的 [] 副作用:m[key] 不存在时会插入默认值,如果只是想查询,误用会污染 map。
• unordered_map 的最坏复杂度:理论上哈希冲突时退化为 O(n)。攻击者可构造恶意 key 让你的程序卡死(哈希碰撞攻击)。
• 拷贝代价:vector 等容器拷贝是 O(n)。函数参数用 const vector<T>& 避免。
• emplace_back vs push_back:emplace_back 直接在容器内构造,避免临时对象的拷贝/移动。

小结

这一章你认识了 STL 的核心:vector(动态数组)、map/unordered_map(键值对)、set(集合)、string(字符串)、algorithm(算法)、迭代器。知道了容器选型原则——默认 vector + unordered_map。下一篇我们看 C++ 的内存管理——new/delete 与智能指针。

← 上一篇 C++ 模板

下一篇 C++ 内存管理 →