好的，我们来详细解析 C++ 标准库中的 set/multiset 和 map/multimap。它们是关联容器，基于有序结构（通常是红黑树）实现，提供高效的查找、插入和删除操作。

1. 基本概念

• set：存储唯一键值（Key）的集合。容器中的元素一旦插入，其键值就不能被修改（但可以删除后重新插入）。元素按键值自动排序。
• multiset：与 set 类似，但允许存储重复键值。元素按键值自动排序。
• map：存储由唯一键值（Key）和映射值（Value）组成的键值对（pair<const Key, Value>）。键值唯一且不可修改，映射值可以修改。元素按键值自动排序。
• multimap：与 map 类似，但允许存储重复键值。同一个键值可以对应多个不同的映射值。元素按键值自动排序。

2. 共同特性

1. 有序性：元素按键值（对于 set/multiset 就是元素本身）严格弱序排序。默认使用 operator< 进行比较，也可以自定义比较函数对象。
2. 关联容器：通过键值（Key）来访问元素，而不是位置（索引）。
3. 底层实现：通常基于平衡二叉搜索树（如红黑树）实现，这保证了主要的操作（查找、插入、删除）具有对数时间复杂度 $O(\log n)$。
4. 迭代器：提供双向迭代器。遍历容器将按排序后的顺序访问元素。修改键值（对于 set 的元素或 map 的 key）会破坏容器的有序性，因此 set 的元素和 map 的 key 是 const 的（在 map 中，key 是 pair 的第一个成员，类型为 const Key）。
5. 头文件：#include <set>（用于 set, multiset），#include <map>（用于 map, multimap）。

3. set 和 multiset

• 模板参数：

  template <
      class Key,
      class Compare = std::less<Key>,
      class Allocator = std::allocator<Key>
  > class set;
  
  template <
      class Key,
      class Compare = std::less<Key>,
      class Allocator = std::allocator<Key>
  > class multiset;
  

  • Key：元素的类型，也是排序的依据。
  • Compare：比较函数对象的类型，定义排序规则。默认为 std::less<Key>。
  • Allocator：内存分配器类型。通常使用默认值。
• 主要操作：
  • 插入：insert(const Key& key)。set 仅在键不存在时插入并返回 pair<iterator, bool>（迭代器和是否插入成功）。multiset 总是插入成功，返回插入位置的迭代器。
  • 查找：
    • find(const Key& key)：返回指向键等于 key 的元素的迭代器，若找不到则返回 end()。
    • count(const Key& key)：返回键等于 key 的元素个数（set 为 0 或 1，multiset 可能大于 1）。
    • lower_bound(const Key& key)：返回指向第一个不小于 key 的元素的迭代器。
    • upper_bound(const Key& key)：返回指向第一个大于 key 的元素的迭代器。
    • equal_range(const Key& key)：返回一个 pair<iterator, iterator>，表示键等于 key 的元素范围（set 中该范围最多一个元素）。
  • 删除：erase(iterator pos), erase(const Key& key)（删除所有匹配键的元素），erase(iterator first, iterator last)。
  • 大小：size(), empty()。
  • 迭代器：begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), crend()。
• 示例：

  #include <iostream>
  #include <set>
  #include <string>
  
  int main() {
      // set (唯一键)
      std::set<int> uniqueNumbers;
      uniqueNumbers.insert(3);
      uniqueNumbers.insert(1);
      uniqueNumbers.insert(4);
      uniqueNumbers.insert(1); // 插入失败，键 1 已存在
      // 输出: 1 3 4
      for (int num : uniqueNumbers) {
          std::cout << num << " ";
      }
      std::cout << std::endl;
  
      // multiset (允许重复键)
      std::multiset<std::string> words;
      words.insert("apple");
      words.insert("banana");
      words.insert("apple");
      // 输出: apple apple banana (按字典序排序)
      for (const auto& word : words) {
          std::cout << word << " ";
      }
      std::cout << std::endl;
  
      // 在 multiset 中查找 'apple' 的所有出现
      auto range = words.equal_range("apple");
      for (auto it = range.first; it != range.second; ++it) {
          std::cout << *it << " found!" << std::endl;
      }
      // 输出: apple found! apple found!
  
      return 0;
  }
  

