C++ STL 中 map 和 set 详解：从使用到红黑树底层理解

Emberone

373人浏览 · 2026-06-10 17:30:06

Emberone · 2026-06-10 17:30:06 发布

适合对象：正在学习 C++ STL、数据结构、关联式容器的同学。
本文重点：set、map、multiset、multimap 的使用、区别、常见接口、易错点，以及它们为什么底层通常用红黑树实现。

为什么要学习 map 和 set
序列式容器与关联式容器的区别
pair：理解 map 的前置知识
set 详解
multiset 详解
map 详解
multimap 详解
四个容器的对比总结
map 和 set 的底层：红黑树
为什么 key 不能被修改
常见使用场景
常见易错点总结
练习题与参考代码

1. 为什么要学习 map 和 set

在学习 vector、list、deque、stack、queue 之后，我们接触的大多数容器都是“按位置组织数据”的容器。

比如：

vector<int> v = {3, 1, 4, 2};

vector 关心的是：

第 0 个元素是谁？
第 1 个元素是谁？
能不能尾插？
能不能随机访问？

但是在很多实际问题中，我们更关心的是：

某个值有没有出现过？
某个单词出现了几次？
某个 key 对应的 value 是什么？
如何边插入边保持数据有序？

这时候 map 和 set 就非常有用。

例如：

set<int> s;              // 判断某个数字是否出现过，并自动排序去重
map<string, int> count;  // 统计每个单词出现的次数

简单记忆：

set：key 模型，只存 key
map：key-value 模型，存 key 和 value 的映射关系

2. 序列式容器与关联式容器的区别

2.1 序列式容器

常见序列式容器：

vector
list
deque
forward_list

它们的特点是：

1. 元素按线性顺序存储。
2. 容器主要关心元素的位置。
3. 查找某个值通常需要遍历，时间复杂度可能是 O(N)。

例如：

vector<int> v = {10, 20, 30, 40};

查找 30 可能要从头往后找。

2.2 关联式容器

常见关联式容器：

set
multiset
map
multimap

它们的特点是：

1. 通过 key 来组织数据。
2. 查找、插入、删除效率较高。
3. 元素默认有序。
4. 底层通常是平衡搜索树，也就是红黑树。

例如：

set<int> s = {3, 1, 4, 2};

遍历结果不是插入顺序，而是：

1 2 3 4

3. pair：理解 map 的前置知识

在正式学习 map 之前，必须先理解 pair。

pair 是一个存放两个数据的结构，常用于表示键值对。

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

int main()
{
    pair<string, string> kv("sort", "排序");

    cout << kv.first << endl;   // sort
    cout << kv.second << endl;  // 排序

    return 0;
}

其中：

first  表示第一个成员，通常理解为 key
second 表示第二个成员，通常理解为 value

也可以使用 make_pair 创建：

pair<string, int> kv = make_pair("apple", 3);

还可以使用大括号隐式构造：

pair<string, int> kv = {"apple", 3};

map 中存储的元素，本质上就是一个个 pair。

例如：

map<string, int> m;

其中每个元素可以理解为：

pair<const string, int>

注意这里是 const string，也就是 map 中的 key 不能被修改。

4. set 详解

4.1 set 是什么

set 是一个按照一定顺序存储元素的容器。

它有两个非常重要的特点：

1. 自动排序
2. 自动去重

例如：

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

int main()
{
    set<int> s;

    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(1);
    s.insert(5);

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    return 0;
}

输出：

1 2 3 5

虽然插入了两次 1，但是 set 中只保留一个。

4.2 set 的头文件

使用 set 需要包含头文件：

#include <set>

4.3 set 的定义方式

set<int> s1;
set<string> s2;
set<double> s3;

也可以用已有区间构造：

vector<int> v = {3, 2, 8, 1, 10, 2};
set<int> s(v.begin(), v.end());

输出：

1 2 3 8 10

这个写法经常用来对数组或 vector 进行排序去重。

4.4 set 的插入 insert

set<int> s;

s.insert(10);
s.insert(20);
s.insert(10);

因为 set 不允许重复，所以第二次插入 10 会失败。

insert 的返回值是：

