映射容器(map/pair/tuple container in STL)

组别：提高组
难度：5

std::map 是 C++ 标准模板库（STL）中的一种关联容器，用于存储键值对（key-value pairs）。它是一种有序的、基于键的容器，提供了高效的查找、插入和删除操作。下面是对 std::map 的完整介绍，包括其功能、特点、使用方法和一些高级用法。

特点:

键的唯一性: 每个键在 std::map 中都是唯一的，不能重复。
自动排序: std::map 中的键值对按照键的顺序自动排序（默认升序）。如果需要自定义排序，可以通过 Compare 参数指定。
对数时间复杂度: 查找、插入和删除操作的时间复杂度为 O(log n)，因为 std::map 通常基于红黑树（或其他平衡二叉树）实现。
双向迭代器: std::map 支持双向迭代器，可以正向或反向遍历。

pair可以看作一个内部有两个任意类型元素的结构体,常作为map的键值进行插入.使用时应加上头文件<utility>或<map>

多重映射(multimap)是允许有重复关键字的map。

unordered_map存储顺序是无序的

pair举例：

/****************************************************************
 * 代码作者: Alex Li
 * 创建时间: 2023-10-17 08:27
 * 最后修改: 2026-07-07 13:29
 * 文件描述: 演示 C++ pair 的创建、赋值以及 first 和 second 成员访问
 * 核心知识: pair 可以把两个值组合成一组，通过 first 访问第一个值，通过 second 访问第二个值。
****************************************************************/
#include <iostream>
#include <utility>
using namespace std;

int main(){
    pair<int, string> p1={0, "Hello"};
    pair<int, string> p2;
    cout<<p1.first<<' '<<p1.second;
    cout<<endl;
    p2= {1, "World"};   
    cout<<p2.first<<' '<<p2.second;
    return 0;
}

map举例一：

/****************************************************************
 * 代码作者: Alex Li
 * 创建时间: 2026-07-07 13:44
 * 最后修改: 2026-07-07 15:35
 * 文件描述: 演示 C++ map 的定义、键值对插入和按键访问
 * 核心知识: map 以 key -> value 的形式保存数据，insert 插入键值对，mymap[key] 可读取或修改对应值。
****************************************************************/
#include <iostream>
#include <map>
using namespace std;

int main(){
    map<char, int> mymap;

    // （1）插入单个值
    mymap.insert({'a', 100});
    mymap.insert({'f', 300});
      mymap.insert({'a', 200}); //不报错，会失败
    mymap['z']= 500;
    mymap['z']= 400;  //第二次会把原来的值覆盖掉。
    cout<<mymap['a']<<endl;
    cout<<mymap['z']<<endl;
    cout<<mymap['f']<<endl;
     mymap['f']++;
    for (const auto& kv : mymap) {
        cout << "Key: " << kv.first << ", Value: " << kv.second << endl;
    }
    return 0;
}

map和pair有什么区别

std::map 和 std::pair 是 C++ 标准模板库（STL）中的两个不同的模板类，它们在用途和功能上有明显的区别。

1. `std::map`

定义: std::map 是一种关联容器，它存储的是键值对（key-value pairs），其中每个键都是唯一的。
结构: 内部使用红黑树（或其他平衡二叉树）实现，因此具有对数时间复杂度的查找、插入和删除操作。
访问: 通过键（key）可以快速查找到对应的值（value）。例如 map[key] 或者 map.at(key)。
特点:
- 键是唯一的，不能重复。
- 键值对按照键的顺序（默认是升序）存储。
- 提供高效的查找、插入和删除操作。
- 支持范围遍历（range-based for loop）和迭代器遍历。

`std::pair`

定义: std::pair 是一个模板类，用于存储两个相关联的值或对象。它可以将两个不同类型或相同类型的对象绑定在一起。
结构: 它只是一种简单的数据结构，包含两个元素 first 和 second，分别代表成对的两个元素。
访问: 通过 pair.first 和 pair.second 访问其中的元素。
特点:
- 可以用于构建临时的键值对（如在 std::map 中存储的键值对就是 std::pair）。
- 是一个轻量级的对象，只包含两个元素，没有额外的管理机制（如 std::map 的平衡树结构）。
- 适合用于简单的配对需求。

map的基本操作函数：

