查找、键值对(key, value)等

目录

1.映射类 map

0. 引入 pair：

1.定义

2.插入

3. 遍历

4.❗operator[]的实现

5. 插入

 运用

2.Multimap 类

0. 引入：不去重的 Multi

1. Multimap 不支持 Operator[]

2. Multimap 的删除

1.映射类 map

0. 引入 pair：

在C++中，std::pair是一个非常有用的容器适配器，它属于C++标准模板库(STL)的一部分，主要用于存储两个相关联的数据项。插入和删除的时间复杂度：对于std::map，这些操作的时间复杂度为O(log n)，其中n是容器中的元素数量。

equal_range是 C++ 标准库中的一个函数模板，主要用于在有序容器（如 set, map, vector等）中查找一个值的范围。这使得std::pair可以用于std::map和std::set等容器中的键值对。

auto range = myMultimap.equal_range(1);for (auto it = range.first; it != range.second; ++it) {    cout << "Value: " << it->second << endl;}

2. Multimap 的删除

• 方法：使用 erase函数可以删除指定键的元素，例如删除所有键为 1 的元素。
• 迭代：由于std::map保持了键的排序，因此迭代访问元素时可以按照键的顺序进行，这对于需要排序访问的场景非常有用。这意味着它的键值对是有序的，按照键的自然顺序或由比较器定义的顺序排列。
• 迭代：std::unordered_map不保证元素的顺序，因此迭代访问元素时，元素的顺序可能是任意的，这取决于哈希函数和哈希表的实现。但在最坏的情况下，如果哈希冲突频繁发生，这些操作可能退化到线性时间复杂度O(n)。插入和删除操作的时间复杂度为O(1)，即常数时间。插入和删除操作上的性能随着容器大小的增长而增长（对数时间复杂度），而std::unordered_map在平均情况下的性能通常是常数时间，但对于特定的输入数据可能会退化。预期的性能、

  ---

  2.Multimap 类

  

  0. 引入：不去重的Multi

  • 背景：对于一词多义的情况，例如单词 "left" 可以表示 "左边" 和 "剩余"，需要存储同一个键的多个值。它将键映射到哈希表中的位置，理想情况下，不同的键将映射到不同的位置，从而允许快速查找。

    ---

    然后这个地方的使用不仅联想到了 hash ，讲个题外的知识点，将两者做个比较：

    std::map和std::unordered_map（通常称为hash map）是C++标准库中提供的两种关联容器，它们的主要区别在于内部实现和性能特征上。

    key 和 value 的类型可以不同，在map 内部，key 和 value 通过成员类型value_type绑定

    Compare:比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

    Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

    2.插入

    例如简单实现一个字典，我们可以有四种插入方法：

    ①我们可以直接调用pair 的构造函数来插入

    ②可以用匿名对象的方式来写

    ③调用神奇的make_pair

    ④直接用{ }

    std::map<std::string, std::string> dict;    std::pair<std::string, std::string> kv1("insert", "插入");    // 传参的四种实现    dict.insert(std::pair<std::string, std::string>("sort", "排序")); // 方法一    dict.insert(kv1); // 方法二    // C++98    dict.insert(std::make_pair("string", "字符串")); // 方法三    // C++11 多参数的构造函数隐式类型转换    // 最常用的    dict.insert({ "erase", "删除" }); // 方法四    // 输出字典的内容以验证是否插入成功    for (const auto& item : dict) {        std::cout << "Key: " << item.first << ", Value: " << item.second << std::endl;    }

    运行：

    

    对于方法四中存在的隐式类型转化:

    // 隐式类型的转换	string str1 = "hello";	A aa1 = { 1, 2 };	pair<string, string> kv2 = { "string", "字符串" };}

    3. 遍历

    和其他容器的迭代器一样，加上::小尾巴后就可以召唤出属于map 的迭代器了：

    map<string, string>::iterator it = dict.begin();//有请autoauto it=dict.begin();

    返回值需要返回迭代器中节点的数据，节点的数据是pair，可惜 pair 并不支持 流(stream)

    

    有问题就有解决方法：使用 it->中分别提取 first 和 second

    //map<string, string>::iterator it = dict.begin();//迭代器返回pair指针	auto it = dict.begin();	while (it != dict.end())	{		//it->first = "xxx";		//it->second = "xxx";		//cout << (*it).first << ":" << (*it).second << endl;		cout << it->first << ":" << it->second << endl;//结构体指针调用		++it;	}	cout << endl;

    map 同样支持甜甜的 范围 for 来遍历，这里建议加上 &提效：

    for (const auto& kv : dict)	{		cout << kv.first << ":"<<kv.second<<endl;	}}

    4.❗operator[]的实现

    mapped_type& operator[] (const key_type& k) {	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));	// return (*(ret.first)).second;	return ret.first->second;}

    判断 pair 的 first 就是map 的迭代器即指针类型 , map 指针->second 实现计数

    • key 已经在树里面，返回 pair<树里面 key 所在节点的 iterator, false>
    • key 不在树里面，返回 pair<新插入 key 所在节点的 iterator, true>

    ---

    5. 插入

    

    注意：

    // 不插入，不覆盖；插入过程中，只比较key，value是相同无所谓	// key已经有了就不插入了	dict.insert(make_pair("insert", "xxxx"));

    测试：

    void test_map4(){	map<string, string> dict;	dict.insert(make_pair("string", "字符串"));	dict.insert(make_pair("sort", "排序"));	dict.insert(make_pair("insert", "插入"));	cout << dict["sort"] << endl; // 查找和读	dict["map"];                  // 插入,返回1	dict["map"] = "映射,地图";     // 修改	dict["insert"] = "xxx";       // 修改	dict["set"] = "集合";         // 插入+修改}

    ---

     运用

    统计次数：例如说我们要计数如下动物：

    "兔子", "大象", "兔子", "长颈鹿", "狮子", "猴子","大象", "兔子", "猴子", "猴子", "大象", "斑马","狮子", "猴子", "长颈鹿", "兔子", "斑马", "猴子"

    我们可以这么写

    map<string, int> count_map;	for (auto& str : arr) {		map<string, int>::iterator it = count_map.find(str);		if (it != count_map.end()) {			it->second++;		}		else {			count_map.insert(make_pair(str, 1));		}	}

    这里实际上可以让insert 来优化一下

    

    我们可以看到insert 的返回值是一个pair<iterator, bool> 类型。

    std::pair由<utility>头文件提供，它包含两个成员，分别是first和second，这两个成员可以是任意类型的组合。

  • 解决方案：使用 multimap类，类似于 multiset，它允许存储具有相同键的多个值，但仍然保持排序。

    示例

    下面是一个使用std::pair的简单示例：

    #include <iostream>#include <utility> // 包含std::pair的定义int main() {    std::pair<std::string, int> studentGrade("Alice", 90);    std::cout << "Student: " << studentGrade.first << ", Grade: " << studentGrade.second << std::endl;   std::pair<std::string, int> studentGradeB("Student:Bob", 85);if (studentGradeA.second > studentGradeB.second) {    std::cout << "Alice has a higher grade than Bob." << std::endl;}    return 0;}

    

    在这个示例中，我们创建了一个std::pair实例，存储了学生的名字和成绩，然后比较了两个学生的成绩。std::pair的设计目的是为了方便地处理需要成对出现的数据，比如坐标点(x, y)、

  std::unordered_map

  • 内部实现：std::unordered_map使用哈希表作为底层数据结构。它返回一对迭代器，表示要查找值在容器中第一次出现的位置所在指针（迭代器）和最后一次出现的位置指针。

    std::map

    • 内部实现：std::map使用红黑树（一种自平衡的二叉搜索树）作为底层数据结构。以及对最坏情况性能的考虑。std::pair的声明语法如下：

      #include <utility> // 包含std::pair的定义std::pair<Type1, Type2> myPair;

      其中，Type1和Type2是你想要存储的两种类型。如果是第二次插入，插入失败，会返回它所在节点的迭代器的次数，再 ++。

      创建pair实例

      可以通过构造函数直接初始化std::pair：

      std::pair<int, double> p1(1, 2.5);

      也可以使用std::make_pair函数：

      std::pair<int, double> p2 = std::make_pair(1, 2.5);

      访问pair成员

      std::pair的成员first和second可以直接访问：

      std::pair<int, double> p(1, 2.5);int x = p.first;double y = p.second;

      pair的比较

      std::pair可以进行比较，比较规则首先比较first成员，如果first相等，则比较second成员。这是因为每次操作都需要在树中移动log n的距离。插入和删除的时间复杂度：平均而言，std::unordered_map的查找、

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