响应式网站手机,中国公司排名500强名单,自己开发的app如何上线,自适应影视网站模板[本节目标] 1. 关联式容器 2. 键值对 3. 树形结构的关联式容器 1. 关联式容器
在初阶阶段#xff0c;我们已经接触过STL中的部分容器#xff0c;比如#xff1a;vector、list、deque、forward_list(C11)等#xff0c;这些容器统称为序列式容器#xff0c;因为其底层为…[本节目标] 1. 关联式容器 2. 键值对 3. 树形结构的关联式容器 1. 关联式容器
在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别
关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是结构的键值对在数据检索时比序列式容器效率更高。
2. 键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然 有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该单词在词典中就可以找到与其对应的中文含义。
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. 树形结构的关联式容器
根据应用场景的不桶STL总共实现了两种不同结构的关联式容器树型结构与哈希结构。树型结 构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使 用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一 个容器。
3.1 set
3.1.1 set的介绍
翻译
1. set是按照一定次序存储元素的容器2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行 排序。4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代。5. set在底层是用二叉搜索树(红黑树)实现的。
注意
1. 与map/multimap不同map/multimap中存储的是真正的键值对set中只放 value但在底层实际存放的是由构成的键值对。2. set中插入元素时只需要插入value即可不需要构造键值对。3. set中的元素不可以重复(因此可以使用set进行去重)。4. 使用set的迭代器遍历set中的元素可以得到有序序列5. set中的元素默认按照小于来比较6. set中查找某个元素时间复杂度为$log_2 n$7. set中的元素不允许修改(为什么?) 8. set中的底层使用二叉搜索树(红黑树)来实现。
3.1.2 set的使用
1. set的模板参数列表 2. set的构造 3. set的迭代器 void test_set1()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;
}
运行结果 我们发现此时的输出结果是有序的这是因为set底层是搜索二叉树此时迭代器即对搜索二叉树进行中序遍历所以此时正好输出有序。但是这是set的附带功能set最主要的还是搜索查找的效率高最坏只需要找高度次其实set还有一个功能删掉重复元素。
void test_set2()
{// 排序 去重setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(3); s.insert(3);s.insert(6);s.insert(5);s.insert(5);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;
}
运行结果 4. set的容量 5.set修改操作 我们先来看一下find的使用 void test_set2()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);setint::iterator pos s.find(3);if (pos ! s.end()){cout 找到了 endl;}
}
运行结果 我们再来看一下erase的使用 erase传入的参数是可以是一个迭代器因此这里可以搭配find一起使用。
void test_set2()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);for (auto e : s){cout e ;}cout endl;setint::iterator pos s.find(3);if (pos ! s.end()){cout 找到了3 endl;s.erase(pos);cout 删除了3 endl;}for (auto e : s){cout e ;}cout endl;
}
运行结果 同时erase传入的参数是可以是一个value进行删除。
void test_set2()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);for (auto e : s){cout e ;}cout endl;s.erase(5);//删除5for (auto e : s){cout e ;}cout endl;
}
运行结果 那么这两个接口有什么区别呢
void test_set3()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);//setint::iterator pos s.find(2);//这里不加判断直接删除//值必须在找到有效位置才能删除//s.erase(pos);//元素在就删除不在就不进行任何处理s.erase(2);
}
如果我们传入的给erase的参数是一个迭代器当前元素不存在并且我们没有对其没有进行没有找到该元素的判断那么此时程序就会崩溃但是给erase的参数是一个value并且当前元素不存在程序不会崩溃。再来看下一个问题我们发现给erase的参数是一个value时它的返回值是size_tset文档里面介绍的是删除元素的个数此时难道不是就是1或者0嘛有什么意义呢我们在后面的multiset解释。我们再来看一下count的使用。 根据count的特性我们就可以使用count来判断元素在不在。
void test_set4()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);if (s.count(3)){cout 在 endl;}else{cout 不在 endl;}
}
运行结果 随后我们再来学习一下lower_bound和upper_bound这两个接口。 void test_set5()
{setint s;s.insert(1);s.insert(7);s.insert(3);s.insert(6);s.insert(5);//删除[3, 6]的值,这里都是闭区间//这里不能使用find,1.有可能3和6不一定在 2.erase给的是左闭右开的区间[ )//使用lower_bound和upper_boundsetint::iterator start s.lower_bound(3);//3存在返回3如果3不存在返回5//结论lower_bound返回 val的那个值cout *start endl;setint::iterator finish s.upper_bound(6);cout *finish endl;//6存在返回7如果6不在返回7//结论upper_bound返回 val的那个值for (auto e : s){cout e ;}cout endl;s.erase(start, finish);for (auto e : s){cout e ;}cout endl;
}
运行结果 6. set的使用举例
void test_set6()
{// 用数组array中的元素构造setint array[] { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,6, 8, 0 };setint s(array, array sizeof(array) / sizeof(array[0]));cout s.size() endl;// 正向打印set中的元素从打印结果中可以看出set可去重for (auto e : s)cout e ;cout endl;// 使用迭代器逆向打印set中的元素for (auto it s.rbegin(); it ! s.rend(); it)cout *it ;cout endl;// set中值为3的元素出现了几次cout s.count(3) endl;
}
运行结果 3.2 multiset
3.2.1 multiset的介绍
[翻译]
1. multiset是按照特定顺序存储元素的容器其中元素是可以重复的。2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是组成 的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器 中进行修改(因为元素总是const的)但可以从容器中插入或删除。3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则 进行排序。4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭 代器遍历时会得到一个有序序列。5. multiset底层结构为二叉搜索树(红黑树)。
注意
1. multiset中再底层中存储的是的键值对2. mtltiset的插入接口中只需要插入即可3. 与set的区别是multiset中的元素可以重复set是中value是唯一的4. 使用迭代器对multiset中的元素进行遍历可以得到有序的序列5. multiset中的元素不能修改6. 在multiset中找某个元素时间复杂度为$O(log_2 N)$7. multiset的作用可以对元素进行排序
3.3.2 multiset的使用
此处只简单演示set与multiset的不同其他接口接口与set相同可参考set。
void test_muliset1()
{int array[] { 2, 1, 3, 2 ,4 ,2 ,5 };// 注意multiset在底层实际存储的是int, int的键值对// 允许键值冗余// multiset实际上是排序multisetint s(array, array sizeof(array) / sizeof(array[0]));for (auto e : s)cout e ;cout endl;
}
运行结果 此时我们再来解释之前set给erase的参数是一个value时它的返回值是size_tset文档里面介绍的是删除元素的个数此时难道不是就是1或者0而对于multiset它是允许键值冗余的所以这里的erase删除的参数就是多个至于set这样设计就是为了与multiset保持一致所以count接口也是为multiset设计的随后我们来看一下find的细节问题由于multiset允许键值冗余那么就find在寻找的时候返回的是哪个位置的值呢返回的是中序第一个值。
void test_muliset2()
{int array[] { 2, 1, 3, 2 ,4 ,2 ,5 };// 注意multiset在底层实际存储的是int, int的键值对// 允许键值冗余multisetint s(array, array sizeof(array) / sizeof(array[0]));// 返回的是第几个位置的2呢 - 返回中序第一个2multisetint::iterator pos s.find(2);while (pos ! s.end()){cout *pos ;pos;}cout endl;
}
运行结果 3.3 map
3.3.1 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通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
3.2.2 map的使用
1. map的模板参数说明 2. map的构造 3. map的迭代器 4. map的容量与元素访问 我们这里先来写一个统计水果出现的次数的代码
void test_map3()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){mapstring, int::iterator it countMap.find(e);if (it ! countMap.end()){it-second;}else{countMap.insert(make_pair(e, 1));}}for (auto kv : countMap){cout kv.first : kv.second endl;}
}
运行结果 除了上面的方法我们还可以使用[ ]来解决。 void test_map4()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}
} 运行结果 问题当key不在map中时通过operator获取对应value时会发生什么问题 我们可以看到这里的operator[ ]的底层实现是调用了insert接口 所以我们这里就也可以使用insert来统计次数
void test_map5()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){pair mapstring, int::iterator, bool ret;ret countMap.insert(make_pair(e,1));if (ret.second false) //当前值已经存在{//ret.first是当前值的迭代器ret.first-second;}}for (auto kv : countMap){cout kv.first : kv.second endl;}
} 运行结果 所以我们此时就能很好的理解operator[ ]了根据理解初步实现一下operator[ ]底层原理。
V operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;
}
现在我们就可以总结operator[ ]的功能
void test_map6()
{mapstring, string dict;dict.insert(make_pair(orange, 橙子));dict.insert(make_pair(cherry, 樱桃));dict.insert(make_pair(apple, 苹果));//mapped_type operator[] (const key_type k);dict[banana];//插入cout dict[cherry] endl;//查找dict[orange] 橙色的;//修改dict[watermelon] 西瓜;//插入 修改for (auto kv : dict){cout kv.first : kv.second endl;}
} 运行结果 我们发现map还提供了at接口那么它和operator[ ]有什么区别呢 注意在元素访问时有一个与operator[]类似的操作at()(该函数不常用)函数都是通过 key找到与key对应的value然后返回其引用不同的是当key不存在时operator[]用默认 value与key构造键值对然后插入返回该默认valueat()函数直接抛异常。
5. map中元素的修改 void test_map1()
{mapstring, string dict;//匿名对象dict.insert(pairstring, string(sort, 排序));//有名对象//pairstring, string kv(string, 字符串);pairstring, string kv { string, 字符串 };//构造 拷贝构造 构造dict.insert(kv);// C11 多参数隐式类型转换(构造函数)dict.insert({ apple,苹果 });//隐式类型转换// C98 make_pair是一个函数模板dict.insert(make_pair(orange,橘子));mapstring, string::iterator it dict.begin();while (it ! dict.end()){//cout *it endl; pair没有重载cout (*it).first : (*it).second endl;cout it-first : it-second endl;it;}cout endl;
}
运行结果 那如果我们的key值是一样的但是我们的value不一样会发生什么情况呢
void test_map2()
{// key相同value不同不会插入也不会更新mapstring, string dict;dict.insert(make_pair(orange, 橙子));dict.insert(make_pair(orange, 橙色的));dict.insert(make_pair(cherry, 樱桃));dict.insert(make_pair(apple, 苹果));for (auto kv : dict){cout kv.first : kv.second endl;}
}
运行结果 从结果上看此时key值是一样的但是我们的value不一样这是因为我们的树的插入比较规则是按照key值来判断的value仅仅是多存入了一个值所以第二次出现key会认为当前值已经存在而不插入也不更新会认为插入失败树的关联规则和value没有关系。
void test_map8()
{mapstring, string m;// 向map中插入元素的方式// 将键值对peach,桃子插入map中用pair直接来构造键值对m.insert(pairstring, string(peach, 桃子));// 将键值对peach,桃子插入map中用make_pair函数来构造键值对m.insert(make_pair(banan, 香蕉));// 借用operator[]向map中插入元素/*operator[]的原理是用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中如果key已经存在插入失败insert函数返回该key所在位置的迭代器如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回*/// 将apple, 插入map中插入成功返回value的引用将“苹果”赋值给该引用结果m[apple] 苹果;// key不存在时抛异常//m.at(waterme) 水蜜桃;cout m.size() endl;// 用迭代器去遍历map中的元素可以得到一个按照key排序的序列for (auto e : m)cout e.first --- e.second endl;cout endl;// map中的键值对key一定是唯一的如果key存在将插入失败auto ret m.insert(make_pair(peach, 桃色));if (ret.second)cout peach, 桃色不在map中, 已经插入 endl;elsecout 键值为peach的元素已经存在 ret.first-first --- ret.first-second 插入失败 endl;// 删除key为apple的元素m.erase(apple);if (1 m.count(apple))cout apple还在 endl;elsecout apple被吃了 endl;
}
运行结果 【总结】
1. map中的的元素是键值对2. map中的key是唯一的并且不能修改3. 默认按照小于的方式对key进行比较4. map中的元素如果用迭代器去遍历可以得到一个有序的序列5. map的底层为平衡搜索树(红黑树)查找效率比较高$O(log_2 N)$6. 支持[]操作符operator[]中实际进行插入查找。
3.4 multimap
3.4.1 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的唯一不同就是map中的key是唯一的而multimap中key是可以 重复的。
3.4.2 multimap的使用
multimap中的接口可以参考map功能都是类似的。
注意
1. multimap中的key是可以重复的。2. multimap中的元素默认将key按照小于来比较3. multimap中没有重载operator[]操作4. 使用时与map包含的头文件相同
void test_multimap2()
{multimapstring, string dict;dict.insert(make_pair(orange, 橙子));dict.insert(make_pair(orange, 橙色的));dict.insert(make_pair(cherry, 樱桃));dict.insert(make_pair(apple, 苹果));for (auto kv : dict){cout kv.first : kv.second endl;}
}
运行结果 此时也和value一样没有关系只和key进行关联但是与map不同的是key一样我也进行插入。
3.5 在OJ中的使用
3.5.1 两个数组的交集 首先我们来看一下这种思路能否行通将数组nums1利用set去重然后遍历num2的元素是否在num1的里面如果在就是两个数组的交集。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s(nums1.begin(),nums1.end());vectorint v;for(auto e : nums2){if(s.count(e)){v.push_back(e);}}return v;}
};
运行结果 此时解答错误因为数组num2中和num1的交集可能会存在重复值所以我们可以刚开始就对num2进行去重解决问题。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());vectorint v;for(auto e : s2){if(s1.count(e)){v.push_back(e);}}return v;}
};
此时我们的代码就通过了测试案例现在我们对题目改编一下我们想在找到交集的同时顺便找到差集按照上面的逻辑如果num2的元素不在num1的里面那么就是差集但是我们这里换一个思路先拿set容器去重拿两个迭代器分别指向数组num1和num2然后依次比较不相等小的值就是差集相同的值就是差集让当前值小的迭代器加加如果值相同就同时加加。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());vectorint v;setint::iterator it1 s1.begin();setint::iterator it2 s2.begin();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;}
};
此时我们的程序也能通过。
3.5.2 前K个高频单词 我们直接来说思路首先我们利用map统计单词出现的次数但是这里不能利用map为有序选出前k个高频单词因为map有序的是key而不是value我们这里要让value排序所以我们就可以把数据放到vector中利用sort进行排序pair但是在文档中pair的比较方法是先比较first然后再比较second所以我们这里就不能使用默认的pair排序方法我们要单独实现一个仿函数来实现除我们的value排序也就是second排序。
class Solution {
public:struct kvCom{bool operator()(const pairstring, int left, const pairstring, int right){return left.second right.second;}};vectorstring topKFrequent(vectorstring words, int k) {//统计单词出现次数mapstring ,int countMap;for(auto e : words){countMap[e]; }//单词仍然按照字典排序vectorpairstring,int v(countMap.begin(),countMap.end());//按照value大小进行排序sort(v.begin(),v.end(),kvCom());//取前k个value大的值放入vectorvectorstring ret;auto it v.begin();while(k--){ret.push_back(it-first);it;}return ret;}
};
但是此时我们发现我们的程序没有通过所有的测试案例我们来看一下原因我们可以打印一下前k个高频出现的单词。 此时我们可以发现没有满足题目的要求相同频率的单词要按照字典顺序排序在vectorint v中经过map之后我们的单词已经按照字典排序但是我们这里使用的算法sort底层是快排它是一个不稳定的排序所以在排序second之后原本的字典排序就已经打乱了我们这里可以使用算法库中的稳定排序方法stable_sort去解决它底层是用归并排序是一种稳定的算法它就能保存相同频率的单词之间的相对顺序不变。
class Solution {
public:struct kvCom{bool operator()(const pairstring, int left, const pairstring, int right){return left.second right.second;}};vectorstring topKFrequent(vectorstring words, int k) {//统计单词出现次数mapstring ,int countMap;for(auto e : words){countMap[e]; }//单词仍然按照字典排序vectorpairstring,int v(countMap.begin(),countMap.end());//按照value大小进行排序stable_sort(v.begin(),v.end(),kvCom());//取前k个value大的值放入vectorvectorstring ret;auto it v.begin();while(k--){cout it-first : it-second endl;ret.push_back(it-first);it;}return ret;}
};
我们这里还可以通过修改仿函数来解决当单词出现的频率相同的时候我们让再让first小的在前面这也就是按字典排序。
class Solution {
public:struct kvCom{bool operator()(const pairstring, int left, const pairstring, int right){return left.second right.second || (left.second right.second left.first right.first);}};vectorstring topKFrequent(vectorstring words, int k) {//统计单词出现次数mapstring ,int countMap;for(auto e : words){countMap[e]; }//单词仍然按照字典排序vectorpairstring,int v(countMap.begin(),countMap.end());//按照value大小进行排序stable_sort(v.begin(),v.end(),kvCom());//取前k个value大的值放入vectorvectorstring ret;auto it v.begin();while(k--){cout it-first : it-second endl;ret.push_back(it-first);it;}return ret;}
};
本章节就先到这里啦
