C++ std::map

1. 什么是 std::map？

std::map 是 C++ 标准库提供的一种关联容器，它基于红黑树实现，可以存储键值对（key-value pairs）。map 中的元素根据键的大小自动排序，且每个键在 map 中是唯一的。

2. std::map 的特点

  • 自动排序：map 会根据键（key）进行自动排序，默认为升序排列。
  • 唯一键：每个键值在 map 中是唯一的，不能重复。
  • 高效查找：map 采用平衡二叉搜索树（如红黑树）实现，因此支持高效的插入、删除和查找操作，平均时间复杂度为 O(log n)。
  • 元素类型：map 中的元素类型是 std::pair<const Key, T>，即键和值分别为 Key 类型和 T 类型，键是不可修改的。

3. std::map 常用操作

操作 描述
insert() 插入元素，如果键已经存在，则不会插入新的键值对。
find() 查找指定键的元素，返回一个迭代器，若找不到则返回 end()。
count() 查找指定键是否存在，返回键出现的次数（对于 map 来说，一般为 0 或 1）。
lower_bound() 返回指向第一个 不小于 指定键的元素的迭代器。
upper_bound() 返回指向第一个 大于 指定键的元素的迭代器。
erase() 删除指定键的元素，或者删除指定范围内的元素。
size() 返回 map 中元素的数量。
empty() 检查 map 是否为空。

4. std::map 示例代码

  1. #include <iostream>
  2. #include <map>
  4. using namespace std;
  6. int main() {
  7.     // 创建一个 map，键为字符串，值为整数
  8.     map<string, int> ma;
  10.     // 插入元素
  11.     ma["apple"] = 1;
  12.     ma["banana"] = 2;
  13.     ma["lemon"] = 3;
  15.     // 输出 map 的大小
  16.     cout << "Size of map: " << ma.size() << endl;
  18.     // 查找并输出键 "apple" 的值
  19.     cout << "Value of apple: " << ma["apple"] << endl;
  21.     // 检查键 "pear" 是否存在
  22.     if (ma.count("pear")) {
  23.         cout << "pear exists" << endl;
  24.     } else {
  25.         cout << "pear does not exist" << endl;
  26.     }
  28.     // 使用 lower_bound 查找不小于 "cow" 的第一个元素
  29.     auto it = ma.lower_bound("cow");
  30.     if (it != ma.end()) {
  31.         cout << "Lower bound of cow: " << it->first << " -> " << it->second << endl;
  32.     } else {
  33.         cout << "No element greater than or equal to cow" << endl;
  34.     }
  36.     // 遍历 map 并输出每个键值对
  37.     for (const auto& pair : ma) {
  38.         cout << pair.first << " -> " << pair.second << endl;
  39.     }
  41.     // 删除键为 "banana" 的元素
  42.     ma.erase("banana");
  44.     // 输出删除后的 map
  45.     cout << "After erase:" << endl;
  46.     for (const auto& pair : ma) {
  47.         cout << pair.first << " -> " << pair.second << endl;
  48.     }
  50.     return 0;
  51. }

5. 代码解析

  1. 插入元素：

    1.  ma["apple"] = 1;
    2.  ma["banana"] = 2;
    3.  ma["lemon"] = 3;

    使用 map 的 [] 操作符可以插入或修改元素。如果指定的键不存在，会插入新的键值对；如果键已经存在，会更新对应的值。

  2. 查找元素：

    1.  if (ma.count("pear")) {
    2.      cout << "pear exists" << endl;
    3.  } else {
    4.      cout << "pear does not exist" << endl;
    5.  }

    使用 count 来检查一个键是否存在。对于 map，count 返回值要么是 0（不存在），要么是 1（存在）。

  3. 使用 lower_bound 查找第一个不小于给定键的元素：

    1.  auto it = ma.lower_bound("cow");
    2.  if (it != ma.end()) {
    3.      cout << "Lower bound of cow: " << it->first << " -> " << it->second << endl;
    4.  }

    lower_bound("cow") 会返回一个指向第一个键不小于 "cow" 的元素的迭代器。在这里，返回的是 "lemon"。

  4. 遍历 map：

    1.  for (const auto& pair : ma) {
    2.      cout << pair.first << " -> " << pair.second << endl;
    3.  }

    使用范围基 for 循环遍历 map，可以通过 pair.first 获取键，pair.second 获取值。

  5. 删除元素：

    1.  ma.erase("banana");

    使用 erase 删除指定键的元素，删除后该元素不再存在于 map 中。

6. 小结

  • std::map 是一个有序的关联容器，键值对按照键的顺序自动排列。
  • 常用操作包括插入、查找、删除、遍历以及查找指定位置的元素（如使用 lower_bound 和 upper_bound）。
  • map 提供了高效的查找和插入操作，适用于需要按键排序存储数据的场景。