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

C++程序设计第十四章标准模板库(STL) 映射容器(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。

映射的底层一般用平衡树作为底层数据结构

pair举例：

#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= make_pair(1, "World");
    cout<<p2.first<<' '<<p2.second;
    return 0;
}

map举例一：

#include <iostream>
#include <map>

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

    // 插入元素
    myMap[1] = "apple";
    myMap[2] = "banana";
    myMap[3] = "cherry";

    // 访问元素
    std::cout << "Key 1: " << myMap[1] << std::endl;

    return 0;
}

map举例二：

#include <iostream>
#include <map>
using namespace std;

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

    // 使用 std::pair 方式插入
    mymap.insert(pair<char, int>('a', 100));
    mymap.insert(pair<char, int>('b', 200));

    // 使用 make_pair 方式插入
    mymap.insert(make_pair('c', 300));

    // 使用 operator[] 方式插入
    mymap['d'] = 400;

    // 使用 emplace 方式插入
    mymap.emplace('e', 500);

    // 输出 map 中的元素
    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的基本操作函数：

C++ maps是一种关联式容器，包含“关键字/值”对
begin() 返回指向map头部的迭代器
clear(）删除所有元素
count() 返回指定元素出现的次数, (帮助评论区理解：因为key值不会重复，所以只能是1 or 0)
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数

多重映射（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

C++程序设计

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

1. std::map

std::pair

1. `std::map`

`std::pair`