好的，我们来详细解析C++标准库中的 set/multiset 和 map/multimap 这四个关联容器。它们都基于红黑树（一种平衡二叉搜索树）实现，因此具有高效的元素查找、插入和删除能力，时间复杂度通常为 $O(\log n)$。

核心特性：有序性 这些容器中的元素总是按键（Key）自动排序。默认情况下按 operator< 排序，但用户也可以提供自定义的比较函数（Compare）。

1. set 和 multiset

• 元素类型：只存储键（Key）本身。set 和 multiset 是集合。
• 核心区别：
  • set：键唯一。不允许重复的键。
  • multiset：键允许重复。可以插入多个值相同的键。
• 主要成员函数：
  • 插入：

    std::pair<iterator, bool> insert(const value_type& val); // set，返回pair<迭代器, 是否插入成功>
    iterator insert(const value_type& val); // multiset，总是成功，返回新元素迭代器
    iterator insert(iterator position, const value_type& val); // 提示位置插入
    template <class InputIterator>
    void insert(InputIterator first, InputIterator last); // 范围插入
    

  • 查找：

    iterator find(const key_type& k); // 找到返回迭代器，否则返回end()
    size_type count(const key_type& k) const; // 返回键k的数量 (set为0或1，multiset可能>1)
    iterator lower_bound(const key_type& k) const; // 返回首个>=k的元素迭代器
    iterator upper_bound(const key_type& k) const; // 返回首个>k的元素迭代器
    std::pair<iterator, iterator> equal_range(const key_type& k) const; // 返回键k的范围 [lower_bound, upper_bound)
    

  • 删除：

    size_type erase(const key_type& k); // 删除所有键为k的元素，返回删除数量
    iterator erase(iterator position); // 删除指定位置元素
    iterator erase(iterator first, iterator last); // 删除范围
    

  • 大小与遍历：

    bool empty() const;
    size_type size() const;
    iterator begin() const;
    iterator end() const;
    reverse_iterator rbegin() const; // C++11起
    reverse_iterator rend() const; // C++11起
    

• 示例 (set):

  #include <iostream>
  #include <set>
  #include <string>
  
  int main() {
      std::set<std::string> names;
  
      // 插入
      names.insert("Alice");
      names.insert("Bob");
      auto [it, success] = names.insert("Alice"); // 插入失败，success=false
  
      // 查找
      if (names.find("Bob") != names.end()) {
          std::cout << "Bob found!\n";
      }
      std::cout << "Count of Alice: " << names.count("Alice") << "\n"; // 输出 1
  
      // 遍历 (有序)
      for (const auto& name : names) {
          std::cout << name << " "; // 输出 Alice Bob (按字母排序)
      }
  
      // 删除
      names.erase("Bob"); // 删除 Bob
      return 0;
  }
  

2. map 和 multimap

• 元素类型：存储键值对（Key-Value Pair）。map 和 multimap 是关联数组或字典。
  • 元素类型是 std::pair<const Key, T>。键是 const，不能直接修改。
• 核心区别：
  • map：键唯一。每个键最多关联一个值。
  • multimap：键允许重复。同一个键可以关联多个不同的值。
• 主要成员函数：
  • 插入：

    std::pair<iterator, bool> insert(const value_type& val); // map，val是pair<const Key, T>
    iterator insert(const value_type& val); // multimap
    // ... 其他insert形式与set/multiset类似
    // map特有便捷插入/访问 (C++11起)
    T& operator[](const key_type& k); // 如果k不存在，则插入一个默认构造的T，并返回其引用
    T& operator[](key_type&& k); // 移动语义版本
    T& at(const key_type& k); // 访问k对应的值，若k不存在则抛出std::out_of_range
    

  • 查找：

    iterator find(const key_type& k); // 找到返回迭代器 (指向pair)，否则end()
    size_type count(const key_type& k) const;
    iterator lower_bound(const key_type& k) const;
    iterator upper_bound(const key_type& k) const;
    std::pair<iterator, iterator> equal_range(const key_type& k) const; // 对multimap处理重复键尤其有用
    // map特有访问 (C++20起)
    bool contains(const key_type& k) const; // 检查是否存在键k
    

  • 删除：与 set/multiset 的 erase 类似。
  • 大小与遍历：与 set/multiset 类似。遍历时通过迭代器解引用访问 it->first (键) 和 it->second (值)。
• 示例 (map):

  #include <iostream>
  #include <map>
  
  int main() {
      std::map<std::string, int> ages;
  
      // 插入方式1: insert
      ages.insert(std::make_pair("Alice", 30));
      auto [it, inserted] = ages.insert({"Bob", 25}); // C++11
  
      // 插入方式2: operator[] (便捷，但可能插入默认值)
      ages["Charlie"] = 28; // 插入或修改
      ages["Bob"] = 26; // 修改现有值
  
      // 访问方式1: operator[] (若不存在会插入!)
      std::cout << "Alice is " << ages["Alice"] << " years old.\n";
  
      // 访问方式2: at (安全，检查存在性)
      try {
          std::cout << "Dave's age: " << ages.at("Dave") << "\n"; // 抛出异常
      } catch (const std::out_of_range& e) {
          std::cerr << "Dave not found!\n";
      }
  
      // 访问方式3: find (推荐检查存在性)
      auto search = ages.find("Eve");
      if (search != ages.end()) {
          std::cout << "Eve found, age: " << search->second << "\n";
      } else {
          std::cout << "Eve not found.\n";
      }
  
      // 遍历 (按键排序)
      for (const auto& [name, age] : ages) { // C++17 结构化绑定
          std::cout << name << ": " << age << "\n";
      }
  
      return 0;
  }
  

• 示例 (multimap):

  #include <iostream>
  #include <map>
  #include <string>
  
  int main() {
      std::multimap<std::string, std::string> favorites;
  
      favorites.insert({"Alice", "Pizza"});
      favorites.insert({"Alice", "Sushi"}); // 同一个键可以关联多个值
      favorites.insert({"Bob", "Burger"});
  
      // 查找所有Alice喜欢的食物
      auto range = favorites.equal_range("Alice");
      for (auto it = range.first; it != range.second; ++it) {
          std::cout << it->first << " likes " << it->second << "\n";
      }
  
      return 0;
  }
  

总结对比表

关键点提醒

1. 排序依据：容器内部始终保持元素按键排序。自定义类型作为键时，必须提供比较规则（仿函数或重载operator<）。
2. 迭代器稳定性：除了被删除的元素，插入和删除操作通常不会使指向其他元素的迭代器、指针或引用失效。
3. map 的 operator[]：非常方便，但要小心！如果键不存在，它会插入一个值初始化（基本类型为0，类类型为默认构造）的键值对。如果不想插入新元素，应优先使用 find 或 at。
4. multimap 的查找：使用 equal_range 是查找特定键所有关联值的标准方法。
5. 性能：插入、删除、查找的平均和最坏时间复杂度均为 $O(\log n)$，其中 $n$ 是容器大小。基于红黑树的特性。

希望这份详细的解析能帮助你更好地理解和使用这些强大的C++关联容器！