备案控制台
开发者社区 开发与运维 文章 正文

【C++】map和set的使用（下）

2023-02-08 99
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++】map和set的使用（下） 
void MapTest1()
{
  map<string, string> dict;
  // 有名对象
  pair<string, string> kv1("sort", "排序");
  dict.insert(kv1);
  // 匿名对象
  dict.insert(pair<string, string>("test", "测试"));
  dict.insert(pair<string, string>("sort", "排序"));
  dict.insert(pair<string, string>("string", "字符串"));
  typedef pair<string, string> DictKV;
  dict.insert(DictKV("left", "左边"));
  dict.insert(make_pair("left", "剩下")); // make_pair是个函数模板
  //map<string, string>::iterator it = dict.begin();
  auto it = dict.begin();
  while (it != dict.end())
  {
    //cout << (*it).first << ":" << (*it).second << endl;
    // operator->返回的是结构的指针,再加上一个->就是结构中的数据
    // 为了可读性,编译器省略了一个->
    cout << it->first << ":" << it->second << endl;
    ++it;
  }
  cout << endl;
  for (auto& kv : dict)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << endl;
}


注：map 的 operator* 返回的是结构体 pair。

c0b3cc875120479483457263332fe433.png


注：map 和 set 的迭代器都是双向迭代器！！！


统计出现次数


void MapTest2()
{
  string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  map<string, int> countMap;
  for (auto& str : arr)
  {
    map<string, int>::iterator it = countMap.find(str);
    if (it != countMap.end())
      ++it->second;
    else
      countMap.insert(make_pair(str, 1));
  }
  for (auto& kv : countMap)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << endl;
}

e1d39a226cd243368e1e28b870df6481.png

128d3a5c983148c78274e610de756f2b.png

void MapTest3()
{
  string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  map<string, int> countMap;
  for (auto& str : arr)
  {
    // 1. str不在countMap中，插入pair(str, int())，再对value的引用进行++
    // 2. str在countMap中，对value的引用进行++
    ++countMap[str];
  }
  for (auto& kv : countMap)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << endl;
}


multimap


1. multimap 的介绍


multimap 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对 <key, value>，其中多个键值对之间的 key 是可以重复的。

在 multimap 中，通常按照 key 排序和唯一地标识元素，而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type 是组合 key 和 value 的键值对：typedef pair<const Key, T> value_type;

在内部，multimap 中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对 key 进行排序的。

multimap 通过 key 访问单个元素的速度通常比unordered_multimap 容器慢，但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列。

multimap 在底层用二叉搜索树（红黑树）来实现。


注意：multimap 和 map 的唯一不同就是：map中的key 是唯一的，而 multimap 中 key 是可以重复的。


2. multimap 的使用


multimap 中没有重载[]，原因是 multimap 允许键值冗余。当有多个相同的键值时，不知道返回哪一个。


void MultimapTest()
{
  multimap<string, string> mdict;
  mdict.insert(make_pair("sort", "排序"));
  mdict.insert(make_pair("left", "左边"));
  mdict.insert(make_pair("left", "剩下"));
  mdict.insert(make_pair("string", "字符串"));
  for (auto& kv : mdict)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << endl;
}

fa90d0fe585b4eeb96ca78bd87dae3f7.png


👉前K个高频单词👈


给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。


返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序排序。

b14df3b2585045fbba0f74db07246dd3.png


思路一：可以通过优先级队列来做，认为出现次数多的单词优先级高。如果出现次数相同，则在字典顺序靠前的优先级高。根据优先级比较的规则，我们自己实现一个仿函数即可。


class Solution 
{
    struct Less
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const
        {
            if(kv1.second < kv2.second)
                return true;
            else if(kv1.second == kv2.second && kv1.first > kv2.first)
                return true;
            else
                return false;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 统计出现的次数
        map<string, int> countMap;
        for(auto& str : words)
        {
            ++countMap[str];
        }
        // TOPK问题
        priority_queue<pair<string, int>, vector<pair<string, int>>, Less> mh(countMap.begin(), countMap.end());
        vector<string> v;
        while(k--)
        {
            v.push_back(mh.top().first);
            mh.pop();
        }
        return v;
    }
};

8b880a2df2f24907b6777a88a1e06b59.png


思路二：因为countMap中已经按照字典顺序排序了，所以我们可以采用稳定的排序对countMap中的元素按照出现次数来排序就行了。sort 底层是一个快排，快排是不稳定排序，那么我们可以给 sort 传一个比较方式，就可以保证稳定性了。注：sort 要求传入的迭代器是随机迭代器，而 map 的迭代器是双向迭代器。那我们可以先将 map 的元素存储 vector 中。


class Solution 
{
    struct Greater
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const
        {
            if(kv1.second > kv2.second)
                return true;
            else if(kv1.second == kv2.second && kv1.first < kv2.first)
                return true;
            else
                return false;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 统计出现的次数
        map<string, int> countMap;
        for(auto& str : words)
        {
            ++countMap[str];
        }
        vector<pair<string, int>> sortV(countMap.begin(), countMap.end());  
        sort(sortV.begin(), sortV.end(), Greater());
        vector<string> v;
        for(size_t i = 0; i < k; ++i)
        {
            v.push_back(sortV[i].first);
        }
        return v;
    }
};

7441f137a9bc4d799a29f7ca343d0c7b.png

上面的解法是通过比较方式来控制稳定性的。那么我们也可以使用库里提供的稳定排序stable_sort来控制稳定性。


