关联容器(Associative containers)

关联容器概述

关联容器是 C++ STL（标准模板库）的核心组件之一，其设计目标是通过「键（Key）」高效查找、插入和删除元素，而非像序列容器（如 vector、list）那样通过「位置索引」访问。关联容器内部通常基于平衡二叉搜索树（如红黑树） 或哈希表实现，保证了高效的查找性能（平均 O (log n) 或 O (1)）。

关联容器的分类

关联容器主要分为两大类别：有序关联容器和无序关联容器，二者的核心区别在于是否按「键的有序性」存储元素，以及底层实现机制的不同。

有序关联容器

有序关联容器的共性

• 键有序：元素默认按键的升序排列（可通过自定义比较函数修改，如 std::greater<Key> 实现降序）。
• 键的唯一性：set/map 要求键唯一，插入重复键会失败；multiset/multimap 允许键重复，插入重复键会成功并存储。
• 迭代器特性：迭代器为「双向迭代器」（支持 ++/--，但不支持随机访问如 it + 5），且迭代时会按键的顺序遍历。
• 查找效率：基于平衡二叉搜索树，查找、插入、删除的时间复杂度均为 O(log n)。

map和multimap

以下通过代码示例展示核心关联容器的关键操作（插入、查找、遍历、删除）。

1. map（有序键值对，键唯一）

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

int main() {
    // 1. 初始化：键（学号）-> 值（姓名），默认按键升序
    std::map<int, std::string> student_map = {{101, "Alice"}, {103, "Bob"}};

    // 2. 插入元素（三种方式）
    student_map.insert({102, "Charlie"});  // 键唯一，成功插入
    student_map[104] = "David";            // 用[]访问，不存在则插入
    auto ret = student_map.insert({101, "Eve"});  // 键101已存在，插入失败
    if (!ret.second) {
        std::cout << "键101已存在，对应值：" << ret.first->second << std::endl;
    }

    // 3. 查找元素（find()返回迭代器，未找到则为end()）
    auto it = student_map.find(102);
    if (it != student_map.end()) {
        std::cout << "找到学号102：" << it->second << std::endl;  // 输出 Charlie
    }

    // 4. 遍历元素（按键升序）
    std::cout << "所有学生：" << std::endl;
    for (const auto& pair : student_map) {
        std::cout << "学号：" << pair.first << "，姓名：" << pair.second << std::endl;
    }
    // 输出顺序：101(Alice) → 102(Charlie) → 103(Bob) → 104(David)

    // 5. 删除元素（按键删除）
    student_map.erase(103);  // 删除学号103
    std::cout << "删除后size：" << student_map.size() << std::endl;  // 输出 3

    return 0;
}

3. multimap（有序键值对，键可重复）

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

int main() {
    // 1. 初始化：键（课程ID）-> 值（学生姓名），键可重复
    std::multimap<int, std::string> course_multimap = {{1001, "Alice"}, {1001, "Bob"}};

    // 2. 插入重复键
    course_multimap.insert({1001, "Charlie"});  // 键1001已存在，仍成功插入
    course_multimap.insert({1002, "David"});     // 新键插入

    // 3. 查找所有相同键的元素（用equal_range()获取范围）
    auto range = course_multimap.equal_range(1001);
    std::cout << "课程1001的学生：" << std::endl;
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";  // 输出 Alice Bob Charlie
    }
    std::cout << std::endl;

    // 4. 遍历（按键升序）
    std::cout << "所有课程-学生：" << std::endl;
    for (const auto& pair : course_multimap) {
        std::cout << "课程" << pair.first << "：" << pair.second << std::endl;
    }

    return 0;
}

有序关联容器的关键细节

1. 排序规则：弱排序（Strict Weak Ordering）

（接上文）弱排序需满足以下 4 个条件（设比较函数为 comp(a, b)，表示 “a 应排在 b 之前”）：

