电子商务网站的开发语言,信息流广告的三个特点,温州合作网站,织梦和wordpress哪个好set和map 1. 预备知识2. set2.1 set的概念2.2 set的常见接口 3. multiset4. map4.1 map的概念4.2 map的常见接口 5. multimap6. 练习 1. 预备知识
set和map是关联式容器#xff0c;里面存储的不是元素本身#xff0c;存储的是key,value结构的键值对#xff0c;比ve… set和map 1. 预备知识2. set2.1 set的概念2.2 set的常见接口 3. multiset4. map4.1 map的概念4.2 map的常见接口 5. multimap6. 练习 1. 预备知识
set和map是关联式容器里面存储的不是元素本身存储的是key,value结构的键值对比vector、list、deque这些底层为线性序列的序列式容器在数据检索时效率更高。关联性容器有两种不同的结构树形结构和哈希结构。set和map的底层结构是树形结构。使用平衡搜索树即红黑树作为底层结构容器中的元素是一个有序的序列。键值对一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。 2. set
2.1 set的概念 set存储的是具有一定次序升序和降序的元素。set存储的元素被const修饰不可更改。为什么因为set的底层是用二叉搜索树实现的改变了元素会影响次序。用迭代器遍历set可以得到有序序列。set中的元素是唯一的因此使用set会去重。set看起来存放的只有key值实际底层存放的是value,value键值对。
2.2 set的常见接口
构造 迭代器 void test1()
{//构造空setsetint s1;s1.insert(3);s1.insert(2);s1.insert(4);s1.insert(5);s1.insert(1);auto it s1.begin();//用迭代器遍历set可以得到有序序列。while (it ! s1.end()){cout *it ;it;}cout endl;//用迭代器构造setsetints2(s1.begin(), s1.end());for (auto e : s2){cout e ;}cout endl;//拷贝构造setints3(s2);for (auto e : s3){cout e ;}cout endl;
}容量 增加
set中插入元素时只需要插入value即可不需要构造键值对。 删除 若删除的参数是键值键值存在就删除不存在也不会报错。若删除的参数是迭代器迭代器是end()就会报错。
void test2()
{setint s1;s1.insert(3);s1.insert(2);s1.insert(4);s1.insert(5);s1.insert(1);auto it s1.find(6);s1.erase(6);//✔//s1.erase(it);//❌
}交换 清理 void test3()
{setint s1;s1.insert(3);s1.insert(2);s1.insert(4);s1.insert(5);s1.insert(1);int arr[] { 9,8,7,6,5,4,3,2,1,0 };setints2(arr, arr sizeof(arr) / sizeof(arr[0]));//交换s1和s2s1.swap(s2);cout s1的元素 ;for (auto e : s1){cout e ;}cout endl;cout s2的元素;for (auto e : s2){cout e ;}cout endl;//清理s1s1.clear();cout s1大小为 s1.size() endl;cout s1是否为空 s1.empty() endl;
}查找 1查找键值为val的元素找到了返回该元素在set中的迭代器找不到返回end()的迭代器。 2库里的find和set的find有区别。库里的find是暴力查找时间复杂度是O(N)set的find是大于查找元素就往左找小于查找元素就往右找。
计数 返回set中与val相等的元素个数。由于set会去重 元素都是唯一所以count只能返回0或者1所以count也可以用来判断元素是否在set中。
获得迭代器区间 1lower_bound找到参数的元素的迭代器upper_bound找到参数的最小元素的迭代器。配合使用可以获得左闭右开的区间。 2若两个函数的参数相同则区间内的元素都是相同的但set的元素是唯一的所以这两函数用处不大可以用于multiset。 3若参数在set中找不到则返回set的end()的迭代器。
void test4()
{int arr[] { 9,8,7,6,5,4,3,2,1,0 };setints1(arr, arr sizeof(arr) / sizeof(arr[0]));auto begin s1.lower_bound(5);auto end s1.upper_bound(10);while (begin ! end){cout *begin ;begin;}cout endl;
}获得相同元素的迭代器区间 1在set中查找相同元素的区间返回左闭右开的区间。 2返回键值对键值对的第一个迭代器是set中val的位置第二个迭代器是set中大于val的最小元素的位置。 3对于set来说用处不大因为set不能有重复的元素但对multiset就有用处。 4若参数不存在于set返回类似于[参数参数)这样不存在的区间。
void test5()
{int arr[] { 9,8,7,6,5,4,3,2,1,0 };setints1(arr, arr sizeof(arr) / sizeof(arr[0]));auto ret s1.equal_range(5);auto itlow ret.first;//找到5auto itupper ret.second;//找到比5大的最小元素while (itlow ! itupper){cout *itlow ;itlow;}cout endl;
}3. multiset
multiset是在set的基础上加上可以插入重复元素的功能。multiset依旧是按照一定次序升序和降序存储元素通过迭代器遍历元素可以得到有序序列。multiset的元素可以重复不能修改。equal_range和count对于multiset用处更大更有意义。
void test6()
{int arr[] { 9,8,7,6,5,4,3,2,1,0 ,1,2,3,4,5,6,7,8,9 };multisetint ms(arr,arrsizeof(arr)/sizeof(arr[0]));cout multiset的元素;for (auto e : ms){cout e ;}cout endl;cout9出现的次数ms.count(9)endl;auto range ms.equal_range(5);auto low_range range.first;auto upper_range range.second;while (low_range ! upper_range){cout *low_range ;low_range;}cout endl;
}4. map
4.1 map的概念 map也是关联式容器存储的是具有一定次序升序和降序的元素。map中存放的是key,value键值对key代表键值value表示与key对应的信息。map中元素的次序就是根据key进行排序的因此key不能修改且key在map中唯一value则不一定唯一。
//键值对的定义
template class T1, class T2
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){}
};map通过迭代器遍历元素可以得到有序序列。特点map支持[]访问通过[key]可以找到对应的value。operator[]中实际进行插入查找。
4.2 map的常见接口
构造 迭代器 set的迭代器都是const迭代器因此它的key不能修改map的迭代器和const迭代器分明key不可修改value可以修改。
//例子
void test()
{mapstring,string dict;//词典//插入键值对dict.insert({insert, 插入});dict.insert({erase, 删除});dict.insert({size, 大小});dict.insert({find,查找});//为什么要将key和value封装因为C不支持返回两个值但支持返回一个结构体auto it dict.begin();while (it ! dict.end()){//cout *it ;//❌pair不支持流插入cout it-first : it-second endl;it;}cout endl;//范围forfor (auto e : dict){cout e.first : e.second endl;}
}插入 1key与value通过成员类型value_type绑定在一起为其取别名称为pairtypedef pairconst key, T value_type;。 2不同于setmap插入的是键值对不是单独的value。返回的也是键值对插入成功iterator是新插入节点的位置bool是true发现map已有相同的key插入失败iterator是map中key的位置bool是false。 3如何插入键值对
//map
void test7()
{mapstring,string dict;//词典//法1//pair也是一个类模板pairstring, stringword1(insert, 插入);dict.insert(word1);//法2//先调用构造再调用拷贝构造编译器会优化为构造dict.insert(pairstring, string(erase, 删除));//法3//make_pair是模板函数可以构造键值对dict.insert(make_pair(size, 大小));//法4//C11支持多参数的构造函数隐式类型转换C98支持单参数的构造函数隐式类型转换dict.insert({ find,查找 });//等价于pairstring,string word2 {find,查找}然后dict.insert(word2);
}最常用的是法3和法4。
[]下标访问
//例子统计次数
//常规做法
void test9()
{string arr[] { 西瓜, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){auto it countMap.find(e);if (it countMap.end()){countMap.insert(make_pair(e, 1));}else{it-second;}}for (const auto kv : countMap){cout kv.first : kv.second endl;}
}
//优化
void test9()
{// 统计次数string arr[] { 西瓜, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (const auto kv : countMap){cout kv.first : kv.second endl;}
}把key放入[]中就可以得到相应的value可问题是还没插入怎么[]下标访问先试着插入key如果key已经存在则返回key对应的value此时就可以对value操作。如果key不存在先插入key再返回对应的value。
//底层类似这样定义
T operator[](cosnt K key)
{pairiterator,boolret insert(make_pair(key,T()));//因为value可能是其他类型所以不能单纯用int。//1key已在map里面返回pairmap中key所在节点的位置false//2key不在map里面返回pair新插入key所在节点的位置truereturn ret-first-second;
}练习 有效的括号
class Solution {
public://将左括号入栈遇到右括号出栈判断是否相同不相等就return falsebool isValid(string s) {stackchar st;mapchar,char m;m[(] );m[[] ];m[{] };for(auto e:s){//如果e等于左括号返回1就入栈if(m.count(e)){st.push(e);}//遇到右括号就出栈判断是否相等else{if(st.empty()){return false; }char tmp st.top();st.pop();if(m[tmp]!e){return false;}}}if(st.empty()){return true;}return false;}
};5. multimap
multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。因此multimap不支持[]下标访问。 6. 练习
两个数组的交集
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {//先将两个数组放进set中可以帮助去重//法1遍历一个set中所有元素判断在不在另一个set中在就加到交集中//法2从头开始比较两个set中的元素相等就是加到交集,然后同时小的就指向下一个元素继续比较setints1(nums1.begin(),nums1.end());setints2(nums2.begin(),nums2.end());vectorintv;//存放交集auto it1 s1.begin();auto it2 s2.begin();while(it1!s1.end()it2!s2.end())if(*it1*it2){v.push_back(*it1);it1;it2;}else if(*it1*it2){it2;}else{it1;}return v;}
};前k个高频单词
class Solution {
public:struct Greater{bool operator()(const pairstring,int p1,const pairstring,intp2){return p1.secondp2.second;}};vectorstring topKFrequent(vectorstring words, int k) {//法一:先将words的单词map中可以起到去重和计数的作用mapstring,int m;for(auto e:words){m[e];}//此时map已经按照字典序排好了//再按照单词出现频率排序使用sort进行排序但是sort不能对map排序因为map的迭代器是双向的双向迭代器不能使用随机迭代器的函数。所以将map的键值对加到vector中就可以用sort。vectorpairstring,int v(m.begin(),m.end());//但是sort底层是快排快排不稳定排序结束后出现频率相同的单词的字典序可能被破坏所以得用另一个函数stable_sortstable_sort不会破坏字典序。//又因为是排降序得自己写仿函数stable_sort(v.begin(),v.end(),Greater());//排序后需要将前K个string取出放入vectorvectorstring ret;for(int i 0;ik;i){ret.push_back(v[i].first);}return ret;}
};class Solution {
public://法2如果偏要用sort排序怎么办修改仿函数在频率相同的情况下不改变字典序。struct Greater{bool operator()(const pairstring,int p1,const pairstring,intp2){return (p1.secondp2.second) ||(p1.secondp2.secondp1.firstp2.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int m;for(auto e:words){m[e];}vectorpairstring,int v(m.begin(),m.end());sort(v.begin(),v.end(),Greater());vectorstring ret;for(int i 0;ik;i){ret.push_back(v[i].first);}return ret;}
};class Solution {
public://法3用map按字典序排序用multimap再按频率排序multimap排序是稳定的不会破坏字典序。vectorstring topKFrequent(vectorstring words, int k) {mapstring,int m;for(auto e:words){m[e];}multimapint,string,greaterintmm;for(autoe:m){mm.insert(make_pair(e.second,e.first));}vectorstringret;auto it mm.begin();while(k--){ret.push_back(it-second);it;}return ret;}
};
