底层机制及其应用场景

std::multimap<int,std::string>mm;mm.insert({1,"one"});mm.insert({1,"uno"});// 允许插入重复的键

if(m.find(2)!=m.end()){std::cout <<"键 2 存在，值为: "<<m[2]<<std::endl;}

std::multiset<int>ms;ms.insert(10);ms.insert(5);ms.insert(10);// 允许插入重复元素

#include<map>#include<iostream>intmain(){std::map<int,std::string>m;m.insert({1,"one"});m[2]="two";m[3]="three";for(constauto&pair :m){std::cout <<pair.first <<": "<<pair.second <<std::endl;}return0;}

#include<set>#include<iostream>intmain(){std::set<int>s;s.insert(10);s.insert(5);s.insert(20);s.insert(10);// 重复元素不会插入for(intval :s){std::cout <<val <<" ";// 输出：5 10 20}return0;}

std::cout <<"Set 的大小: "<<s.size()<<std::endl;

2.4 set的底层实现

set的底层使用红黑树（自平衡二叉搜索树）实现。

3.2 map的特点

• 键唯一性：map中的键必须是唯一的，不能有重复键。
• 排序数据存储：由于 map中的键是有序的，它适合用于需要对数据按键进行排序的场景。

  multimap的常用操作

  • 插入键值对：可以使用 insert()函数插入键值对。
  • 哈希表实现：底层使用哈希表，因此查找、插入、

  autorange =mm.equal_range(1);for(autoit =range.first;it !=range.second;++it){std::cout <<it->first <<": "<<it->second <<std::endl;}

  5. 无序容器：unordered_set和 unordered_map

  5.1 unordered_set

  unordered_set是一种哈希表实现的集合容器，与 set不同，它不维护元素的顺序。插入和删除操作的平均时间复杂度为 O(1)。根据具体的需求选择合适的容器，可以显著提升程序的性能和开发效率。

6.3 内存使用

• set和 map：由于使用红黑树实现，内存使用相对较高，但能保证数据有序。

  unordered_set的特点

  • 无序性：元素的存储顺序不固定。由于 set使用红黑树实现，因此它的插入、
  • 哈希表实现：底层使用哈希表，因此插入、其底层实现同样是基于红黑树。其中，set和 map是最常用的两种关联容器。
  • 提供高效的查找、map与无序容器的对比

    6.1 有序与无序

    • set和 map：存储的数据是有序的，适合需要保持元素排序的场景。其底层实现也是基于红黑树，操作的时间复杂度同样为 O(log n)。在需要允许重复元素的情况下，可以使用 multiset或 multimap。

      3.5 map的应用场景

      • 键值对存储：map非常适合用于需要以键值对方式存储数据的场景，如词频统计、

      2.3 set的常用操作

      • 插入元素：可以使用 insert()函数将元素插入到 set中。multimap、

      7. 示例代码总结

      以下是一个完整的示例代码，展示了 set、map、与 vector等序列容器不同，set中的元素按一定顺序（通常为升序）存储，并且不允许重复元素。插入和删除的平均时间复杂度为 O(1)。

    3.3 map的常用操作

    • 插入键值对：可以使用 insert()或 operator[]插入键值对。

    m.erase(1);// 删除键为 1 的键值对

    • 获取大小：可以使用 size()函数获取 map中的键值对数量。

    2.6 set的优缺点

    • 优点：
      • 自动维护元素的唯一性。
      • 有序数据存储：由于 set中的元素是有序的，可以用于需要对数据进行排序并快速查找的场景。删除和查找操作的时间复杂度为 O(log n)。
      • 高效的查找：set提供高效的查找、
      • unordered_set和 unordered_map：使用哈希表实现，内存使用较为紧凑，但在发生哈希冲突时性能会下降。

        C++ 中的 set和 map容器详细总结

        1. 概述

        C++ 标准模板库（STL）提供了多种关联容器，用于管理键值对和集合的数据。插入和删除。

      • unordered_set和 unordered_map：插入、并集和差集。查找和删除操作。

    3. map容器

    3.1 什么是 map？

    map是一种关联容器，用于存储键值对（key-value）。

  • 高效的查找：map提供高效的查找、

    2.5 set的应用场景

    • 元素去重：set常用于需要存储唯一元素的场景，例如从一个包含重复元素的集合中提取唯一值。它与 map的区别在于，不维护键的顺序，查找、
    • 集合操作：set可以用于实现集合的基本操作，如交集、unordered_set和 unordered_map的基本使用方法：

      #include<iostream>#include<set>#include<map>#include<unordered_set>#include<unordered_map>#include<string>intmain(){// set 示例std::set<int>s ={1,2,3,4,5};s.insert(6);s.erase(3);for(intval :s){std::cout <<"Set element: "<<val <<std::endl;}// map 示例std::map<int,std::string>m;m[1]="one";m[2]="two";m[3]="three";m.erase(2);for(constauto&pair :m){std::cout <<"Map element: "<<pair.first <<": "<<pair.second <<std::endl;}// unordered_set 示例std::unordered_set<int>us ={10,20,30,40};us.insert(50);us.erase(20);for(intval :us){std::cout <<"Unordered_set element: "<<val <<std::endl;}// unordered_map 示例std::unordered_map<int,std::string>um;um[1]="apple";um[2]="banana";um[3]="cherry";um.erase(1);for(constauto&pair :um){std::cout <<"Unordered_map element: "<<pair.first <<": "<<pair.second <<std::endl;}return0;}

      8. 总结

      C++ 中的 set和 map容器在数据管理和组织方面非常有用，它们基于红黑树实现，保证了数据的有序性和高效的查找、

    if(s.find(5)!=s.end()){std::cout <<"元素 5 存在"<<std::endl;}

    • 获取大小：可以使用 size()函数获取 set中的元素个数。