• 非自反性：comp(a, a) 必须为 false（自己不能排在自己前面）；
• 非对称性：若 comp(a, b) 为 true，则 comp(b, a) 必须为 false；
• 传递性：若 comp(a, b) 为 true 且 comp(b, c) 为 true，则 comp(a, c) 必须为 true；
• 不可比性传递：若 a 与 b 不可比（comp(a,b) 和 comp(b,a) 均为 false），且 b 与 c 不可比，则 a 与 c 必须不可比。

示例：若自定义 “按字符串长度排序” 的比较函数，需确保满足弱排序：

// 自定义比较函数：长度短的字符串排在前面；长度相同则视为不可比
struct StrLenCmp {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() < b.size(); // 满足弱排序的 4 个条件
    }
};

// 使用自定义比较函数的 set
std::set<std::string, StrLenCmp> len_set = {"apple", "pear", "banana", "grape"};
// 遍历结果：按长度排序为 "pear"（4）、"apple"（5）、"grape"（5）、"banana"（6）

2. 键的不可修改性

有序关联容器中，键（Key）是不可修改的。原因是键的排序决定了元素在容器中的位置，修改键会破坏容器的有序结构，导致查找、插入等操作失效。

• 对于 set：元素本身就是键，因此 set 的迭代器是 “常量迭代器”（const_iterator），无法通过迭代器修改元素；
• 对于 map：元素是 std::pair<const Key, T>（键为 const 类型），因此只能修改 pair 的 “值（T）”，不能修改 “键（Key）”。

错误示例（修改 map 的键）：

std::map<int, std::string> id_name = {{1, "Alice"}, {2, "Bob"}};
auto it = id_name.find(1);
if (it != id_name.end()) {
    // it->first = 3; // 编译错误：键是 const 类型，不可修改
    it->second = "Alice Smith"; // 正确：仅修改值
}

lower_bound、upper_bound和 equal_range

lower_bound、upper_bound 和 equal_range 是 C++ 有序关联容器（如 set、map、multiset、multimap）提供的范围查找函数，利用容器的有序性高效定位元素。以下通过具体代码示例详细说明它们的用法：

假设有一个按「键（int）」升序排列的 map，存储学生分数与等级的对应关系：

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

int main() {
    // 创建并初始化有序map（键为分数，值为等级）
    std::map<int, std::string> score_map = {
        {60, "D"}, {70, "C"}, {80, "B"}, {90, "A"}, {100, "S"}
    };

    // 1. lower_bound(key)：返回第一个 >= key 的元素迭代器
    auto it_low = score_map.lower_bound(80);
    if (it_low != score_map.end()) {
        std::cout << "lower_bound(80)：" 
                  << it_low->first << " → " << it_low->second << std::endl;
        // 输出：80 → B（第一个>=80的元素）
    }

    // 2. upper_bound(key)：返回第一个 > key 的元素迭代器
    auto it_high = score_map.upper_bound(80);
    if (it_high != score_map.end()) {
        std::cout << "upper_bound(80)：" 
                  << it_high->first << " → " << it_high->second << std::endl;
        // 输出：90 → A（第一个>80的元素）
    }

    // 3. equal_range(key)：返回包含所有 == key 的元素范围 [first, last)
    auto range = score_map.equal_range(80);
    std::cout << "equal_range(80) 包含的元素：" << std::endl;
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "  " << it->first << " → " << it->second << std::endl;
        // 输出：80 → B（map中键唯一，因此只有一个元素）
    }

    return 0;
}

在 multiset 中处理重复键（关键场景）

multiset 允许存储重复键，这三个函数的作用更明显：

#include <iostream>
#include <set>

int main() {
    // 创建包含重复元素的有序multiset
    std::multiset<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    // multiset默认按升序排序，实际存储顺序：1,1,2,3,3,4,5,5,6,9

    // 1. lower_bound(3)：第一个 >=3 的元素
    auto it_low = nums.lower_bound(3);
    std::cout << "lower_bound(3)：" << *it_low << std::endl; // 输出 3

    // 2. upper_bound(3)：第一个 >3 的元素
    auto it_high = nums.upper_bound(3);
    std::cout << "upper_bound(3)：" << *it_high << std::endl; // 输出 4

    // 3. equal_range(3)：所有 ==3 的元素范围
    auto range = nums.equal_range(3);
    std::cout << "equal_range(3) 包含的元素：";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " "; // 输出 3 3（所有等于3的元素）
    }
    std::cout << std::endl;

    return 0;
}

