21. STL关联容器：set、multiset、map、multimap、unordered_set、unordered_map

关联容器这块，说实话是C++里最容易让人「用错」的地方。我见过不少项目，明明该用map的地方用了vector硬查，或者该用unordered_set的地方用了set，结果性能惨不忍睹。今天咱们就把这六个容器掰扯清楚。

21.1 关联容器家族概览

先看一张图，把这六个容器的关系理清楚。我习惯把它们分成两类：有序的和无序的。

STL关联容器分类 有序关联容器（红黑树） 无序关联容器（哈希表） set multiset map multimap unordered_set unordered_multiset unordered_map unordered_multimap 键唯一：set / map / unordered_set / unordered_map 键可重复：multiset / multimap / unordered_multiset / unordered_multimap 有序容器：自动排序，查找O(log n) | 无序容器：不排序，查找O(1)平均

说白了，这六个容器就是两个维度交叉的结果：有序 vs 无序，键唯一 vs 键可重复。有序的底层是红黑树，无序的底层是哈希表。你想想看，这决定了它们的性能特征和使用场景完全不同。

21.2 set 和 multiset

set 是个集合，里面的元素自动排序，而且每个元素只能出现一次。我最早用 set 是在做数据去重的时候，那叫一个爽——直接往里插，重复的自动被忽略。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    
    // 自动排序，重复的1和5只保留一个
    for (int x : s) {
        std::cout << x << " ";  // 输出: 1 2 3 4 5 6 9
    }
    std::cout << std::endl;
    
    // 查找元素
    auto it = s.find(4);
    if (it != s.end()) {
        std::cout << "找到了: " << *it << std::endl;
    }
    
    // 插入 - 返回pair<iterator, bool>
    auto result = s.insert(7);
    if (result.second) {
        std::cout << "插入成功" << std::endl;
    }
    
    return 0;
}

小技巧：set的insert返回一个pair，first是迭代器，second是bool表示是否真的插入了。这个设计很实用，我经常用它来判断元素是否已经存在。

multiset 和 set 几乎一样，唯一的区别是允许重复元素。嗯，这里要注意：multiset 的 find 返回的是第一个匹配元素的迭代器，如果有多个重复，需要用 equal_range 来获取全部。

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3, 4};
    
    // count 可以统计某个值出现了几次
    std::cout << "3出现了 " << ms.count(3) << " 次" << std::endl;
    
    // equal_range 返回一对迭代器，表示所有匹配元素的范围
    auto range = ms.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " ";  // 输出: 2 2
    }
    std::cout << std::endl;
    
    return 0;
}

21.3 map 和 multimap

map 是键值对容器，每个键对应一个值。我个人觉得 map 是 STL 里最实用的容器之一。你想想看，很多场景下我们需要「根据某个key快速找到对应的value」，map 就是干这个的。

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

int main() {
    std::map<std::string, int> ages;
    
    // 插入方式1：用 []
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    
    // 插入方式2：用 insert
    ages.insert({"Charlie", 22});
    
    // 访问
    std::cout << "Alice的年龄: " << ages["Alice"] << std::endl;
    
    // 注意：用 [] 访问不存在的key会自动创建
    std::cout << "David的年龄: " << ages["David"] << std::endl;  // 输出0，并插入David
    
    // 安全访问用 find
    auto it = ages.find("Eve");
    if (it != ages.end()) {
        std::cout << "Eve的年龄: " << it->second << std::endl;
    } else {
        std::cout << "没有找到Eve" << std::endl;
    }
    
    return 0;
}

避坑指南：我曾经在代码里用 map 的 [] 操作符查找元素，结果不小心创建了一堆不存在的键值对，导致内存暴涨。记住：[] 在 key 不存在时会自动插入一个默认值。如果你只是想查找，请用 find() 或 at()。

multimap 允许一个键对应多个值。说实话，我实际项目中用得不多，但有个场景特别合适：比如一个学生可以选修多门课程，用 multimap 就很自然。

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

