C++ STL 中 map 和 set 的使用详解

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

在学习 map 和 set 之前，我们先了解 STL 中两类常见容器：序列式容器 和 关联式容器。

我们之前接触过的 string、vector、list、deque、array、forward_list 等都属于序列式容器。

序列式容器的特点是：
元素之间按照线性顺序存储，主要依靠元素在容器中的位置进行访问。

而 map 和 set 属于关联式容器。

关联式容器的特点是：
元素之间不是单纯按照插入顺序存储，而是按照关键字 key 进行组织和访问。

STL 中常见的关联式容器主要分为两类：

容器	底层结构	是否有序
set / map	红黑树	有序
unordered_set / unordered_map	哈希表	无序

本文主要介绍基于红黑树实现的 set 和 map。

由于 set 和 map 底层通常是红黑树，所以它们的插入、删除、查找效率一般都是：

O(logN)

---

二、set 的使用

1. set 的基本概念

set 是一种只存储 key 的关联式容器。

它有两个重要特点：

1. 自动去重。
2. 默认按照升序排序。

set 的模板声明如下：

template <class T,
          class Compare = less<T>,
          class Alloc = allocator<T>>
class set;

其中：

• T：set 中存储的数据类型。
• Compare：比较规则，默认是 less<T>，也就是升序。
• Alloc：空间配置器，一般情况下不需要关心。

常见使用方式：

set<int> s;                // 默认升序
set<int, greater<int>> s2; // 降序

---

2. set 的构造

set 常见构造方式如下：

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

int main()
{
    set<int> s1;                         // 默认构造
    set<int> s2 = { 5, 2, 7, 2, 8 };      // initializer_list 构造

    int arr[] = { 3, 1, 4, 1, 5 };
    set<int> s3(arr, arr + 5);            // 迭代器区间构造

    set<int> s4(s3);                      // 拷贝构造

    return 0;
}

因为 set 会自动去重并排序，所以：

set<int> s = { 5, 2, 7, 2, 8 };

最终存储结果为：

2 5 7 8

---

3. set 的遍历

set 支持迭代器遍历，也支持范围 for。

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

int main()
{
    set<int> s = { 5, 2, 7, 2, 8 };

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

    cout << endl;

    return 0;
}

输出结果：

2 5 7 8

因为 set 底层是搜索树结构，迭代器遍历时走的是中序遍历，所以默认结果是升序的。

如果想让 set 降序排列，可以使用 greater<int>：

set<int, greater<int>> s = { 5, 2, 7, 2, 8 };

输出结果：

8 7 5 2

需要注意的是，set 的迭代器不能修改元素。

auto it = s.begin();

// *it = 10; // 错误

原因是 set 中的元素本身就是关键字，修改关键字可能会破坏底层搜索树结构。

---

4. set 的插入

set 使用 insert 插入元素。

set<int> s;

s.insert(5);
s.insert(2);
s.insert(7);
s.insert(5);

由于 set 不允许元素重复，所以第二次插入 5 会失败。

单个元素插入的返回值是：

pair<iterator, bool>

其中：

• first：指向插入元素所在位置的迭代器。
• second：表示是否插入成功。

示例：

auto ret = s.insert(5);

if (ret.second)
{
    cout << "插入成功" << endl;
}
else
{
    cout << "插入失败，元素已经存在" << endl;
}

也可以一次插入多个元素：

s.insert({ 2, 8, 3, 9 });

还可以插入一段迭代器区间：

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

s.insert(v.begin(), v.end());

---

5. set 的查找

set 中常用的查找接口有两个：

find
count

find

auto pos = s.find(7);

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

set 自身的 find 查找效率是：

O(logN)

不建议使用算法库中的 find 查找 set：

auto pos1 = find(s.begin(), s.end(), 7); // O(N)
auto pos2 = s.find(7);                   // O(logN)

对于 set 来说，应该优先使用容器自身提供的 find。

count

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

因为 set 不允许元素重复，所以 count 的返回值只有两种情况：

0 或 1

---

6. set 的删除

set 常见删除方式有三种。

按值删除

int num = s.erase(7);

if (num == 0)
{
    cout << "删除失败，元素不存在" << endl;
}
else
{
    cout << "删除成功" << endl;
}

按迭代器删除

auto pos = s.find(7);

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

删除一段区间

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

s.erase(left, right);

其中：

lower_bound(x)

返回第一个大于等于 x 的位置。

upper_bound(x)

返回第一个大于 x 的位置。

示例：

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

auto itlow = s.lower_bound(30); // 指向 30
auto itup = s.upper_bound(60);  // 指向 70

s.erase(itlow, itup);

删除的是：

30 40 50 60

删除后剩余：

10 20 70 80 90

---

三、multiset 的使用

