一、前言：关联式容器分类概览

我们学习了vector、list、deque三大序列式容器，元素顺序完全由插入顺序决定。本篇讲解关联式容器。

关联式容器不以插入顺序存储元素，而是根据key键值来组织数据，分为两大分支：

• 有序关联容器（红黑树实现）：set、multiset、map、multimap，key自动排序，查询时间复杂度O(logN)

• 无序关联容器（哈希表实现）：unordered_set、unordered_multiset、unordered_map、unordered_multimap，不保证顺序，平均查询O(1)，最坏O(N)

map存储key‑value键值对；set只存储key；带multi前缀容器允许key重复；不带multi则key唯一不允许重复。

这一组容器是业务开发字典、去重、统计计数高频工具，也是C++面试高频考点：红黑树性质、哈希冲突、负载因子、rehash、迭代器失效，很多同学只会调用operator[]，底层细节一知半解。

---

二、map / set 红黑树底层实现

2.1 红黑树五大性质

• 每个节点是红色或者黑色

• 根节点一定是黑色

• 所有叶子节点(NIL空节点)都是黑色

• 红色节点的两个子节点必须是黑色，不能出现连续红色节点

• 从任意节点出发，到达其所有后代叶子节点，路径上黑色节点数量相同（黑高一致）

红黑树是近似平衡二叉搜索树，不追求绝对平衡，通过颜色约束保证最长路径不会超过最短路径两倍，增删查复杂度稳定O(logN)。

2.2 set与map的关系

set底层就是红黑树，存储元素本身作为key，不允许重复，内部自动升序排序。

map存储pair<const Key,T>键值对，key不允许修改，value可以修改；按照key大小完成排序。

⚠️ map里面的key是const，不能通过迭代器修改key的值，只能修改value。

2.3 multiset / multimap

multiset允许重复key；multimap允许键重复，multimap没有operator[]访问接口，因为同一个key对应多个value，无法确定取哪一个。

2.4 map的operator[]细节（重点踩坑）

mp[key]行为：如果key存在，返回对应value引用；如果key不存在，会自动插入该key，value执行默认构造。

如果只是想查询key是否存在，不要直接写if(mp["test"])，会无意间插入无效数据，应当使用mp.find(key) != mp.end()判断。

2.5 有序容器全套实战代码（set/map/multimap）

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

int main()
{
    // 1. set 集合：自动去重、升序排序
    set<int> st;
    st.insert(5);
    st.insert(2);
    st.insert(8);
    st.insert(2); // 重复元素，插入无效

    cout << "set有序遍历：";
    for (auto& val : st)
    {
        cout << val << " ";
    }
    cout << endl;

    // 2. map 键值对容器
    map<string, int> mp;
    // 三种插入方式
    mp["张三"] = 20;
    mp.insert(pair<string, int>("李四", 18));
    mp.emplace("王五", 22);

    cout << "map键值对遍历：" << endl;
    for (auto& item : mp)
    {
        // item.first为key(不可修改)，item.second为value(可修改)
        cout << item.first << "：" << item.second << endl;
    }

    // 3. map查询：正确写法（无副作用）
    string key = "赵六";
    if (mp.find(key) != mp.end())
    {
        cout << "找到" << key << endl;
    }
    else
    {
        cout << key << "不存在" << endl;
    }

    // 4. multimap 允许key重复，无[]运算符
    multimap<string, int> mmp;
    mmp.insert({"语文", 90});
    mmp.insert({"语文", 95});
    mmp.insert({"数学", 88});

    cout << "multimap重复key遍历：" << endl;
    for (auto& item : mmp)
    {
        cout << item.first << "：" << item.second << endl;
    }

    return 0;
}

2.6 map[] 副作用踩坑复现代码

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

int main()
{
    map<string, int> mp;
    cout << "初始容器元素个数：" << mp.size() << endl;

    // 错误用法：查询不存在的key，自动插入数据
    if (mp["测试"]) 
    {
        cout << "存在" << endl;
    }
    cout << "误用[]后元素个数：" << mp.size() << endl; // 变为1，多余空数据

    // 正确用法：find查询，无任何副作用
    if (mp.find("测试2") != mp.end())
    {
        cout << "存在" << endl;
    }
    cout << "使用find后元素个数：" << mp.size() << endl; // 保持1，无新增

    return 0;
}

