《21天学通C++》（第二十章）STL映射类（map和multimap）

为什么需要map和multimap：
1.查找高效： 映射类允许通过键快速查找对应的值，这对于需要频繁查找特定元素的场景非常适合。
2.自动排序： 会自动根据键的顺序对元素进行排序
3.多级映射： 映射类可以嵌套使用，创建多级映射，这对于复杂的数据结构非常有用
4.键值对存储： 映射类专门设计用于存储键值对（key-value）

map 和multimap 之间的区别在于，后者能够存储重复的键，而前者只能存储唯一的键，要使用需要包含头文件<map>

1.实例化map和multimap

map实例化：

std::map<key_type, value_type> map_instance;
//key_type 是键的类型。
//value_type 是与每个键关联的值的类型。

#include <iostream>
#include <map>

int main() {
    // 实例化std::map，键类型为int，值类型为std::string
    std::map<int, std::string> myMap;

    // 向map中添加元素
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    // 打印map和multimap的内容
    std::cout << "Map:" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    // 尝试添加重复的键，这将更新已存在的键对应的值
    myMap[1] = "ONE"; // "one" 将被 "ONE" 替换

    // 打印map的内容
    std::cout << "Map:" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    system("pause");
    return 0;
}

multimap实例化：

std::multimap<key_type, value_type> multimap_instance;
//key_type 是键的类型，可以有重复。
//value_type 是与每个键关联的值的类型。

#include <iostream>
#include <map>

int main() {
    // 实例化std::multimap，允许有相同键的多个元素
    std::multimap<int, std::string> myMultimap;

    // 向multimap中添加具有相同键的多个元素
    myMultimap.insert(std::make_pair(1, "uno"));
    myMultimap.insert(std::make_pair(1, "eins"));

    // 打印multimap的内容
    std::cout << "Multimap:" << std::endl;
    for (const auto& pair : myMultimap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }
    system("pause");
    return 0;
}

2.在map和multimap中插入元素

使用insert()成员函数插入

//key为键，val为值
map.insert(std::make_pair(key,val));
map.insert(std::pair<int,string>(key,val));
map[key]=val;

//multimap操作相同，但无法使用数组语法[]来插入

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

int main() {
    // 实例化std::multimap，允许有相同键的多个元素
    multimap<int, string> myMultimap;

    // 向multimap中添加具有相同键的多个元素
    myMultimap.insert(make_pair(1, "one"));
    myMultimap.insert(pair<int,string>(1, "two"));

    // 打印multimap的内容
    cout << "Multimap:" << endl;
    for (const auto& pair : myMultimap) {
        cout << pair.first << " : " << pair.second << endl;
    }

    //实例化std::map
    map<int,string> myMap;

    //向map中添加元素
    myMap[1]="map_one";
    myMap.insert(make_pair(2,"map_two"));
    myMap.insert(pair<int,string>(3,"map_three"));

    // 打印map的内容
    cout << "map:" << endl;
    for (const auto& pair : myMap) {
        cout << pair.first << " : " << pair.second << endl;
    }
    

    system("pause");
    return 0;
}

3.在map和multimap中查找元素

使用find()成员函数，该函数会返回一个迭代器

在map中查找

#include <map>
#include <iostream>
#include <string>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "one";
    myMap[2] = "two";

    // 查找键为1的元素
    auto it = myMap.find(1);
    //检查是否查找成功
    if (it != myMap.end()) {
        //myMap.end()指向容器的末尾，即最后一个元素之后的位置
        //如果已经找到了，就不会指向这个位置，反之则没有找到
        std::cout << "Found: " << it->second << std::endl; // 输出 "Found: one"
    } else {
        std::cout << "Not found" << std::endl;
    }

    // 查找键为3的元素，这个键不存在于map中
    it = myMap.find(3);
    if (it == myMap.end()) {
        std::cout << "Not found" << std::endl;
    }

    system("pause");
    return 0;
}

在multimap中查找
因为mulitimap允许包含多个键相同的键值对，所以可以用multimap::count()函数确定有多少个，再对迭代器进行递增，来访问这些值

#include <map>
#include <iostream>
#include <string>

int main() {
    std::multimap<int, std::string> myMultimap;
    
    // 插入具有相同键的不同值的元素
    myMultimap.insert(std::make_pair(1, "one"));
    myMultimap.insert(std::make_pair(1, "ONE"));
    myMultimap.insert(std::make_pair(2, "two"));
    
    // 查找键为1的元素
    auto it = myMultimap.find(1);
    
    // 如果找到了至少一个元素
    if (it != myMultimap.end()) {
        // 使用count()确定键为1的元素数量
        size_t count = myMultimap.count(1);
        
        // 遍历所有具有键为1的元素
        for (size_t i = 0; i < count; ++i) {
            std::cout << it->second << " ";
            // 递增迭代器以移动到下一个具有相同键的元素
            ++it;
        }
    }
    
    // 如果没有找到键为1的元素，输出"Not found"
    else {
        std::cout << "Not found" << std::endl;
    }
    
    system("pause");
    return 0;
}