multiset 和 set 的使用方式基本类似。

它们的主要区别是：

容器	是否排序	是否去重
set	是	是
multiset	是	否

示例：

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

int main()
{
    multiset<int> s = { 4, 2, 7, 2, 4, 8, 4, 5, 4, 9 };

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

    cout << endl;

    return 0;
}

输出结果：

2 2 4 4 4 4 5 7 8 9

1. multiset 的 count

multiset 允许元素重复，所以 count 返回的是某个元素真实出现的次数。

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

如果 4 出现了 4 次，那么输出：

4

2. multiset 的 erase

对于 multiset 来说：

s.erase(4);

会删除所有值为 4 的元素。

如果只想删除一个 4，应该使用迭代器删除：

auto pos = s.find(4);

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

---

四、map 的使用

1. map 的基本概念

map 是一种存储键值对的关联式容器。

它的特点是：

1. 每个元素都是一个 key-value 键值对。
2. key 不允许重复。
3. 默认按照 key 升序排序。
4. 可以通过 key 快速查找对应的 value。

map 的模板声明如下：

template <class Key,
          class T,
          class Compare = less<Key>,
          class Alloc = allocator<pair<const Key, T>>>
class map;

其中：

• Key：关键字类型。
• T：映射值类型。
• Compare：比较规则，默认按照 key 升序。
• Alloc：空间配置器，一般不需要关心。

常见使用方式：

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

---

2. pair 类型

map 底层存储的是键值对，也就是 pair。

pair<const Key, T>

pair 有两个成员：

first
second

对于：

map<string, int> m;

其中：

• first 表示 key
• second 表示 value

示例：

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

cout << kv.first << endl;   // apple
cout << kv.second << endl;  // 3

也可以使用 make_pair 创建：

auto kv = make_pair("apple", 3);

---

3. map 的构造和遍历

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

int main()
{
    map<string, string> dict = {
        {"left", "左边"},
        {"right", "右边"},
        {"insert", "插入"},
        {"string", "字符串"}
    };

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

    return 0;
}

map 遍历时会按照 key 的升序顺序输出。

需要注意：

auto it = dict.begin();

// it->first = "new";   // 错误，key 不能修改
it->second = "新的值";  // 正确，value 可以修改

原因是 key 决定了红黑树中的存储位置，修改 key 会破坏搜索树结构。

---

4. map 的插入

map 插入的是键值对。

常见插入方式如下：

map<string, string> dict;

pair<string, string> kv1("first", "第一个");
dict.insert(kv1);

dict.insert(pair<string, string>("second", "第二个"));

dict.insert(make_pair("sort", "排序"));

dict.insert({ "auto", "自动的" });

其中比较推荐的写法是：

dict.insert(make_pair("sort", "排序"));
dict.insert({ "auto", "自动的" });

如果 key 已经存在，插入会失败。

dict.insert({ "left", "左边" });
dict.insert({ "left", "左边，剩余" }); // 插入失败

因为 map 不允许 key 重复。

---

5. map 的查找

auto ret = dict.find("left");

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

find 返回的是迭代器。

通过迭代器可以访问：

ret->first;   // key
ret->second;  // value

也可以使用 count 判断某个 key 是否存在：

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

因为 map 中的 key 不允许重复，所以 count 的返回值也是：

0 或 1

---

6. map 的删除

map 的删除方式和 set 类似。

按 key 删除

dict.erase("left");

按迭代器删除

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

if (pos != dict.end())
{
    dict.erase(pos);
}

删除区间

auto left = dict.lower_bound("a");
auto right = dict.upper_bound("m");

dict.erase(left, right);

---

五、map 的 operator[] 详解

map 中有一个非常重要的接口：

operator[]

它不仅可以查找，还可以插入和修改。

示例：

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

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

    dict["insert"];              // key 不存在，插入 {"insert", string()}
    dict["left"] = "左边";        // 插入 + 修改
    dict["left"] = "左边、剩余";   // 修改
    cout << dict["left"] << endl; // 查找

    return 0;
}

operator[] 的底层逻辑可以理解为：

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

也就是说：

1. 如果 key 不存在，会插入一个默认值。
2. 如果 key 已经存在，会返回对应 value 的引用。
3. 因为返回的是引用，所以可以直接修改 value。

---

1. 使用 find 统计水果出现次数

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

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

    map<string, int> countMap;

    for (const auto& str : arr)
    {
        auto ret = countMap.find(str);

        if (ret == countMap.end())
        {
            countMap.insert({ str, 1 });
        }
        else
        {
            ret->second++;
        }
    }

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

    return 0;
}

---

2. 使用 operator[] 统计水果出现次数

上面的代码可以使用 operator[] 进行简化。

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

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

    map<string, int> countMap;

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

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

    return 0;
}

