C++修炼：map和set的使用

        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的主要特性   

1. 唯一性：set中的元素都是唯一的，不允许重复

2. 自动排序：元素插入后会自动排序

3. 不可修改元素：set中的元素是const的，不能直接修改

4. 高效的查找操作：基于红黑树实现，查找时间复杂度为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;//0cout << s.size() << endl;//6return 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);  // 输出1multiset<int> ms = {1,2,2,3};
cout << ms.count(2); // 输出2

        3.3、erase不同

        multiset一次性会删除所有符合元素，而set只会删除一个元素（如果存在）。如果存在该元素返回true,如果不存在该元素（删除失败）返回false。

4、map

        map是一种关联容器，存储键值对(key-value pairs)，其中键是唯一的，且元素按照键的顺序进行排序。

4.1、map的主要特性

1. 键值对存储：每个元素都是一个pair<const Key, T>

2. 键的唯一性：每个键只能在map中出现一次

3. 自动排序：元素按键的顺序自动排序

4. 高效的查找操作：基于红黑树实现，查找时间复杂度为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;//5it->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;//4return 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;//0return 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;//0cout << num2 << endl;//1return 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); // 输出1multimap<int, string> mm = {{1,"A"}, {1,"B"}, {2,"C"}};
cout << mm.count(1); // 输出2

        multimap的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;//3cout << num2 << endl;//3return 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;//4return 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的工作机制，我们下期再见！