map和set的
序列式容器和关联式容器
前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本博客讲解的map和set底层是红黑树，红黑树是⼀颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。
set系列的使用
set类的介绍：
set的声明如下，T就是set底层关键字的类型
• set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数
• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• set底层是用红黑树实现，增删查效率是 ，迭代器遍历是走的搜索树的中序，所以是有序的。
set参考文档：点击查看
我们已经学习了vector/list等容器的使用，STL容器接口设计，高度相似，所以这里我就不再一个接口一个接口的介绍，而是直接带着大家看文档，挑比较重要的接口进行介绍
底层是这样的：
template<classT,// set::key_type/value_typeclassCompare=less<T>,// set::key_compare/value_compareclassAlloc=allocator<T>// set::allocator_type>classset;set的构造和迭代器
set的构造我们关注以下几个接口即可。
set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
文档：
// empty (1) ⽆参默认构造explicitset(constkey_compare&comp=key_compare(),constallocator_type&alloc=allocator_type());// range (2) 迭代器区间构造template<classInputIterator>set(InputIterator first,InputIterator last,constkey_compare&comp=key_compare(),constallocator_type&=allocator_type());// copy (3) 拷⻉构造set(constset&x);// initializer list (5) initializer 列表构造set(initializer_list<value_type>il,constkey_compare&comp=key_compare(),constallocator_type&alloc=allocator_type());// 迭代器是⼀个双向迭代器iterator->a bidirectional iterator toconstvalue_type// 正向迭代器iteratorbegin();iteratorend();// 反向迭代器reverse_iteratorrbegin();reverse_iteratorrend();语法：
#include<iostream>#include<set>#include<vector>usingnamespacestd;intmain(){// 1. 无参默认构造 set()set<int>st1;cout<<"1. 默认构造空set，大小："<<st1.size()<<endl;st1.insert(5);st1.insert(2);st1.insert(8);cout<<"插入元素后st1：";// 正向迭代器 begin() end()for(set<int>::iterator it=st1.begin();it!=st1.end();++it){cout<<*it<<" ";}cout<<"\n";// 2. 迭代器区间构造：接收任意输入迭代器区间vector<int>vec={3,1,4,1,5};set<int>st2(vec.begin(),vec.end());cout<<"2. 迭代器区间构造st2（自动去重有序）：";for(autoit=st2.begin();it!=st2.end();++it){cout<<*it<<" ";}cout<<"\n";// 3. 拷贝构造：用已有set复制新setset<int>st3(st1);cout<<"3. 拷贝构造st3（复制st1）：";for(autoit=st3.begin();it!=st3.end();++it){cout<<*it<<" ";}cout<<"\n";// 4. initializer_list 列表构造set<int>st4{9,2,7,2,1};cout<<"4. initializer_list构造st4：";for(autoval:st4)// 范围for底层也是正向迭代器{cout<<val<<" ";}cout<<"\n";// ========== 反向迭代器 rbegin() rend() ==========cout<<"\n反向迭代器遍历st1（从大到小）：";for(set<int>::reverse_iterator rit=st1.rbegin();rit!=st1.rend();++rit){cout<<*rit<<" ";}cout<<"\n";return0;}set的增删查
文档：
Member types key_type->The firsttemplateparameter(T)value_type->The firsttemplateparameter(T)// 单个数据插⼊，如果已经存在则插⼊失败pair<iterator,bool>insert(constvalue_type&val);// 列表插⼊，已经在容器中存在的值不会插⼊voidinsert(initializer_list<value_type>il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊template<classInputIterator>voidinsert(InputIterator first,InputIterator last);// 查找val，返回val所在的迭代器，没有找到返回end()iteratorfind(constvalue_type&val);// 查找val，返回Val的个数size_typecount(constvalue_type&val)const;// 删除⼀个迭代器位置的值iteratorerase(const_iterator position);// 删除val，val不存在返回0，存在返回1size_typeerase(constvalue_type&val);// 删除⼀段迭代器区间的值iteratorerase(const_iterator first,const_iterator last);// 返回⼤于等val位置的迭代器iteratorlower_bound(constvalue_type&val)const;// 返回⼤于val位置的迭代器iteratorupper_bound(constvalue_type&val)const;案例：
#include<iostream>#include<set>#include<vector>usingnamespacestd;intmain(){// ---------------------- 1. Member types 成员类型说明 ----------------------set<int>::key_type k;// key_type = int，set的键类型set<int>::value_type v;// value_type = int，set存储的值类型k=10;v=20;cout<<"key_type变量："<<k<<" | value_type变量："<<v<<"\n\n";// ---------------------- 2. 三种insert插入接口演示 ----------------------set<int>st;// ① 单个值插入：pair<iterator, bool> insert(val)autoret1=st.insert(5);cout<<"插入5：迭代器值="<<*ret1.first<<"，是否插入成功="<<ret1.second<<"\n";autoret2=st.insert(5);// 重复元素，插入失败cout<<"再次插入5：迭代器值="<<*ret2.first<<"，是否插入成功="<<ret2.second<<"\n";// ② initializer_list 列表插入st.insert({2,8,2,1});cout<<"列表插入{2,8,2,1}后集合：";for(autox:st)cout<<x<<" ";cout<<"\n";// ③ 迭代器区间插入vector<int>vec={7,3,9,3};st.insert(vec.begin(),vec.end());cout<<"区间插入vector{7,3,9,3}后集合：";for(autox:st)cout<<x<<" ";cout<<"\n\n";// ---------------------- 3. find / count 查找接口 ----------------------// find：找到返回对应迭代器，找不到返回end()autoitFind=st.find(8);if(itFind!=st.end())cout<<"find(8) 找到，值："<<*itFind<<"\n";elsecout<<"find(8) 未找到\n";autoitNull=st.find(100);if(itNull==st.end())cout<<"find(100) 未找到\n";// count：set元素唯一，存在返回1，不存在返回0cout<<"count(3) = "<<st.count(3)<<"\n";cout<<"count(99) = "<<st.count(99)<<"\n\n";// ---------------------- 4. 三种erase删除接口 ----------------------set<int>stDel={1,2,3,5,7,8,9};// ① 删除指定迭代器位置autopos=stDel.find(5);stDel.erase(pos);cout<<"erase(迭代器5)后：";for(autox:stDel)cout<<x<<" ";cout<<"\n";// ② 删除指定值，返回删除个数（0/1）size_t delNum=stDel.erase(2);cout<<"erase(2) 删除数量："<<delNum<<"\n";size_t delNull=stDel.erase(100);cout<<"erase(100) 删除数量："<<delNull<<"\n";cout<<"删除2后集合：";for(autox:stDel)cout<<x<<" ";cout<<"\n";// ③ 删除迭代器区间 [first, last)autoleft=stDel.find(7);autoright=stDel.end();stDel.erase(left,right);cout<<"erase(7到末尾区间)后：";for(autox:stDel)cout<<x<<" ";cout<<"\n\n";// ---------------------- 5. lower_bound / upper_bound 边界查找 ----------------------set<int>stBound={1,3,5,7,9};inttarget=4;// lower_bound(val)：第一个 >= val 的元素迭代器autolow=stBound.lower_bound(target);cout<<"lower_bound("<<target<<") 第一个>=4的值："<<*low<<"\n";// upper_bound(val)：第一个 > val 的元素迭代器autoup=stBound.upper_bound(target);cout<<"upper_bound("<<target<<") 第一个>4的值："<<*up<<"\n";// 测试等于的情况 target=5autolow5=stBound.lower_bound(5);autoup5=stBound.upper_bound(5);cout<<"\ntarget=5：\n";cout<<"lower_bound(5) = "<<*low5<<"\n";cout<<"upper_bound(5) = "<<*up5<<"\n";return0;}insert和迭代器遍历使用样例
#include<iostream>#include<set>usingnamespacestd;intmain(){// 去重+升序排序set<int>s;// 去重+降序排序（给⼀个⼤于的仿函数）//set<int, greater<int>> s;s.insert(1);s.insert(2);s.insert(9);s.insert(5);//set<int>::iterator it = s.begin();autoit=s.begin();while(it!=s.end()){// error C3892: “it”: 不能给常量赋值// *it = 1;cout<<*it<<" ";++it;}cout<<endl;// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败s.insert({2,9,6,0});for(autoe:s){cout<<e<<" ";}cout<<endl;set<string>strset={"sort","insert","add"};// 遍历string⽐较ascll码⼤⼩顺序遍历的for(auto&e:strset){cout<<e<<" ";}cout<<endl;}find和erase使用样例：
#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s={4,2,7,2,8,5,9};for(autoe:s){cout<<e<<" ";}cout<<endl;// 删除最⼩值s.erase(s.begin());for(autoe:s){cout<<e<<" ";}cout<<endl;// 直接删除xintx;cin>>x;intnum=s.erase(x);if(num==0){cout<<x<<"不存在！"<<endl;}for(autoe:s){cout<<e<<" ";}cout<<endl;// 直接查找在利⽤迭代器删除xcin>>x;autopos=s.find(x);if(pos!=s.end()){s.erase(pos);}else{cout<<x<<"不存在！"<<endl;}for(autoe:s){cout<<e<<" ";}cout<<endl;// 算法库的查找 O(N)autopos1=find(s.begin(),s.end(),x);// set⾃⾝实现的查找 O(logN)autopos2=s.find(x);// 利⽤count间接实现快速查找cin>>x;if(s.count(x)){cout<<x<<"在！"<<endl;}else{cout<<x<<"不存在！"<<endl;}return0;}#include<iostream>#include<set>usingnamespacestd;intmain(){std::set<int>myset;for(inti=1;i<10;i++)myset.insert(i*10);// 10 20 30 40 50 60 70 80 90for(autoe:myset){cout<<e<<" ";}cout<<endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 >= 30autoitlow=myset.lower_bound(30);// 返回 > 60autoitup=myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow,itup);for(autoe:myset){cout<<e<<" ";}cout<<endl;return0;}
