复试机试map

在 C++ 标准库中，与映射相关的容器主要有四种，分别是 std::map、std::multimap、std::unordered_map 和 std::unordered_multimap。下面将详细介绍这四种容器，同时解释 std::pair，并说明 std::map 的插入、删除和查找操作。

四种映射容器

1. `std::map`

有序性：基于红黑树（一种自平衡的二叉搜索树）实现，元素按照键（key）的大小进行排序，默认使用 std::less<Key> 作为比较函数，即升序排列。
键的唯一性：每个键只能出现一次，插入重复的键时，插入操作会被忽略。
适用场景：当需要对键进行排序，并且每个键对应唯一值的场景，例如字典，每个单词对应一个解释。

2. `std::multimap`

有序性：同样基于红黑树实现，元素按照键的大小进行排序。
键的重复性：允许键重复，即一个键可以对应多个值。
适用场景：当一个键可能对应多个值的场景，例如一个学生的多个成绩记录，学生姓名作为键，成绩作为值。

3. `std::unordered_map`

有序性：基于哈希表实现，元素的存储位置由键的哈希值决定，不保证元素的顺序。
键的唯一性：每个键只能出现一次，插入重复的键时，插入操作会被忽略。
适用场景：当不需要对键进行排序，且对查找、插入和删除操作的效率要求较高的场景，例如缓存系统。

4. `std::unordered_multimap`

有序性：基于哈希表实现，不保证元素的顺序。
键的重复性：允许键重复，一个键可以对应多个值。
适用场景：当一个键可能对应多个值，且不需要对键进行排序的场景，例如统计一篇文章中每个单词的出现位置。

`std::pair`

std::pair 是一个模板类，用于将两个值组合成一个对象。在映射容器中，每个元素都是一个 std::pair，其中第一个元素是键（first），第二个元素是值（second）。

示例代码

#include <iostream>
#include <utility>

int main() {
    std::pair<int, std::string> p(1, "apple");
    std::cout << "Key: " << p.first << ", Value: " << p.second << std::endl;
    return 0;
}

代码解释

std::pair<int, std::string> p(1, "apple");：创建一个 std::pair 对象 p，键的类型为 int，值的类型为 std::string。
p.first：访问 std::pair 的第一个元素（键）。
p.second：访问 std::pair 的第二个元素（值）。

`std::map` 的插入、删除和查找操作

插入操作

可以使用 insert 方法或 [] 运算符进行插入。

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    // 使用 insert 方法插入
    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert({2, "banana"});

    // 使用 [] 运算符插入
    myMap[3] = "cherry";

    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

删除操作

可以使用 erase 方法删除指定键的元素。

#include <iostream>
#include <map>

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

    // 删除键为 2 的元素
    myMap.erase(2);

    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

查找操作

可以使用 find 方法查找指定键的元素。

#include <iostream>
#include <map>

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

    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    } else {
        std::cout << "Key not found." << std::endl;
    }

    return 0;
}

`std::multimap` 的查找操作，主要包括查找单个键对应的所有元素、统计某个键的元素数量以及查找键的范围等操作。

包含头文件

在使用 std::multimap 之前，需要包含 <map> 头文件：

#include <map>

查找单个键对应的所有元素

可以使用 equal_range 或 lower_bound 与 upper_bound 组合来查找某个键对应的所有元素。

使用 `equal_range` 方法

equal_range 方法返回一个 std::pair，其中 first 是指向该键第一个匹配元素的迭代器，second 是指向该键最后一个匹配元素的下一个位置的迭代器。通过遍历这个范围，可以访问该键对应的所有元素。

#include <iostream>
#include <map>

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

    // 查找键为 1 的所有元素
    auto range = myMultimap.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

使用 `lower_bound` 和 `upper_bound` 方法

lower_bound 方法返回指向该键第一个匹配元素的迭代器，upper_bound 方法返回指向该键最后一个匹配元素的下一个位置的迭代器。通过这两个迭代器可以确定该键对应的元素范围。

#include <iostream>
#include <map>

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

    // 查找键为 1 的所有元素
    auto lower = myMultimap.lower_bound(1);
    auto upper = myMultimap.upper_bound(1);
    for (auto it = lower; it != upper; ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

统计某个键的元素数量

可以使用 count 方法来统计某个键在 std::multimap 中出现的次数，也就是该键对应的元素数量。

#include <iostream>
#include <map>

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

    // 统计键为 1 的元素数量
    size_t count = myMultimap.count(1);
    std::cout << "Count of key 1: " << count << std::endl;

    return 0;
}

查找键是否存在

可以使用 find 方法来查找某个键是否存在于 std::multimap 中。如果找到，返回指向该键第一个匹配元素的迭代器；如果未找到，返回 end() 迭代器。

#include <iostream>
#include <map>

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

    // 查找键为 2 的元素
    auto it = myMultimap.find(2);
    if (it != myMultimap.end()) {
        std::cout << "Key 2 found, Value: " << it->second << std::endl;
    } else {
        std::cout << "Key 2 not found." << std::endl;
    }

    return 0;
}

综上所述，std::multimap 提供了多种查找操作，你可以根据具体需求选择合适的方法来查找元素。

考研机试常用的数据结构文章被收录于专栏

考研机试常用的数据结构