天天做网站,wordpress图片放大滑动,大连旧房翻新装修哪家公司好,爱丫爱丫影院在线看免费目录 map和set1.关联式容器2.键值对3.树形结构的关联式容器3.1set3.1.1set的介绍3.1.2set的使用3.1.2.1set的模版参数列表3.1.2.2set的构造3.1.2.3set的迭代器3.1.2.4set基本接口的使用3.1.2.5set使用案例 3.2map3.2.1map介绍3.2.2map的使用3.2.2.1map的构造3.2.2.2map的迭代器… 目录 map和set1.关联式容器2.键值对3.树形结构的关联式容器3.1set3.1.1set的介绍3.1.2set的使用3.1.2.1set的模版参数列表3.1.2.2set的构造3.1.2.3set的迭代器3.1.2.4set基本接口的使用3.1.2.5set使用案例 3.2map3.2.1map介绍3.2.2map的使用3.2.2.1map的构造3.2.2.2map的迭代器3.2.2.3map的容量与访问[]的使用和原理 3.2.2.4map的基础接口的使用3.2.2.5map的使用案例3.2.2.6map的总结 3.3multiset3.3.1multiset的介绍3.3.2multiset的使用 3.4multimap3.4.1multimap的介绍3.4.2multimap的使用 4.有关map和set的oj4.1前K个高频单词4.2两个数组的交集 map和set 在学习map和set之前要先铺垫一下二叉搜索树。算是有个小基础。 1.关联式容器
STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。
那什么是关联式容器它与序列式容器有什么区别
关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高
2.键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息
在前面学习二叉搜索树的时候已经接触过KV模型的二叉搜索树了。
SGI-STL中关于键值对的定义
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){}
};3.树形结构的关联式容器
3.1set
3.1.1set的介绍
set的文档介绍
主要使用的一些成员函数迭代器接口 总结 set是按照一定次序存储元素的容器 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。 set在底层是用二叉搜索树(红黑树)实现的。
注意 与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。 set中插入元素时只需要插入value即可不需要构造键值对。 set中的元素不可以重复(因此可以使用set进行去重)。 使用set的迭代器遍历set中的元素可以得到有序序列 set中的元素默认按照小于来比较 set中查找某个元素时间复杂度为O(log_2 n) set中的元素不允许修改(为什么?)[二叉搜索树不允许数据重复] set中的底层使用二叉搜索树(红黑树)来实现
3.1.2set的使用
3.1.2.1set的模版参数列表 T: set中存放元素的类型实际在底层存储value, value的键值对。
Compareset中元素默认按照小于来比较
Allocset中元素空间的管理方式使用STL提供的空间配置器管理
注意 前面已经学习过很多的容器了对其构造函数迭代器基本接口的使用都很熟悉了这里不再一个一个详细的说明如何使用了 3.1.2.2set的构造 3.1.2.3set的迭代器 3.1.2.4set基本接口的使用 这里要特别说明的是find iterator find ( const key_type x ) const 功能找到set中 x的位置。 这里除了set容器自带的find在算法部分还有一个find这两个find都能直线找到x的位置但是不一样的是时间复杂度 set容器的find接口时间复杂度是O(logN) 算法模块里的find接口时间复杂度是O(N) 3.1.2.5set使用案例
这里使用的都是一些需要注意的其他接口都是大差不差的。
void test_set01()
{setint s;s.insert(1);s.insert(2);s.insert(5);s.insert(7);s.insert(5); // 这个5是无法插入set的因为二叉搜索树不允许数据重复。// 这个迭代的过程其实就是中序遍历setint::iterator it s.begin();while (it ! s.end()){cout *it ; // 1 2 5 7 it;}cout endl;// 这里这个find如果找不到返回的是迭代器的末尾 也就是 s.end()//setint::iterator pos find(s.begin(), s.end(), 2); // 时间复杂度ONsetint::iterator pos s.find(20); // 这个是set容器的接口时间复杂度是O(logN)if (pos ! s.end()){s.erase(pos);}s.erase(5);s.erase(9); // 找不到不会进行操作// 只要支持迭代器就可以支持范围forfor (auto e : s){cout e ;}cout endl;
}3.2map
3.2.1map介绍
map文档介绍
总结 map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。 在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair: typedef pairconst key, T value_type; 在内部map中的元素总是按照键值key进行比较排序的。 map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。 map支持下标访问符即在[]中放入key就可以找到与key对应的value。 map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
3.2.2map的使用 key: 键值对中key的类型
T 键值对中value的类型
Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
**Alloc**通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器
3.2.2.1map的构造 3.2.2.2map的迭代器
这里迭代器也是以中序遍历来迭代map的 3.2.2.3map的容量与访问 []的使用和原理
先来看一个[]的应用场景——统计次数
// 统计次数还有更简洁的写法
void test_map04()
{string strArr[] { 苹果, 苹果, 苹果, 苹果, 苹果, 橘子, 橘子, 橘子, 香蕉 };mapstring, int countMap;for (auto str : strArr){// 找str这个key是否存在存在就让对应的value找不到就插入countMap[str]; // 这里用方括号可以直接实现,相当于调用的下面那句话//(*((this-insert(make_pair(str, mapped_type()))).first)).second}// 输出统计好的次数for (auto e : countMap){cout e.first 出现次数的 : e.second endl;}cout endl;
}
在调用[]的时候实际上是调用(*((this-insert(make_pair(k, mapped_type()))).first)).second 因此要想搞懂[]的使用就要先搞定insert的使用 插入的时候要给一个value_type这个类型是键值对类型mapped_type才是value的类型 除了看函数参数列表还得看返回值这里有一个返回值是pairiterator,bool插入失败不应该返回false成功返回true吗给一个pair类型是什么意思呢
返回值的解释如下 意思就是这里返回的pair类型first是key这里设置成iterator类型意味着这里的迭代器要不指向新插入的节点要不指向已经存在于map的那个节点。second是value这里设置成bool类型代表是否成功插入成功插入就是true插入失败就是false。【这个时候迭代器就指向map中已经存在的节点因为插入失败代表map已经存在所要插入的数据的】
现在我们尝试调用insert来实现上面[]实现的功能
// 统计次数还有更简洁的写法
void test_map04()
{string strArr[] { 苹果, 苹果, 苹果, 苹果, 苹果, 橘子, 橘子, 橘子, 香蕉 };mapstring, int countMap;for (auto str : strArr){// 找str这个key是否存在存在就让对应的value找不到就插入//countMap[str]; // 这里用方括号可以直接实现,相当于调用的下面那句话//(*((this-insert(make_pair(str, mapped_type()))).first)).second// 了解如何调用insert实现的pairmapstring, int::iterator, bool ret countMap.insert(make_pair(str, 1));// 这里这个insert的过程自动就帮我们筛选了 str这个key是否存在于map中insert返回一个pair类型// 我们通过pair这个类型来获取str是否插入map中if (ret.second false) {// bool为假说明插入失败key已经存在于map中//(*ret.first).second; // 就通过迭代器找到该节点在将该节点的second也就是出现的次数ret.first-second; // 等价于(*ret.first).second;}else{// bool为真说明插入成功,不做处理。这个else分支不写都行这里写出来方便理解}}// 输出统计好的次数for (auto e : countMap){cout e.first 出现次数的 : e.second endl;}cout endl;
}在了解了insert的返回值pair的使用之后我们就能理解[]的原理了
mapped_type operator[] (const key_type k)
{(*((this-insert(make_pair(k, mapped_type()))).first)).second
}了解了[]的原理之后我们来解析一下统计次数场景中使用的[]是如何实现统计次数的
// 解析[]如何实现需求
void test_map05()
{string strArr[] { 苹果, 苹果, 苹果, 苹果, 苹果, 橘子, 橘子, 橘子, 香蕉 };mapstring, int countMap;for (auto str : strArr){countMap[str]; // 1. 如果str这个k不存在于countMap中那就插入pairstr, int(),也就是pairstr, 0// 在通过insert返回的pair类型拿到插入的节点的迭代器通过迭代器拿到出现的次数进行此时存储的就是pairstr, 1// 2. 如果str这个k存在于countMap中就通过insert返回的pair类型拿到该k的节点的迭代器// 在通过该迭代器拿到节点的value。也就是出现次数进行。}// 输出统计好的次数for (auto e : countMap)// 这里的auto是pairconst string, int{cout e.first 出现次数的 : e.second endl;}cout endl;
}总结
map的operator[]的三层作用
插入不存在的k和v查找k对应的映射对象修改k对应的映射对象
这也能解释为什么[]的底层原理是用insert来实现的。因为这样才能实现这三层作用 注意在元素访问时有一个与operator[]类似的操作at()(该函数不常用)函数都是通过key找到与key对应的value然后返回其引用不同的是当key不存在时operator[]用默认value与key构造键值对然后插入返回该默认valueat()函数直接抛异常。 3.2.2.4map的基础接口的使用 这里需要讲一下map和set的区别。
在使用insert的时候要注意因为map是KV模型的平衡二叉搜索树因此插入的时候要插入一个键值对。在cpp是一个类型pair类型是一个类模版。 为什么呢?
其实结合迭代器会更好的理解。cpp函数仅支持一个返回值意味着迭代器只能返回一个键值对pair。不能返回一个key和一个value。
void test_map01()
{mapint, int m;//m.insert(1, 1); // 这样是不行的。 m.insert(pairint, int(1, 4));// 这里是通过匿名对象调用构造函数m.insert(pairint, int(3, 3));m.insert(pairint, int(2, 2));m.insert(make_pair(5, 8)); // 通过函数模版构造一个pair类型的对象mapint, int::iterator it m.begin();while (it ! m.end()){//cout *it ; // 这样也是不行的因为map是KV模型的搜索二叉树// 返回一个节点的内容应该是既有key也有value但是cpp只支持返回值是一个// 这样也解释了为什么insert的时候要插入pair类型//cout (*it).first : (*it).second endl; // 实际不怎么用这个cout it-first : it-second endl; // 实际更用这个,这个编译器进行特殊处理了。本来是it--second的it;}cout endl;mapint, int::iterator pos m.find(1); // 这里找的是key而不是valueif (pos ! m.end()){m.erase(pos);}// 支持迭代器就支持范围forfor (auto e : m)// 这里的auto是pairconst string, int{cout e.first : e.second endl;}cout endl;
}实际中更喜欢用make_pair来构造键值对参数因为这里不需要传模版参数。会自动推导模版参数 3.2.2.5map的使用案例
这里来一个模拟工程环境的代码
// 这里来一个模拟工程的场景
void test_map02()
{std::mapstd::string, std::string dict;dict.insert(pairstd::string, std::string(sort, 排序));dict.insert(make_pair(string, 字符串));std::mapstd::string, std::string::iterator it dict.begin();while (it ! dict.end()){cout it-first : it-second endl;it;}cout endl;}再来一个map的应用场景————统计次数
// 再来一个map的应用场景————统计次数
void test_map03()
{string strArr[] { 苹果, 苹果, 苹果, 苹果, 苹果, 橘子, 橘子, 橘子, 香蕉 };mapstring, int countMap;for (auto str : strArr){// 找str这个key是否存在存在就让对应的value找不到就插入mapstring, int::iterator pos countMap.find(str);if (pos countMap.end()){// 找不到就插入countMap.insert(make_pair(str, 1));}else{// 找到了就让出现次数pos-second;}}// 输出统计好的次数for (auto e : countMap)// 这里的auto是pairconst string, int{cout e.first 出现次数的 : e.second endl;}cout endl;
}除了用上述方法我们还可以直接使用[]来实现该场景.
[]的原理上面有讲
void test_map04()
{string strArr[] { 苹果, 苹果, 苹果, 苹果, 苹果, 橘子, 橘子, 橘子, 香蕉 };mapstring, int countMap;for (auto str : strArr){// 找str这个key是否存在存在就让对应的value找不到就插入countMap[str]; // 输出统计好的次数for (auto e : countMap)// 这里的auto是pairconst string, int{cout e.first 出现次数的 : e.second endl;}cout endl;
}3.2.2.6map的总结
对于map来说是可以进行增删查改的当然改的是v不是k
增 insert或者operator[]删 erase查 find 【也可以用[]但是不用[]。因为如果key不存在就会插入map中】改 operator[]遍历 iterator 或者范围for
map的总结 map中的的元素是键值对pairkey, value访问的时候要注意。 map中的key是唯一的并且不能修改 默认按照小于的方式对key进行比较 map中的元素如果用迭代器去遍历可以得到一个有序的序列 map的底层为平衡搜索树(红黑树)查找效率比较高 O ( l o g 2 N ) O(log_2 N) O(log2N) 支持[]操作符operator[]中实际进行插入查找
3.3multiset
3.3.1multiset的介绍
multiset的文档介绍
总结 multiset是按照特定顺序存储元素的容器其中元素是可以重复的。 在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。 multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列。 multiset底层结构为二叉搜索树(红黑树)。
注意 与set的区别是multiset中的元素可以重复(键值冗余)set是中value是唯一的 并且使用find在寻找相同的key的时候会按照中序遍历的顺序去寻找
3.3.2multiset的使用
multiset和set的使用非常相似这里就看看multiset和set不同的地方的使用就好了。
// 使用一下multiset
void test_multiset()
{// 和set区别就是允许键值冗余multisetint ms;ms.insert(3);ms.insert(1);ms.insert(4);ms.insert(2);ms.insert(6);ms.insert(3); //允许键值冗余// 再查找的时候如果查找的数据是重复的那找到的是中序遍历顺序的第一个。multisetint::iterator pos ms.find(3); // 这里找到3是中序遍历顺序的第一个3multisetint::iterator it ms.begin();while (it ! ms.end()){cout *it ; // 1 2 3 3 4 6it;}cout endl;setint s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);s.insert(6);s.insert(3); //不允许键值冗余for (auto e : s){cout e ; // 1 2 3 4 6}cout endl;
}
3.4multimap
3.4.1multimap的介绍
multimap的文档介绍
总结 Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key, value其中多个键值对之间的key是可以重复的。 在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起value_type是组合key和value的键值对:typedef pairconst Key, T value_type; 在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对key进行排序的。 multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。 multimap在底层用二叉搜索树(红黑树)来实现。 注意 multimap和map的区别就是map的key不能重复multimap允许重复还有一个multimap没有operator[]的存在因为如果存在多个key不知道返回那个key的value 3.4.2multimap的使用
同理multimap和map的使用也是非常相似的这里就只使用不同的地方、
void test_multimap()
{// multimap和map的区别和上面是一样的也是允许键值冗余// 还有就是multimap没有operator[]因为当有多个key的时候不知道返回那个key的valuemultimapstring, int mmap;mmap.insert(pairstring, int(苹果, 1));mmap.insert(pairstring, int(苹果, 2));mmap.insert(make_pair(苹果, 3));for (auto e : mmap){cout e.first : e.second endl;}cout endl;
}4.有关map和set的oj
4.1前K个高频单词
前K个高频单词 思路1
优先级队列
先用一个map统计单词出现的次数然后通过优先级队列搞一个小堆转换为TopK问题。 注意 这里在用优先级队列的时候优先级队列要存储一个pairstring, int类型容器是vectorpairstring, int,并且由于pair类型无法进行大小比较在插入进队列的时候无法保持堆的逻辑因此需要为它专门弄个仿函数。 auto cmp [](const pairstring, int a, const pairstring, int b) {return a.second b.second ? a.first b.first : a.second b.second;};priority_queuepairstring, int, vectorpairstring, int, decltype(cmp) que(cmp);思路2
用map和multimap解决
思路在代码中有讲述
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {vectorstring ret;// 通过map来统计单词出现的次数mapstring, int countMap;// 统计各单词出现的次数for(auto str : words){countMap[str]; }/* // 方便调试for(auto e : countMap){cout e.first : e.second endl; }cout endl;*/// 将单词出现的次数用multimap放起来因为可能有多个重复key存在用multimapmultimapint, string, greaterint countSort; // greaterint导致中序遍历的结果是倒序。出现次数多的往左走少的往右走for(auto kv : countMap) //auto是pairconst string, int{// 将各单词出现的次数进行排序countSort.insert(make_pair(kv.second, kv.first));//这里在插入的时候是大的往左走}/* // 方便调试for(auto e : countSort){cout e.first : e.second endl; }cout endl;*///将前k个出现次数最多的单词放到ret中for(auto e : countSort) // pairconst int, const string{ret.push_back(e.second);k--;if(k 0)break;}return ret;}
};4.2两个数组的交集 两个数组的交集 - LeetCode 思路1
将nums1和nums2分别装在一个set中这里叫s1、s2、通过依次取出s1中的元素去s2中寻找该元素是否存在找到了就是交集元素
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {vectorint ret;// 用set解决 set的key不能重复setint s1; // s1用来装nums1中出现过的数字setint s2; // s2用来装nums2中出现过的数字for(int e : nums1){s1.insert(e);}for(int e : nums2){s2.insert(e);}// 这个时候s1装着nums1中出现过的数字s2装着nums2出现过的数字for(auto e : s1){// 取出s1中的元素依次去寻找在s2中是否存在setint::iterator pos s2.find(e);// 如果s2中存在。就说明是交集元素放进ret中if(pos ! s2.end()) // pos s2.end()就说明没找到{ret.push_back(e);}}// 此时ret就装着交集元素return ret;}
};思路2
和思路1一样但是在判断是否是交集元素的时候思路不一样。思路1通过寻找这里我们通过比较的方式。我们让s1的元素去和s2的比较只要发现相等的元素就一定是交集元素。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {vectorint ret;// 用set解决 set的key不能重复setint s1; // s1用来装nums1中出现过的数字setint s2; // s2用来装nums2中出现过的数字for(int e : nums1){s1.insert(e);}for(int e : nums2){s2.insert(e);}// 除了寻找也可以通过比较的方式判断是否是交集元素// set排过序依次比较小的一定不是交集相等的是交集auto it1 s1.begin(); // auto就是setint::iteratorauto it2 s2.begin();while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){it1;}else if(*it2 *it1){it2;}else{ret.push_back(*it1);it1;it2;}}// 此时ret就装着交集元素return ret;}
};setint s2; // s2用来装nums2中出现过的数字for(int e : nums1){s1.insert(e);}for(int e : nums2){s2.insert(e);}// 除了寻找也可以通过比较的方式判断是否是交集元素// set排过序依次比较小的一定不是交集相等的是交集auto it1 s1.begin(); // auto就是setint::iteratorauto it2 s2.begin();while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){it1;}else if(*it2 *it1){it2;}else{ret.push_back(*it1);it1;it2;}}// 此时ret就装着交集元素return ret;}};
