C++ STL（8）map

一、map

1、简介

std::map 是 C++ 标准模板库中的一个关联容器，它存储的元素是键值对（std::pair<Key, T>），其中 Key 表示键的类型，T 表示与键关联的值的类型。具备下面的特点：

• 通常是基于红黑树（Red-Black Tree）实现的。
• 元素按照键的顺序存储。键必须支持 < 运算符（或提供自定义比较函数），这样容器会根据键的大小自动排序元素。默认是按照键的升序排列元素，也可以提供自定义的比较函数或比较对象来改变排序规则。
• 提供双向迭代器，允许正向和反向遍历元素。
• 插入、删除和查找操作的时间复杂度为 O(logn)。

2、初始化

以下是 std::map 的声明和初始化示例：

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

int main() {
    // 声明一个存储 std::string 到 int 的映射
    std::map<std::string, int> myMap;

    // 初始化
    std::map<std::string, int> anotherMap = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};
    return 0;
}

3、插入

可以使用下面的方法往std::map插入元素，如下：

方法一：使用 insert 方法：

std::map<std::string, int> myMap;
myMap.insert(std::make_pair("Alice", 25));
myMap.insert({"Bob", 30});
// 或者使用 insert 的返回值检查插入是否成功
auto result = myMap.insert({"Charlie", 35});
if (result.second) {
    std::cout << "Insertion successful" << std::endl;
}

• insert 方法会尝试插入一个键值对，如果键已经存在，插入将失败。
• 对于 insert 方法的返回值，它是一个 std::pair<iterator, bool>，其中 iterator 指向已存在的元素或新插入的元素，bool 表示插入是否成功。

方法二：使用 operator[]

myMap["David"] = 28;

• 使用 operator[] 插入元素时，如果键不存在，会创建一个新元素并使用默认值初始化，对于基本类型，如 int，默认值为 0。
• 如果键已经存在，会更新该键对应的值。

4、删除

使用erase方法删除std::map中的元素，如下：

std::map<std::string, int> myMap = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};

// 方法一：删除键为 "Bob" 的元素
myMap.erase("Bob");

// 方法二：查找 "Bob" 元素的迭代器，通过迭代器删除元素
auto it = myMap.find("Bob");
if (it!= myMap.end()) {
    myMap.erase(it);
}

5、遍历

可以使用下面两种方式遍历std::map，如下：

// 使用范围 for 循环
for (const auto& pair : myMap) {
    std::cout << pair.first << " is " << pair.second << " years old." << std::endl;
}

// 使用迭代器
for (auto it = myMap.begin(); it!= myMap.end(); ++it) {
    std::cout << it->first << " is " << it->second << " years old." << std::endl;
}

6、查找

使用find方法查找指定的元素，如下：

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

int main() {
    std::map<std::string, int> myMap = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};

    // 使用 find 方法查找元素
    std::string targetKey = "Bob";
    auto it = myMap.find(targetKey);

    if (it!= myMap.end()) {
        std::cout << "Found element with key '" << targetKey << "': " << it->first << " is " << it->second << " years old." << std::endl;
    } else {
        std::cout << "Element with key '" << targetKey << "' not found." << std::endl;
    }

    return 0;
}