pair<iterator, bool>

例如：

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

int main()
{
    set<int> s;

    auto ret1 = s.insert(10);
    auto ret2 = s.insert(10);

    cout << ret1.second << endl; // 1，插入成功
    cout << ret2.second << endl; // 0，插入失败

    return 0;
}

其中：

ret.first  表示元素所在位置的迭代器
ret.second 表示是否插入成功

4.5 set 的遍历

范围 for 遍历

for (auto e : s)
{
    cout << e << " ";
}

迭代器遍历

set<int>::iterator it = s.begin();
while (it != s.end())
{
    cout << *it << " ";
    ++it;
}

反向遍历

for (auto it = s.rbegin(); it != s.rend(); ++it)
{
    cout << *it << " ";
}

如果：

set<int> s = {1, 2, 3, 4, 5};

正向遍历：

1 2 3 4 5

反向遍历：

5 4 3 2 1

4.6 set 的查找 find

auto pos = s.find(3);

if (pos != s.end())
{
    cout << "找到了：" << *pos << endl;
}
else
{
    cout << "没找到" << endl;
}

注意，判断是否找到时，必须和 end() 比较。

错误写法：

if (s.find(3)) // 错误思路
{
}

正确写法：

if (s.find(3) != s.end())
{
}

4.7 set 的 count

cout << s.count(3) << endl;
cout << s.count(100) << endl;

对于 set 来说，count 的结果只可能是：

0：不存在
1：存在

因为 set 中元素不允许重复。

所以也可以用 count 判断元素是否存在：

if (s.count(x))
{
    cout << "存在" << endl;
}
else
{
    cout << "不存在" << endl;
}

4.8 set 的删除 erase

按值删除

s.erase(3);

如果 3 存在，就删除；如果不存在，也不会报错。

按迭代器删除

auto pos = s.find(3);
if (pos != s.end())
{
    s.erase(pos);
}

注意：按迭代器删除之前，最好先判断迭代器是否有效。

删除一个区间

s.erase(first, last);

删除范围是：

[first, last)

也就是左闭右开。

4.9 lower_bound 和 upper_bound

这是 set 中非常常用但容易忘的两个接口。

lower_bound(x) 返回第一个 >= x 的位置
upper_bound(x) 返回第一个 > x 的位置

例子：

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

int main()
{
    set<int> myset;

    for (int i = 1; i < 10; i++)
    {
        myset.insert(i * 10);
    }

    // myset: 10 20 30 40 50 60 70 80 90

    auto itlow = myset.lower_bound(25); // 30
    auto itup = myset.upper_bound(60);  // 70

    myset.erase(itlow, itup);

    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;

    return 0;
}

删除的是：

[30, 70)

也就是：

30 40 50 60

最后剩下：

10 20 70 80 90

4.10 set 为什么不能修改元素

下面这段代码是错误的：

set<int> s = {1, 2, 3};

auto it = s.find(2);
*it = 20; // 错误

原因是：set 的底层是搜索树，元素的值本身就是 key，key 决定了这个节点在树中的位置。

如果允许直接修改元素，树的有序结构可能被破坏。

例如：

set<int> s = {1, 2, 3};

如果把 2 直接改成 100，它的位置就不应该还在 1 和 3 中间。

所以 set 禁止直接修改元素。

正确做法是：

s.erase(2);
s.insert(100);

5. multiset 详解

5.1 multiset 是什么

multiset 和 set 很像，但有一个关键区别：

set       不允许重复
multiset  允许重复

例如：

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

int main()
{
    multiset<int> s;

    s.insert(1);
    s.insert(1);
    s.insert(2);
    s.insert(2);
    s.insert(2);
    s.insert(3);

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    return 0;
}

输出：

1 1 2 2 2 3

所以可以记：

set       排序 + 去重
multiset  排序 + 不去重

5.2 multiset 的 count

对于 multiset：

multiset<int> s = {1, 1, 2, 2, 2, 3};

cout << s.count(2) << endl;

输出：

这和 set 不同。

set 的 count 只能是 0 或 1，而 multiset 的 count 可以大于 1。

5.3 multiset 的 find

