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 常用操作

4. std::map 示例代码

#include <iostream>
#include <map>
using namespace std;
int main() {
    // 创建一个 map，键为字符串，值为整数
    map<string, int> ma;
    // 插入元素
    ma["apple"] = 1;
    ma["banana"] = 2;
    ma["lemon"] = 3;
    // 输出 map 的大小
    cout << "Size of map: " << ma.size() << endl;
    // 查找并输出键 "apple" 的值
    cout << "Value of apple: " << ma["apple"] << endl;
    // 检查键 "pear" 是否存在
    if (ma.count("pear")) {
        cout << "pear exists" << endl;
    } else {
        cout << "pear does not exist" << endl;
    }
    // 使用 lower_bound 查找不小于 "cow" 的第一个元素
    auto it = ma.lower_bound("cow");
    if (it != ma.end()) {
        cout << "Lower bound of cow: " << it->first << " -> " << it->second << endl;
    } else {
        cout << "No element greater than or equal to cow" << endl;
    }
    // 遍历 map 并输出每个键值对
    for (const auto& pair : ma) {
        cout << pair.first << " -> " << pair.second << endl;
    }
    // 删除键为 "banana" 的元素
    ma.erase("banana");
    // 输出删除后的 map
    cout << "After erase:" << endl;
    for (const auto& pair : ma) {
        cout << pair.first << " -> " << pair.second << endl;
    }
    return 0;
}

5. 代码解析

1. 插入元素：

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

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

2. 查找元素：

    if (ma.count("pear")) {
        cout << "pear exists" << endl;
    } else {
        cout << "pear does not exist" << endl;
    }

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

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

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

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

4. 遍历 map：

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

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

5. 删除元素：

    ma.erase("banana");

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

6. 小结

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