C++ STL 容器:map 与 set

如果说 vector 是"有序的列表",那 map 就是"键值查找表",set 是"自动去重的集合"。它们内部用红黑树实现,查找、插入、删除都是 O(log n),是算法题和工程里查表、去重、统计的利器。

1. map 的基本用法

map<Key, Value> 按键自动排序,键唯一。用 [] 访问不存在的键会自动插入默认值:

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

map<string, int> scores;
scores["Alice"] = 95;      // 插入
scores["Bob"] = 88;
scores["Alice"] = 96;      // 覆盖旧值

// 统计词频的经典写法
map<string, int> freq;
freq[word]++;              // 不存在则先插入 0 再加 1

2. 查找与删除

// find:找不到返回 end()
auto it = scores.find("Alice");
if (it != scores.end()) {
    cout << it->first << " = " << it->second;
}

// count:0 或 1,判断键是否存在
if (scores.count("Tom") == 0) {
    cout << "Tom 不在表中";
}

scores.erase("Bob");            // 按键删除
scores.erase(scores.begin());   // 按迭代器删除

遍历时 it->first 是键,it->second 是值,顺序按键升序。

3. set:自动去重的集合

#include <set>

set<int> s = {5, 3, 8, 3, 1};   // 自动排序并去重 → {1,3,5,8}
s.insert(3);                    // 已存在,插入失败
s.insert(7);                    // → {1,3,5,7,8}

if (s.count(5)) {               // 成员判断 O(log n)
    cout << "5 在集合中";
}

// 求有序集合的边界
auto lo = s.lower_bound(3);     // 第一个 >= 3 的元素
auto up = s.upper_bound(5);     // 第一个 > 5 的元素

4. unordered_map:哈希表版本

不需要有序时,用 unordered_map/unordered_set 更快,平均 O(1) 查找:

#include <unordered_map>

unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;    // 统计频次,平均 O(1)

// 注意:哈希容器没有 lower_bound,
// 遍历顺序也不保证与插入一致

代价:无序、常数更大、对自定义类型需要提供哈希函数。默认只支持内置类型和 string。

5. 两种容器的选择

6. 实战:两数之和

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> pos;   // 值 → 下标
    for (int i = 0; i < nums.size(); ++i) {
        int need = target - nums[i];
        if (pos.count(need)) {
            return {pos[need], i};
        }
        pos[nums[i]] = i;
    }
    return {};
}

💡 多写"统计类"题目:词频统计、出现次数最多的元素、去重排序。用 map/set 各实现一遍,再对比 unordered 版本,感受 O(log n) 与 O(1) 的实际差距。