三、unordered_map / unordered_set 哈希表底层

unordered系列底层是开链法哈希表：由哈希桶数组 + 每个桶下面挂一条链表实现。

1. 传入key，调用哈希函数计算哈希值；

2. 哈希值对桶数组大小取模，得到对应的桶下标；

3. 将key‑value节点挂到该桶的链表上；

4. 查询时，同样算出桶位置，遍历链表，用相等运算符==比对key，找到目标元素。

3.1 哈希冲突

不同key经过哈希计算得到同一个桶下标，就发生哈希冲突。STL unordered容器使用链地址法（开链法）解决冲突，同一个桶位置把冲突节点连成链表。

冲突越多，链表越长，查询效率下降，最坏退化成O(N)遍历链表。

3.2 负载因子与rehash重哈希

• 负载因子load_factor = 元素总个数 / 桶数组的桶数量

• STL默认最大负载因子一般为1.0；当负载因子超过阈值，触发rehash

• rehash会创建一个更大的桶数组（通常扩大为原来2倍），对所有旧元素重新计算哈希、重新挂桶，释放旧桶数组内存。

rehash是很重的操作，会遍历全部元素，大量拷贝。如果预估数据量，可以调用reserve()提前设置桶数量，减少rehash次数。

3.3 unordered_map / unordered_set 完整实战代码

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

int main()
{
    // 1. unordered_set 无序去重
    unordered_set<int> ust;
    ust.insert(10);
    ust.insert(5);
    ust.insert(20);
    ust.insert(10);

    cout << "unordered_set无序遍历：";
    for (auto val : ust)
    {
        cout << val << " ";
    }
    cout << endl;

    // 2. unordered_map 哈希字典 + reserve性能优化
    unordered_map<string, int> ump;
    ump.reserve(100); // 预分配桶数量，避免多次rehash

    // 插入数据
    ump["苹果"] = 10;
    ump["香蕉"] = 20;
    ump.insert({"橙子", 15});

    // 遍历（无序）
    cout << "unordered_map遍历：" << endl;
    for (auto& item : ump)
    {
        cout << item.first << "：" << item.second << endl;
    }

    // 3. 查看负载因子、桶数量
    cout << "当前元素个数：" << ump.size() << endl;
    cout << "桶总数量：" << ump.bucket_count() << endl;
    cout << "负载因子：" << ump.load_factor() << endl;

    return 0;
}

3.4 自定义结构体适配map/unordered_map代码

自定义结构体作为key，map需重载<运算符，unordered_map需自定义哈希函数+重载==。

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

// 自定义结构体
struct Student
{
    int id;
    string name;

    // 适配map：重载小于号（排序规则）
    bool operator<(const Student& other) const
    {
        return this->id < other.id;
    }

    // 适配unordered_map：重载相等判断
    bool operator==(const Student& other) const
    {
        return this->id == other.id && this->name == other.name;
    }
};

// 自定义哈希函数
struct StudentHash
{
    size_t operator()(const Student& s) const
    {
        // 简单哈希映射
        return hash<int>()(s.id);
    }
};

int main()
{
    // 自定义结构体作为map的key
    map<Student, int> stuMap;
    stuMap[{1, "小明"}] = 95;
    stuMap[{2, "小红"}] = 98;

    // 自定义结构体作为unordered_map的key
    unordered_map<Student, int, StudentHash> stuUmp;
    stuUmp[{1, "小明"}] = 95;

    return 0;
}

四、有序容器与无序容器完整对比

对比维度	map / set（红黑树）	unordered_map / unordered_set（哈希表）
底层数据结构	红黑树（平衡搜索树）	哈希表（桶数组+链表开链）
元素顺序	按照key自动排序	无序，不保证存储顺序
查找时间复杂度	稳定 O(logN)	平均O(1)，冲突严重最坏O(N)
插入删除复杂度	O(logN)	平均O(1)，rehash时O(N)
迭代器遍历顺序	有序升序遍历	遍历顺序随机，与插入无关
内存开销	较大，树节点存储颜色、左右父指针	中等，桶数组+链表节点
key要求	key必须支持小于比较<运算符	key需要哈希函数，还要支持==相等比较
迭代器失效	插入不会失效；仅erase当前被删迭代器失效	rehash发生时全部迭代器失效；不rehash仅erase对应迭代器失效
典型场景	需要key有序；数据量不大；不希望性能抖动	大量数据，高频查询插入，不需要排序，追求平均高性能

