本文详细解析 C++ STL 中的关联式容器 map 和 set，涵盖底层原理、核心操作、性能分析和实际应用场景，帮助各位读者深入理解并灵活运用这两种重要数据结构。

一、 序列式容器与关联式容器

在 C++ STL 中，容器分为两大类型：序列式容器和关联式容器。

我们所接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为其逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，它依旧是序列式容器。顺序容器中的元素是按它们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，它的逻辑结构就被破坏了。顺序容器中的元素是按位置来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

本章节讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

1.1 序列式容器 (Sequence Containers)

序列式容器维护元素的线性序列，元素在容器中的位置取决于插入的时机和位置，与元素值无关。常见的序列式容器包括：

• vector：动态数组，支持快速随机访问

• list：双向链表，支持高效插入删除

• deque：双端队列，两端都可高效插入删除

• array：固定大小数组

• forward_list：单向链表

特点：元素按存储位置顺序保存和访问，逻辑结构为线性序列。

1.2 关联式容器 (Associative Containers)

关联式容器使用键值对 (key-value) 的存储方式，元素的位置取决于特定的排序准则，与插入顺序无关。主要包括：

• 树形结构：map、set、multimap、multiset

• 哈希结构：unordered_map、unordered_set、unordered_multimap、unordered_multiset

特点：元素按关键字保存和访问，逻辑结构通常是非线性的（如树或哈希表）。

1.3 核心差异对比

特性	序列式容器	关联式容器
存储方式	按物理位置	按键值排序
查找效率	O(n)	O(log n) 或 O(1)
元素关系	独立	关联关系紧密
典型应用	需要保持插入顺序的场景	需要快速查找、去重的场景

二、set 系列容器深度解析

2.1 set 的基本特性

set 是 C++ STL 中存储唯一键值的关联容器，其内部元素按特定顺序自动排序且不允许重复。底层实现通常采用红黑树（Red-Black Tree）这种自平衡二叉搜索树结构，保证了元素的有序性和操作效率。

template <class T,                        // set::key_type/value_type
          class Compare = less<T>,        // set::key_compare/value_compare  
          class Alloc = allocator<T>>     // set::allocator_type
class set;

核心特性：

• 元素唯一，自动去重

• 元素自动排序（默认升序）

• 迭代器遍历按中序遍历顺序（有序）

• 不支持直接修改元素值（会破坏树结构）

2.2 set 的构造与初始化

代码

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

int main() {
    // 1. 默认构造
    set<int> s1;
    
    // 2. 初始化列表构造
    set<int> s2 = {5, 2, 7, 2, 8, 1};
    
    // 3. 迭代器范围构造
    vector<int> vec = {3, 1, 4, 1, 5};
    set<int> s3(vec.begin(), vec.end());
    
    // 4. 拷贝构造
    set<int> s4(s3);
    
    // 5. 自定义排序规则（降序）
    set<int, greater<int>> s5 = {5, 2, 7, 1};
    
    return 0;
}

2.3 set 的迭代器与遍历

set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中 序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

void setIterationDemo() {
    set<int> s = {5, 2, 7, 1, 8, 3};
    
    // 正向迭代器遍历（升序）
    cout << "升序遍历: ";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 反向迭代器遍历（降序）
    cout << "降序遍历: ";
    for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 范围for循环（推荐）
    cout << "范围for: ";
    for (const auto& elem : s) {
        cout << elem << " ";
    }
    cout << endl;
}

2.4 set 的核心操作

插入操作

set 的插入操作主要有以下几种方式：

void setInsertDemo() {
    set<int> s;
    
    // 单个插入
    auto ret1 = s.insert(5);
    cout << "插入5: " << (ret1.second ? "成功" : "失败") << endl;
    
    auto ret2 = s.insert(5);  // 重复插入
    cout << "再次插入5: " << (ret2.second ? "成功" : "失败") << endl;
    
    // 批量插入
    s.insert({2, 7, 1, 8, 3});
    
    // 迭代器范围插入
    vector<int> additional = {4, 6, 9};
    s.insert(additional.begin(), additional.end());
    
    cout << "最终集合: ";
    for (const auto& elem : s) {
        cout << elem << " ";
    }
    cout << endl;
}

查找与统计

查找是指在数据集合中定位特定元素的过程，常见的查找方法包括：

