简介

  • C++ <map>标准库

有序关联容器

  • 与顺序关联容器不同，有序关联容器不采用线性方式保存元素。相反，有序关联容器将键映射到值。通常情况下，有序关联容器的插入，删除和查找时间是相等的。
  • 标准库提供的4个有序关联容器分别为: map, multimap, set, multiset。
  • 每种有序关联容器都将元素保存在类似于树的有序数据结构。
  • 还有4个无序关联容器: unordered_map, unordered_multimap, unordered_set, unordered_multiset

map

  • map定义在<map>头文件中，它保存的是键/值对，而不是只保存值
  • 插入，查找和删除操作都是基于键的，值只不过是附属品。从概念上讲，map这个术语源于容器将键映射到值
  • 当需要根据键保存或获取元素时，以及需要按照特定顺序保存元素时，应该使用map

构建map

  • map类模板接受4种类型: 键类型，值类型，比较类型以及分配器类型
  • 如果忽略比较参数和分配器参数，那么map的构建和vector或list的构建是一样的，区别在于模板实例化中需要分别指定键和值的类型。
  • 例如构建一个map，使用int值作为键，Data类的对象作为值，map<int, Data> dataMap;在内部，dataMap为map中的每个元素存储一个pair<int, Data>

插入元素

  • 向顺序容器(例如vector和list)插入元素时，总是需要指定要插入元素的位置，而map不一样，它和其他关联容器都不需要指定插入位置。

  • map的内部实现会决定要保存新元素的位置，只需要提供键和值即可。

  • insert()方法。
  • 可以使用insert()方法向map添加元素，它有一个好处：允许判断键是否已经存在。insert()方法的一个问题是必须将键/值对指定为pair对象或initializer_list。
  • insert()的基本形式的返回类型是迭代器和布尔值组成的pair。返回类型这么复杂的原因是：
    • 如果指定的键已经存在，那么insert()不会改写元素值。返回的pair中的bool元素指出insert()是否真的插入了新的键/值对。
    • 迭代器引用是map中带有指定键的元素(根据插入成功与否这个键对应的值可能是新值或旧值)
  • operator[]
  • 向map插入元素的另一种方法是通过重载的operator[]。这种方法的区别主要在于语法：键和值分别是指定的。
  • 此外，operator[]总是成功的。如果给定键没有对应的元素值，那么就会创建带有对应键值的新元素。如果具有给定键的元素已经存在，operator[]会将元素值替换为新指定的值。
  • 不过operator[]有一点要注意：
    • 它总会构建一个新的值对象，即并不需要使用这个值对象，也同样如此。
    • 因为需要为元素提供一个默认的构造函数，这样可能会比insert()的效率低
  • emplace方法
  • map支持emplace()和emplace_hint()，从而在原位置构建元素，这与vector的emplace方法类似。
  • 还有一个try_emplace()方法，如果给定的键还不存在，那么它将在原位置插入元素；如果map中 已经存在相应的键，则什么也不做。

查找元素

  • map可根据指定的键查找元素，时间复杂度为指数时间
  • 如果只想指导在map中是否存在具有给定键的元素，那么可以使用count()成员函数。这个函数返回map中给定键的元素个数。对于map来说，这个函数返回的结果不是0就是1,因为map中不允许具有重复键的元素。

C++ std::map::find() 函数 详解

std::map::find() 是 C++ 标准模板库（STL）中 std::map 类的成员函数之一，用于在 map 中查找给定键的位置。以下是该函数的详细解释：

函数签名：

1
2

iterator find(const key_type& k);
const_iterator find(const key_type& k) const;

参数：

  • k：要查找的键值。

