引言

关联容器（Associative Containers）是一类通过键值对（key-value）进行数据管理的数据结构，支持高效的查找、插入和删除操作。分为有序关联容器和无序关联容器。

本文主要介绍有序关联容器，它能够自动维护元素的有序性，并以对数复杂度支持高效的查找、插入和删除操作。

• 包含：std::set、std::map、std::multiset、std::multimap

• 底层实现：红黑树（自平衡二叉查找树）

• 特点：所有元素自动按键升序排列（可自定义排序）

1 std::set

定义与特性：

• 存储唯一元素，自动按指定顺序（默认升序）排列。

• 底层实现为红黑树。

• 只存储“键”，没有“值”。

• 查找、插入、删除的时间复杂度均为 O(log n)。

代码示例：

#include <set>
#include <iostream>

// 示例：set的基本用法
void SetExample() {
  std::set<int> numbers;
  numbers.insert(4);  // 插入元素
  numbers.insert(2);
  numbers.insert(4);  // 重复插入无效

  numbers.erase(2);   // 删除元素

  // 查找元素
  if (numbers.find(4) != numbers.end()) {
    std::cout << "4 exists in set" << std::endl;
  }

  // 遍历
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;
}

适用场景：

• 需要存储不重复且有序的数据。

• 频繁查找、插入和删除操作。

2 std::multiset

定义与特性：

• 与set类似，但允许元素重复。

• 元素自动排序。

• 底层同样为红黑树。

• 查找、插入、删除为 O(log n)。

代码示例：

#include <set>
#include <iostream>

// 示例：multiset的用法
void MultisetExample() {
  std::multiset<int> numbers;
  numbers.insert(4);
  numbers.insert(2);
  numbers.insert(4);  // 可重复插入

  // 统计某个元素的数量
  std::cout << "Count of 4: " << numbers.count(4) << std::endl;

  // 删除所有值为4的元素
  numbers.erase(4);

  // 遍历
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;
}

适用场景：

• 需要存储有序且可能重复的数据。

• 统计某个元素的出现次数。

3 std::map

定义与特性：

• 存储键值对（key-value），键唯一且自动排序。

• 底层为红黑树。

• 查找、插入、删除为 O(log n)。

• 支持通过operator[]访问和插入元素。

代码示例：

#include <map>
#include <iostream>
#include <string>

// 示例：map的基本用法
void MapExample() {
  std::map<std::string, int> ages;
  ages["Tom"] = 18;    // 插入/修改
  ages["Jerry"] = 20;

  // 查找
  if (ages.count("Tom")) {
    std::cout << "Tom's age: " << ages["Tom"] << std::endl;
  }

  // 遍历
  for (const auto& kv : ages) {
    std::cout << kv.first << ": " << kv.second << std::endl;
  }

  // 注意：operator[]会插入默认值
  std::cout << "Bob's age: " << ages["Bob"] << std::endl;  // 插入Bob，值为0
}

适用场景：

• 需要存储唯一键与值的映射关系，且自动排序。

• 频繁查找、插入、删除。

4 std::multimap

定义与特性：

• 存储键值对（key-value），允许键重复，即同一个键可以对应多个值，所有元素自动排序。

• 底层为红黑树实现，保证元素有序。

• 查找、插入、删除操作复杂度为 O(log⁡n)。

• 不支持通过operator[]访问或插入元素，需使用insert方法进行插入。

• 支持通过equal_range、find等方法查找同一键的所有值。

代码示例：

#include <map>
#include <iostream>
#include <string>

// 示例：multimap的基本用法
void MultiMapExample() {
  std::multimap<std::string, int> scores;
  // 插入元素，允许相同key
  scores.insert({"Tom", 90});
  scores.insert({"Tom", 85});
  scores.insert({"Jerry", 88});

  // 查找Tom的所有分数
  auto range = scores.equal_range("Tom");
  std::cout << "Tom's scores: ";
  for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";
  }
  std::cout << std::endl;

  // 遍历所有元素
  for (const auto& kv : scores) {
    std::cout << kv.first << ": " << kv.second << std::endl;
  }

  // 删除某个key的所有元素
  scores.erase("Tom");
}

适用场景：

• 需要存储一对多关系，即同一个键可能对应多个值（如学生选课、商品多标签等）。

• 希望自动排序，且频繁查找、插入、删除。

• 需要根据键高效地获取所有相关值。

5 有序容器对比

6 注意事项

1. 元素不可修改：set和map的元素（key部分）不可直接修改，否则会破坏有序性。

2. 效率问题：有序容器操作为 O(log⁡n)，对性能极度敏感场景建议考虑哈希容器。

3. 迭代器失效：删除元素后相关迭代器会失效，需谨慎操作。