Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》
欢迎点赞，关注！
这一期我们来讲讲map和set的使用，之后的红黑树模拟实现以及map和set的封装做铺垫
1、引言
在C++标准模板库(STL)中，map和set是两种非常重要的关联容器，它们基于红黑树实现，提供了高效的查找、插入和删除操作。
关联容器是C++标准模板库(STL)中的一类重要容器，它们与序列容器(如vector、list等)不同，不是通过位置来存储和访问元素，而是通过键(key)来高效地组织和管理数据。
关联式容器逻辑结构通常是非线性结构， 两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。这类容器查找效率一般都很高，可以达O(logN)或以上。本期的set和map都是关联容器，我们通过键值key来排序，访问内容。其中set存储的是单独的键值，而map存储的是键值对。键值和键值对就分别对应我们之前提到的key和key_value。
2、set系列的使用
之所以叫set系列，是因为这部分包含set和multiset两个容器，他们的不同是set允许重复值，而multiset不支持重复值。在学习之前，我们可以把set理解为可以自动排序的容器，对于容器内的值，我们使用迭代器遍历它总是成升序的。
2.1、set的主要特性
唯一性：set中的元素都是唯一的，不允许重复
自动排序：元素插入后会自动排序
不可修改元素：set中的元素是const的，不能直接修改
高效的查找操作：基于红黑树实现，查找时间复杂度为O(log n)
2.2、 set容器的插入
我们包一下set的头文件，然后新建一个set容器，接着在set容器中插入三个元素：
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(10);
s.insert(15);
s.insert(20);
return 0;
}当然set在C++11之后支持范围插入和初始化列表了：
vector<int> vec = {2, 4, 6, 8};
set<int> mySet;
mySet.insert(vec.begin(), vec.end());//范围插入
set<int> s={1,2,3,4};//初始化列表尖括号里是我们想要存储的值的类型，对于这个值类型，他必须支持<的比较。基础的编译器自带的int,char,double等类型以及常用的string类型编译器都支持<比较。但是对于我们自定义类型，必须自己实现仿函数对他进行比较。
#include<iostream>
#include<set>
using namespace std;
struct node
{
node(int a,int b)
:x(a)
,y(b)
{}
int x;
int y;
};
template<class node>
struct A
{
bool operator()(node a, node b) const
{
return a.y< b.y;
}
};
int main()
{
set<pair<int,int>> s;
s.insert({ 4,2 });
s.insert({ 2,2 });
s.insert({ 3,2 });
s.insert({ 5,6 });
s.insert({ 6,8 });
s.insert({ 7,9 });
for (auto e : s)
{
cout << e.first << " ";
}
cout << endl;
set<node,A<node>> s1;
s1.insert({1,2});
s1.insert({ 1,1 });
s1.insert({ 1,6 });
s1.insert({ 1,4 });
s1.insert({ 1,3 });
for (auto e : s1)
{
cout << e.y << " ";
}
return 0;
}pair类型自带的有<类型比较，pair类型的比较是按照字典序来的，首先按照first的值进行排序，如果first的值相等再按照second的值进行比较。上面的代码我们就支持了自定义类型的比较。
把仿函数里面的<改成>他就变成升序了。
输出结果：
2.3、set的删除
我们使用一下删除接口：
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(6);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
s.erase(2);
s.erase(s.begin());//删除接口支持迭代器
for (auto e : s)
{
cout << e << " ";
}
return 0;
}
输出结果：
2.4、set的查找
set的查找返回的是迭代器：
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(6);
auto it = s.find(5);
cout << *it << endl;
return 0;
}
2.5、遍历set
set支持迭代器遍历和范围for遍历。
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(6);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
return 0;
}
到目前位置我们应该可以感受到set使用这一块很“无聊”。和之前的容器在使用上区别不大。
接下来我们看个稍微有那么一点点意思的代码：
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(6);
for (auto e : s)
{
e += 1;
cout << e << " ";
}
cout << endl;
auto it = s.begin();
while (it != s.end())
{
*it += 1;
cout << *it << " ";
it++;
}
return 0;
}
首先告诉大家这串代码会编译报错，*it+=1会编译报错，因为我们之前说过set里面的值不支持更改。我们迭代器返回的是const迭代器，所以说不支持更改值。 但问题是为什么范围for中e可以+=1，并且打印结果确实达到我们的目的了呢？
不卖关子了直接告诉大家，其实这也很无聊没什么意思，就是我们范围for写的是auto e:s,那么对于这个e其实是拷贝了set中的每一个值，然后我们再对这个拷贝下来的值进行+=1.看似更改了set中的值，实际上set中的值并没有改变。
2.6、set的容量查询
这个和之前容器也没什么区别。
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(6);
cout<<s.empty()<<endl;//0
cout << s.size() << endl;//6
return 0;
}
3、multiset
首先说明，multiset和set在同一个头文件中，所以我们不需要包其他的头文件。multiset和set主要的区别就是multiset支持重复元素：
#include<iostream>
#include<set>
using namespace std;
int main()
{
multiset<int> s;
s.insert(1);
s.insert(2);
s.insert(2);//重复元素
s.insert(3);
s.insert(4);
s.insert(4);
s.insert(5);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}
输出结果：
那么基于set不支持重复元素的特性，我们经常使用set进行去重的操作。当然去重也可以用算法库的unique，但是我个人感觉不如set用着顺手。
除此之外还有一些区别：
3.1、insert返回值不同
set的insert返回值为pair<iterator,bool>,如果一个元素已经存在了就会插入失败，返回已经存在的元素的迭代器和false。
而由于multiset允许重复元素的特性，他不会插入失败，他一直会返回新插入元素位置的迭代器。
auto it = ms.insert(2); // 总是成功3.2、count和find不同
在set中，count只能返回0或1，find返回查找元素位置的迭代器，如果没有该元素返回end()，而multiset中count可能是任意非负整数，而find返回的是正向遍历第一次出现的位置的迭代器。
set<int> s = {1,2,3};
cout << s.count(2); // 输出1
multiset<int> ms = {1,2,2,3};
cout << ms.count(2); // 输出23.3、erase不同
multiset一次性会删除所有符合元素，而set只会删除一个元素（如果存在）。如果存在该元素返回true,如果不存在该元素（删除失败）返回false。
4、map
map是一种关联容器，存储键值对(key-value pairs)，其中键是唯一的，且元素按照键的顺序进行排序。
4.1、map的主要特性
键值对存储：每个元素都是一个pair<const Key, T>
键的唯一性：每个键只能在map中出现一次
自动排序：元素按键的顺序自动排序
高效的查找操作：基于红黑树实现，查找时间复杂度为O(log n)
4.2、map的基本操作
4.2.1、map的插入
首先由于map插入的时候需要插入两个值，key和value，所以说有很多种插入方式，我来介绍一下主流的几个插入方法：
map<string, int> mp;
mp.insert(pair<string,int>("apple",5));//临时对象插入法
mp.insert({ "pear",4 });//C++11花括号插入法
mp.emplace("orange", 6);//C++11emplace直接构建，避免构建临时对象
mp["banana"] = 6;//下标访问插入，后面会详细介绍
除了这四个以外，我们还可以在构建是初始化：
map<string, int> mp = {
{"apple",5},
{"pear",4}
}; 4.2.2、map元素的访问
访问元素的方式有很多种，我们可以使用find来找到特定的元素（key），然后通过返回的迭代器访问其value，也可以改变value值，但注意不能改变key值：
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string, int> mp = {
{"apple",5},
{"pear",4}
};
auto it=mp.find("apple");
//如果apple不存在，则返回end()，解引用会报错。
cout << it->second << endl;//5
it->second = 10;
cout << it->second << endl;//10
//it->first += "x";报错
return 0;
}
其次我们可以使用方括号访问：
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string, int> mp = {
{"apple",5},
{"pear",4}
};
cout << mp["pear"] << endl;//4
return 0;
}
同时方括号也可以进行插入值。如果方括号中的元素不存在，则会向mp中插入该值，并返回插入的默认value值0：
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string, int> mp = {
{"apple",5},
{"pear",4}
};
cout << mp["p"] << endl;//0
return 0;
}
4.2.3、删除元素
删除元素可以传迭代器，也可以传key值。
myMap.erase("Bob"); // 删除键为"Bob"的元素
myMap.erase(myMap.begin()); // 删除第一个元素4.2.4、容量查询
和set没什么不同。
if (myMap.empty()) {
cout << "Map is empty" << endl;
}
cout << "Map size: " << myMap.size() << endl;map同样要求插入元素类型至少支持<比较，和set同理，在这我就不重复写了。
4.2.5、find和count
首先说find，有一点需要特别注意，就是我们的find只能根据key值进行查找：
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string, int> mp = {
{"apple",5},
{"pear",4}
};
auto it=mp.find("pear");
cout << it->second << endl;
mp.find({ "pear",4 });
cout << it->second<< endl;
mp.find({ "pear",5 });
cout << it->second << endl;
return 0;
}
以上代码输出结果都是4，因为我们无论传什么进去他都是根据key值找的，对于value并不关心。
其次count统计的是符合key值的元素个数。 只能返回0或1。
我们来看下面这串代码，虽然输出结果是0和1，但是这不代表map中的count不是只按照key值进行比较的。第一个之所以是0，是因为我们花括号里的值隐式类型转换成了pair,而pair对象和我们的string是对应不上的，所以找不到，返回0。
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string, int> mp = {
{"apple",5},
{"pear",4},
};
int num1 = mp.count({ "pear" ,2});
int num2 = mp.count("pear");
cout << num1 << endl;//0
cout << num2 << endl;//1
return 0;
}
5、multimap
同样，他也是支持重复key元素版本的map。这一特点我不再多说了，说说其他的不同。
5.1、元素访问方式
multimap不支持[]访问，必须使用迭代器进行访问：
multimap<int, string> mm;
// mm[1] = "Apple"; // 错误！不能这样使用
mm.insert({1, "Apple"});5.2、查找和计数
multimap的count会返回符合key值的值的数量。
map<int, string> m = {{1,"A"}, {2,"B"}};
cout << m.count(1); // 输出1
multimap<int, string> mm = {{1,"A"}, {1,"B"}, {2,"C"}};
cout << mm.count(1); // 输出2multimap的count也是只按照key进行统计：
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
multimap<string, int> mp = {
{"apple",5},
{"pear",4},
{"pear",5},
{"pear",6}
};
int num1 = mp.count({ "pear" ,4});
int num2 = mp.count("pear");
cout << num1 << endl;//3
cout << num2 << endl;//3
return 0;
}
multimap的find会返回第一个符合key值的元素的迭代器。
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string, int> mp = {
{"apple",5},
{"pear",4},
{"pear",5},
{"pear",6}
};
auto it = mp.find("pear");
cout << it->second << endl;//4
return 0;
}
5.3、获取范围
multimap特有的equal_range()方法可以获取所有相同键的元素范围:
multimap<int, string> mm = {{1,"A"}, {1,"B"}, {2,"C"}};
auto range = mm.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << " "; // 输出A B
}5.4、删除操作
相比map，multimap删除的是所有符合key值的元素。erase接口中只能传key值，如果传key_value的pair临时对象会显示读取无效数据。达不到删除元素的目的。
好了，到这里map和set的使用我们就讲完了，下一期我们开始模拟实现map和set底层的红黑树，更进一步理解map和set的工作机制，我们下期再见！