返回值：

  • 如果找到了给定键，则返回指向该键值对的迭代器；
  • 如果未找到，则返回指向 end() 的迭代器。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <map>

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

    // 插入一些键值对
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";
    myMap[4] = "Four";

    // 查找键为2的位置
    auto it = myMap.find(2);

    // 检查结果
    if (it != myMap.end()) {
        std::cout << "Key found: " << it->first << ", Value: " << it->second << std::endl;
    } else {
        std::cout << "Key not found" << std::endl;
    }

    // 尝试查找不存在的键
    it = myMap.find(5);

    // 检查结果
    if (it != myMap.end()) {
        std::cout << "Key found: " << it->first << ", Value: " << it->second << std::endl;
    } else {
        std::cout << "Key not found" << std::endl;
    }

    return 0;
}

在这个例子中，我们使用 myMap.find(2) 查找键为2的位置，并输出结果。然后，我们尝试使用 myMap.find(5) 查找不存在的键，并输出结果。通过使用 find 函数，我们可以有效地检查某个键是否存在于 std::map 中，以及在存在的情况下获取相应的值。

C++ <map>标准库

<map> 是 C++ 标准库中的头文件，定义了一组容器类模板，用于实现键-值对形式的关联容器。

std::map：

  • std::map 是一个关联容器，用于存储一组键值对（key-value pairs）。
  • 每个元素都是一个键值对，其中键（key）唯一，用于索引和快速查找值（value）。
  • 内部元素按照键的严格弱顺序（默认是升序）排列。
  • 主要特点：
    • 键值对按照键的严格弱顺序排列。
    • 键是唯一的，不允许重复。
    • 支持快速的查找、插入和删除操作。

主要操作：

  • insert(const value_type& val): 插入键值对。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const key_type& key): 查找键对应的值。
  • size(): 返回 map 中元素的数量。
  • empty(): 判断 map 是否为空。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <map>

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

    // 插入键值对
    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    myMap["Charlie"] = 35;

    // 查找元素
    auto it = myMap.find("Bob");
    if (it != myMap.end()) {
        std::cout << "Bob's age: " << it->second << std::endl;
    } else {
        std::cout << "Bob not found in map" << std::endl;
    }

    // 输出 map 中的元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

这个示例展示了 std::map 的基本使用方法，包括插入键值对、查找元素、遍历输出 map 中的键值对等操作。

C++ <map>标准库 详解

<map> 是 C++ 标准库中的头文件，定义了一组容器类模板，用于实现关联容器，允许存储一组唯一键和对应的值。主要包括 std::map 和 std::multimap。

std::map：

  • std::map 是一个关联容器，存储键值对，其中每个键都是唯一的，用于快速查找对应的值。
  • 主要特点：
    • 键值对是按照键的严格弱顺序（默认是升序）排列。
    • 键是唯一的，不允许重复。
  • 主要操作：
    • insert(const value_type& val): 插入键值对。
    • erase(const_iterator position): 删除指定位置的元素。
    • find(const key_type& key): 查找键对应的值。
    • size(): 返回 map 中元素的数量。
    • empty(): 判断 map 是否为空。

std::multimap：

  • std::multimap 与 std::map 类似，但允许键重复出现。
  • 主要特点：
    • 键值对是按照键的严格弱顺序（默认是升序）排列。
    • 键允许重复。
  • 主要操作与 std::map 类似。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <map>

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

    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    myMap["Charlie"] = 35;

    auto it = myMap.find("Bob");
    if (it != myMap.end()) {
        std::cout << "Bob's age: " << it->second << std::endl;
    } else {
        std::cout << "Bob not found in map" << std::endl;
    }

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

    return 0;
}

这个示例演示了 std::map 的基本用法，包括插入键值对、查找元素、遍历输出 map 中的键值对等操作。std::multimap 的使用与此类似，但允许键重复出现。

C++ <map>标准库 常用的类和函数

在 C++ <map> 标准库中，最常用的类是 std::map 和 std::multimap，它们提供了操作键-值对集合的常用函数和方法。