auto pos = s.find(2);

如果有多个 2，find 返回的是其中一个 2 的位置，通常是第一个可以找到的位置。

如果想遍历所有等于 2 的元素，可以写：

auto pos = s.find(2);
while (pos != s.end() && *pos == 2)
{
    cout << *pos << " ";
    ++pos;
}

更推荐使用 equal_range：

auto range = s.equal_range(2);

for (auto it = range.first; it != range.second; ++it)
{
    cout << *it << " ";
}

6. map 详解

6.1 map 是什么

map 是一种 key-value 结构的关联式容器。

可以把它理解成字典。

例如：

map<string, string> dict;

dict["sort"] = "排序";
dict["left"] = "左边";
dict["right"] = "右边";

逻辑上可以理解为：

sort  -> 排序
left  -> 左边
right -> 右边

map 的核心特点：

1. 每个元素都是 key-value 键值对。
2. key 唯一，不能重复。
3. 默认按照 key 从小到大排序。
4. key 不能修改，value 可以修改。
5. 查找、插入、删除时间复杂度通常是 O(logN)。
6. 底层通常是红黑树。

6.2 map 的头文件

使用 map 需要包含：

#include <map>

6.3 map 的定义方式

map<string, string> dict;
map<string, int> countMap;
map<int, string> idName;

含义分别是：

string -> string
string -> int
int    -> string

6.4 map 的插入方式

方式一：使用 pair

map<string, string> dict;

pair<string, string> kv("sort", "排序");
dict.insert(kv);

方式二：直接构造 pair

dict.insert(pair<string, string>("left", "左边"));

方式三：使用 make_pair

dict.insert(make_pair("right", "右边"));

方式四：使用大括号

dict.insert({"string", "字符串"});

方式五：使用 operator[]

dict["map"] = "映射";

6.5 insert 不会覆盖已有 key

这是 map 里非常重要的点。

map<string, string> dict;

dict.insert({"right", "右边"});
dict.insert({"right", "错误"});

cout << dict["right"] << endl;

输出：

右边

原因：

map 中 key 是唯一的。
如果 key 已经存在，insert 会插入失败，不会覆盖原 value。

如果想修改已有 value，应该使用：

dict["right"] = "右侧";

6.6 map 的 insert 返回值

map 的 insert 返回值也是：

pair<iterator, bool>

例如：

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

int main()
{
    map<string, string> dict;

    auto ret = dict.insert({"apple", "苹果"});

    if (ret.second)
    {
        cout << "插入成功" << endl;
    }
    else
    {
        cout << "插入失败" << endl;
    }

    return 0;
}

其中：

ret.first  指向 key 所在位置的迭代器
ret.second 表示是否插入成功

如果插入失败，ret.first 仍然指向已经存在的那个 key。

6.7 map 的遍历

方式一：迭代器遍历

map<string, string> dict;

dict.insert({"sort", "排序"});
dict.insert({"left", "左边"});
dict.insert({"right", "右边"});

auto it = dict.begin();
while (it != dict.end())
{
    cout << it->first << ":" << it->second << endl;
    ++it;
}

这里：

it->first
it->second

等价于：

(*it).first
(*it).second

方式二：范围 for

for (auto& kv : dict)
{
    cout << kv.first << ":" << kv.second << endl;
}

建议使用引用：

for (auto& kv : dict)

而不是：

for (auto kv : dict)

因为不加引用会拷贝每个键值对。

方式三：C++17 结构化绑定

for (auto& [key, value] : dict)
{
    cout << key << ":" << value << endl;
}

这个写法很清晰，但需要 C++17 支持。

6.8 map 的 key 不能修改，value 可以修改

map<string, string> dict;

dict["sort"] = "排序";

auto it = dict.begin();

// it->first += "x";  // 错误：key 不能修改
it->second += "算法"; // 正确：value 可以修改

原因：

map 按 key 在搜索树中排序。
如果允许修改 key，会破坏树的有序结构。

6.9 map 的 find

auto pos = dict.find("sort");

if (pos != dict.end())
{
    cout << pos->first << ":" << pos->second << endl;
}
else
{
    cout << "没找到" << endl;
}