void setSearchDemo() {
    set<int> s = {1, 2, 3, 5, 7, 8};
    
    // find 查找
    auto it = s.find(5);
    if (it != s.end()) {
        cout << "找到元素: " << *it << endl;
    } else {
        cout << "未找到元素" << endl;
    }
    
    // count 统计
    cout << "5的个数: " << s.count(5) << endl;
    cout << "10的个数: " << s.count(10) << endl;
    
    // 范围查找
    auto lower = s.lower_bound(3);  // >= 3
    auto upper = s.upper_bound(7);  // > 7
    
    cout << "[3, 7]区间: ";
    for (auto it = lower; it != upper; ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

删除操作

删除操作是指从文件、数据库、列表或任意数据集合中移除指定的数据项或内容的过程。它是计算机系统中常见的基本操作之一，与创建、读取、更新并称为CRUD四大基础操作。

void setEraseDemo() {
    set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    cout << "原始集合: ";
    for (const auto& elem : s) {
        cout << elem << " ";
    }
    cout << endl;
    
    // 按值删除
    size_t removed = s.erase(5);
    cout << "删除5, 实际删除: " << removed << " 个元素" << endl;
    
    // 按迭代器删除
    auto it = s.find(3);
    if (it != s.end()) {
        s.erase(it);
        cout << "通过迭代器删除3" << endl;
    }
    
    // 范围删除
    auto first = s.find(6);
    auto last = s.find(9);
    if (first != s.end() && last != s.end()) {
        s.erase(first, last);  // 删除[6, 9)，注意是前闭后开
        cout << "删除[6, 9)区间" << endl;
    }
    
    cout << "最终集合: ";
    for (const auto& elem : s) {
        cout << elem << " ";
    }
    cout << endl;
}

2.5 multiset 的多重集合

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么 insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。

void multisetDemo() {
    multiset<int> ms = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    
    cout << "multiset元素: ";
    for (const auto& elem : ms) {
        cout << elem << " ";
    }
    cout << endl;
    
    // 查找所有重复元素
    int target = 4;
    auto range = ms.equal_range(target);
    
    cout << "所有" << target << "的位置: ";
    for (auto it = range.first; it != range.second; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 统计重复元素个数
    cout << target << "的个数: " << ms.count(target) << endl;
    
    // 删除所有指定值
    ms.erase(target);
    cout << "删除所有" << target << "后: ";
    for (const auto& elem : ms) {
        cout << elem << " ";
    }
    cout << endl;
}

三、map 系列容器深度解析

3.1 map类的介绍

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持 小于比较，如果不支持或者需要的话，可以自行实现仿函数传给第二个模板参数，map底层存储数据的 内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模板参数。map底层是用红黑树实 现，增删查改效率是 O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

template <class Key,                            // map::key_type
          class T,                              // map::mapped_type  
          class Compare = less<Key>,            // map::key_compare
          class Alloc = allocator<pair<const Key, T>>  // map::allocator_type
> class map;

https://legacy.cplusplus.com/reference/map/

核心特性：

• 键唯一，值可以重复

• 按键自动排序（默认升序）

• 支持通过键快速访问值

• 插入、删除、查找时间复杂度 O(log n)

3.2 pair 类型介绍

map 的元素类型为 pair<const Key, T>：

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    
    T1 first;
    T2 second;
    
    // 构造函数
    pair() : first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

// 便捷函数
template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y) {
    return pair<T1, T2>(x, y);
}

3.3 map 的构造

map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

void mapConstructionDemo() {
    // 1. 初始化列表构造
    map<string, string> dict = {
        {"left", "左边"},
        {"right", "右边"}, 
        {"insert", "插入"},
        {"string", "字符串"}
    };
    
    // 2. 迭代器遍历
    cout << "字典内容:" << endl;
    for (auto it = dict.begin(); it != dict.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }
    
    // 3. 范围for遍历（推荐）
    cout << "\n范围for遍历:" << endl;
    for (const auto& pair : dict) {
        cout << pair.first << ": " << pair.second << endl;
    }
}

3.4 map 的增删查

map增接口，插入的pair键值对数据，跟set有所不同，但是查和删的接口只用关键字key，跟set是完全类似的。不过，find返回iterator，不仅仅可以确认key在不在，还能找到key映射的value，同时通过迭代还可以修改value。

插入操作

void mapInsertDemo() {
    map<string, string> dict;
    
    // 四种插入方式
    // 1. 直接插入pair对象
    pair<string, string> kv1("first", "第一个");
    dict.insert(kv1);
    
    // 2. 插入临时pair对象
    dict.insert(pair<string, string>("second", "第二个"));
    
    // 3. 使用make_pair（推荐）
    dict.insert(make_pair("sort", "排序"));
    
    // 4. 初始化列表插入
    dict.insert({"auto", "自动的"});
    
    // 重复键插入失败
    auto ret = dict.insert({"left", "左边，剩余"});
    cout << "插入left: " << (ret.second ? "成功" : "失败") << endl;
    
    // 输出结果
    for (const auto& pair : dict) {
        cout << pair.first << ": " << pair.second << endl;
    }
}

访问与修改

void mapAccessDemo() {
    map<string, int> ageMap = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 28}
    };
    
    // 1. 通过迭代器访问和修改
    auto it = ageMap.find("Alice");
    if (it != ageMap.end()) {
        it->second = 26;  // 修改值
        cout << "Alice的年龄: " << it->second << endl;
    }
    
    // 2. 通过[]运算符访问（键不存在时会插入）
    cout << "Bob的年龄: " << ageMap["Bob"] << endl;
    
    // 3. []运算符的插入和修改功能
    ageMap["David"] = 32;      // 插入新键值对
    ageMap["Alice"] = 27;      // 修改现有值
    
    // 4. 安全的查找访问
    string name = "Eve";
    if (ageMap.count(name)) {
        cout << name << "的年龄: " << ageMap[name] << endl;
    } else {
        cout << name << "不在映射中" << endl;
    }
    
    // 输出最终结果
    cout << "\n最终年龄映射:" << endl;
    for (const auto& pair : ageMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
}

3.5 map 的 operator[] 原理

operator[] 是 map 最重要的特性之一，具有查找、插入、修改三重功能：

// operator[] 的内部实现原理
mapped_type& operator[] (const key_type& k) {
    // 尝试插入键k和mapped_type的默认值
    pair<iterator, bool> ret = insert({k, mapped_type()});
    
    // 返回对应值的引用
    iterator it = ret.first;
    return it->second;
}

工作原理：

1. 键存在：返回对应值的引用，可用于修改

2. 键不存在：插入新键值对（值为默认构造），返回值的引用

3.6 multimap 和 map 的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么 insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如 find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支 持插入了，不能支持修改。

void multimapDemo() {
    multimap<string, string> authors = {
        {"鲁迅", "狂人日记"},
        {"鲁迅", "阿Q正传"},
        {"茅盾", "子夜"},
        {"巴金", "家"},
        {"鲁迅", "呐喊"}
    };
    
    // 查找特定作者的所有作品
    string author = "鲁迅";
    auto range = authors.equal_range(author);
    
    cout << author << "的作品:" << endl;
    for (auto it = range.first; it != range.second; ++it) {
        cout << " - " << it->second << endl;
    }
    
    // 统计作者作品数量
    cout << author << "的作品数量: " << authors.count(author) << endl;
}

四、底层原理：红黑树

4.1 红黑树特性

map 和 set 的底层通常使用红黑树实现，红黑树是一种自平衡的二叉搜索树，具有以下特性：

1. 节点颜色：每个节点是红色或黑色

2. 根节点：根节点是黑色

3. 叶子节点：所有叶子节点（NIL）是黑色

4. 红色节点规则：红色节点的子节点必须是黑色

5. 黑色高度：从任一节点到其每个叶子的所有路径包含相同数目的黑色节点

4.2 红黑树的优势

• 平衡性：保证树的高度为 O(log n)

• 高效操作：插入、删除、查找都是 O(log n)

• 稳定性：相对于 AVL 树，插入删除的旋转操作更少

五、性能分析与使用建议

5.1 时间复杂度对比

操作	set/map	unordered_set/unordered_map
插入	O(log n)	O(1) 平均，O(n) 最坏
删除	O(log n)	O(1) 平均，O(n) 最坏
查找	O(log n)	O(1) 平均，O(n) 最坏
遍历	O(n)	O(n)

5.2 选择建议

• 需要元素有序：选择 set/map

• 最高性能需求：选择 unordered_set/unordered_map

• 需要重复元素：选择 multiset/multimap

• 内存敏感场景：哈希表通常使用更多内存

5.3 最佳实践

1. 预分配空间：如果知道元素数量，可以预先 reserve 空间

2. 使用emplace：C++11+ 推荐使用 emplace 避免临时对象

3. 利用有序特性：有序容器支持范围查询和有序遍历

4. 自定义比较函数：支持复杂类型的自定义排序

六、总结

map 和 set 是 C++ STL 中强大的关联式容器，基于红黑树实现，提供 O(log n) 的高效操作。它们的主要特点包括：

• 自动排序：元素按键值自动排序

• 快速查找：基于键的快速查找能力

• 唯一性：set/map 保证元素唯一性

• 灵活性：支持自定义比较函数和内存分配器

通过本文的详细解析和实际案例，相信读者已经能够深入理解 map 和 set 的工作原理，并能在实际开发中灵活运用这些强大的容器工具。

扩展阅读：

• C++ STL 源码分析

• 更多 LeetCode 容器相关题目

• C++ 标准文档