c++|【C++篇】map和set的简单介绍

系列文章目录 准备 博主:大大怪先森(记得关注哦!)
编程环境:vs2013
所示代码:码源


文章目录

  • 系列文章目录
  • 准备
  • 前言
  • 一、关联式容器
    • 键值对
  • 二、树形结构的关联式容器
    • set
      • set的介绍
      • set的使用
        • 1.模板参数列表
        • 2.set的函数介绍
        • 3.代码举例
    • multiset
      • multiset的介绍
      • multiset的使用
        • 1.multiset模板参数
        • multiset函数说明
        • 代码举例
    • map
      • map的介绍
      • map的使用
        • map的模板参数
        • map的函数说明
        • 代码举例
    • multimap
      • multimap的介绍
      • multimap的使用
  • 现学现用
  • 总结

前言
本文将讲解map和set的语法使用!!!
提示:以下是本篇文章正文内容
一、关联式容器
我们之前已经接触过STL中的部分容器,比如:vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
那么序列容器又是怎样的呢?
关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是结构的键值对,在数据检索时比序列式容器效率更高
键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值, value表示与key对应的信息

SGI-STL中关于键值对的定义:
template struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1& a, const T2& b): first(a), second(b) {} };

二、树形结构的关联式容器
STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式
容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。
set set的介绍
set的介绍:
  1. set是按照一定次序存储元素的容器
  2. 在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
  3. 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代。
  5. set在底层是用二叉搜索树(红黑树)实现
set的使用
1.模板参数列表 【c++|【C++篇】map和set的简单介绍】c++|【C++篇】map和set的简单介绍
文章图片

2.set的函数介绍
函数声明 函数介绍
iterator begin() 返回set中起始位置的迭代器 (拥有rbegin)
iterator end() 返回set中最后一个元素的迭代器(拥有rend)
pair insert (const value_type& x ) 插入一个value值
void erase ( iterator position ) 删除set中position位置上的元素
size_type erase ( constkey_type& x ) 删除set中值为x的元素,返回删除的元素的个数
void erase ( iterator first, iterator last ) 删除set中[first, last)区间中的元素
iterator find ( const key_type& x ) const 返回set中值为x的元素的位
3.代码举例
//排序 + 去重 set s; s.insert(3); s.insert(1); s.insert(3); s.insert(5); s.insert(8); s.insert(10); set::iterator it = s.begin(); //遍历的方式是中序遍历 while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; set::iterator pos = s.find(5); if (pos != s.end()) { //pos必须是一个有效的迭代器 s.erase(pos); } cout << s.erase(1) << endl; cout << s.erase(30) << endl; for (auto e : s) { cout << e << " "; } cout << endl;

multiset multiset的介绍
multiset的介绍
  1. multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。
  2. 在multiset中,元素的value也会识别它(因为multiset中本身存储的就是组成的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的),但可以从容器中插入或删除。
  3. 在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
  4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭代器遍历时会得到一个有序序列。
  5. multiset底层结构为二叉搜索树(红黑树)
multiset的使用
1.multiset模板参数 c++|【C++篇】map和set的简单介绍
文章图片

multiset函数说明
函数声明 函数介绍
iterator begin() 返回set中起始位置的迭代器 (拥有rbegin)
iterator end() 返回set中最后一个元素的迭代器(拥有rend)
pair insert (const value_type& x ) 插入一个value值
void erase ( iterator position ) 删除set中position位置上的元素
size_type erase ( constkey_type& x ) 删除set中值为x的元素,返回删除的元素的个数
void erase ( iterator first, iterator last ) 删除set中[first, last)区间中的元素
iterator find ( const key_type& x ) const 返回set中值为x的元素的位
代码举例
//排序 multiset s; s.insert(3); s.insert(1); s.insert(1); s.insert(5); s.insert(1); s.insert(8); s.insert(10); s.insert(12); auto it = s.begin(); while (it != s.end()) { cout << (*it) << " "; ++it; } cout << endl; //这里需要注意的是mult、iset的作用没有去重那么find返回的是哪一个节点的迭代器呢? //返回中序第一个val值所在的节点的迭代器 multiset::iterator pos = s.find(8); while (pos != s.end()) { cout << (*pos) << " "; ++pos; } cout << endl; pos = s.find(1); /*while (pos != s.end() && *pos == 1) { auto next = pos; ++next; s.erase(pos); pos = next; }*/ //erase(值)会删除所有你需要删除的需要删除的节点,返回值是你删除节点的个数 cout << s.erase(1) << endl; for (auto e : s) { cout << e<< " "; } cout << endl; pos = s.find(5); if (pos != s.end()) { //不允许修改 //*pos += 10; }

map map的介绍
map的介绍
  1. map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:typedef pair value_type;
  3. 在内部,map中的元素总是按照键值key进行比较排序的。
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。
  5. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
  6. map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。
map的使用
map的模板参数 c++|【C++篇】map和set的简单介绍
文章图片