查找是否存在时，推荐使用：

if (dict.find(key) != dict.end())

6.10 map 的 count

因为 map 中 key 唯一，所以：

dict.count(key)

结果只可能是：

0：不存在
1：存在

例如：

if (dict.count("sort"))
{
    cout << "存在" << endl;
}
else
{
    cout << "不存在" << endl;
}

6.11 map 的 erase

按 key 删除

dict.erase("sort");

按迭代器删除

auto pos = dict.find("sort");
if (pos != dict.end())
{
    dict.erase(pos);
}

删除区间

dict.erase(dict.begin(), dict.end());

等价于清空。

6.12 map 的 operator[] 详解

operator[] 是 map 最重要、也最容易出错的接口。

例如：

map<string, int> countMap;

countMap["苹果"]++;

这行代码背后有两种情况。

情况一：key 已经存在

如果 "苹果" 已经存在，那么：

countMap["苹果"]

会返回它对应的 value 的引用，然后执行 ++。

情况二：key 不存在

如果 "苹果" 不存在，那么：

countMap["苹果"]

会先插入一个默认键值对：

{"苹果", 0}

然后返回 value 的引用，再执行 ++。

所以：

countMap["苹果"]++;

第一次执行后，结果就是：

苹果 -> 1

6.13 operator[] 的底层逻辑

可以简单理解为：

V& operator[](const K& key)
{
    pair<iterator, bool> ret = insert(make_pair(key, V()));
    return ret.first->second;
}

也就是说：

1. 用 key 和 V() 构造一个默认键值对。
2. 调用 insert 尝试插入。
3. 无论插入成功还是失败，ret.first 都指向 key 所在位置。
4. 返回该位置 value 的引用。

这就是为什么 map 可以这样统计次数：

countMap[e]++;

6.14 operator[] 和 at 的区别

map<string, int> m;

operator[]

cout << m["apple"] << endl;

如果 apple 不存在，会自动插入：

{"apple", 0}

at

cout << m.at("apple") << endl;

如果 apple 不存在，会抛异常。

所以：

m[key]

适合：

插入
修改
计数

而：

m.at(key)

适合：

确定 key 存在时访问

如果只是判断某个 key 是否存在，不建议使用 []，因为它可能会插入新元素。

6.15 map 统计次数经典例子

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

int main()
{
    string arr[] = {
        "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
        "苹果", "香蕉", "苹果", "香蕉", "苹果", "草莓", "苹果", "草莓"
    };

    map<string, int> countMap;

    for (auto& e : arr)
    {
        countMap[e]++;
    }

    for (auto& kv : countMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }

    return 0;
}

这段代码的核心是：

countMap[e]++;

含义是：

如果 e 不存在，先插入 {e, 0}，然后 ++。
如果 e 已存在，直接对次数 ++。

7. multimap 详解

7.1 multimap 是什么

multimap 和 map 的关系类似于 multiset 和 set 的关系。

map       key 唯一
multimap  key 可以重复

例如：

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

int main()
{
    multimap<int, string> m;

    m.insert({1, "张三"});
    m.insert({1, "李四"});
    m.insert({2, "王五"});

    for (auto& kv : m)
    {
        cout << kv.first << ":" << kv.second << endl;
    }

    return 0;
}

输出可能是：

1:张三
1:李四
2:王五

7.2 multimap 为什么没有 operator[]

map 可以写：

m[key]

因为一个 key 只对应一个 value。

但是 multimap 中，一个 key 可以对应多个 value。

例如：

1 -> 张三
1 -> 李四

如果写：

m[1]

到底应该返回 张三，还是 李四？

无法确定。

所以 multimap 没有 operator[]。

必须使用：

m.insert({key, value});

7.3 multimap 的使用场景

multimap 适合一个 key 对应多个 value 的场景。

例如：

分数 -> 学生姓名
部门 -> 员工姓名
出现次数 -> 单词

一个例子：先统计水果次数，再按次数排序。

map<string, int> countMap;
multimap<int, string> sortMap;

for (auto& kv : countMap)
{
    sortMap.insert({kv.second, kv.first});
}

这里把：

水果 -> 次数