函数返回值的关键说明

1. 迭代器范围的含义

   • [lower_bound(key), upper_bound(key)) 表示所有 >= key 且 <= key 的元素（即所有 == key 的元素），与 equal_range(key) 返回的范围完全一致。
   • 对于不包含 key 的容器，lower_bound 和 upper_bound 会返回同一个迭代器（插入 key 时的位置）。

2. 未找到元素的情况
   若容器中所有元素都小于 key，三个函数都会返回 end() 迭代器。

总结

• lower_bound(key)：找「第一个 >= key」的元素，用于定位范围的起点。
• upper_bound(key)：找「第一个 > key」的元素，用于定位范围的终点。
• equal_range(key)：直接返回所有「== key」的元素范围，等价于 pair(lower_bound, upper_bound)。

这三个函数仅适用于有序关联容器（依赖元素的排序特性），时间复杂度均为 O (log n)，是处理有序数据范围查询的高效工具。

无序关联容器

无序关联容器的共性

• 键无序：元素按「哈希值」分散存储在哈希表的「桶（Bucket）」中，遍历顺序不固定。
• 键的唯一性：unordered_set/unordered_map 键唯一，unordered_multiset/unordered_multimap 键可重复。
• 迭代器特性：迭代器为「前向迭代器」（仅支持 ++），遍历顺序与插入顺序无关。
• 查找效率：平均时间复杂度 O(1)（哈希表命中时），最坏情况 O (n)（哈希冲突严重时，需遍历桶内所有元素）。
• 哈希依赖：需为键类型提供默认哈希函数（std::hash<Key>），若为自定义类型，需手动实现哈希函数和 == 运算符（用于解决哈希冲突）。

 unordered_set（无序唯一键）

#include <iostream>
#include <unordered_set>

int main() {
    // 1. 初始化：存储唯一整数，无序
    std::unordered_set<int> num_set = {3, 1, 4};

    // 2. 插入元素
    num_set.insert(2);       // 成功插入
    auto ret = num_set.insert(3);  // 键3已存在，插入失败
    if (!ret.second) {
        std::cout << "元素3已存在" << std::endl;
    }

    // 3. 查找元素（平均O(1)）
    if (num_set.count(4)) {  // count()返回元素个数（0或1，因键唯一）
        std::cout << "找到元素4" << std::endl;
    }

    // 4. 遍历元素（无序，每次运行顺序可能不同）
    std::cout << "所有元素：";
    for (int num : num_set) {
        std::cout << num << " ";  // 可能输出：3 1 4 2（顺序不固定）
    }
    std::cout << std::endl;

    // 5. 删除元素
    num_set.erase(1);        // 删除元素1
    std::cout << "删除后size：" << num_set.size() << std::endl;  // 输出 3

    return 0;
}

无序关联容器的关键细节

1. 哈希函数与相等性判断

无序关联容器（如 unordered_map、unordered_set）基于哈希表实现，核心依赖两个组件：

• 哈希函数：将键（Key）映射为哈希表的 “桶索引”，默认使用 std::hash<Key>；
• 相等性判断函数：判断两个键是否 “相等”（用于处理哈希冲突），默认使用 std::equal_to<Key>。

若自定义键类型（如自定义结构体），需手动提供：

1. 特化的 std::hash<自定义类型> 模板（或在容器模板参数中指定哈希函数）；
2. 相等性判断函数（或重载 == 运算符，因为 std::equal_to 会调用 ==）。

示例（自定义结构体作为 unordered_map 的键）：