map的函数说明
函数说明 功能介绍
mapped_type& operator[] (const key_type& k) 返回去key对应的value
pair insert (const value_type& x) 在map中插入键值对x,注意x是一个键值对,返回值也是键值对:iterator代表新插入元素的位置,bool代表释放插入成功
void erase ( iterator position ) 删除position位置上的元素
size_type erase ( const key_type& x ) 删除键值为x的元素
void erase ( iterator first,iterator last ) 删除[first, last)区间中的元素
iterator find ( const key_type& x) 在map中插入key为x的元素,找到返回该元素的位置的迭代器,否则返回end
size_type count ( const key_type& x ) const 返回key为x的键值在map中的个数,注意map中key是唯一的,因此该函数的返回值要么为0,要么为1,因此也可以用该函数来检测一个key是否在map中
代码举例 代码如下(示例):
void test_map1() { map, string> dict; pair, string> kv1("sort", "排序"); dict.insert(kv1); dict.insert(pair, string>("string", "字符串")); //自动推到类型 --- c++11的内容 dict.insert(make_pair("test", "测试")); map, string>::iterator it = dict.begin(); while (it != dict.end()) { //it->first = "wess"; //it->second = "目击"; //cout << (*it).first << endl; cout << it->first << ":" << it->second << endl; ++it; } cout << endl; for (auto& kv : dict) { cout << kv.first << ":" << kv.second << endl; } cout << endl; } void test_map2() { string arr[] = { "苹果", "苹果", "香蕉", "苹果", "樱桃" }; map,int> CountMap; for (auto& str : arr) { auto ret = CountMap.find(str); if (ret == CountMap.end()) { CountMap.insert(make_pair(str, 1)); } else { ret->second++; } } for (auto& str : arr) { auto kv = CountMap.insert(make_pair(str, 1)); if (kv.second == false) { kv.first->second++; } } for (auto& str : arr) { CountMap[str]++; //实现原理可以理解为上面给出的两种实现。 } for (auto& kv : CountMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; } void test_map3() { map, string> dict; dict.insert(make_pair("sort", "排序")); dict.insert(make_pair("left", "左边")); dict.insert(make_pair("right", "右边")); dict["left"] = "剩余"; //修改 dict["test"]; //插入 //cout << dict["sort"] << endl; //查找 dict["string"] = "字符串"; //插入 + 修改 for (auto& e : dict) { cout << e.first << ":" << e.second << endl; } } void test_map4() { multimap, string> dict; dict.insert(make_pair("sort", "排序")); dict.insert(make_pair("left", "左边")); dict.insert(make_pair("left", "剩余")); dict.insert(make_pair("left", "遗留")); auto e = dict.find("left"); cout << (*e).first << ":" << (*e).second << endl; cout << dict.count("left") << endl; }

补充:
for (auto& str : arr) { CountMap[str]++; //实现原理可以理解为上面给出的两种实现。 }

实现原理:
c++|【C++篇】map和set的简单介绍
文章图片

multimap multimap的介绍
multimap的介绍
  1. Multimaps是关联式容器,它按照特定的顺序,存储由key和value映射成的键值对,其中多个键值对之间的key是可以重复的。
  2. 在multimap中,通常按照key排序和惟一地标识元素,而映射的value存储与key关联的内容。key和value的类型可能不同,通过multimap内部的成员类型value_type组合在一起,value_type是组合key
    和value的键值对:typedef pair value_type;
  3. 在内部,multimap中的元素总是通过其内部比较对象,按照指定的特定严格弱排序标准对key进行排序的。
  4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢,但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
  5. multimap在底层用二叉搜索树(红黑树)来实现。
multimap的使用
与map类似,唯一不同的就是不会去重,可以参上。
现学现用
题目:本公司现在要给公司员工发波福利,在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多,但是却又不知道哪种水果比较受欢迎,然后公司就让每个员工报告了自己最爱吃的k种水果,并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数,并且求出大家最喜欢吃的前k种水果
void GetFavoriteFruit(vector>& v, int K) { map, int> CountMap; for (auto e : v) { CountMap[e]++; } //将map的元素放入SortV当中进行快速排序 /*vector> SortV; for (auto e : CountMap) { SortV.push_back(e); } sort(SortV.begin(), SortV.end(), CountVal()); */ /*vector SortV; auto it = CountMap.begin(); while (it != CountMap.end()) { SortV.push_back(it); ++it; } sort(SortV.begin(), SortV.end(), CountIteraVal()); for (int i = 0; i < K; i++) { cout << SortV[i]->first << ":" << SortV[i]->second << endl; }*/ //multimap> SortMap; //for (auto& e : CountMap) //{ // SortMap.insert(make_pair(e.second, e.first)); //} // //for (auto & kv : SortMap) //{ // cout << kv.second << ":" << kv.first << endl; //} //cout << endl; //auto it = SortMap.begin(); //for (int i = 0; i < K; i++) //{ // cout << it->second << ":" << it->first << endl; // ++it; //} ///堆 //priority_queue, vector>, CountVal> pq; //for (auto& kv : CountMap) //{ // pq.push(kv); //} //for (int i = 0; i < K; i++) //{ // cout << pq.top().first << ":" << pq.top().second << endl; // pq.pop(); //} priority_queue::iterator, vector::iterator>, CountIteraVal> pq; auto it = CountMap.begin(); while (it != CountMap.end()) { pq.push(it); ++it; } while (K--) { cout << pq.top()->first << ":" << pq.top()->second << endl; pq.pop(); } cout << endl; } int main() { vector> v = { "苹果", "苹果", "香蕉", "苹果", "香蕉", "苹果", "樱桃", "哈密瓜", "榴莲", "榴莲", "苹果" }; GetFavoriteFruit(v, 3); return 0; }

总结
希望本篇文章能给各位带来帮助,如有不足还请指正!!! 码字不易,各位大大给个收藏点赞吧!!!

各位大大记得点赞,关注,一键三连哦!!!
c++|【C++篇】map和set的简单介绍
文章图片

    推荐阅读