C++关联容器详解：set/map高效操作指南

核心概念： 这些容器都是关联容器。它们的特点是其中的元素是按照特定的排序准则（通常是 < 运算符或者自定义的比较函数）进行排序的。这种排序使得查找、插入和删除操作非常高效，时间复杂度通常为 $O(\\log n)$。它们的底层实现通常是红黑树。

1. set 和 multiset

• 存储内容： 存储唯一的键 (key)。set 中的键是唯一的，multiset 中的键可以重复。

• 定义：

  #include <set>
  std::set<Key, Compare = std::less<Key>, Allocator = std::allocator<Key>> set_name;
  std::multiset<Key, Compare = std::less<Key>, Allocator = std::allocator<Key>> multiset_name;

  • Key: 容器中存储的元素类型。这个类型必须支持比较操作（通过 < 运算符或自定义的 Compare）。
  • Compare: 比较函数对象的类型，用于定义排序规则。默认是 std::less<Key>，即升序排列。可以自定义，例如 std::greater<Key> 实现降序。
  • Allocator: 内存分配器类型，通常使用默认值。

• 主要特性：

  • 排序： 元素始终按 Compare 定义的规则保持有序。
  • 唯一性 (仅 set): set 中不允许两个元素具有相同的值（根据 Compare 判断相等）。
  • 键即值： 在 set 和 multiset 中，key 就是存储的值本身 (value_type 就是 Key)。
  • 迭代器： 提供双向迭代器 (iterator, const_iterator)。迭代器按排序顺序遍历元素。修改元素的值（通过迭代器）可能破坏容器的排序，因此是不允许的。 只能插入新元素或删除现有元素。

• 关键成员函数：

  • 插入: std::pair<iterator, bool> insert(const Key& key); // set: 插入成功返回 {iterator, true}, 失败(重复)返回 {iterator, false}
    iterator insert(const Key& key); // multiset: 总是成功，返回新元素迭代器
    iterator insert(iterator hint, const Key& key); // 使用提示位置尝试优化插入
    void insert(InputIterator first, InputIterator last); // 插入一个范围内的元素

    https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjQzNS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjczNy5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjM5My5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0Mjc0My5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjkwNy5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MzAyMi5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0Mjc2NC5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjgyMS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjU2Mi5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjY0OS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjM1NS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjM2My5zaHRtbA==.html  

  • 查找: iterator find(const Key& key); // 查找等于 key 的元素，找到返回迭代器，否则返回 end()
    const_iterator find(const Key& key) const;
    size_type count(const Key& key) const; // 返回等于 key 的元素个数 (set 为 0 或 1， multiset 可能 >1)

  • 范围查询 (基于排序): iterator lower_bound(const Key& key); // 返回第一个不小于 key 的元素的迭代器
    iterator upper_bound(const Key& key); // 返回第一个大于 key 的元素的迭代器
    std::pair<iterator, iterator> equal_range(const Key& key); // 返回包含所有等于 key 的元素的范围 [lower_bound, upper_bound)
    • 这些操作对于 multiset 查找重复键的所有元素非常有用。
  • 删除: size_type erase(const Key& key); // 删除所有等于 key 的元素，返回删除的个数
    iterator erase(iterator position); // 删除迭代器 position 指向的元素
    iterator erase(iterator first, iterator last); // 删除范围 [first, last) 内的元素

  • 大小和容量: bool empty() const;
    size_type size() const;
    size_type max_size() const;

    https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjQzNS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjczNy5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjM5My5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0Mjc0My5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjkwNy5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MzAyMi5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0Mjc2NC5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDQxNTQ4MjkwLzY5NTk0MjgyMS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjU2Mi5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjY0OS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjM1NS5zaHRtbA==.html https://tv.sohu.com/v/dXMvNDM4OTIwMjE2LzY5NTk0MjM2My5zaHRtbA==.html  

  • 其他: void clear(); // 清空容器
    key_compare key_comp() const; // 返回比较函数对象的副本
    value_compare value_comp() const; // 对于 set/multiset, value_compare 等同于 key_compare

2. map 和 multimap