4. map 和 multimap

• 模板参数：

  template <
      class Key,
      class T,
      class Compare = std::less<Key>,
      class Allocator = std::allocator<std::pair<const Key, T>>
  > class map;
  
  template <
      class Key,
      class T,
      class Compare = std::less<Key>,
      class Allocator = std::allocator<std::pair<const Key, T>>
  > class multimap;
  

  • Key：键的类型，排序的依据。
  • T：映射值的类型。
  • Compare：比较函数对象的类型，定义键的排序规则。默认为 std::less<Key>。
  • Allocator：内存分配器类型，用于分配 pair<const Key, T>。通常使用默认值。
• 主要操作：
  • 插入：
    • insert(const value_type& value)：插入一个键值对 std::pair<Key, T> 或 std::pair<const Key, T>。
    • insert_or_assign (C++17, 仅 map)：若键存在则赋值，不存在则插入。
    • emplace：构造元素并插入。
    • map 还有 operator[] 和 at：
      • operator[](const Key& key)：若键存在，返回其映射值的引用；若不存在，则插入一个用 Key 和 T 的默认构造函数创建的键值对，并返回该映射值的引用。注意：operator[] 是非 const 的，可能修改容器（插入新元素）！
      • at(const Key& key)：若键存在，返回其映射值的引用；若不存在，抛出 std::out_of_range 异常。
  • 查找：与 set/multiset 类似，但基于键：
    • find(const Key& key)
    • count(const Key& key)
    • lower_bound(const Key& key)
    • upper_bound(const Key& key)
    • equal_range(const Key& key)
  • 访问元素：通过迭代器访问时，迭代器指向 value_type（即 pair<const Key, T>）。可以使用 it->first 访问键，it->second 访问映射值。映射值 (second) 可以修改。
  • 删除：与 set/multiset 类似，erase(iterator pos), erase(const Key& key), erase(iterator first, iterator last)。
  • 大小：size(), empty()。
  • 迭代器：begin(), end() 等。
• 示例：

  #include <iostream>
  #include <map>
  #include <string>
  
  int main() {
      // map (唯一键)
      std::map<std::string, int> wordCount;
      // 插入方式 1: insert
      wordCount.insert(std::make_pair("apple", 1)); // 或者 wordCount.insert({"apple", 1});
      // 插入方式 2: operator[] (可能插入)
      wordCount["banana"] = 2; // 插入 {"banana", 2}
      wordCount["apple"] = 3;  // 修改已存在的 "apple" 的值
      wordCount["cherry"];     // 插入 {"cherry", 0} (int 默认初始化)
  
      // 输出: apple: 3, banana: 2, cherry: 0 (按键排序)
      for (const auto& pair : wordCount) {
          std::cout << pair.first << ": " << pair.second << std::endl;
      }
  
      // 查找
      auto it = wordCount.find("banana");
      if (it != wordCount.end()) {
          it->second = 5; // 修改映射值
      }
  
      // multimap (允许重复键)
      std::multimap<std::string, std::string> authorBooks;
      authorBooks.insert({"Author A", "Book 1"});
      authorBooks.insert({"Author A", "Book 2"});
      authorBooks.insert({"Author B", "Book 3"});
  
      // 输出 Author A 的所有书
      auto range = authorBooks.equal_range("Author A");
      for (auto it = range.first; it != range.second; ++it) {
          std::cout << it->first << " wrote " << it->second << std::endl;
      }
      // 输出:
      // Author A wrote Book 1
      // Author A wrote Book 2
  
      // 注意: multimap 没有 operator[]
      // authorBooks["Author A"]; // 错误！
  
      return 0;
  }
  

5. 如何选择

• 需要存储唯一键，并且每个键关联一个值：使用 map。
• 需要存储唯一键的集合（不关联额外值）：使用 set。
• 允许重复键，并且每个键关联一个或多个值：使用 multimap。
• 允许重复键的集合（不关联额外值）：使用 multiset。

6. 关键点总结

希望这份详细的解析能帮助你更好地理解和使用 C++ 中的 set, multiset, map 和 multimap。