常见 STL 用法

本文按常见使用场景整理 STL 的基础写法、典型组合与注意事项，重点覆盖：

• 顺序容器与关联容器的选择
• 常见算法接口的直接用法
• 删除、去重、查找等高频模式
• 迭代器失效、隐式插入等容易遗漏的细节

容器选择

场景	推荐容器	说明
尾插、随机访问、批量处理	vector	默认首选，连续内存，适合配合算法库
有序键值映射	map	按键有序，支持 lower_bound 和区间操作
无序键值映射	unordered_map	均摊 O(1) 查找，适合计数和映射
有序去重集合	set	元素唯一，自动排序
无序去重集合	unordered_set	判重效率高，不保序
维护最大值/最小值	priority_queue	适合 Top-K、贪心、调度

对于一次性读入、后续批量查询的数据，vector + sort + lower_bound 通常比节点型容器更简洁，也更有利于缓存访问。

vector

基础写法

#include <vector>

std::vector<int> a;
a.push_back(1);
a.push_back(2);
a.emplace_back(3);

预分配容量

已知大致元素数量时，优先使用 reserve：

std::vector<int> a;
a.reserve(n);
for (int i = 0; i < n; ++i) {
    a.push_back(i);
}

这样可以减少扩容带来的重新分配与元素搬移。

push_back 与 emplace_back

std::vector<std::pair<int, std::string>> v;
v.push_back({1, "alice"});
v.emplace_back(2, "bob");

• push_back：插入已有对象或临时对象
• emplace_back：直接在容器尾部构造对象

对象已经存在时，push_back(std::move(obj)) 通常更直接。

删除指定元素

std::vector<int> a = {1, 2, 3, 2, 4, 2};
a.erase(std::remove(a.begin(), a.end(), 2), a.end());

这是标准的 erase-remove 模式：

• remove 将保留元素前移，返回新的逻辑结尾
• erase 真正删除尾部无效区间

排序后去重

std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());

unique 只去除相邻重复元素，因此通常先排序。

string 与 string_view

string

std::string s = "hello";
s += " world";

std::string 持有实际字符串数据，适合需要所有权的场景。

只读传参

void print(const std::string& s);

只读场景优先使用 const std::string&，避免不必要的拷贝。

string_view

#include <string_view>

void log(std::string_view msg);

std::string_view 适合只读、短期观察字符串内容的场景，可以避免额外构造。
需要注意的是，string_view 不拥有数据，必须保证底层字符序列在使用期间仍然有效。

map 与 unordered_map

map

std::map<std::string, int> cnt;
cnt["cpu"] = 3;
cnt["gpu"] = 5;

特点：

• 键有序
• 查找、插入、删除复杂度为 O(log n)
• 支持范围查询和有序遍历

适合需要顺序输出、前驱后继、区间边界定位的场景。

unordered_map

std::unordered_map<std::string, int> cnt;
cnt["alice"]++;
cnt["bob"]++;

特点：

• 无序
• 均摊 O(1) 查找
• 适合计数、频率统计、值到索引映射

operator[] 的隐式插入

std::unordered_map<std::string, int> cnt;

if (cnt["alice"] > 0) {
    // ...
}

如果 "alice" 不存在，上面的写法会插入默认值 0。
只查询时，建议使用 find 或 contains：

auto it = cnt.find("alice");
if (it != cnt.end() && it->second > 0) {
    // ...
}

if (cnt.contains("alice")) {
    // ...
}

插入接口

cnt.insert({"alice", 1});
cnt.emplace("bob", 2);
cnt.try_emplace("carol", 3);

• insert：插入已有值
• emplace：原位构造
• try_emplace：键不存在时才构造 value

set 与 unordered_set

判重

std::unordered_set<int> vis;
vis.insert(42);

if (vis.contains(42)) {
    // visited
}

只需要集合语义时，直接使用 set 或 unordered_set 即可。

pair 与结构化绑定

std::unordered_map<std::string, int> cnt = {
    {"alice", 3},
    {"bob", 5}
};

for (const auto& [name, value] : cnt) {
    std::cout << name << ": " << value << '\n';
}

结构化绑定适合遍历键值对、返回多个结果的场景，代码更直接。

priority_queue

默认是大根堆：

#include <queue>
#include <vector>

std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);

while (!pq.empty()) {
    std::cout << pq.top() << ' ';
    pq.pop();
}

小根堆

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

自定义比较器

struct Node {
    int id;
    int dist;
};

struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        return a.dist > b.dist;
    }
};

std::priority_queue<Node, std::vector<Node>, Cmp> pq;

写完比较器后，建议直接验证 top() 的结果是否符合预期。

算法库

容器负责组织数据，<algorithm> 负责表达处理逻辑。

sort

std::vector<int> a = {4, 2, 5, 1, 3};
std::sort(a.begin(), a.end());

自定义排序：

std::vector<std::pair<int, int>> a;

std::sort(a.begin(), a.end(),
    [](const auto& lhs, const auto& rhs) {
        if (lhs.first != rhs.first) return lhs.first < rhs.first;
        return lhs.second > rhs.second;
    });

比较器应满足严格弱序，否则行为未定义。

lower_bound 与 upper_bound

std::vector<int> a = {1, 2, 2, 2, 4, 7};

auto it1 = std::lower_bound(a.begin(), a.end(), 2);
auto it2 = std::upper_bound(a.begin(), a.end(), 2);

int left = it1 - a.begin();
int right = it2 - a.begin();

• lower_bound：第一个 >= x 的位置
• upper_bound：第一个 > x 的位置

适合有序数组中的边界查找。

binary_search

bool ok = std::binary_search(a.begin(), a.end(), 4);

只判断存在性时，binary_search 足够直接。
需要具体位置时，使用 lower_bound。

accumulate

#include <numeric>

int sum = std::accumulate(a.begin(), a.end(), 0);

类型较大时，初值也要使用对应类型：

long long sum = std::accumulate(a.begin(), a.end(), 0LL);

count / count_if 与 find / find_if

int c = std::count(a.begin(), a.end(), 2);

auto it = std::find_if(a.begin(), a.end(), [](int x) {
    return x % 2 == 0;
});

适合直接表达“统计”和“查找满足条件的元素”。

all_of / any_of / none_of

bool all_positive = std::all_of(a.begin(), a.end(), [](int x) {
    return x > 0;
});

适合校验型逻辑。

nth_element

std::vector<int> a = {7, 1, 4, 9, 3, 6};
int k = 2; // 第 3 小

std::nth_element(a.begin(), a.begin() + k, a.end());
std::cout << a[k] << '\n';

适合中位数、Top-K 分界和选择问题，不必为了单个位置的结果做完整排序。

迭代器失效

vector 扩容

std::vector<int> a = {1, 2, 3};
auto it = a.begin();

a.push_back(4); // 可能触发扩容
// 此时 it 可能已经失效

遍历中删除元素

for (auto it = a.begin(); it != a.end(); ) {
    if (*it % 2 == 0) {
        it = a.erase(it);
    } else {
        ++it;
    }
}

删除后应使用 erase 返回的新迭代器继续遍历。

常用建议

1. 只读遍历优先 const auto&

for (const auto& x : vec) {
    // read only
}

2. 修改元素时使用引用

for (auto& x : vec) {
    x *= 2;
}

3. 批量处理优先考虑 vector + algorithm

这通常更简洁，也更有利于性能。

4. 排序需求和范围查询需求优先考虑有序容器

unordered_map 和 unordered_set 不提供顺序相关能力。

5. 写比较器后直接验证结果

尤其是 priority_queue 和多关键字 sort 场景。

示例：统计单词频率

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

int main() {
    std::vector<std::string> words = {
        "cpu", "gpu", "cpu", "ram", "gpu", "cpu", "ssd"
    };

    std::unordered_map<std::string, int> freq;
    for (const auto& w : words) {
        ++freq[w];
    }

    std::vector<std::pair<std::string, int>> items(freq.begin(), freq.end());

    std::sort(items.begin(), items.end(),
        [](const auto& lhs, const auto& rhs) {
            if (lhs.second != rhs.second) return lhs.second > rhs.second;
            return lhs.first < rhs.first;
        });

    for (const auto& [word, count] : items) {
        std::cout << word << ' ' << count << '\n';
    }
}

这段代码组合了：

• vector 保存原始数据
• unordered_map 统计频率
• pair 表示键值项
• sort + lambda 完成多关键字排序

总结

STL 的常用写法可以归纳为几条固定模式：

• 顺序数据优先考虑 vector
• 需要有序语义时使用 map / set
• 只关心快速查找时使用 unordered_map / unordered_set
• 查找、排序、去重、选择等操作尽量优先考虑标准算法
• 删除元素、扩容、重排时始终关注迭代器失效

以上为常见 STL 模式。