网站内页不收录,高端网站建设网站定制,众筹网站开发价格,app软件开发价目表目录 一、关联式容器 二、键值对 三、树形结构的关联式容器 3.1 set 3.1.1 set的介绍 3.1.2 set的使用 3.2 multiset 3.2.1 multiset的介绍 3.2.2 multiset的使用 3.3 map 3.3.1 map的介绍 3.3.2 map的使用 … 目录 一、关联式容器 二、键值对 三、树形结构的关联式容器 3.1 set 3.1.1 set的介绍 3.1.2 set的使用 3.2 multiset 3.2.1 multiset的介绍 3.2.2 multiset的使用 3.3 map 3.3.1 map的介绍 3.3.2 map的使用 extra map的[ ]重载代码剖析 3.4 multimap 3.4.1 multimap的介绍 3.3.2 multimap的使用 附录 力扣编程题 如果你已经了解了KV二叉搜索树将会更容易读懂本文 一、关联式容器 STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 二、键值对 用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量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){}
}; 三、树形结构的关联式容器 根据应用场景的不桶STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。 3.1 set 3.1.1 set的介绍 文档介绍 set - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/set/?kwset set是按照一定次序存储元素的容器底层是用二叉搜索树(红黑树)实现的对于set元素的value也标识它本身(即value就是key类型为T)并且每个value必须是唯一的确保每个元素都可以标识它本身。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序默认按照小于来比较set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代 3.1.2 set的使用 详细内容见文档介绍下面是接口和示例代码接下来通过下面这段代码学习 lower_bound 和 up_bound void test_set2()
{setint myset;setint::iterator itlow, itup;for (int i 1; i 10; i) myset.insert(i * 10);// 10 20 30 40 50 60 70 80 90itlow myset.lower_bound(30); // val值位置的iteratoritup myset.upper_bound(70); // val值位置的iteratorsetint::iterator it itup;while (it ! myset.end()){cout *it ;it;}cout endl; // 80 90myset.erase(itlow, itup); // 10 20 70 80 90for (auto e : myset){cout e ;}cout endl;
}void test_set3()
{std::setint myset;for (int i 1; i 5; i) myset.insert(i * 10); // myset: 10 20 30 40 50//std::pairstd::setint::const_iterator, std::setint::const_iterator ret;auto ret myset.equal_range(35);std::cout the lower bound points to: *ret.first \n; // valstd::cout the upper bound points to: *ret.second \n; // val
} 3.2 multiset 3.2.1 multiset的介绍 文档介绍 multiset - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/multiset/?kwmultiset multiset是按照特定顺序存储元素的容器其中元素是可以重复的multiset底层结构为二叉搜索树(红黑树)在multiset中元素的value也会识别它本身(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T)。multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列 3.2.2 multiset的使用 仅演示与set的不同之处大体上可以参考set的用法 void test_multiset()
{// 排序multisetint s;s.insert(5);s.insert(2);s.insert(6);s.insert(1);s.insert(5);s.insert(2);multisetint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;// 如果有多个值find返回中序第一个valit s.find(5);while (it ! s.end()){cout *it ;it;}cout endl;cout s.count(2) endl;// [val, val)//auto ret s.equal_range(2);//s.erase(ret.first, ret.second);size_t n s.erase(2);cout n endl;for (auto e : s){cout e ;}cout endl;
}VS2022 运行结果1 2 2 5 5 6
5 5 6
2
2
1 5 5 6 3.3 map 3.3.1 map的介绍 文档介绍 map - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/map/map/?kwmap map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pairtypedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的默认按照小于的方式对key进行比较。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value 3.3.2 map的使用 void test_map1()
{mapstring, string dict;dict.insert(pairstring, string(sort, 排序));dict.insert(pairstring, string(insert, 插入));dict.insert(pairconst char*, const char*(left, 左边));//dict.insert(make_pair(right, 右边)); // 优化dict[erase]; // 插入cout dict[erase] endl; // 查找dict[erase] 删除; // 修改cout dict[erase] endl; // 查找dict[test] 测试; // 插入修改dict[left] 左边、剩余; // 修改string s1(xxxx), s2(yyyy);dict.insert(make_pair(s1, s2));mapstring, string::iterator it dict.begin();while (it ! dict.end()){ // 三种打印方式cout (*it).first : (*it).second endl;//cout it.operator-()-first : it.operator-()-second endl;//cout it-first : it-second endl;it;}cout endl;for (auto kv : dict){// kv.first x;kv.second x;cout kv.first : kv.second endl;}
}运行结果删除
erase:删除
insert:插入
left:左边、剩余
right:右边
sort:排序
test:测试
xxxx:yyyyerase:删除x
insert:插入x
left:左边、剩余x
right:右边x
sort:排序x
test:测试x
xxxx:yyyyx 使用map统计水果出现的次数 void test_map2()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;//for (auto str : arr)//{// //auto ret countMap.find(str);// //if (ret countMap.end())// //{// // // 没有表示第一次出现插入// // countMap.insert(make_pair(str, 1));// //}// //else// //{// // // 有就让次数// // ret-second;// //}// countMap[str];//}// 更优代码for (auto str : arr){countMap[str];}for (auto kv : countMap){cout kv.first : kv.second endl;}
}extra map的[ ]重载代码剖析 3.4 multimap 3.4.1 multimap的介绍 文档介绍 multimap - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/map/multimap/?kwmultimap multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key,value其中多个键值对之间的key是可以重复的。multimap在底层用二叉搜索树(红黑树)来实现。在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有序的序列。 3.3.2 multimap的使用 multimap中的接口可以参考map功能都是类似的需要注意的是multimap没有重载operator[]操作为什么multimap可以有多个重复的keyoperator[ ]无法判断返回哪个key的value 附录 力扣编程题 692. 前K个高频单词 - 力扣LeetCode class Solution {
public:// pair类型的relation比较重载不符合我们的需求我们可以自己写一个仿函数struct kvCompare{bool operator()(const pairstring, int kv1, const pairstring, int kv2){return kv1.second kv2.second || (kv1.second kv2.second kv1.first kv2.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring, int countMap;for(auto kv : words) countMap[kv];// map的迭代器是双向迭代器重载、--不支持、-// 所以我们把数据放入vector再使用sort进行排序vectorpairstring, int kv(countMap.begin(), countMap.end());sort(kv.begin(), kv.end(), kvCompare());// 返回的结果只需要string我们整理一下vectorstring v;for(int i0; ik; i){v.push_back(kv[i].first);}return v;}
}; 349. 两个数组的交集 - 力扣LeetCode class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {// 数据类型相同使用迭代器区间初始化去重setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());vectorint ret;// 找交集(已经有序)// 相同的就是交集的元素it1、it2; 不相等较小的it。有一个it结束了整个筛查就结束了// 找差集(已经有序)// 相等it1、it2; 不相等较小的是差集的元素较小的it。有一个it结束了另一个没结束的也都是差集的元素auto it1 s1.begin();auto it2 s2.begin();while(it1 ! s1.end() it2! s2.end()){if(*it1 *it2) it1;else if(*it1 *it2) it2;else{ret.push_back(*it1);it1, it2;}}return ret;}
};