转换成：

次数 -> 水果

这样就可以按照次数排序。

8. 四个容器的对比总结

容器	存储模型	key 是否唯一	是否有序	是否支持 `[]`	常见用途
`set`	key	唯一	有序	不支持	排序、去重、判断存在
`multiset`	key	可重复	有序	不支持	排序、保留重复元素
`map`	key-value	唯一	按 key 有序	支持	字典、计数、映射关系
`multimap`	key-value	可重复	按 key 有序	不支持	一个 key 对应多个 value

一句话记忆：

set       只有 key，key 唯一
multiset  只有 key，key 可重复

map       key-value，key 唯一
multimap  key-value，key 可重复

9. map 和 set 的底层：红黑树

9.1 它们的底层是什么

set、map、multiset、multimap 的底层通常是：

红黑树

红黑树是一种：

近似平衡的二叉搜索树

所以这些容器天然具有以下特点：

1. 元素有序。
2. 查找效率高。
3. 插入效率高。
4. 删除效率高。
5. 查找、插入、删除通常都是 O(logN)。

9.2 为什么不是普通二叉搜索树

普通二叉搜索树有一个严重问题：可能退化成链表。

例如按顺序插入：

1 2 3 4 5 6 7

普通搜索树可能变成：

这时候查找就不是 O(logN)，而是退化成：

O(N)

所以 map 和 set 不能直接用普通二叉搜索树，而要使用平衡搜索树。

9.3 AVL 树和红黑树的区别

平衡搜索树常见有：

AVL 树
红黑树

AVL 树

AVL 树是高度平衡的二叉搜索树。

它要求每个节点左右子树高度差的绝对值不超过 1。

优点：

查找效率非常高。

缺点：

插入和删除时，为了维持严格平衡，可能需要更多旋转。

红黑树

红黑树不追求绝对平衡，而是追求近似平衡。

它通过节点颜色和若干规则保证树不会太高。

优点：

插入、删除时旋转次数相对较少，综合性能更好。

所以在实际工程中，map 和 set 通常使用红黑树。

9.4 红黑树的基本性质

红黑树是二叉搜索树，每个节点有颜色：

RED
BLACK

常见性质：

1. 每个节点不是红色就是黑色。
2. 根节点是黑色。
3. 如果一个节点是红色，那么它的孩子必须是黑色。
4. 从任意节点到其所有后代叶子节点的路径上，黑色节点数量相同。
5. 空节点也被认为是黑色。

这些性质保证红黑树不会退化得太严重。

9.5 为什么遍历 map/set 是有序的

红黑树本质上仍然是二叉搜索树。

二叉搜索树的特点是：

左子树 < 根 < 右子树

对二叉搜索树进行中序遍历，得到的就是有序序列。

所以：

set<int> s = {3, 1, 5, 2};

遍历输出：

1 2 3 5

map 也是按照 key 有序，而不是按照 value 有序。

例如：

map<string, int> m;

m["banana"] = 3;
m["apple"] = 5;
m["orange"] = 1;

遍历顺序是按照 key 排序：

apple
banana
orange

不是按照 value 排序。

10. 为什么 key 不能被修改

这一点非常重要。

无论是 set 还是 map，只要元素在树中，key 就不能被直接修改。

原因是：

key 决定节点在树中的位置。

如果 key 被修改，原来的树结构可能就不满足搜索树规则。

10.1 set 中为什么元素不能修改

set 中 value 本身就是 key。

set<int> s = {1, 2, 3};

如果允许：

*it = 100;

那原来位于 1 和 3 中间的节点，突然变成 100，树的有序关系就乱了。

所以 set 的迭代器不能修改元素。

10.2 map 中为什么 first 不能修改

map 中每个元素是：

pair<const K, V>

所以：

kv.first  不能改
kv.second 可以改

例如：

map<string, int> m;

m["apple"] = 1;

for (auto& kv : m)
{
    // kv.first = "banana"; // 错误
    kv.second = 10;         // 正确
}

11. 常见使用场景

11.1 set：排序去重

vector<int> v = {3, 1, 2, 3, 5, 1};
set<int> s(v.begin(), v.end());