这段代码非常经典。

当某个水果第一次出现时：

countMap[str]

会先插入：

{ str, 0 }

然后执行：

++

次数变成 1。

如果这个水果已经存在，就直接让它对应的次数加一。

---

六、multimap 的使用

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

容器	key 是否允许重复	是否支持 operator[]
map	不允许	支持
multimap	允许	不支持

multimap 不支持 operator[]。

原因是 multimap 允许多个相同的 key 存在，如果写：

mm["apple"]

那么当存在多个 "apple" 时，到底应该返回哪一个 value 就不明确了。

所以 multimap 只能通过 insert 插入数据。

multimap<string, int> mm;

mm.insert({ "apple", 1 });
mm.insert({ "apple", 2 });
mm.insert({ "banana", 3 });

---

七、set 和 map 的典型应用

1. set 解决两个数组的交集

题目：给定两个数组，返回它们的交集。

思路：

1. 使用 set 对两个数组去重并排序。
2. 使用两个迭代器进行有序序列比较。
3. 相等时加入结果数组。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());

        vector<int> ret;

        auto it1 = s1.begin();
        auto it2 = s2.begin();

        while (it1 != s1.end() && it2 != s2.end())
        {
            if (*it1 < *it2)
            {
                ++it1;
            }
            else if (*it1 > *it2)
            {
                ++it2;
            }
            else
            {
                ret.push_back(*it1);
                ++it1;
                ++it2;
            }
        }

        return ret;
    }
};

---

2. set 解决环形链表 II

题目：判断链表是否有环，并返回入环节点。

思路：

1. 使用 set 存储已经访问过的节点地址。
2. 如果某个节点第二次出现，说明它就是入环点。
3. 如果遍历到空指针，说明无环。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;

        ListNode* cur = head;

        while (cur)
        {
            auto ret = s.insert(cur);

            if (ret.second == false)
            {
                return cur;
            }

            cur = cur->next;
        }

        return nullptr;
    }
};

这个方法非常直观，适合初学者理解。

---

3. map 解决随机链表的复制

题目：复制一个带随机指针的链表。

思路：

1. 先创建新链表。
2. 使用 map<Node*, Node*> 建立原节点和拷贝节点之间的映射关系。
3. 再根据映射关系处理 random 指针。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeMap;

        Node* copyhead = nullptr;
        Node* copytail = nullptr;

        Node* cur = head;

        while (cur)
        {
            if (copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }

            nodeMap[cur] = copytail;
            cur = cur->next;
        }

        cur = head;
        Node* copy = copyhead;

        while (cur)
        {
            if (cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                copy->random = nodeMap[cur->random];
            }

            cur = cur->next;
            copy = copy->next;
        }

        return copyhead;
    }
};

这里 map 的作用是建立原节点和新节点之间的一一映射关系。

---

4. map 解决前 K 个高频单词

题目：返回出现频率最高的前 k 个单词。
如果频率相同，按照字典序升序排列。

思路：

1. 使用 map<string, int> 统计每个单词出现次数。
2. 将统计结果放入 vector。
3. 按照次数降序、字典序升序排序。
4. 取前 k 个单词。

class Solution {
public:
    struct Compare
    {
        bool operator()(const pair<string, int>& x,
                        const pair<string, int>& y) const
        {
            return x.second > y.second ||
                  (x.second == y.second && x.first < y.first);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;

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

        vector<pair<string, int>> v(countMap.begin(), countMap.end());

        sort(v.begin(), v.end(), Compare());

        vector<string> ret;

        for (int i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }

        return ret;
    }
};

---

八、set、multiset、map、multimap 对比总结

容器	存储内容	是否排序	是否去重	是否支持 operator[]
set	key	是	是	否
multiset	key	是	否	否
map	key-value	是	key 去重	是
multimap	key-value	是	key 不去重	否

---

九、总结

set 和 map 都是 STL 中非常重要的关联式容器。

它们的底层通常是红黑树，所以插入、删除、查找效率一般都是：

O(logN)

set 适合只关心 key 的场景，例如：

• 去重
• 排序
• 快速查找

map 适合处理 key-value 映射关系，例如：

• 字典
• 计数统计
• 节点映射
• 数据索引

学习时需要重点掌握以下内容：

1. set 会自动排序并去重。
2. multiset 会自动排序但不去重。
3. map 存储的是键值对，key 不允许重复。
4. map 的 operator[] 具有查找、插入、修改三种功能。
5. multimap 允许 key 重复，因此不支持 operator[]。
6. set 和 map 的查找、插入、删除效率通常都是 O(logN)。
7. 遍历 set 和 map 时，默认都是有序的。

掌握 map 和 set 后，在处理去重、排序、映射、统计、查找类问题时，会更加方便高效。