文章目录1. 序列式容器和关联式容器2. set系列的使用2.1 set和multiset参考文档2.2 set类的介绍2.3 set的构造和迭代器2.4 set的增删查2.5 insert和迭代器遍历使用样例2.6 find和erase使用样例2.7 multiset和set的差异2.8 349. [两个数组的交集](https://leetcode.cn/problems/intersection-of-two-arrays/) - 力扣LeetCode2.9 142. [环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/description/) - 力扣LeetCode1. 序列式容器和关联式容器前面我们已经接触过STL中的部分容器如string、vector、list、deque、array、forward_list等这些容器统称为序列式容器因为逻辑结构为线性序列的数据结构两个位置存储的值之间一般没有紧密的关联关系比如交换一下他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。本篇和下篇讲解的map和set底层是红黑树红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构map是key/value搜索场景的结构。2. set系列的使用2.1 set和multiset参考文档点击跳转2.2 set类的介绍set的声明如下T就是set底层关键字的类型set默认要求T支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模板参数set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。一般情况下我们都不需要传后两个模板参数。set底层是用红黑树实现增删查效率是 O(logN)迭代器遍历是走的搜索树的中序所以是有序的。templateclassT,// set::key_type/value_typeclassComparelessT,// set::key_compare/value_compareclassAllocallocatorT// set::allocator_typeclassset;2.3 set的构造和迭代器set的构造我们关注以下几个接口即可。set的支持正向和反向迭代遍历遍历默认按升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围forset的iterator和const_iterator都不支持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。// empty (1) 无参默认构造explicitset(constkey_comparecompkey_compare(),constallocator_typeallocallocator_type());// range (2) 迭代器区间构造templateclassInputIteratorset(InputIterator first,InputIterator last,constkey_comparecompkey_compare(),constallocator_typeallocator_type());// copy (3) 拷贝构造set(constsetx);// initializer list (5) initializer 列表构造set(initializer_listvalue_typeil,constkey_comparecompkey_compare(),constallocator_typeallocallocator_type());// 迭代器是一个双向迭代器iterator-a bidirectional iterator toconstvalue_type// 正向迭代器iteratorbegin();iteratorend();// 反向迭代器reverse_iteratorrbegin();reverse_iteratorrend();2.4 set的增删查set的增删查关注以下几个接口即可Member types key_type-The firsttemplateparameter(T)value_type-The firsttemplateparameter(T)// 单个数据插入如果已经存在则插入失败pairiterator,boolinsert(constvalue_typeval);// 列表插入已经在容器中存在的值不会插入voidinsert(initializer_listvalue_typeil);// 迭代器区间插入已经在容器中存在的值不会插入templateclassInputIteratorvoidinsert(InputIterator first,InputIterator last);// 查找val返回val所在的迭代器没有找到返回end()iteratorfind(constvalue_typeval);// 查找val返回Val的个数size_typecount(constvalue_typeval)const;// 删除一个迭代器位置的值iteratorerase(const_iterator position);// 删除valval不存在返回0存在返回1size_typeerase(constvalue_typeval);// 删除一段迭代器区间的值iteratorerase(const_iterator first,const_iterator last);// 返回大于等val位置的迭代器iteratorlower_bound(constvalue_typeval)const;// 返回大于val位置的迭代器iteratorupper_bound(constvalue_typeval)const;2.5 insert和迭代器遍历使用样例#includeiostream#includesetusingnamespacestd;intmain(){// 去重升序排序setints;// 去重降序排序给一个大于的仿函数//setint, greaterint s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//setint::iterator it s.begin();autoits.begin();while(it!s.end()){// error C3892: “it”: 不能给常量赋值// *it 1;cout*it ;it;}coutendl;// 插入一段initializer_list列表值已经存在的值插入失败s.insert({2,8,3,9});for(autoe:s){coute ;}coutendl;setstringstrset{sort,insert,add};// 遍历string比较ascll码大小顺序遍历的for(autoe:strset){coute ;}coutendl;}2.6 find和erase使用样例#includeiostream#includesetusingnamespacestd;intmain(){setints{4,2,7,2,8,5,9};for(autoe:s){coute ;}coutendl;// 删除最小值s.erase(s.begin());for(autoe:s){coute ;}coutendl;// 直接删除xintx;cinx;intnums.erase(x);if(num0){coutx不存在endl;}for(autoe:s){coute ;}coutendl;// 直接查找在利用迭代器删除xcinx;autoposs.find(x);if(pos!s.end()){s.erase(pos);}else{coutx不存在endl;}for(autoe:s){coute ;}coutendl;// 算法库的查找 O(N)autopos1find(s.begin(),s.end(),x);// set自身实现的查找 O(logN)autopos2s.find(x);// 利用count间接实现快速查找cinx;if(s.count(x)){coutx在endl;}else{coutx不存在endl;}return0;}#includeiostream#includesetusingnamespacestd;intmain(){std::setintmyset;for(inti1;i10;i)myset.insert(i*10);// 10 20 30 40 50 60 70 80 90for(autoe:myset){coute ;}coutendl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 30autoitlowmyset.lower_bound(30);// 返回 60autoitupmyset.upper_bound(60);// 删除这段区间的值myset.erase(itlow,itup);for(autoe:myset){coute ;}coutendl;return0;}2.7 multiset和set的差异multiset和set的使用基本完全类似主要区别点在于multiset支持值冗余那么insert/find/count/erase都围绕着支持值冗余有所差异具体参看下面的样例代码理解。#includeiostream#includesetusingnamespacestd;intmain(){// 相比set不同的是multiset是排序但是不去重multisetints{4,2,7,2,4,8,4,5,4,9};autoits.begin();while(it!s.end()){cout*it ;it;}coutendl;// 相比set不同的是x可能会存在多个find查找中序的第一个intx;cinx;autoposs.find(x);while(pos!s.end()*posx){cout*pos ;pos;}coutendl;// 相比set不同的是count会返回x的实际个数couts.count(x)endl;// 相比set不同的是erase给值时会删除所有的xs.erase(x);for(autoe:s){coute ;}coutendl;return0;}multset查找多个key返回第一个find(3)思路找到第一个key再去key左子树找key直到左子树找不到key那个结点迭代器才是中序第一个删除删除所有的key2.8 349.两个数组的交集 - 力扣LeetCodeclassSolution{public:vectorintintersection(vectorintnums1,vectorintnums2){setints1(nums1.begin(),nums1.end());setints2(nums2.begin(),nums2.end());// 因为set遍历是有序的有序值依次比较// 小的相等的就是交集vectorintret;autoit1s1.begin();autoit2s2.begin();while(it1!s1.end()it2!s2.end()){if(*it1*it2){it1;}elseif(*it1*it2){it2;}else{ret.push_back(*it1);it1;it2;}}returnret;}};2.9 142.环形链表 II - 力扣LeetCode数据结构初阶阶段我们通过证明一个指针从头开始走一个指针从相遇点开始走会在入口点相遇理解证明都会很麻烦。这里我们使用set查找记录解决非常简单方便这里体现了set在解决一些问题时的价值完全是降维打击。classSolution{public:ListNode*detectCycle(ListNode*head){setListNode*s;ListNode*curhead;while(cur){autorets.insert(cur);if(ret.secondfalse)returncur;curcur-next;}returnnullptr;}};