4.删除map和multimap中的元素、

使用erase()函数，有以下几种版本

删除指定位置的元素

map.erase(iterator pos);//使用迭代器
map.erase(key);//使用键

删除指定范围的元素

map.erase(iterator first, iterator last);//使用迭代器确定边界

#include <map>
#include <iostream>
#include <string>

int main() {
    std::multimap<int, std::string> myMultimap;
    
    // 插入具有相同键的不同值的元素
    myMultimap.insert(std::make_pair(1, "one"));
    myMultimap.insert(std::make_pair(1, "ONE"));
    myMultimap.insert(std::make_pair(2, "two"));
    myMultimap.insert(std::make_pair(3, "three"));
    myMultimap.insert(std::make_pair(4, "four"));
    myMultimap.insert(std::make_pair(5, "five"));


    //删除键为2
    myMultimap.erase(2);
    //删除键为1的元素
    myMultimap.erase(myMultimap.find(1));//只能删除one，而ONE删不掉
    //删除键3和键4
    auto it3=myMultimap.find(3);
    auto it4=myMultimap.find(4);
    myMultimap.erase(it3,it4);
    
    for(auto& pair:myMultimap){
        std::cout<<pair.first<<":"<<pair.second<<std::endl;
    }
    
    
    system("pause");
    return 0;
}

输出结果

5.提供自定义排序谓词

语法

#include <map>
#include <iostream>
#include <string>

// 自定义比较函数
struct CustomCompare {
    bool operator()(int a, int b) const {
        // 基于字符串长度进行比较
        return std::to_string(a).length() < std::to_string(b).length();
    }
};

int main() {
    // 使用自定义比较函数的std::map
    std::map<int, std::string, CustomCompare> myMap;
    // 使用自定义比较函数的std::multimap
    std::multimap<int, std::string, CustomCompare> myMultimap;

    // 向map中插入元素。由于map中键必须是唯一的，这里插入的元素将根据自定义的比较逻辑被排序。
    myMap.insert({100, "Hundred"});
    myMap.insert({10, "Ten"});
    myMap.insert({1000, "Thousand"});

    // 向multimap中插入元素。multimap允许有相同键的多个元素。
    myMultimap.insert({100, "Hundred"});
    myMultimap.insert({10, "Ten"});
    myMultimap.insert({1000, "Thousand"});
    myMultimap.insert({100, "Another Hundred"}); // 允许重复键

    // 遍历map并打印键值对
    std::cout << "Map contents:" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    // 遍历multimap并打印键值对
    std::cout << "Multimap contents:" << std::endl;
    for (const auto& pair : myMultimap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    system("pause");
    return 0;
}

6.基于散列表的unordered_map和unordered_multimap

从C++11起，支持散列映射，要使用这两个容器，需要包含<unordered_map>，有以下特点

1. 因为散列表的特性，理想情况下性能更高，最坏情况下性能更差
2. 无序性

基本操作

#include <unordered_map>
#include <iostream>
#include <string>

int main() {
    // 使用整数作为键，字符串作为值的unordered_map
    std::unordered_map<int, std::string> um;

    // 插入元素
    um.insert({1, "one"});
    um[2] = "two"; // 使用下标操作符

    // 查找元素
    auto it = um.find(1);
    if (it != um.end()) {
        std::cout << "Found: " << it->second << std::endl; // 输出 "Found: one"
    } else {
        std::cout << "Element with key 1 not found" << std::endl;
    }

    // 删除键为1的元素
    um.erase(1);

    // 再次尝试查找键为1的元素
    it = um.find(1);
    if (it == um.end()) {
        std::cout << "Element with key 1 not found after erase" << std::endl;
    }

    // 使用整数作为键，字符串作为值的unordered_multimap
    std::unordered_multimap<int, std::string> umm;

    // 插入具有相同键的多个元素
    umm.insert({1, "one"});
    umm.insert({1, "ONE"});

    // 查找所有键为1的元素
    auto range = umm.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " "; // 输出 "one ONE"
    }
    std::cout << std::endl;

    // 删除所有键为1的元素
    umm.erase(1);

    // 再次查找键为1的元素，应该找不到
    range = umm.equal_range(1);
    if (std::distance(range.first, range.second) == 0) {
        std::cout << "No elements with key 1 found after erase" << std::endl;
    }

    system("pause");
    return 0;
}