# map

URL: https://caijiao.org/cpp/stl/map
Source: docs/cpp/stl/map.md
Description: 本节介绍 C++ 标准库中的 'map' 容器，讲解其基本操作，如插入元素、查找元素、删除元素等，以及其在实际开发中的应用。

`map` 是 C++ 标准库中提供的关联容器，它是一种基于红黑树实现的有序字典容器，用于存储键值对。每个元素包含一个键（key）和一个值（value），并且 `map` 会根据键自动排序。`map` 中的键是唯一的，且键值对的顺序由键决定。

## map 的基本操作

### 1. 创建 `map`

`map` 可以通过多种方式进行初始化，如空初始化、使用初始化列表等。

```cpp
#include <iostream>
#include <map>

int main() {
    // 空初始化
    std::map<int, std::string> map1;

    // 使用初始化列表初始化
    std::map<int, std::string> map2 = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};

    // 打印 map
    for (const auto& pair : map2) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
````

### 2. 插入元素

可以使用 `insert()` 函数插入新的键值对，`insert()` 返回一个 `pair`，其中包含插入操作的状态信息。

```cpp
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> map = {{1, "apple"}, {2, "banana"}};

    // 插入新元素
    map.insert({3, "cherry"});

    // 使用返回值检查是否插入成功
    auto result = map.insert({2, "blueberry"});
    if (!result.second) {
        std::cout << "Key 2 already exists, insertion failed!" << std::endl;
    }

    // 打印 map
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
```

### 3. 查找元素

使用 `find()` 函数查找特定键的元素。如果元素存在，返回指向该元素的迭代器；如果不存在，返回 `end()` 迭代器。

```cpp
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> map = {{1, "apple"}, {2, "banana"}};

    // 查找键为 2 的元素
    auto it = map.find(2);
    if (it != map.end()) {
        std::cout << "Found: " << it->first << ": " << it->second << std::endl;
    } else {
        std::cout << "Not found!" << std::endl;
    }

    return 0;
}
```

### 4. 删除元素

使用 `erase()` 函数删除元素，可以根据键删除指定元素，也可以通过迭代器删除指定元素。

```cpp
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> map = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};

    // 根据键删除元素
    map.erase(2);

    // 删除指定位置的元素
    auto it = map.find(1);
    if (it != map.end()) {
        map.erase(it);
    }

    // 打印 map
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
```

### 5. 访问元素

`map` 提供了两种方式来访问元素：使用 `[]` 操作符或者 `at()` 函数。`at()` 函数会进行越界检查，而 `[]` 操作符则会在键不存在时创建一个新元素。

```cpp
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> map = {{1, "apple"}, {2, "banana"}};

    // 使用 [] 操作符访问元素
    std::cout << "Key 1: " << map[1] << std::endl;

    // 使用 at() 函数访问元素
    std::cout << "Key 2: " << map.at(2) << std::endl;

    return 0;
}
```

### 6. 遍历 `map`

可以使用迭代器遍历 `map`，并通过迭代器访问键值对。

```cpp
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> map = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};

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

    return 0;
}
```

## map 的优势

* **自动排序**：`map` 内部使用红黑树存储键值对，自动根据键进行排序。
* **键唯一性**：`map` 保证每个键在容器中是唯一的，这使得它非常适合用于存储不重复的数据。
* **快速查找**：通过二叉查找树，`map` 提供了对元素的快速查找。

## map 的局限性

* **性能**：虽然 `map` 提供对元素的快速查找，但由于内部是基于红黑树实现，插入和删除操作的性能相对较低，尤其是在容器中有大量元素时。
* **内存占用**：与 `unordered_map` 相比，`map` 的内存占用稍高，因为它需要存储额外的树结构信息。

## 小结

`map` 是一个非常有用的容器，适用于需要按照键顺序存储数据的场景。掌握 `map` 的基本操作可以有效地提升数据管理和查找的效率。