map

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

map 的基本操作

1. 创建 map

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

#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，其中包含插入操作的状态信息。

#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() 迭代器。

#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() 函数删除元素，可以根据键删除指定元素，也可以通过迭代器删除指定元素。

#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() 函数会进行越界检查，而 [] 操作符则会在键不存在时创建一个新元素。

#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，并通过迭代器访问键值对。

#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 的基本操作可以有效地提升数据管理和查找的效率。