【C++标准模版库】map和set的先容及利用

一、先分清序列式容器和关联式容器

之前用过的 string、vector、list、deque、array、forward_list 这一类，逻辑上都是线性序列：元素按在容器里的位置排着，两个位置的值之间通常没紧密关联，把它们换个顺序，它还是序列式容器，靠"位置"访问。

map 和 set 属于关联式容器，逻辑结构通常是非线性的：某个位置和另一个位置有紧密的绑定关系（比如一个 key 对应一个 value），换一下位置，整个存储结构就被破坏了。所以它们靠"关键字"访问，不靠下标。

具体分两大类：

• map/set 系列：底层是红黑树，一棵自平衡的二叉搜索树。set 服务于"只有 key"的查找场景，map 服务于"key 对应 value"的查找场景。
• unordered_map/unordered_set 系列：底层是哈希表，查找平均是常数级，但顺序不保证。

下面按 set、map 两条线走一遍，重点是构造、迭代、增删查这几个接口。

二、set 系列

2.1 模板声明

template < class T,                    // set::key_type / value_type
           class Compare = less<T>,    // set::key_compare / value_compare
           class Alloc = allocator<T>  // 空间配置器
           > class set;

三个参数里，T 是底层关键字的类型；Compare 默认要求 T 支持小于比较，如果要按自己的规则比（比如日期类想按先后比），就传一个仿函数进去；Alloc 是内存分配器，一般不用管。日常写代码只传第一个就行。

2.2 set 的四种构造

set<int> s1;                          // 无参默认构造
set<int> s2(v.begin(), v.end());      // 迭代器区间构造
set<int> s3(s2);                      // 拷贝构造
set<int> s4 = { 1,5,4,2,3 };          // initializer list 构造

遍历用正向迭代器，从 begin 到 end：

auto it = s2.begin();
while (it != s2.end())
{
    cout << *it << " ";
    ++it;
}

输出是 1 2 3 4 5 6 7 8 9 —— 升序。不要被"set 保序"这个结论骗了，顺序不是排序排出来的，而是迭代器走的中序遍历：二叉搜索树的性质是左子树小于根、根小于右子树，中序遍历自然就有序了。set 的迭代器是双向迭代器（支持 ++ 和 --，不支持 + n），所以反向遍历用 -- 走到 end 之前一个位置作为终止条件。

2.3 增删查：注意 set 不能改

pair<iterator, bool> insert(const value_type& val);   // 单个插入，已存在则失败
void insert(initializer_list<value_type> il);          // 列表插入，已存在的不插
iterator find(const key_type& k);                      // 找不到返回 end()
size_type count(const key_type& k) const;              // 个数，set 里只会是 0 或 1
size_type erase(const key_type& k);                    // 删除，返回删了几个

重点提醒：set 支持增删查，但不支持修改 key。因为改了 key 就破坏了红黑树的性质，底层结构直接失效。这就是 set 和 map 的迭代器都不能用来改元素的原因。

三、map 系列

3.1 模板声明与 pair 类型

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> >    // 空间配置器
           > class map;

这里有个容易混的地方：map 里的 T 我们习惯叫"value"，但类型名里它叫 mapped_type；而 value_type 指的是红黑树结点里存的那个 pair<const key_type, mapped_type>。记一句话就行：key_type 是 key，mapped_type / T 是 value，value_type 是整对。

3.2 四种构造与遍历

map<int, int> m1;                        // 无参
map<int, int> m2(m1.begin(), m1.end());  // 区间
map<int, int> m3(m2);                    // 拷贝
map<int, int> m4 = { {1,1},{2,2} };      // 列表初始化

遍历时产出的是 pair，pair 没有重载流插入，所以要分开打：

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

这里的 it-> 其实省了一个箭头：第一个 -> 是迭代器 operator-> 重载返回 pair*，第二个 -> 才是解引用取成员。

3.3 map 的增删查

pair<iterator, bool> insert(const value_type& val);   // key 已存在则插入失败
iterator find(const key_type& k);                      // 返回迭代器，能改 mapped_type
size_type count(const key_type& k) const;
size_type erase(const key_type& k);
iterator lower_bound(const key_type& k);               // 第一个 >= k 的位置
const_iterator upper_bound(const key_type& k) const;   // 第一个 > k 的位置

插入有四种写法，实际最常用 make_pair 和列表插入：

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

四、operator[] 是最常用的复合接口

map 的 operator[] 一个接口同时干三件事：查找、插入、修改。它的内部实现就是调 insert：

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

逻辑是：key 不在就插入一个 value 的默认值（对 int 是 0，对 string 是空串），然后把新值那格的引用返回；key 在就直接返回已有的那一格。所以统计词频可以直接这么写：

map<string, int> countMap;
for (const auto& str : arr)
    countMap[str]++;

对照一下用 find 的写法，可以看出 [] 确实省事很多。但也要知道它的副作用：对一个你以为"肯定存在"的 key 用 []，结果 key 不存在时它会偷偷插一条空记录，这是 bug 的常见来源，所以不确定存在与否时用 find 更安全。

五、multimap 和 unordered 系列的区别

• multimap 支持 key 冗余，同一 key 可以存多条，find 时返回中序第一个。它不支持 operator[]，因为没法确定该改哪一个。
• unordered_map/unordered_set 底层是哈希表，查询平均 O(1)，但遍历顺序是无序的，需要有序就还是用 map/set。

六、一个典型例题：链表是否有环

判断链表有没有环，传统解法是快慢指针：两个指针从同一起点出发，快指针每次走两步、慢指针走一步，有环时会相遇；再从相遇点和起点各放一个指针，再次相遇的位置就是入环点。

用 set 做就退化成一行逻辑——遍历时把访问过的节点地址塞进 set，一旦发现已经在 set 里，那个地址就是入环点：

set<ListNode*> s;
ListNode* cur = head;
while (cur)
{
    if (s.count(cur)) return cur;
    s.insert(cur);
    cur = cur->next;
}
return nullptr;

这是同一个问题在 C++ 容器视角下的另一种解法，代价是多了 O(n) 的空间，换来的是代码量减半。

七、小结

把 map/set 抓成三句话：seq 容器按位置、关联容器按关键字；map/set 底层是红黑树，遍历中序所以有序，查询增删是 O(logN)；map 的 key 不能改（改了树就废了），value 可以，operator[] 是查找+插入+修改三合一。真要追求极致查询速度、又不要求顺序，就换 unordered_map/unordered_set。

qidao123.com企服评测-应用市场 编辑提示