目录一. 序列式容器和关联式容器二. set 容器2.1 了解 set 类2.2 set的构造和迭代器2.3 set 的增删查2.3.1 set 的增2.3.2 set 的查2.3.3 set 的删2.3.3.1 count2.3.3.2 lower_bound 和 upper_bound2.4 multiset2.4.1 multiset 和 set 的差异代码实现2.4.1.1 查找2.4.1.2 删除2.5 实战演练349. 两个数组的交集 - 力扣LeetCode142. 环形链表 II - 力扣LeetCode三.map 容器3.1 了解 map 类3.2 pair 类型3.3 map 的增删查3.3.1 map 的增3.3.1.1 map 的 key 的唯一性3.3.2 遍历3.3.3 equal_range3.3.4 map 的查3.3.5 map 的删3.4 operator[ ]3.4.1 统计次数查找 插入利用operator[ ]搞定dict查找3.5 mutimap3.5.1 插入3.5.2 equal_range3.6 实战演练138. 随机链表的复制 - 力扣LeetCode692. 前K个高频单词 - 力扣LeetCode写法一写法二写法三一. 序列式容器和关联式容器前面我们已经接触过STL中的部分容器比如string、vector、list、deque、array、forward_list等这些容器统称为序列式容器因为逻辑结构为线性序列的数据结构两个位置存储的值之间一般没有紧密的关联关系比如交换一下依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。这部分要介绍的map和set底层是红黑树红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构map是key / value搜索场景的结构。二. set 容器2.1 了解 set 类1、set的声明如下T就是set底层关键字的类型2、set对T要求比较大小默认要求T支持小于比较的就可以了如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数3、set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数——这一点不需要管4、一般情况下我们都不需要传后两个模版参数5、set底层是用红黑树实现的红黑树我们已经知道是平衡二叉树增删查效率是O(logN) 迭代器遍历是走的搜索树的中序左根右所以是有序的6、前面部分我们已经介绍了vector / list等容器的使用因为STL容器接口设计高度相似所以这里我们就不再一个接口一个接口的介绍而是直接带大家看文档挑比较重要的接口进行介绍。template class T, // set::key_type/value_type class Compare lessT, // set::key_compare/value_compare class Alloc allocatorT // set::allocator_type class set;2.2 set的构造和迭代器// empty (1) 无参默认构造 explicit set(const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // range (2) 迭代器区间构造 template class InputIterator set(InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type allocator_type()); // copy (3) 拷贝构造 set(const set x); // initializer list (5) initializer 列表构造 set(initializer_listvalue_type il, const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // 迭代器是一个双向迭代器 iterator-a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();#includeiostream #includeset using namespace std; int main() { //默认构造 setint a1; //迭代器构造 int arr[] { 1,2,3,4,5 }; setint a2(arr, arr sizeof(arr)/sizeof(int)); //拷贝构造 setint a3(a1); //赋值运算符重载 a2 a1; return 0; }2.3 set 的增删查2.3.1 set 的增#includeset int main() { //去重升序排序(换成greaterint变降序) setint,greaterint s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); setint, greaterint::iterator it s1.begin(); while (it ! s1.end()) { //不支持*it; cout *it ; it; } cout endl; return 0; }2.3.2 set 的查#includeset int main() { //去重升序排序(换成greaterint变降序) setint,greaterint s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); setint, greaterint::iterator pos s1.find(2); if (pos ! s1.end()) { cout *pos endl; } return 0; }2.3.3 set 的删#includeset int main() { //去重升序排序(换成greaterint变降序) setint,greaterint s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); int x; cin x; int num s1.erase(x); if (num 0) { cout x 不存在 endl; } else { cout x 删除成功 endl; } return 0; }2.3.3.1 count#includeset int main() { //去重升序排序(换成greaterint变降序) setint,greaterint s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); if (s1.count(2)) { cout 存在 endl; } else { cout 不存在 endl; } return 0; }2.3.3.2 lower_bound 和 upper_bound#includeset #includeiostream using namespace std; int main() { setint myset; for (int i 1; i 10; i) { myset.insert(i * 10); } for (auto e : myset) { cout e ; } cout endl; //删除[30,50] setint::iterator itlow myset.lower_bound(30); setint::iterator itup myset.upper_bound(50); myset.erase(itlow, itup); for (auto e : myset) { cout e ; } cout endl; return 0; }2.4 multiset2.4.1 multiset 和 set 的差异multiset和set的使用基本完全类似主要区别点在于multiset支持值冗余。代码实现#includeset #includeiostream using namespace std; int main() { multisetint,greaterint s { 4,2,3,1,4,5,2,3,1,6,8,6,3,9 }; multisetint::iterator it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; return 0; }2.4.1.1 查找比如查找3这个节点如果有多个3节点会查找中序遍历的第一个3节点——#includeset #includeiostream using namespace std; int main() { int x; cin x; multisetint,greaterint s { 4,2,3,1,4,5,2,3,1,6,8,6,3,9 }; multisetint::iterator pos s.find(x); while (pos ! s.end() *pos x) { cout *pos ; pos; } cout endl; return 0; }2.4.1.2 删除#includeiostream #includeset using namespace std; int main() } multisetint,greaterint s { 4,2,3,1,4,5,2,3,1,6,8,6,3,9 }; multisetint::iterator it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; //删除全部的3 s.erase(3); multisetint::iterator _it s.begin(); while (_it ! s.end()) { cout *_it ; _it; } cout endl; return 0; }2.5 实战演练349. 两个数组的交集 - 力扣LeetCode使用set直接实现排序j去重class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { setint set1(nums2.begin(),nums2.end()); setint set2(nums1.begin(),nums1.end()); vectorint ans; setint::iterator itset1.begin(); while(it!set1.end()) { auto posset2.find(*it); if(pos!set2.end()) { ans.push_back(*it); } it; } return ans; } };142. 环形链表 II - 力扣LeetCodeset存指针用count函数判断是否重复class Solution { public: ListNode *detectCycle(ListNode *head) { multisetListNode* st; ListNode* curhead; while(cur) { st.insert(cur); if(st.count(cur)2) { return cur; } curcur-next; } return nullptr; } };三.map 容器3.1 了解 map 类map的声明如下Key就是map底层关键字的类型T是map底层value的类型set默认要求Key支持小于比较如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数map底层存储数据的内存是从空间配置器申请的。一般情况下我们都不需要传后两个模版参数。map底层是用红黑树实现增删查改效率是OlogN迭代器遍历是走的中序所以是按key有序顺序遍历的。3.2 pair 类型3.3 map 的增删查3.3.1 map 的增#includeiostream #includemap using namespace std; int main() { mapstring, string dict; dict.insert(pairstring, string(first, 第一个)); dict.insert(pairstring, string(second, 第二个)); //更简洁一点的话就用make_piar dict.insert(make_pair(sort, 排序)); //隐式类型转换,构造pair再插入 dict.insert({ auto,自动的 }); return 0; }3.3.1.1 map 的 key 的唯一性想插入相同的 key 值 value 并不会更新也不会插入成功。#includeiostream #includemap using namespace std; int main() { mapstring, string dict; dict.insert(pairstring, string(first, 第一个)); dict.insert(pairstring, string(second, 第二个)); //更简洁一点的话就用make_piar dict.insert(make_pair(sort, 排序)); //隐式类型转换,构造pair再插入 dict.insert({ auto,自动的 }); dict.insert({ auto,自动的xxxxxx }); mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { cout it.operator-()-first : it.operator-()-second endl; it; } return 0; }3.3.2 遍历map 的迭代器遍历稍微有点不同因为 pia r本身没有重载流插入和流提取所以不能直接打印。#includeiostream #includemap using namespace std; int main() { mapstring, string dict; dict.insert(pairstring, string(first, 第一个)); dict.insert(pairstring, string(second, 第二个)); //更简洁一点的话就用make_piar dict.insert(make_pair(sort, 排序)); //隐式类型转换,构造pair再插入 dict.insert({ auto,自动的 }); mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { cout it.operator-()-first : it.operator-()-second endl; it; } return 0; }3.3.3 equal_range3.3.4 map 的查#includeiostream #includemap using namespace std; int main() { mapstring, string dict; dict.insert(pairstring, string(first, 第一个)); dict.insert(pairstring, string(second, 第二个)); //更简洁一点的话就用make_piar dict.insert(make_pair(sort, 排序)); //隐式类型转换,构造pair再插入 dict.insert({ auto,自动的 }); string x; cin x; auto it dict.find(x); if (it ! dict.end()) { cout找到了 it-first : it-second endl; } else { cout 没有找到 endl; } return 0; }3.3.5 map 的删#includemap using namespace std; int main() { mapstring, string dict; dict.insert(pairstring, string(first, 第一个)); dict.insert(pairstring, string(second, 第二个)); //更简洁一点的话就用make_piar dict.insert(make_pair(sort, 排序)); //隐式类型转换,构造pair再插入 dict.insert({ auto,自动的 }); dict.erase(first); mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { cout it.operator-()-first : it.operator-()-second endl; it; } return 0; }3.4 operator[ ]简单点说就是我给你一个 key你帮我找到对应的 value然后返回这个 value。operator[ ]有三种功能插入、查找、修改mapstring, string dict; dict.insert(make_pair(sort, 搜索)); //key不存在-插入 dict[insert]; //插入修改 dict[left] 左边; //修改 dict[left] 剩余; mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { cout it.operator-()-first : it.operator-()-second endl; it; } return 0;这些功能的实现也离不开insert的返回类型3.4.1 统计次数查找 插入// 查找 插入组合 mapstring, int countMap; for (auto e : arr) { auto it countMap.find(e); if (it ! countMap.end()) { it-second; // 存在则递增 } else { countMap.insert({ e,1 }); // 不存在则插入 } }利用operator[ ]搞定dict查找// 利用 operator[] 的特性 for (auto e : arr) { countMap[e]; }3.5 mutimapmultimap和map的使用基本完全类似主要区别点在于multimap支持关键值key冗余那么insert / find / count / erase都围绕着支持关键值key冗余有所差异这里跟set和multiset完全一样比如find时有多个key返回中序第一个。其次就是multimap不支持[]因为支持key冗余[ ]就只能支持插入了不能支持修改。3.5.1 插入无论 key 值是否相同都会插入#includeiostream #includemap using namespace std; int main() { multimapstring, stringdict; dict.insert(make_pair(sort, 排序)); dict.insert(make_pair(sort, 排序1)); dict.insert(make_pair(sort, 排序2)); dict.insert(make_pair(sort, 排序3)); dict.insert(make_pair(sort, 排序4)); dict.insert(make_pair(sort, 排序5)); multimapstring, string::iterator it dict.begin(); while (it ! dict.end()) { cout it.operator-()-first : it.operator-()-second endl; it; } return 0; }3.5.2 equal_rangeequal_range 在 multimap上可以用于找出一段相同值#includeiostream #includemap using namespace std; int main() { multimapstring, stringdict; dict.insert(make_pair(sort, 排序)); dict.insert(make_pair(ort, 排序1)); dict.insert(make_pair(ort, 排序2)); dict.insert(make_pair(sort, 排序3)); dict.insert(make_pair(ort, 排序4)); dict.insert(make_pair(sort, 排序5)); auto _pair dict.equal_range(sort); auto it _pair.first; while (it ! _pair.second) { cout it-first : it-second endl; it; } return 0; }3.6 实战演练138. 随机链表的复制 - 力扣LeetCode数据结构初阶阶段为了控制随机指针我们将拷贝结点链接在原节点的后面解决后面拷贝节点还得解下来链接非常麻烦。这里我们直接让{原结点拷贝结点}建立映射关系放到map中控制随机指针会非常简单方便这里体现了map在解决一些问题时的价值完全是降维打击。/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { mapNode*,Node* nodeMap; Node* copyhead nullptr,*copytail nullptr; Node* cur head; while(cur) { Node* copynew Node(cur-val); // 尾随 if(copytail nullptr) { copyhead copytailcopy; } else { copytail-nextcopy; copytailcopy; } nodeMap.insert({cur,copy}); curcur-next; } cur head; Node* copy copyhead; while(cur) { if(cur-random nullptr) { copy-random nullptr; } else { copy-random nodeMap[cur-random]; } cur cur-next; copy copy-next; } return copyhead; } };692. 前K个高频单词 - 力扣LeetCode本题目我们利用map统计出次数以后返回的答案应该按单词出现频率由高到低排序有一个特殊要求如果不同的单词有相同出现频率按字典顺序排序。写法一用排序找前k个单词因为map中已经对key单词排序过也就意味着遍历map时次数相同的单词字典序小的在前面字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求但是sort底层是快排是不稳定的所以我们要用stable_sort他是稳定的。// 方法1 class Solution { public: struct kv_pair { bool operator()(const pairstring, int kv1,const pairstring, int kv2) { return kv1.second kv2.second; } }; vectorstring topKFrequent(vectorstring words, int k) { mapstring, int countMap; for(auto str : words) { countMap[str]; } // multimapint,string sortMap; // 降序 vectorpairstring, int v(countMap.begin(), countMap.end()); // sort(v.begin(),v.end(),kv_pair()); // 稳定的排序 stable_sort(v.begin(), v.end(), kv_pair()); for (auto [k, v] : v) { cout k : v endl; } cout endl; vectorstring ret; for (size_t i 0; i k; i) { ret.push_back(v[i].first); } return ret; } };写法二将map统计出的次数的数据放到vector中排序或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的字典序小的在前面。// 方法2 class Solution { public: // 自己实现一个仿函数控制比较逻辑 struct kv_pair { // 次数大的在前面次数相等的、字典序小的在前面 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) { for(auto str : words) { countMap[str]; } // multimapint,string sortMap; // 降序 vectorpairstring,int v(countMap.begin(),countMap.end()); sort(v.begin(),v.end(),kv_pair); for(auto [k,v] : v) { cout k : v endl; } cout endl; vectorstring ret; for(size_t i 0;i k;i) { ret.push_back(v[i].first); } return ret; } };写法三使用优先级队列大堆提供的小于的比较逻辑。次数大的在前面次数相等的字典序小的在前面——// 方法3 class Solution { public: struct kv_pair{ // 次数大的在前面次数相等的字典序小的在前面 // 优先级队列大堆提供的小于的比较逻辑 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 str : words) { countMap[str]; } // 大堆 priority_queuepairstring,int,vectorpairstring,int, kv_pair pq(countMap.begin(),countMap.end()); vectorstring ret; for(size_t i 0;i k;i) { ret.push_back(pq.top().first); pq.pop(); } return ret; } };