// 自定义结构体：表示二维点
struct Point {
    int x;
    int y;
    // 重载 ==，用于相等性判断
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 特化 std::hash<Point>，提供哈希函数
namespace std {
template <>
struct hash<Point> {
    size_t operator()(const Point& p) const {
        // 简单哈希：结合 x 和 y 的哈希值（避免碰撞的更优实现需更复杂逻辑）
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};
}

// 使用自定义键的 unordered_map
std::unordered_map<Point, std::string> point_name = {{{0,0}, "Origin"}, {{1,1}, "Point A"}};

2. 哈希冲突与桶的概念

哈希表通过 “桶（Bucket）” 存储元素：一个桶中可能包含多个哈希值相同（或哈希后索引相同）的元素（即 “哈希冲突”）。无序关联容器提供了与桶相关的成员函数，用于调试或优化性能：

• bucket_count()：返回当前哈希表的桶数量；
• bucket_size(size_t n)：返回第 n 个桶中元素的数量；
• bucket(const Key& k)：返回键 k 所在的桶索引。

示例（查看桶信息）：

std::unordered_set<int> us = {1,2,3,4,5,6,7,8};
std::cout << "桶数量：" << us.bucket_count() << std::endl; // 通常为 8、16 等 2 的幂
for (size_t i = 0; i < us.bucket_count(); ++i) {
    std::cout << "桶 " << i << " 的元素数：" << us.bucket_size(i) << std::endl;
}

使用关联容器的核心注意事项

1. 有序容器的键需支持比较

• 有序容器（set/map/multiset/multimap）默认使用 std::less<Key> 比较键，因此键类型必须支持 < 运算符。
• 若为自定义类型（如 struct），需手动重载 < 运算符，或在定义容器时指定自定义比较函数：

  struct Person {
      std::string name;
      int age;
      // 重载<，按年龄升序
      bool operator<(const Person& other) const {
          return age < other.age;
      }
  };
  std::set<Person> person_set;  // 可正常使用
  

2. 无序容器的键需支持哈希和相等比较

• 无序容器（unordered_*）依赖 std::hash<Key> 计算哈希值，且需 == 运算符判断键是否相等（解决哈希冲突）。
• 自定义类型需手动实现：

  struct Point {
      int x, y;
      // 重载==
      bool operator==(const Point& other) const {
          return x == other.x && y == other.y;
      }
  };
  // 特化std::hash<Point>
  namespace std {
      template<>
      struct hash<Point> {
          size_t operator()(const Point& p) const {
              // 简单哈希：组合x和y的哈希值
              return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
          }
      };
  }
  std::unordered_set<Point> point_set;  // 可正常使用
  

3. map 与 unordered_map 的 [] 运算符注意事项

• map 和 unordered_map 支持 [] 访问值（map[key] = value），但若键不存在，会自动插入一个默认构造的键值对（可能导致意外插入）。
• 若仅需「查找键是否存在」，优先用 find() 或 count()，避免 [] 的意外插入：

  std::map<int, std::string> m;
  // 错误：若键200不存在，会插入 {200, ""}（默认空字符串）
  if (m[200] == "Tom") { ... }
  // 正确：用find()判断
  auto it = m.find(200);
  if (it != m.end() && it->second == "Tom") { ... }
  

4. 迭代器有效性

• 有序容器：插入 / 删除元素后，除被删除元素的迭代器外，其他迭代器仍有效（平衡二叉树仅调整指针，节点地址不变）。
• 无序容器：
  • 插入元素时，若未触发哈希表扩容（load_factor 未超过阈值），迭代器有效；若触发扩容，所有迭代器失效（哈希表重建）。
  • 删除元素时，仅被删除元素的迭代器失效，其他迭代器仍有效。

5. 性能选择：有序 vs 无序

• 若需按键排序或范围查询（如 lower_bound()/upper_bound()），选有序容器（map/set）。
• 若仅需快速查找、插入、删除（不关心顺序），选无序容器（unordered_map/unordered_set），平均性能更优。

通过理解关联容器的分类、特性和使用注意事项，可以根据实际需求（如是否需排序、键是否唯一、性能要求）选择最合适的容器，避免常见错误并优化代码效率。