主要类：

  1. std::map：
    • 用于存储一组唯一的键值对，其中每个键是唯一的。
    • 特点：
      • 键值对按照键的严格弱顺序（默认是升序）排列。
      • 键是唯一的，不允许重复。
    • 主要方法：
      • insert(const value_type& val): 插入键值对。
      • erase(const_iterator position): 删除指定位置的元素。
      • find(const key_type& key): 查找键对应的值。
      • size(): 返回 map 中元素的数量。
      • empty(): 判断 map 是否为空。
  2. std::multimap：
    • 与 std::map 类似，但允许键重复出现。
    • 特点：
      • 键值对按照键的严格弱顺序（默认是升序）排列。
      • 键允许重复。
    • 主要方法与 std::map 类似。

常用方法：

  • insert(const value_type& val): 插入键值对。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const key_type& key): 查找键对应的值。
  • size(): 返回 map 中元素的数量。
  • empty(): 判断 map 是否为空。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <map>

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

    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    myMap["Charlie"] = 35;

    auto it = myMap.find("Bob");
    if (it != myMap.end()) {
        std::cout << "Bob's age: " << it->second << std::endl;
    } else {
        std::cout << "Bob not found in map" << std::endl;
    }

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

    return 0;
}

这个示例展示了 std::map 的基本用法，包括插入键值对、查找元素、遍历输出 map 中的键值对等操作。std::multimap 的使用与此类似，但允许键重复出现。

std::map

std::map 是 C++ 标准库中的关联容器，用于存储一组键值对（key-value pairs）。每个键都是唯一的，可以快速查找对应的值。

特点：

  • 有序性： 内部元素按照键的严格弱顺序（默认是升序）排列。
  • 唯一键： 键是唯一的，每个键对应一个值，不允许键的重复。
  • 底层实现： 通常使用平衡二叉树（红黑树）来实现。

主要操作：

  • insert(const value_type& val): 插入键值对。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const key_type& key): 查找键对应的值。
  • size(): 返回 map 中键值对的数量。
  • empty(): 判断 map 是否为空。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <map>

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

    myMap["Alice"] = 25;
    myMap["Bob"] = 30;
    myMap["Charlie"] = 35;

    auto it = myMap.find("Bob");
    if (it != myMap.end()) {
        std::cout << "Bob's age: " << it->second << std::endl;
    } else {
        std::cout << "Bob not found in map" << std::endl;
    }

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

    return 0;
}

这个示例展示了 std::map 的基本用法，包括插入键值对、查找元素、遍历输出 map 中的键值对等操作。

std::multimap

std::multimap 是 C++ 标准库中的关联容器，类似于 std::map，但允许键重复出现。

特点：

  • 有序性： 内部元素按照键的严格弱顺序（默认是升序）排列。
  • 允许重复键： std::multimap 中的键允许重复出现，即允许多个键对应不同的值。
  • 底层实现： 通常使用平衡二叉树（红黑树）来实现。

主要操作：

  • insert(const value_type& val): 插入键值对。
  • erase(const_iterator position): 删除指定位置的元素。
  • find(const key_type& key): 查找键对应的值。
  • size(): 返回 multimap 中键值对的数量。
  • empty(): 判断 multimap 是否为空。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <map>

int main() {
    std::multimap<std::string, int> myMultiMap;

    myMultiMap.insert(std::make_pair("Alice", 25));
    myMultiMap.insert(std::make_pair("Bob", 30));
    myMultiMap.insert(std::make_pair("Charlie", 35));
    myMultiMap.insert(std::make_pair("Bob", 32)); // 允许重复键

    auto it = myMultiMap.find("Bob");
    if (it != myMultiMap.end()) {
        std::cout << "Bob's age: " << it->second << std::endl;
    } else {
        std::cout << "Bob not found in multimap" << std::endl;
    }

    for (const auto& pair : myMultiMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

这个示例展示了 std::multimap 的基本用法，包括插入键值对、查找元素、遍历输出 multimap 中的键值对等操作。与 std::map 不同，std::multimap 允许多个键对应不同的值。