for (auto e : s)
{
    cout << e << " ";
}

输出：

1 2 3 5

11.2 set：判断元素是否存在

set<int> s = {1, 3, 5, 7};

if (s.count(3))
{
    cout << "存在" << endl;
}

11.3 map：做字典

map<string, string> dict;

dict["sort"] = "排序";
dict["string"] = "字符串";
dict["left"] = "左边";

string word;
cin >> word;

if (dict.count(word))
{
    cout << dict[word] << endl;
}
else
{
    cout << "查无此词" << endl;
}

11.4 map：统计次数

map<string, int> countMap;

string arr[] = {"apple", "banana", "apple", "orange", "banana", "apple"};

for (auto& e : arr)
{
    countMap[e]++;
}

for (auto& kv : countMap)
{
    cout << kv.first << ":" << kv.second << endl;
}

11.5 multimap：一个 key 对应多个 value

multimap<string, string> classes;

classes.insert({"一班", "张三"});
classes.insert({"一班", "李四"});
classes.insert({"二班", "王五"});

for (auto& kv : classes)
{
    cout << kv.first << ":" << kv.second << endl;
}

12. 常见易错点总结

易错点 1：set 和 map 遍历不是插入顺序

set<int> s = {3, 1, 2};

输出：

1 2 3

不是：

3 1 2

易错点 2：set 不能修改元素

set<int> s = {1, 2, 3};

auto it = s.find(2);
// *it = 20; // 错误

正确：

s.erase(2);
s.insert(20);

易错点 3：map 的 key 不能修改，value 可以修改

map<string, int> m;

m["apple"] = 1;

for (auto& kv : m)
{
    // kv.first = "banana"; // 错误
    kv.second = 10;         // 正确
}

易错点 4：insert 不会覆盖已有 key

map<string, string> m;

m.insert({"right", "右边"});
m.insert({"right", "错误"});

cout << m["right"] << endl;

输出：

右边

如果要修改，应该写：

m["right"] = "错误";

易错点 5：map 的 [] 可能会插入新 key

map<string, int> m;

cout << m["apple"] << endl;
cout << m.size() << endl;

输出：

0
1

因为 m["apple"] 会插入：

{"apple", 0}

如果只是想判断是否存在，不要用 []。

易错点 6：multimap 没有 []

multimap<int, string> m;

// m[1] = "张三"; // 错误

正确：

m.insert({1, "张三"});
m.insert({1, "李四"});

易错点 7：map 按 key 排序，不按 value 排序

map<string, int> m;

m["banana"] = 1;
m["apple"] = 100;
m["orange"] = 2;

遍历顺序：

apple
banana
orange

不是按照 100、2、1 排序。

13. 练习题与参考代码

题 1：set 输出结果

set<int> s = {5, 1, 3, 1, 2, 5};

for (auto e : s)
{
    cout << e << " ";
}

输出：

1 2 3 5

原因：set 自动排序并去重。

题 2：map 的 [] 行为

map<string, int> m;

m["apple"]++;
m["banana"]++;
m["apple"]++;

cout << m["apple"] << endl;
cout << m["banana"] << endl;
cout << m["pear"] << endl;
cout << m.size() << endl;

输出：

解释：

m["apple"] 第一次插入 apple->0，然后 ++，变成 1
m["banana"] 第一次插入 banana->0，然后 ++，变成 1
m["apple"] 第二次已经存在，直接 ++，变成 2
m["pear"] 不存在，会插入 pear->0

所以最终 size 是 3。

题 3：insert 是否覆盖

map<string, string> dict;

dict.insert({"right", "右边"});
dict.insert({"right", "错误"});

cout << dict["right"] << endl;

输出：

右边

原因：insert 不会覆盖已有 key。

题 4：统计水果次数

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

int main()
{
    string arr[] = {
        "苹果", "西瓜", "苹果", "西瓜", "苹果",
        "香蕉", "苹果", "草莓", "草莓"
    };

    map<string, int> countMap;

    for (auto& e : arr)
    {
        countMap[e]++;
    }

    for (auto& kv : countMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }

    return 0;
}

