04. map和set的使用

1. 序列式容器和关联式容器

前面我们已经接触过STL中的部分容器，如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器。

• 逻辑结构：线性序列的数据结构。
• 关联性：两个位置存储的值之间一般没有紧密的关联关系（比如交换一下，它依旧是序列式容器）。
• 访问方式：顺序容器中的元素是按它们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的，与序列式容器不同的是：

• 逻辑结构：通常是非线性结构。
• 关联性：两个位置有紧密的关联关系，交换一下，它的存储结构就被破坏了。
• 访问方式：关联式容器中的元素是按关键字来保存和访问的。
• 分类：关联式容器有 map/set 系列和 unordered_map/unordered_set 系列。

本章节讲解的 map 和 set 底层是红黑树，红黑树是一颗平衡二叉搜索树。

• set：是 key 搜索场景的结构。
• map：是 key/value 搜索场景的结构。

---

2. set系列的使用

• 类模板声明

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           //Compare (比较仿函数):默认情况下，set 要求类型 T 支持小于 < 比较。如果 T 不支持小于比较，或者你想按照自定义的逻辑（如降序）进行排序，可以自行实现仿函数并传给第二个模板参数。
           class Alloc = allocator<T> >    // set::allocator_type
           //Alloc (空间配置器):set 底层存储数据的内存是从空间配置器申请的。如果需要实现自定义内存池以提高效率，可以将自定义的空间配置器传给第三个参数
class set;

set的构造和迭代器

set的构造

set 支持多种构造方式，以下是几个最常用的构造函数接口：

1. 默认构造
   构造一个空的 set 容器。

   set();
   

2. 范围构造
   使用迭代器范围 [first, last) 内的元素构造一个 set。

   template <class InputIterator>
   set (InputIterator first, InputIterator last);
   

3. 拷贝构造
   通过拷贝另一个 set 容器来构造。

   set (const set& x);
   

4. 初始化列表构造 (C++11)
   使用初始化列表来构造 set。

   set (initializer_list<value_type> il);
   

迭代器特性

set支持正向和反向迭代遍历，其特性如下：

1. 默认升序：遍历默认按升序顺序进行。
2. 中序遍历：因为底层是二叉搜索树，迭代器遍历走的是中序遍历。
3. 支持范围for：支持迭代器就意味着支持范围for循环。
4. 只读特性：set的iterator和const_iterator都不支持通过迭代器修改数据。

   注意：修改关键字数据会破坏底层搜索树的结构。

set的增删查

set常用接口整理

功能分类	接口函数	功能描述
插入	pair<iterator,bool> insert (const value_type& val)	单个数据插入，若已存在则插入失败
	void insert (initializer_list<value_type> il)	列表插入，已存在的值不会重复插入
	void insert (InputIterator first, InputIterator last)	迭代器区间插入，已存在的值不会重复插入
查找	iterator find (const value_type& val)	查找val，返回对应迭代器，未找到返回end()
	size_type count (const value_type& val)	查找val，返回val的个数（0或1）
删除	iterator erase (const_iterator position)	删除指定迭代器位置的值
	size_type erase (const value_type& val)	删除指定值val，不存在返回0，存在返回1
	iterator erase (const_iterator first, const_iterator last)	删除指定迭代器区间的值
边界	iterator lower_bound (const value_type& val)	返回大于等于val位置的迭代器
	iterator upper_bound (const value_type& val)	返回大于val位置的迭代器

---

std::multiset 简介

std::multiset 是 C++ 标准模板库（STL）中的一种关联容器，用于存储有序且允许重复的元素。

核心特性

1. 允许重复：与 std::set 不同，multiset 中可以存储多个值相同的元素。
2. 自动排序：元素默认按照升序排列（也可以自定义比较函数实现降序或其他规则）。
3. 底层实现：通常采用红黑树实现，因此插入、删除和查找操作的时间复杂度均为 O(log N)。
4. 键即值：multiset 中的元素既是键也是值，不支持通过迭代器直接修改元素值（因为修改可能会破坏排序规则）。

常用操作差异 (对比 set)

操作	set	multiset
插入	若元素已存在，插入失败	始终插入，允许重复
统计	返回 0 或 1	返回元素的具体个数 (count)
删除	删除指定值（最多1个）	删除所有匹配该值的元素
查找	返回指向元素的迭代器	返回指向第一个匹配元素的迭代器

---

map 类介绍

map 是 C++ 标准模板库（STL）中的一种关联容器，用于存储键值对。它与 set 的核心区别在于，map 中的每个元素都包含一个关键字（Key）和一个关联的值（Value）。

核心特性

1. 键值对存储
   map 存储的数据格式为 std::pair<const Key, T>。其中 Key 是关键字，T 是对应的值。

2. 唯一性
   map 中的 Key 是唯一的，不允许重复。如果尝试插入一个已存在的键，插入操作会失败。

3. 自动排序
   元素默认按照 Key 的升序排列（基于 Key 的 < 比较运算符）。迭代器遍历时，结果是按 Key 有序的。

4. 底层实现
   map 底层通常使用红黑树（一种自平衡的二叉搜索树）实现。