---

五、关联容器迭代器失效规则总结

map / set（红黑树容器）

• insert插入：不会令任何迭代器、指针、引用失效，树只是调整节点指针，原有节点内存地址不变

• erase删除：仅被删除的那个迭代器失效，其余迭代器全部有效

unordered_map / unordered_set（哈希容器）

• insert插入：如果触发rehash重哈希，全部迭代器失效；不触发rehash，迭代器保持有效

• erase删除：只让被删除元素对应的迭代器失效，其他迭代器不受影响

⚠️ unordered容器rehash会整体重建桶数组，旧迭代器全部作废，这是非常容易踩坑的点。

5.1 迭代器失效对比实战代码（map VS unordered_map）

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

int main()
{
    // 1. map迭代器测试：插入不失效
    map<int, int> mp;
    mp[1] = 10;
    auto mapIt = mp.begin();

    // 插入新数据，原有迭代器有效
    mp[2] = 20;
    cout << "map迭代器有效：" << mapIt->first << " " << mapIt->second << endl;

    // erase仅删除当前迭代器，其他有效
    mp.erase(mapIt);


    // 2. unordered_map迭代器测试：rehash导致全部失效
    unordered_map<int, int> ump;
    ump.reserve(2); // 初始桶数量2

    ump[1] = 10;
    auto umpIt = ump.begin();

    // 插入大量数据，触发rehash，迭代器失效
    for (int i = 2; i <= 10; i++)
    {
        ump[i] = i * 10;
    }

    // 此处迭代器已失效，访问会崩溃
    // cout << umpIt->first << endl; 

    return 0;
}

六、工程开发高频踩坑汇总

坑1：map使用[]做存在性判断，key不存在就自动插入，污染容器数据

判断是否存在一律使用find()；operator[]只用于读取或写入已知key。

坑2：multimap使用operator[]编译报错

multimap允许重复key，没有重载[]，取值要用find、equal_range。

坑3：unordered_map不做reserve，数据量上来频繁rehash，性能剧烈抖动

预估数据量提前调用reserve，减少rehash开销。

坑4：自定义类型直接放入unordered_map，编译报错

自定义对象作为key，需要自己提供哈希函数和==相等运算符；map只需要提供<小于比较。

坑5：误以为unordered一定比map快

数据量小的时候，哈希计算、rehash开销反而会让unordered性能不如map；且哈希冲突会带来性能退化。

坑6：遍历unordered_map，误以为遍历顺序等于插入顺序

哈希容器完全无序，不能依赖遍历顺序，如果需要有序输出，请改用map。

---

七、大厂面试真题问答

Q1 简述红黑树五大性质，红黑树和AVL树区别？

红黑树五条性质如上文；AVL是严格平衡树，左右子树高度差不超过1，旋转次数更多；红黑树是弱平衡，旋转更少，增删性能更好，STL关联容器选用红黑树而非AVL。

Q2 map的operator[]有什么副作用？如何只做查询不插入？

operator[]当key不存在会自动插入默认构造的键值对。只查询使用find(key) != mp.end()，不要用[]判断存在。

Q3 unordered_map负载因子是什么？rehash什么时候触发，会带来什么问题？

负载因子 = 元素数量 / 桶的个数；超过最大负载因子阈值触发rehash，开辟更大桶数组，全部元素重新哈希挂桶。rehash开销很大，同时发生rehash之后旧迭代器全部失效。

Q4 map和unordered_map迭代器失效区别？

map插入不会失效迭代器，erase只失效被删迭代器；unordered_map插入如果触发rehash，全部迭代器失效，否则仅erase的迭代器失效。

Q5 什么场景选map，什么场景选unordered_map？

需要key有序、不希望性能剧烈抖动、数据规模不大，选择map；数据量大、频繁增删查找，不需要排序，优先unordered_map，记得reserve预分配桶。

---

八、今日总结

完整吃透STL关联容器：

✅ map/set底层红黑树，五大性质，有序特性

✅ map operator[]副作用，multimap没有[]接口

✅ unordered系列哈希表开链法、哈希冲突原理

✅ 负载因子、rehash重哈希的性能影响

✅ map与unordered完整对比表格、迭代器失效规则

✅ 工程踩坑点、高频面试问答