• C++--map和set--1027


    1. 背景概念

    1.1 键值对

    用来表示具有一一对应关系的结构,一般包含两个成员变量,key和value

    1. template <class T1, class T2>
    2. struct pair
    3. {
    4. T1 first;
    5. T2 second;
    6. pair()
    7. :first(T1()),second(T2())
    8. {}
    9. pair(const T1& a, const T2& b)
    10. : first(a), second(b)
    11. {}
    12. };

    1.2 关联式容器

    存储的是结构的键值对。一一对应,所以数据检索的效率高。

    1.3 树形关联式容器

    map、set、multimap、multiset。底层使用的是平衡搜索树(红黑树),容器中的元素是一个有序的序列。

    2. set

    2.1 set简介

    • set是按照一定次序存储元素的容器。
    • 不允许冗余数据,所以可以去重。因为有序,数据不能修改。
    • 可以插入可以删除
    • 默认排升序
    • set中只放value,但在底层实际存放的是由构成的键值对
    • 没有支持operator[]

    2.2 set的使用

    2.2.1 构造set

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5. // 1234567
    6. set<int>s1;
    7. s1.insert(1);s1.insert(2);s1.insert(3);//...
    8. set<int>s2={1,2,3,4,5,6,7};
    9. int a[]={1,2,3,4,5,6,7};
    10. set<int>s3(a,a+sizeof(a)/sizeof(int));
    11. return 0;
    12. }

     2.2.2 使用迭代器更新

    string str={sadhjwiajh};
    set s4(str.begin(),str.end());

    打印

    1. void print(set<int>& s)
    2. {
    3. set<int>::iterator it = s.begin();
    4. while (it != s.end())
    5. {
    6. //*it = 10;
    7. cout << *it << " ";
    8. ++it;
    9. }
    10. cout << endl;
    11. }

    2.2.3 升序和降序

    默认都排升序

    1. #include
    2. using namespace std;
    3. void test2()
    4. {
    5. set<int>s1={9,5,6,2,4,1,8};//升序
    6. //great的使用需要包含头文件 #include
    7. set<int,great<int>> s2={9,5,6,2,4,1,8};//降序
    8. //print(s2);这里会传参报错 还是手动打印
    9. set<int>::iterator it = s2.begin();
    10. while (it != s2.end())
    11. {
    12. //*it = 10;
    13. cout << *it << " ";
    14. ++it;
    15. }
    16. cout << endl;
    17. }

    2.2.4 修改

    s1.insert(value);//插入value

    s1.erase(value);//删除值为value的键值对,返回删除的元素的个数

    s1.erase(iterator first,iterator last);//删除 迭代器区间[first,last)区间中的元素

    set::iterator pos=s1.find(20);

    if(pos!=s1.end())

    s1.earese(pos);//删除迭代器值为pos的键值对

     2.2.5 统计

    s1.count(val);//返回值为value的元素个数,不存在返回0

    2.2.6 lower_bound   upper_bound

    lower_bound(value);//返回>=value的值的迭代器

    upper_bound(value);//返回>value的值得迭代器

    1. void test3()
    2. {
    3. std::set<int> myset;
    4. std::set<int>::iterator itlow, itup;
    5. for (int i = 1; i < 10; i++)
    6. myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
    7. itlow = myset.lower_bound(25); // >= val
    8. itup = myset.upper_bound(60); // > val
    9. cout << "["<<*itlow <<","<<*itup<<"]"<
    10. myset.erase(itlow, itup); // 10 20 70 80 90
    11. print(myset);
    12. }

    3. multiset

    3.1 multiset介绍

    • 支持数据冗余。即不能去重。
    • 构造方法同set。
    • 使用find(value)函数时,返回的是中序遍历中第一个value值对应的键值对的迭代器。
    • 使用erase(value)时,删除所有的value值对应的键值对。

    4. map

    在内部,map中的元素总是按照键值key进行比较排序的
    map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序
    对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列
    map支持下标访问符,即在[]中放入key,就可以找到与key对应的value

    map默认以key的升序排列

    key不能直接修改

    4.1 map的使用

    打印

    写法一

    map::iterator it = dict.begin();
        //auto it = dict1.begin();
        while (it != dict1.end())
        {
            //cout << (*it).first << (*it).second <         cout << it->first << it->second << endl;
            ++it;
        }
        cout << endl;

     写法二

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

    4.1.1 插入数据

    方法一 实例化pair对象
        mapdict1;
        pairkv1("sort", "排序");
        dict1.insert(kv1);
    方法二 利用匿名对象
        dict1.insert(pair("left", "左边"));
    方法三 make_pair 函数模板
        dict1.insert(make_pair("right", "右边"));

     

    4.1.2 map中元素的修改

    s1.erase(x);//删除键值为x的键值对,返回删除的元素的个数

    s1.erase(iterator first,iterator last);//删除 迭代器区间[first,last)区间中的元素

    m1.find(x);//在map中查找key为x的元素,找到返回该位置的迭代器,找不到返回m1.end()

    m1.count(x);//返回key为x的键值在map中的个数

    4.2 更新value值的方法

    方法一

    1. void test5()
    2. {
    3. string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
    4. "西瓜", "苹果", "香蕉", "苹果", "香蕉","香蕉","香蕉" };
    5. mapint>countmap;
    6. for (auto& str : arr)
    7. {
    8. mapint>::iterator it = countmap.find(str);
    9. if (it != countmap.end())
    10. {
    11. //(*it).second++;
    12. it->second++;
    13. }
    14. else
    15. {
    16. countmap.insert(make_pair(str,1));
    17. }
    18. }

     

     方法二  operator[]

    countmap[key];

    在map中寻找key,找了就返回对应pair的value的引用。

    找不到就插入一个pair,然后返回v()(value类型的构造函数创建的匿名对象)的引用

    1. void test6()
    2. {
    3. string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果",
    4. "西瓜", "苹果", "香蕉", "苹果", "香蕉","香蕉","香蕉" };
    5. mapint>countmap;
    6. for (auto& str : arr)
    7. {
    8. countmap[str]++;
    9. //创建"苹果"时,value创建一个int() 默认构造函数给的值是0
    10. //然后 0++ 变成1
    11. }
    12. for (const auto& kv : countmap)
    13. {
    14. cout << kv.first << ":" << kv.second << endl;
    15. }
    16. cout << endl;
    17. }

    5.multimap

    multimap和map的唯一不同就是:map中的key是唯一的,而multimap中key是可以
    重复的。

    不支持operator[ ]

    6. 在oj中的应用

     前K个高频单词

    力扣

    1. class Solution {
    2. public:
    3. struct less
    4. {
    5. //因为是优先级队列,排降序 要写成排升序
    6. bool operator()(const pairint>& kv1,const pairint>& kv2) const
    7. {
    8. if(kv1.secondreturn true;
    9. if(kv1.second==kv2.second && kv1.first>kv2.first) return true;
    10. // def cde bcd abc
    11. return false;
    12. }
    13. };
    14. vector topKFrequent(vector& words, int k)
    15. {
    16. mapint>countmap;
    17. for(auto& str:words)
    18. {
    19. countmap[str]++;
    20. }
    21. priority_queueint>,vectorint>>, less> maxmap;
    22. for(auto pair:countmap)
    23. {
    24. maxmap.push(pair);
    25. }
    26. vector result;
    27. while(k--)
    28. {
    29. result.push_back(maxmap.top().first);
    30. maxmap.pop();
    31. }
    32. return result;
    33. }
    34. };

    两个数组的交集

    力扣

    1. class Solution {
    2. public:
    3. vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    4. {
    5. // vectorresult;
    6. // unordered_setm1(nums1.begin(),nums1.end());
    7. // for(auto& e:nums2)
    8. // {
    9. // if(m1.find(e)!=m1.end())
    10. // {
    11. // result.push_back(e);
    12. // }
    13. // }
    14. // return result;
    15. //这样结果会出现 {2,2} 要的是去重之后的结果 {2}
    16. unordered_set<int>result_set;
    17. unordered_set<int>m1(nums1.begin(),nums1.end());
    18. for(auto& e:nums2)
    19. {
    20. if(m1.find(e)!=m1.end())
    21. {
    22. result_set.insert(e);
    23. }
    24. }
    25. return vector<int>(result_set.begin(),result_set.end());
    26. }
    27. };
  • 相关阅读:
    [算法刷题笔记]二叉树之左叶子之和
    Kubernetes基本概念
    新160个CrackMe算法分析-002-abexcm5
    Baumer工业相机堡盟工业相如何使用BGAPISDK通过两种不同的方法进行图像回调函数的使用(C#)
    代码随想录算法训练营第四十一天|卡码网46. 携带研究材料(第六期模拟笔试)、416. 分割等和子集
    使用Grafana与MySQL监控监控网络延迟
    windows上 adb devices有设备 wsl上没有
    【c/c++】c和cpp混合编译
    使用正则表达式模块“re”遇到的错误
    FigDraw 16. SCI 文章绘图之树形图(Dendrogram)
  • 原文地址:https://blog.csdn.net/qq_68741368/article/details/127568632