5. 性能效率
   由于基于红黑树，map 的插入、删除和查找操作的平均时间复杂度均为 $O(\log N)$。

与 set 的对比

特性	set	map
存储内容	单一的值 (Value)	键值对 (Key-Value)
唯一性	值唯一	键 (Key) 唯一
底层结构	红黑树	红黑树
主要用途	数据去重、排序	建立映射关系、字典

pair 类型介绍

std::pair 是 C++ 标准模板库（STL）中的一个模板类，用于将两个不同类型的数据组合成一个单一的对象。它在 map 等关联容器中扮演着核心角色，因为 map 的每个元素本质上就是一个键值对。

核心结构

map 底层的红黑树节点中的数据使用 pair<Key, T> 存储键值对数据。map 的 value_type 通常被定义为：

typedef pair<const Key, T> value_type;

以下是 pair 的简化定义：

template <class T1, class T2>
struct pair 
{
    // 类型别名
    typedef T1 first_type;
    typedef T2 second_type;

    // 成员变量
    T1 first;   // 存储第一个值（在 map 中通常是键 Key）
    T2 second;  // 存储第二个值（在 map 中通常是值 Value）

    // 1. 默认构造函数
    pair(): first(T1()), second(T2())
    {}

    // 2. 带参构造函数
    pair(const T1& a, const T2& b): first(a), second(b)
    {}

    // 3. 模板拷贝构造函数（支持类型转换）
    template<class U, class V> 
    pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
    {}
};

map 的构造与遍历

map 的构造方式灵活多样，同时其基于红黑树的底层结构决定了它独特的遍历规则和数据访问权限。

常用构造方式

map 提供了多种构造函数，以下是几种最常用的方式：

1. 默认构造
   创建一个空的 map 容器。

   std::map<int, std::string> m1;
   

2. 初始化列表构造 (C++11)
   这是最简洁、最常用的构造方式，可以直接在创建时填入初始数据。

   std::map<int, std::string> m2 = {
       {1, "one"},
       {2, "two"},
       {3, "three"}
   };
   

3. 迭代器区间构造
   通过一对迭代器，将一个范围内的键值对拷贝到新创建的 map 中。

   std::vector<std::pair<int, std::string>> vec = {{4, "four"}, {5, "five"}};
   std::map<int, std::string> m3(vec.begin(), vec.end());
   

4. 拷贝构造
   使用一个已存在的 map 来初始化一个新的 map。

   std::map<int, std::string> m4(m2); // m4 是 m2 的副本
   

遍历与数据修改规则

map 的遍历和数据修改遵循以下核心规则：

• 有序遍历
  map 支持正向 (begin/end) 和反向 (rbegin/rend) 迭代器遍历。由于底层是二叉搜索树（红黑树），迭代器遍历遵循中序遍历，因此元素会默认按照键（Key）的升序排列。

• 支持范围 for 循环
  因为 map 支持迭代器，所以可以直接使用 C++11 的范围 for 循环，使代码更加简洁。

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

• 可修改 value，不可修改 key
  在遍历或访问 map 元素时，你可以修改值（Value）数据，但严禁修改键（Key）数据。

  • 原因：map 的有序性完全依赖于键。修改键会直接破坏底层红黑树的结构，导致容器内部状态错乱。因此，map 中存储的 pair 的键部分是 const 类型（std::pair<const Key, T>），从编译层面阻止了修改。

map 增删查接口汇总

map 的增删查操作核心在于：插入时需要提供完整的键值对（pair），而查找和删除则主要基于键（Key）。与 set 不同，map 的 find 接口返回的迭代器不仅能定位键，还能直接访问并修改其关联的值（Value）。

功能分类	接口函数	功能描述
插入	pair<iterator, bool> insert (const value_type& val)	插入键值对。若键已存在，插入失败（bool为false）；若不存在，插入成功。
	T& operator[] (const key_type& k)	若键 k 存在，返回其值的引用；若不存在，插入默认值并返回引用。
查找	iterator find (const key_type& k)	查找键 k。若找到，返回指向该键值对的迭代器（可修改值）；否则返回 end()。
	size_type count (const key_type& k)	统计键 k 的个数。由于键唯一，返回 1（存在）或 0（不存在）。
删除	size_type erase (const key_type& k)	删除键为 k 的元素。返回实际删除的元素个数（0 或 1）。
	iterator erase (const_iterator position)	删除迭代器 position 指向的元素。
	void erase (const_iterator first, const_iterator last)	删除迭代器范围 [first, last) 内的所有元素。

map 的数据修改

前面提到，map 支持修改 mapped_type（值）数据，但不支持修改 key（键）数据，因为修改键会破坏底层红黑树（搜索树）的结构。

map 修改数据主要有两种方式：

1. 通过迭代器修改
   在遍历 map 时，或者通过 find 找到键所在的迭代器后，可以通过迭代器直接修改其关联的值。

   auto it = m.find(1);
   if (it != m.end()) {
       it->second = "new value"; // 修改值
       // it->first = 2; // 错误！不能修改键
   }
   

2. 通过 operator[] 修改
   这是一个非常重要的多功能复合接口。它不仅仅支持修改，还支持插入和查找数据。

   m[1] = "one"; // 如果键1存在则修改，不存在则插入