class Solution 
{
    struct Greater
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const
        {
            if(kv1.second > kv2.second)
                return true;
            else
                return false;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 统计出现的次数
        map<string, int> countMap;
        for(auto& str : words)
        {
            ++countMap[str];
        }
        vector<pair<string, int>> sortV(countMap.begin(), countMap.end());  
        stable_sort(sortV.begin(), sortV.end(), Greater());
        vector<string> v;
        for(size_t i = 0; i < k; ++i)
        {
            v.push_back(sortV[i].first);
        }
        return v;
    }
};

aa22d9a2e4ce4ccb87ab696cfed690c1.png


思路三：因为countMap已经按照字典顺序排序了，那可以将其中的元素依次插入到以整型为 key 值的multimap中即可。


class Solution 
{
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 统计出现的次数
        map<string, int> countMap;
        for(auto& str : words)
        {
            ++countMap[str];
        }
    // 传greater<int>也是为了保证稳定性
        multimap<int, string, greater<int>> sortMap;
        for(auto& str : countMap)
        {
            sortMap.insert(make_pair(str.second, str.first));
        }
        vector<string> v;
        auto it = sortMap.begin();
        for(size_t i = 0; i < k; ++i)
        {
            v.push_back(it->second);
            ++it;
        }
        return v;
    }
};

f9d655a6d1904d038c5f446ef75b0cdb.png


👉两个数组的交集👈


给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。

5f0c8be7a16b489a94acbdd520acb92d.png


思路：因为set容器是对元素进行排序加上去重的，所以我们可以用数组中的元素来构造set，然后再来求交集。求交集的思路：谁小谁往后走，相等就添加到vector中并同时往后走。


class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        vector<int> v;
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 < *it2)
                ++it1;
            else if(*it1 > *it2)
                ++it2;
            else
            {
                v.push_back(*it1);
                ++it1;
                ++it2;                
            }
        }
        return v;
    }
};

c1b0e18ad5e8427abb7f31fc3f119ff4.png


补充：求差集的思路：先用两个数组的元素构造出两个et，然后遍历set。谁小就将谁添加到vector中并且往后走，相等时就同时加加。求并集只需要将两个数组的元素插入到set中就能得到两个数组的并集了。


class Solution 
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        vector<int> v;
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 < *it2)
            {
                v.push_back(*it1);
                ++it1;
            }
            else if(*it1 > *it2)
            {
                v.push_back(*it2);
                ++it2;
            }
            else
            {
                ++it1;
                ++it2;                
            }
        }
        // 后面的元素都是相差的元素
        while(it1 != s1.end())
        {
            v.push_back(*it1);
            ++it1;
        }
        while(it2 != s2.end())
        {
            v.push_back(*it2);
            ++it2;
        }
        return v;
    }
};


👉总结👈


本篇博客主要讲解了键值对、关联式容器 set、multiset、map 和 multiset 以及两道 OJ 题前 K 个高频单词和两个数组的交集等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

文章标签：
C++
容器
存储
关键词：
map Set
C++ map set
C++ set
C++ map
游客mpbbpgnnu5sxe
目录
相关文章
龙大吉
|
6天前
|
存储 JavaScript 索引
js开发：请解释什么是ES6的Map和Set，以及它们与普通对象和数组的区别。
ES6引入了Map和Set数据结构。Map的键可以是任意类型且有序，与对象的字符串或符号键不同；Set存储唯一值，无重复。两者皆可迭代，支持for...of循环。Map有get、set、has、delete等方法，Set有add、delete、has方法。示例展示了Map和Set的基本操作。
龙大吉
25 3
老板这功能得加钱
|
5天前
|
JavaScript 前端开发 Java
ES6 逐点突破系列 -- Set Map，工作感悟，完美收官
ES6 逐点突破系列 -- Set Map，工作感悟，完美收官
老板这功能得加钱
6 0
阿珊和她的猫
|
5天前
|
存储 缓存 JavaScript
JavaScript中的Set和Map：理解与使用
JavaScript中的Set和Map：理解与使用
阿珊和她的猫
8 0
游客g7kiuqrvkhn3g
|
6天前
|
存储 JavaScript
ES6+新特性-Symbol与Set/Map数据结构
ES6 引入了三种新的数据结构：Symbol、Set和Map。Symbol是唯一且不可变的值，常用于定义对象的独特属性；Set存储不重复值，适合数组去重；Map则是键值对集合，键可为任意类型，提供了更灵活的存储方式。这些新数据结构提供了更高效的操作手段，分别解决了属性命名冲突、数据去重和复杂键值对存储的问题。示例展示了如何使用Symbol、Set和Map进行基本操作。
游客g7kiuqrvkhn3g
16 6
盒马盒马
|
6天前
|
存储 编译器 C++
C++：map&set 对红黑树的封装
C++：map&set 对红黑树的封装
盒马盒马
11 1
toKeep
|
6天前
|
存储
Map与Set的经典OJ题
Map与Set的经典OJ题
toKeep
13 3
toKeep
|
6天前
|
存储 自然语言处理 容器
Map与Set
Map与Set
toKeep
13 3
盒马盒马
|
6天前
|
存储 C++ 容器
C++：STL - set & map
C++：STL - set & map
盒马盒马
16 4
Yawesh
|
6天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
Yawesh
11 1
小蜗牛~向前冲
|
6天前
|
存储 C++ 容器
[数据结构]-map和set
[数据结构]-map和set
小蜗牛~向前冲
21 2