int main() {
    std::multimap<std::string, std::string> courses;
    
    courses.insert({"Alice", "Math"});
    courses.insert({"Alice", "Physics"});
    courses.insert({"Bob", "Math"});
    courses.insert({"Alice", "Chemistry"});
    
    // 获取Alice的所有课程
    auto range = courses.equal_range("Alice");
    std::cout << "Alice的课程: ";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

21.4 unordered_set 和 unordered_map

这两个是 C++11 引入的哈希表版本。它们不排序，但查找速度更快——平均 O(1)。我个人的习惯是：除非你需要有序遍历，否则优先用 unordered 版本。

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

int main() {
    // unordered_set
    std::unordered_set<int> us = {3, 1, 4, 1, 5, 9};
    // 注意：输出顺序是不确定的
    for (int x : us) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // unordered_map
    std::unordered_map<std::string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    
    // 查找很快
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Bob的分数: " << it->second << std::endl;
    }
    
    return 0;
}

性能对比：

操作set/map (红黑树)unordered_set/map (哈希表)
查找O(log n)O(1) 平均，O(n) 最坏
插入O(log n)O(1) 平均，O(n) 最坏
删除O(log n)O(1) 平均，O(n) 最坏
遍历顺序有序（升序）无序（随机）
内存占用较低较高（需要哈希表桶）

21.5 如何选择？

我总结了一个简单的决策流程，你照着选基本不会错：

  1. 需要有序遍历吗？ 是 → 用 set/map/multiset/multimap；否 → 用 unordered 版本
  2. 键可以重复吗？ 是 → 用 multi 版本；否 → 用普通版本
  3. 需要键值对？ 是 → 用 map 系列；否 → 用 set 系列

举个例子：如果你要做一个「单词出现次数统计」，用 unordered_map<string, int> 最合适。如果你要「维护一个有序的排行榜」，用 set<pair<int, string>> 或者 map<int, string> 更合适。

个人经验：我在做游戏服务器的时候，玩家在线列表用 unordered_set 存玩家ID，查找快。但排行榜必须用 set，因为要按分数排序输出。选对容器，代码性能能差出好几倍。

21.6 自定义类型作为键

如果你想把自定义类型放进 set 或 map，需要提供比较函数（有序版本）或哈希函数（无序版本）。

#include <set>
#include <unordered_set>
#include <iostream>

struct Person {
    std::string name;
    int age;
};

// 用于有序 set：需要 operator<
bool operator<(const Person& a, const Person& b) {
    return a.name < b.name;  // 按名字排序
}

// 用于无序 set：需要哈希函数
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ 
               (std::hash<int>()(p.age) << 1);
    }
};

// 用于无序 set：需要相等比较
struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name && a.age == b.age;
    }
};

int main() {
    // 有序 set
    std::set<Person> ordered_set;
    ordered_set.insert({"Alice", 25});
    ordered_set.insert({"Bob", 30});
    
    // 无序 set
    std::unordered_set<Person, PersonHash, PersonEqual> unordered_set;
    unordered_set.insert({"Alice", 25});
    unordered_set.insert({"Bob", 30});
    
    return 0;
}

注意：自定义哈希函数一定要保证：如果两个对象相等，它们的哈希值也必须相等。我曾经在这上面吃过亏，两个相等的 Person 因为哈希值不同，被放到了不同的桶里，导致查找失败。排查了半天才发现是哈希函数写错了。

21.7 总结

好了，这六个关联容器咱们都过了一遍。记住几个关键点：

  • 有序 vs 无序：看你要不要排序
  • 唯一 vs 可重复：看你的业务逻辑
  • set vs map：看你要不要存额外的 value
  • 自定义类型做键：记得提供比较器或哈希函数

实际开发中，我大概 70% 的场景用 unordered_map，20% 用 set，剩下的 10% 才用其他几个。但不管用哪个，理解它们的底层原理才是关键。你想想看，知道红黑树和哈希表的区别，你自然就知道什么时候该用哪个了。

← 上一章 📖 返回目录 下一章 →