✨✨小新课堂开课了，欢迎欢迎~✨✨
??养成好习惯，先赞后看哦~??
所属专栏：C++：由浅入深篇
小新的主页：编程版小新-CSDN博客
前言：
本章节讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。但是今天我们不谈底层，红黑树会是单独一篇博客。
set是key搜索场景的结构， map是key/value搜索场景的结构。这个我们在介绍二叉搜索树的时候已经提过了key以及key/value的使用，有需要可以回顾一下哦。
C++深入探寻二叉搜索树：数据管理的智慧之选-CSDN博客
一.序列式容器和关联式容器
1.1序列式容器
序列式容器是一种线性的数据结构，其中的元素按照它们被插入的顺序进行存储。可以将序列式容器看作是一个动态数组或链表，其中的元素可以通过迭代器进行遍历。
前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器。
因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
1.2关联式容器
关联式容器是一种基于键值对的数据结构，其中的元素是按照一定的规则进行存储的，通常是根据键的大小进行排序。可以将关联式容器看作是一个字典或映射，其中的键用于唯一标识每个元素，而值则存储与键相关的数据。
与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系（set和map的底层是平衡二叉搜索树，拿我们前面讲的普通的二叉搜索树举例，父节点有左孩子和右孩子，父节点和孩子节点的位置是不能交换的，左右孩子的位置也是不能交换的），交换一下，他的存储结构就被破坏了。关联式容器有map/set系列和unordered_map/unordered_set系列。
1.3键值对
键值对是一种具有一一对应关系的数据结构，它由一个键（key）和一个与之对应的值（value）组成。
比如我们若是要建立一个英汉互译的字典，那么该字典中的英文单词与其对应的中文含义就是一一对应的关系，即通过单词可以找到与其对应的中文含义。
下面是对键值对的定义：
typedef pair<const Key, T> value_type;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){}};总结：
序列式容器里面存储的是元素本身，其底层为线性序列的数据结构。比如：vector，list，deque，forward_list等。
关联式容器里面存储的是<key, value>结构的键值对，其底层是非线性的数据结构，在数据检索时比序列式容器效率更高。比如：set、map、unordered_set、unordered_map等。
二.set系列的使用
2.1set的介绍
set有三个参数。
1. set的声明如下，T就是set底层关键字的类型。（将T理解成key即可，key类型，记住这一点哦）
2.set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数。
3.set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
4.一般情况下，我们都不需要传后两个模版参数。
5. set底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。
6.set当中存储的元素是唯一的，不可以重复，因此可以使用set进行去重。
7.set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树的结构就会被破坏。
8.set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序
2.2set的构造
我们介绍几种主要的构造方式。
// 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_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());方式一：无参的默认构造
set<int>s1;//构造一个某类型的空容器方式二：迭代器区间构造
string str("abcde");set<char> s2(str.begin(), str.end());//使用迭代器构造某一段内容方式三：拷贝构造
set<char>s3(s2);//拷贝构造某类型set容器的复制品方式四：initializer 列表构造
set<string> strset = { "sort", "insert", "add" };//列表构造2.3set的迭代器
迭代器的用法和我们之前讲过的其他容器的迭代器的用法一样，这里就不做介绍了。不带c的是普通的迭代器，c开头的返回的是常量迭代器，只能用于读取容器元素，不支持修改。set的迭代器中包含rebegin和rend，说明set支持双向迭代器，我们之前学过的list也是支持双向迭代器的。
2.4set的插入
我们介绍几种常见的插入方式。
// 单个数据插⼊，如果已经存在则插⼊失败pair<iterator, bool> insert(const value_type& val);// value_type就是Tvoid insert(initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊template <class InputIterator>void insert(InputIterator first, InputIterator last);//列表插入void insert(initializer_list<value_type> il);方式一：单个数据插入
//插入单个元素,已经存在的值插入失败set<int> s1;s1.insert(8);s1.insert(3);s1.insert(1);方式二：迭代器区间插入
//使用迭代器区间插入，已经存在的值插入失败set<char> s2;string str("bacde");s2.insert(str.begin(), str.end());方式三：一段initializer_list列表值插入
// 插⼊⼀段initializer_list列表值，已经存在的值插入失败set<int> s3;s3.insert({ 2,8,3,9 });2.5set的查找
// 查找val，返回val所在的迭代器，没有找到返回end()iterator find(const value_type& val);// 查找val，返回val的个数size_type count(const value_type& val) const;用法如下：
int main(){ set<int> s1;s1.insert(8);s1.insert(3);s1.insert(1);auto pos = s1.find(1);if (pos != s1.end()){cout << "存在" << endl;} else{ cout << "不存在！" << endl;}cout << s1.count(1) << endl;//1cout << s1.count(10) << endl;//0return 0;}2.6set的删除
// 删除一个迭代器位置的值iterator erase(const_iterator position);// 删除val，val不存在返回0，存在返回1size_type erase(const value_type& val);// 删除一段迭代器区间的值iterator erase(const_iterator first, const_iterator last);用法如下：
int main(){ set<int> s = { 4,2,7,2,8,5,9 };for (auto e : s){cout << e << " ";} cout << endl;// 删除最⼩值s.erase(s.begin());//删除一个迭代器位置的值for (auto e : s){cout << e << " ";}cout << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);//删除val，不存在返回0，存在返回1if (num == 0){cout << x << "不存在！" << endl;} for (auto e : s){cout << e << " ";}cout << endl;s.erase(s.begin(), s. end());//删除一段迭代器区间的值for (auto e : s){cout << e << " ";}cout << endl;return 0;}2.7lower_bound和upper_bound
// 返回大于等于val位置的迭代器iterator lower_bound(const value_type & val) const;// 返回大于val位置的迭代器iterator upper_bound(const value_type& val) const;用法如下：
int main(){std::set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout << e << " ";}cout << endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 >= 30auto itlow = myset.lower_bound(30);//在这个示例里，返回30位置的迭代器，因为刚好有30存在// 返回 > 60auto itup = myset.upper_bound(60);//返回70 位置的迭代器// 删除这段区间的值myset.erase(itlow, itup);//区间都是左闭右开for (auto e : myset){cout << e << " ";}cout << endl;return 0;}运行结果;
2.8set的参考文档及其详细用法
我们并没有将set的所有的接口都详细说明，这些大多数接口我们在前面的学习都详细介绍过，这是只是提了几个set的重要接口，下面我们用一段代码，将这我们没有提到的并且比较常见接口的功能再回忆一下。
int main(){set<int> s;//插入元素（去重）s.insert(4);s.insert(2);s.insert(7);s.insert(2);s.insert(8);s.insert(5);s.insert(9);for (auto e : s){cout << e << " ";//2 4 5 7 8 9}cout << endl; s.erase(8);//删除单个元素set<int>::iterator pos = s.find(1); //查找值为1的元素，查找val，返回val所在的迭代器，没有找到返回end()if (pos != s.end()){s.erase(pos);}//正向迭代器set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";//2 4 5 7 9it++;}cout << endl; //容器中值为2的元素个数cout << s.count(2) << endl; //1//容器大小cout << s.size() << endl; //5//清空容器s.clear();//容器判空cout << s.empty() << endl; //1//交换两个容器的数据set<int> tmp = { 8,3,5,1};s.swap(tmp);//反向迭代器set<int>::reverse_iterator rit = s.rbegin();while (rit != s.rend()){cout << *rit << " ";//8 5 3 1rit++;}cout << endl; return 0;}2.9multiset 和 set的区别
multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余（支持插入相同的值），那么insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
支持值冗余：
insert：支持插入相同的值
find：若要查找的值存在多个，返回中序的第一个
count：一个值可能存在多个，就不止返回0/1这两种可能了
erase：删除时，若给定值存在，则全部删除
int main(){// 相比set不同的是，multiset是排序，但是不去重（支持值冗余）multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;} cout << endl;// 相比set不同的是，x可能会存在多个，find查找中序的第⼀个int x;cin >> x;//4auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;}cout << endl;// 相比set不同的是，count会返回x的实际个数cout << s.count(x) << endl;// 相⽐set不同的是，erase给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";} cout << endl;return 0;}运行结果：
三.map系列的使用
3.1map的介绍
map有四个参数。
1. map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型。（将Key理解成key，T理解成val即可，key/value类型，记住这一点哦）
2.set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数
3.set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
4.一般情况下，我们都不需要传后两个模版参数。
5. map底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序，所以是有序的。
6.map是关联式容器，它按照特定的次序（按照key来比较）存储键值key和值value组成的元素，使用map的迭代器遍历map中的元素，可以得到有序序列。
7.在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，并取别名为pair。
8.map容器中元素的键值key不能被修改，但是元素的值value可以被修改，因为map底层的二叉搜索树是根据每个元素的键值key进行构建的，而不是值value。
9.map容器支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
3.2map的构造
// empty (1) ⽆参默认构造explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造template <class InputIterator>map(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type & = allocator_type());// copy (3) 拷⻉构造map(const map& x);// initializer list (5) initializer 列表构造map(initializer_list<value_type> il, const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());方式一：无参的默认构造
//构造一个key为int类型，value为string类型的空容器map<int, string> m1;方式二：迭代器区间构造
map<int, string> m2 = { {1,"one"},{2,"two"},{3,"three"} };map<int, string> m3(m2.begin(), m2.end());//使用迭代器构造m2容器某段区间的复制品方式三：拷贝构造
//拷贝构造map<int, string> m4(m3);//拷贝构造key为int类型，value为string类型的m4容器的复制品方式四：initializer 列表构造
// initializer 列表构造map<string, string> m5 = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };3.3map的迭代器
map迭代器的用法和之前其他容器的迭代器的用法也是相似的，和list，set一样，map也支持双向迭代器。
3.4map的插入
我们来介绍几种常见的插入方式。
Member typeskey_type->The first template parameter(Key)mapped_type->The second template parameter(T)value_type->pair<const key_type, mapped_type>// 单个数据插⼊，如果已经key存在则插⼊失败,key相等value不相等也会插⼊失败pair<iterator, bool> insert(const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊void insert(initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊template <class InputIterator>void insert(InputIterator first, InputIterator last);方式一：单个数据插入
//Member types //key_type->The first template parameter(Key) //mapped_type->The second template parameter(T) //value_type->pair<const key_type, mapped_type>// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败//pair<iterator, bool> insert(const value_type& val);//单个数据插入map<int, string> m1;m1.insert(pair<int, string>(1, "one"));m1.insert(pair<int, string>(2, "two"));m1.insert(pair<int, string>(3, "three"));方式二：一段initializer_list列表值插入
//一段initializer_list列表值插入map<int, string> m2 = { {1,"one"},{2,"two"},{3,"three"} };方式三：迭代器区间插入
//使用迭代器区间插入map<int, string> m3(m2.begin(), m2.end());补充+总结：
make_pair的函数模版：
template <class T1, class T2>pair<T1, T2> make_pair(T1 x, T2 y){return (pair<T1, T2>(x, y));}// insert插⼊pair对象的4种方式，对比之下，最后一种最方便map<string, string> m1;pair<string, string> kv1("first", "第⼀个");//1.m1.insert(kv1);//2.m1.insert(pair<string, string>("second", "第⼆个"));//3.m1.insert(make_pair("sort", "排序"));//4.m1.insert({ "auto", "⾃动的" });insert插入一个pair<key, T>对象
1、如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，返回pair对象
first是key所在结点的迭代器，second是false。
2、如果key不在在map中，插入成功，则返回一个pair<iterator,bool>对象，返回pair对象first是新插⼊key所在结点的迭代器，second是true。
也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器，那么也就意味着insert插入失败时充当了查找的功能，正是因为这⼀点，insert可以用来实现operator[]。这个我们后面会说。
需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair<key, T>，另一个是insert返回值pair<iterator,bool>
3.5map的查找
map的查找和set的查找是一样，查找都是key，因为map也不支持插入相同的key，count的返回值也只存在1/0两种情况。
// 查找k，返回k所在的迭代器，没有找到返回end()iterator find(const key_type& k);// 查找k，返回k的个数size_type count(const key_type& k) const;用法如下：
int main(){map<int, string> m1 = { {1,"one"},{2,"two"},{3,"three"} };auto it = m1.find(1);if (it != m1.end()){cout << "存在" << endl;}else{cout << "不存在" << endl;}cout << m1.count(5) << endl;//0cout << m1.count(2) << endl;//1return 0;}3.6map的删除
// 删除⼀个迭代器位置的值iterator erase(const_iterator position);// 删除k，k存在返回0，存在返回1size_type erase(const key_type& k);// 删除⼀段迭代器区间的值iterator erase(const_iterator first, const_iterator last);用法如下：
int main(){map<int, string>m1 = { {1, "one"}, {2, "two"}, {3, "three"} ,{4,"four"},{5,"five"} };for (const auto& pair : m1){cout << pair.first << ": " << pair.second << " ";//first就是key，second就是value}cout << endl;m1.erase(m1.begin());//删除一个迭代器位置的数据for (const auto& pair : m1){cout << pair.first << ": " << pair.second <<" ";}cout << endl;// 直接删除xint x;cin >> x;size_t num = m1.erase(x);//删除val，不存在返回0，存在返回1if (num == 0){cout << x << "不存在！" << endl;}for (const auto& pair : m1){cout << pair.first << ": " << pair.second << " ";}cout << endl;m1.erase(m1.begin(), m1.end());//删除一段迭代器区间的值for (const auto& pair : m1){cout << pair.first << ": " << pair.second << " ";}cout << endl;return 0;}3.7map的修改（operator[]）
前面在map的介绍里我们也提到了map支持修改mapped_type （value）数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是⼀个多功能复合接口。
前面我们在map的插入部分，提到insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[]。
我们来看一下operator[]的底层实现。
// operator的内部实现mapped_type& operator[] (const key_type& k){// 1、如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储//mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能// 2、如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的//迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;}用法如下：
示例一：
int main(){// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠","苹果", "⾹蕉", "苹果", "⾹蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找找果在不在map中// 1、不在，说明水果第⼀次出现，则插入{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了// 2、在，则返回水果对应的次数++countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;}示例二：
int main(){map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插⼊ {"insert", string()}dict["insert"];// 插⼊+修改dict["left"] = "左边";// 修改dict["left"] = "左边、剩余";// key存在->查找cout << dict["left"] << endl;// "左边、剩余" ,因为operator[]的返回值是mapped_type(value)return 0;}3.8lower_bound和upper_bound
// 返回⼤于等于k位置的迭代器iterator lower_bound (const key_type& k);// 返回⼤于k位置的迭代器const_iterator lower_bound (const key_type& k) const;用法如下：
int main() {map<int, string> myMap = { {1, "one"}, {3, "three"}, {5, "five"}, {7, "seven"} };for (auto e : myMap){cout << e.first << " -> " << e.second << endl;}cout << endl;//返回>=3auto itlow = myMap.lower_bound(3);//在这个示例里，返回3位置的迭代器//返回>5auto itupper = myMap.upper_bound(5);//在这个示例里，返回7位置的迭代器//删除这段区间的值myMap.erase(itlow, itupper);//区间都是左闭右开for (auto e : myMap){cout << e.first << " -> " << e.second << endl;}cout << endl;return 0;}运行结果：
3.9map的参考文档及其详细用法
我们也没有将map的所有的接口都详细说明，这些大多数接口我们在前面的学习都详细介绍过，这是只是提了几个map的重要接口，下面我们用一段代码，将这我们没有提到的并且比较常见接口的功能再回忆一下。
int main(){map<int, string> m;//去重m.insert(make_pair(2, "two"));m.insert(make_pair(1, "one"));m.insert(make_pair(3, "three"));m.insert(make_pair(3, "three"));m.insert(make_pair(5, "five"));m.insert(make_pair(8, "eight"));for (auto e :m){cout << e.first << " -> " << e.second << endl;}cout << endl;m.erase(1);//删除//正向迭代器map<int,string>::iterator it = m.begin();while (it != m.end()){cout << it->first << " -> "<<it->second<< endl;it++;}cout << endl;map<int,string>::iterator pos = m.find(1); //查找值为1的元素，查找val，返回val所在的迭代器，没有找到返回end()if (pos != m.end()){m.erase(pos);}//获取容器中元素的个数cout << m.size() << endl; //4//容器中key值为3的元素个数cout << m.count(3) << endl; //1//清空容器m.clear();//容器判空cout << m.empty() << endl; //1cout << endl;//交换两个容器中的数据map<int, string> tmp = { {1, "one"}, {2, "two"}, {3, "three"} ,{4,"four"},{5,"five"} };m.swap(tmp);//反向迭代器map<int,string>::reverse_iterator rit = m.rbegin();while (rit != m.rend()){cout << rit->first <<" -> " << rit->second << endl;rit++;}cout << endl;return 0;}运行结果：
3.10multimap和map的区别
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持operator[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。
支持值冗余：
insert：支持插入相同的值
find：若要查找的值存在多个，返回中序的第一个
count：一个值可能存在多个，就不止返回0/1这两种可能了
erase：删除时，若给定值存在，则全部删除
operator[]: multimap不支持operator[]
int main(){// 相比map不同的是，multimap是排序，但是不去重（支持值冗余）multimap<int, string> m;m.insert(make_pair(2, "two"));m.insert(make_pair(1, "one"));m.insert(make_pair(3, "three"));m.insert(make_pair(3, "three"));m.insert(make_pair(5, "five"));m.insert(make_pair(8, "eight"));auto it = m.begin();while (it != m.end()){cout << it->first << " -> " << it->second << endl;++it;}cout << endl;// 相比map不同的是，x可能会存在多个，find查找中序的第⼀个int x;cin >> x;//3auto pos = m.find(x);while (pos != m.end() && pos->first== x){cout << pos->first << " ";++pos;}cout << endl;// 相比map不同的是，count会返回x的实际个数cout << m.count(x) << endl;// 相⽐map不同的是，erase给值时会删除所有的xm.erase(x);for (auto e : m){cout << e.first << " -> " << e.second << endl;}cout << endl;return 0;}运行结果：
总结：
我们简单的学习了set/multiset,map/multimap的用法，并没有没有涉及底层，后面我们会先介绍AVL树，AVL树和红黑树一样，也是一颗平衡二叉搜索树，在AVL的篇章中，我们会介绍如何使得树保持平衡，在这些的基础上再学习红黑树就会好许多，大家快来一起进步吧。
感谢各位大佬的观看，创作不易，还请各位大佬点赞支持~