• 存储内容： 存储由键 (key) 和值 (value) 组成的键值对 (pair<const Key, Value>)。map 中的键是唯一的，multimap 中的键可以重复。

• 定义：

  #include <map>
  std::map<Key, Value, Compare = std::less<Key>, Allocator = std::allocator<std::pair<const Key, Value>>> map_name;
  std::multimap<Key, Value, Compare = std::less<Key>, Allocator = std::allocator<std::pair<const Key, Value>>> multimap_name;

  • Key: 键的类型。必须支持比较操作。
  • Value: 与键关联的值的类型。
  • Compare: 比较键的函数对象的类型，用于定义排序规则。默认是 std::less<Key>。
  • Allocator: 内存分配器类型，通常使用默认值。

• 主要特性：

  • 排序： 元素（键值对）始终按照键 (Key)，根据 Compare 定义的规则保持有序。
  • 唯一性 (仅 map): map 中不允许两个元素具有相同的键（根据 Compare 判断相等）。
  • 键值对： 元素类型是 std::pair<const Key, Value>。键 (Key) 是 const 类型，不能修改（修改会破坏排序）。值 (Value) 可以通过迭代器或特定接口修改。
  • 迭代器： 提供双向迭代器 (iterator, const_iterator)。迭代器按键的排序顺序遍历元素。通过迭代器可以修改 value (it->second = new_value;)，但不能修改 key (it->first 是 const)。

• 关键成员函数 (大部分与 set/multiset 类似):

  • 插入: std::pair<iterator, bool> insert(const value_type& kv_pair); // map: 插入成功返回 {iterator, true}, 失败(重复键)返回 {iterator, false}
    iterator insert(const value_type& kv_pair); // multimap: 总是成功，返回新元素迭代器
    iterator insert(iterator hint, const value_type& kv_pair); // 使用提示位置
    void insert(InputIterator first, InputIterator last); // 插入一个范围内的键值对
    • value_type 是 std::pair<const Key, Value>。通常使用 std::make_pair(key, value) 或 {key, value} (C++11 起) 创建。
  • 访问/修改元素 (map 特有): Value& operator[](const Key& key); // 1. 如果 key 存在，返回其 value 的引用。
    // 2. 如果 key 不存在，则插入一个具有该 key 的默认构造的 Value，并返回其引用。
    Value& at(const Key& key); // 访问指定 key 的 value 的引用，若 key 不存在则抛出 std::out_of_range 异常。
    const Value& at(const Key& key) const;
    • operator[] 提供了一种便捷但可能插入新元素的方式。at() 提供了边界检查的安全访问。
    • multimap 没有 operator[]，因为一个键可能对应多个值。
  • 查找: iterator find(const Key& key); // 查找键等于 key 的元素，找到返回迭代器，否则返回 end()
    const_iterator find(const Key& key) const;
    size_type count(const Key& key) const; // 返回键等于 key 的元素个数 (map 为 0 或 1， multimap 可能 >1)

  • 范围查询 (基于键排序): iterator lower_bound(const Key& key); // 返回第一个键不小于 key 的元素的迭代器
    iterator upper_bound(const Key& key); // 返回第一个键大于 key 的元素的迭代器
    std::pair<iterator, iterator> equal_range(const Key& key); // 返回包含所有键等于 key 的元素的范围 [lower_bound, upper_bound)
    • 这些操作对于 multimap 查找同一键对应的所有值非常有用。
  • 删除、大小、容量、比较函数等： 与 set/multiset 中的对应函数功能和使用方式基本相同，只是操作的对象是键值对。

总结与对比

选择指南：

• 需要存储唯一值并按值排序：用 set。
• 需要存储可能重复的值并按值排序：用 multiset。
• 需要建立唯一键到值的映射，并按键排序：用 map。可以通过键快速查找或修改对应的值。
• 需要一个键对应多个值，并按键排序：用 multimap。使用 equal_range 或遍历来获取同一键的所有值。

这些关联容器是 C++ STL 中非常强大和常用的工具，理解它们的特性和区别对于编写高效、正确的代码至关重要。