好的，我们来详细解析 C++ STL 中的有序关联容器：set/multiset 和 map/multimap。它们基于红黑树（一种平衡二叉搜索树）实现，保证了元素的有序性（默认按升序排列）。

一、核心概念与区别

1. set 与 multiset

   • 存储内容：只存储 键（key） 本身。元素值即键值。
   • 唯一性：
     • set：键唯一。不允许重复键。
     • multiset：允许重复键。
   • 用途：维护一个唯一或可重复的有序集合。

2. map 与 multimap

   • 存储内容：存储 键值对（key-value pairs）。每个元素是一个 pair<const Key, Value> 对象。
   • 唯一性：
     • map：键唯一。每个键最多关联一个值。插入相同键会覆盖（或忽略）原值（取决于插入方法）。
     • multimap：允许重复键。一个键可以关联多个不同的值。
   • 用途：建立键到值的有序映射关系。

简单记忆：

• set/multiset：纯集合。
• map/multimap：键值映射。
• 前缀 multi：允许重复键。

二、常用操作与示例

1. set 与 multiset

#include <iostream>
#include <set>
using namespace std;

int main() {
    // set (唯一键)
    set<int> uniqueSet;
    uniqueSet.insert(3);
    uniqueSet.insert(1);
    uniqueSet.insert(4);
    uniqueSet.insert(1); // 重复插入会被忽略
    uniqueSet.insert(2);
    cout << "set: ";
    for (int num : uniqueSet) {
        cout << num << " "; // 输出: 1 2 3 4 (有序且唯一)
    }
    cout << endl;

    // multiset (允许重复键)
    multiset<int> multiSet;
    multiSet.insert(3);
    multiSet.insert(1);
    multiSet.insert(4);
    multiSet.insert(1); // 允许重复
    multiSet.insert(2);
    cout << "multiset: ";
    for (int num : multiSet) {
        cout << num << " "; // 输出: 1 1 2 3 4 (有序)
    }
    cout << endl;

    // 查找与计数
    auto it = uniqueSet.find(3);
    if (it != uniqueSet.end()) {
        cout << "Found 3 in set" << endl;
    }
    cout << "Count of 1 in multiset: " << multiSet.count(1) << endl; // 输出 2

    // 删除 (multiset 会删除所有匹配项)
    multiSet.erase(1); // 删除所有值为1的元素
    cout << "multiset after erase(1): ";
    for (int num : multiSet) {
        cout << num << " "; // 输出: 2 3 4
    }
    cout << endl;

    return 0;
}

2. map 与 multimap

#include <iostream>
#include <map>
using namespace std;

int main() {
    // map (键唯一)
    map<string, int> studentScores;
    studentScores["Alice"] = 95; // 插入方式1: 使用[]
    studentScores.insert(make_pair("Bob", 88)); // 插入方式2: insert(pair)
    studentScores["Charlie"] = 92;
    studentScores["Alice"] = 100; // []会覆盖已存在的键

    cout << "map:" << endl;
    for (const auto& pair : studentScores) { // 遍历键值对
        cout << pair.first << ": " << pair.second << endl;
    }
    // 输出:
    // Alice: 100
    // Bob: 88
    // Charlie: 92

    // multimap (允许重复键)
    multimap<string, string> authorBooks;
    authorBooks.insert(make_pair("AuthorA", "Book1"));
    authorBooks.insert(make_pair("AuthorA", "Book2")); // 同一作者多本书
    authorBooks.insert(make_pair("AuthorB", "Book3"));
    authorBooks.insert(make_pair("AuthorA", "Book4"));

    cout << "\nmultimap:" << endl;
    for (const auto& pair : authorBooks) {
        cout << pair.first << " - " << pair.second << endl;
    }
    // 输出 (有序，AuthorA 出现多次):
    // AuthorA - Book1
    // AuthorA - Book2
    // AuthorA - Book4
    // AuthorB - Book3

    // 查找特定键的所有值 (multimap 关键操作)
    cout << "\nBooks by AuthorA:" << endl;
    auto range = authorBooks.equal_range("AuthorA"); // 获取键范围
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->second << endl; // 输出: Book1, Book2, Book4
    }

    // map 的查找与访问
    auto itMap = studentScores.find("Bob");
    if (itMap != studentScores.end()) {
        cout << "Bob's score: " << itMap->second << endl; // 输出 88
    }

    return 0;
}

三、关键特性总结

1. 有序性：元素始终按键排序（默认 <，可通过比较函数对象自定义）。
2. 查找效率：插入、删除、查找操作的平均时间复杂度为 $O(\log n)$。
3. 迭代器稳定性：插入/删除操作不会使指向其他元素的迭代器失效（除非删除该迭代器指向的元素）。
4. 键类型要求：键必须支持严格弱序比较（通常需要定义 < 运算符或提供自定义比较函数）。
5. map的operator[]：
   • 若键存在，返回对应值的引用。
   • 若键不存在，插入该键并用值类型的默认构造函数初始化值，返回此新值的引用。需谨慎使用。

四、如何选择？

• 需要存储唯一键的集合：set
• 需要存储可重复键的集合：multiset
• 需要建立键到值的唯一映射：map
• 需要建立键到值的一对多映射：multimap

五、注意事项

1. map 的 operator[] 会在键不存在时自动插入，有时 find() 或 count() 更安全。
2. multimap 没有 operator[]，因为一个键可能对应多个值。
3. 遍历 multimap 或 multiset 时，同一键的元素是连续存储的。
4. 自定义比较函数：当键是自定义类型或需要特殊排序规则时使用。

// 自定义比较函数示例 (按字符串长度排序)
struct LengthCompare {
    bool operator()(const string& a, const string& b) const {
        return a.length() < b.length();
    }
};

set<string, LengthCompare> lengthSet;
lengthSet.insert("apple");
lengthSet.insert("banana");
lengthSet.insert("cherry");
// 遍历输出: apple, cherry, banana (按长度升序)

熟练掌握这些容器及其特性，能极大提升处理有序、关联数据的效率。