这个例子一定要掌握，因为它体现了 map 最常用的功能：统计次数。

题 5：删除 set 中一个区间

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

int main()
{
    set<int> s = {10, 20, 30, 40, 50, 60, 70, 80, 90};

    auto left = s.lower_bound(25); // 30
    auto right = s.upper_bound(60); // 70

    s.erase(left, right);

    for (auto e : s)
    {
        cout << e << " ";
    }

    return 0;
}

输出：

10 20 70 80 90

14. 最后总结

今天复习 map 和 set，最重要的是掌握以下主线：

1. set 是 key 模型：排序 + 去重。
2. map 是 key-value 模型：通过 key 找 value。
3. multiset 允许 key 重复。
4. multimap 允许 key 重复，所以没有 operator[]。
5. map/set 底层通常是红黑树。
6. 红黑树是一种近似平衡的二叉搜索树。
7. 因为底层是搜索树，所以元素遍历有序。
8. 因为 key 决定树中位置，所以 key 不能修改。
9. map 的 operator[] 在 key 不存在时会插入默认 value。
10. insert 不会覆盖已有 key。

建议你真正敲熟下面两个例子：

set 排序去重
map 统计次数

只要这两个例子理解透，map 和 set 的大部分基础用法就掌握了。

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

圆满落幕｜智驱迭代・昇腾赋能 AI Agent 行业实践 Meetup 上海站，全栈落地干货一次吃透

AtomGit开源社区

AtomGit 2026年6月三方库下载量排行榜重磅发布！双榜格局稳固，生态深耕持续发力

AtomGit开源社区

G-Star 精选开源项目推荐｜第十八期

AtomGit开源社区

所有评论(0)

查看更多评论

Emberone

@m0_62867859

已为社区贡献3条内容

C++ STL 中 map 和 set 详解：从使用到红黑树底层理解

Emberone

目录

1. 为什么要学习 map 和 set

2. 序列式容器与关联式容器的区别

2.1 序列式容器

2.2 关联式容器

3. pair：理解 map 的前置知识

4. set 详解

4.1 set 是什么

4.2 set 的头文件

4.3 set 的定义方式

4.4 set 的插入 insert

4.5 set 的遍历

范围 for 遍历

迭代器遍历

反向遍历

4.6 set 的查找 find

4.7 set 的 count

4.8 set 的删除 erase

按值删除

按迭代器删除

删除一个区间

4.9 lower_bound 和 upper_bound

4.10 set 为什么不能修改元素

5. multiset 详解

5.1 multiset 是什么

5.2 multiset 的 count

5.3 multiset 的 find

6. map 详解

6.1 map 是什么

6.2 map 的头文件

6.3 map 的定义方式

6.4 map 的插入方式

方式一：使用 pair

方式二：直接构造 pair

方式三：使用 make_pair

方式四：使用大括号

方式五：使用 operator[]

6.5 insert 不会覆盖已有 key

6.6 map 的 insert 返回值

6.7 map 的遍历

方式一：迭代器遍历

方式二：范围 for

方式三：C++17 结构化绑定

6.8 map 的 key 不能修改，value 可以修改

6.9 map 的 find

6.10 map 的 count

6.11 map 的 erase

按 key 删除

按迭代器删除

删除区间

6.12 map 的 operator[] 详解

情况一：key 已经存在

情况二：key 不存在

6.13 operator[] 的底层逻辑

6.14 operator[] 和 at 的区别

operator[]

at

6.15 map 统计次数经典例子

7. multimap 详解

7.1 multimap 是什么

7.2 multimap 为什么没有 operator[]

7.3 multimap 的使用场景

8. 四个容器的对比总结

9. map 和 set 的底层：红黑树

9.1 它们的底层是什么

9.2 为什么不是普通二叉搜索树

9.3 AVL 树和红黑树的区别

AVL 树

红黑树

9.4 红黑树的基本性质

9.5 为什么遍历 map/set 是有序的

10. 为什么 key 不能被修改

10.1 set 中为什么元素不能修改

10.2 map 中为什么 first 不能修改

11. 常见使用场景

11.1 set：排序去重

11.2 set：判断元素是否存在

11.3 map：做字典