成员函数	作用说明	示例
`insert()`	插入一个键值对。如果 key 已存在，不会覆盖原值。	`mymap.insert({'f', 300});`
`find()`	查找某个 key，找到返回迭代器，找不到返回 `end()`。	`if (mymap.find('f') != mymap.end())`
`count()`	判断某个 key 是否存在。普通 `map` 结果只可能是 `0` 或 `1`。	`if (mymap.count('f'))`
`erase()`	删除某个 key 对应的元素。	`mymap.erase('f');`
`size()`	返回键值对数量。	`mymap.size()`
`empty()`	判断是否为空。	`mymap.empty()`
`begin()`	返回第一个元素的迭代器。	`mymap.begin()`
`end()`	返回最后一个元素后面的位置，常用于判断遍历结束。	`mymap.end()`
`lower_bound()`	找到第一个 key `>= x` 的位置。	`mymap.lower_bound('c')`
`upper_bound()`	找到第一个 key `> x` 的位置。	`mymap.upper_bound('c')`

无序映射(unordered_map)

unordered_map 是 C++ STL（标准模板库）中的 哈希表（Hash Table）实现，提供 键值对（key-value）存储，可以高效地进行 查找、插入和删除 操作。

它的底层使用 哈希函数（Hash Function） 计算 key 的存储位置，因此：

查找 (find)、插入 (insert)、删除 (erase) 的平均时间复杂度是 O(1)，即非常快。
存储顺序是无序的（不同于 map，map 是有序的二叉搜索树，底层是红黑树）。
使用哈希冲突解决方法（通常是拉链法，维护链表或桶存储相同哈希值的 key）。

代码示例：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-03-05 21:27:09
 * 最后修改: 2025-03-05 22:15:30
 * 文件描述: unordered_map的使用
****************************************************************/

#include <iostream>
#include <unordered_map>
#include <utility>

using namespace std;

int main(){
    unordered_map<string, int> myMap;  //定义一个无序map
    
    myMap["potato"] = 100;   //插入元素方法一
    myMap.insert(make_pair("eggplant", 200));  //插入元素方法二
    myMap.insert({"tomato", 200});             //
    myMap.emplace("cucumber", 300);

    //遍历map
    for(const auto& x : myMap){
        cout << x.first << " " << x.second << endl;
    }

    //查找元素
    if(myMap.count("tomato")){
        cout << "tomato is in the map value: " <<myMap["tomato"]<< endl;
    }

    auto it=myMap.find("potato");
    if(it!=myMap.end()){
        cout << "potato is in the map value: " << it->second << endl;
    }

    myMap.erase("potato");  //删除元素

    cout << "after delete potato nordered_map include :" << endl;
    for (const auto& kv : myMap) {
        cout << kv.first << ": " << kv.second << endl;
    }

}

多重映射（multimap）

multimap 是一种关联容器，允许键的重复。与 std::map 不同，std::multimap 中同一个键可以关联多个值。这在需要将多个值关联到同一个键的情况下非常有用。

注意事项：

可以直接修改 std::pair 的成员变量：由于 first 和 second 是 public 的成员变量，可以直接通过 myPair.first 和 myPair.second 来访问和修改。
在容器中的使用：在使用如 std::map 和 std::multimap 这样的关联容器时，std::pair 的键部分（first）是只读的，而值部分（second）是可修改的。这是因为这些容器依赖键来维护元素的顺序和唯一性。

元组(tuple)

在C++中，tuple（元组）是一种可以存储多个不同类型的对象的数据结构。tuple在C++11标准中引入，并在头文件<tuple>中定义。与pair类似，tuple可以容纳任意数量和类型的元素。

/**************************************************************** 
 * Description: c++ tuple
 * Author: Alex Li
 * Date: 2024-06-25 10:34:41
 * LastEditTime: 2024-06-25 11:03:20
****************************************************************/
#include <iostream>
#include <tuple>
using namespace std;

int main() {
    tuple<int, double, string> myTuple(1, 3.14, "Hello");
    tuple<int, double, string> tuple1(1, 3.14, "World");
    tuple<string, char> tuple2("great", 'A');
    int i = get<0>(myTuple);
    double d = get<1>(myTuple);
    string s = get<2>(myTuple);

    cout << i << ", " << d << ", " << s <<endl;
    cout << "Size of myTuple: " << tuple_size<decltype(myTuple)>::value << endl;
    
     auto [n, m, p] = myTuple;  //-std=c++17
     std::cout << n << ", " << m << ", " << p << std::endl;

    if (myTuple < tuple1) {  
//按元素顺序直到找到第一个不相等的元素为止。比较顺序是从第一个元素开始，如果第一个元素相等，则比较第二个元素，依此类推。
        std::cout << "tuple1 is less than tuple2" << std::endl;
    } else {
        std::cout << "tuple1 is not less than tuple2" << std::endl;
    }
    auto combined = tuple_cat(tuple1, tuple2);

    auto [a,b,c,e,f] = combined;

    std::cout << a << ", " << b << ", " << c << ", " <<e<<", "<<f << std::endl;

    return 0;
}

Previous Topic

Back to Lesson

Next Topic

映射容器(map/pair/tuple container in STL)

1. std::map

std::pair

1. `std::map`

`std::pair`