【C++】认识map和set

前言：

一：认识map和set

二：map和set的使用

1.set的使用

2.map的使用

三：map的insert方法返回值

四：map的[ ]的使用

五：multiset和multimap

六：map和set的底层数据结构

七：map和set的迭代器

总结：

前言：

我们通过之前的学习，已经学会了AVL树和红黑树，但是STL中并没有这两种类，它是对红黑树进行了封装，供上层使用的。

这里，我们就要先学会使用map和set了，是STL中的类模板，它们的底层都是红黑树。

一：认识map和set

大家有没有想过，生活中很多东西都是一对一的。比如去停车场停车时，收费站会先记录车牌号，之后一个车牌号对应一个存放时间；或者通讯录中一个号码对应一个联系人等。这种方法就是键值对。一个唯一的键，对应一个唯一的值。但是你可以发现，这个值是可以修改的，而键不能修改。

比如一个老师要对每个学生管理，就要把每个学生学号管理起来，此时没有用到值，只有键。

通过以上两个例子，你就会发现，键都是唯一的，而值不是。这里再次说明，键也是不能修改的。

map中就是使用键值对的方式存储；而set中只有键。

map中的值能修改，键不能修改；set中只有键，不能修改。

二：map和set的使用

既然我们知道了map存储的是键值对，set存储的是键，那么接下来，我们就要使用它们了。

1.set的使用

这个很简单，引入<set>头文件，之后可以去观察cplusplus官网查看方法的使用(这里不是作者偷懒，而是我们到了现在这个阶段，就必须学会看文档了)。以下给出使用方法：

int main()
{set<int> s;s.insert(4);s.insert(6);s.insert(3);s.insert(5);set<int>::iterator it = s.begin();//auto it = s.begin();//底层是二叉搜索树 默认中序遍历while (it != s.end()){cout << *it << " ";++it;}cout << endl;//删除最小值 也就是最左边的迭代器指向的位置s.erase(s.begin());  //通过返回值判断是否删除成功int x;cin >> x;//int num = s.erase(x);//if (num == 0)//{//	cout << x << "不存在！" << endl;//}for (auto e : s){cout << e << " ";}cout << endl;set<int>::iterator pos = s.find(x);if (pos != s.end()){s.erase(pos);}else{cout << x << "不存在！" << endl;}for (auto e : s){cout << e << " ";}cout << endl;//使用算法头文件的find查找auto pos1 = find(s.begin(), s.end(), x); //O(N) auto pos2 = s.find(x);                   //O(logN)//用find查找元素是否存在并不方便 使用count方便cin >> x;if (s.count(x)){cout << x << "在！" << endl;}else{cout << x << "不存在！" << endl;}return 0;
}

对没错，就这么多。

2.map的使用

map存储的是键值对，那么当然要有两个模板参数，但是我们如何插入数据呢？

在此之前我们先来认识一个pair类：

可以发现它是一个结构体，两个模板参数。

成员变量为：

对，很简单，map就是存的它，但是对first加上了const修饰。接下来我们看看map的使用方法：

int main()
{map<string, string> dict;//我们要使用一个类向map中插入数据pair<string, string> kv1("left", "左边");dict.insert(kv1);//传入匿名对象dict.insert(pair<string, string>("right", "右边"));//还有一个函数模板 make_pair 只用传入键值对 就可以返回一个pair对象dict.insert(make_pair("insert", "插入"));//还有我们可以传入多参数的初始化对象的方法dict.insert({ "string", "字符串" });map<string, string> dict1 = { {"left", "左边"}, {"right", "右边"} };map<string, string>::iterator it = dict.begin();while (it != dict.end()){//*it返回的是pair 但是其不支持流提取//cout << (*it) << endl;//可以去看pair 两个成员变量 first 和 second//这里不是插入顺序 而是字符ASCII码排序 中序遍历//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl; //最好用第二种++it;}cout << endl; //用自定义类型写范围for遍历map 最好这样写 不用深拷贝for (const auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;string arr[] = { "苹果", "西瓜","苹果","西瓜","苹果" };map<string, int> Count;int tmp = 1;for (const auto& str : arr){//find返回的是迭代器auto ret = Count.find(str);//找到返回那个未知的迭代器 没有找到返回endif (ret == Count.end()){//没有这个元素Count.insert({str, 1});}else{++ret->second;}}auto it1 = Count.begin();while (it1 != Count.end()){//*it返回的是pair 但是其不支持流提取//cout << (*it) << endl;//可以去看pair 两个成员变量 first 和 second//这里不是插入顺序 而是字符ASCII码排序 中序遍历//cout << (*it).first << ":" << (*it).second << endl;cout << it1->first << ":" << it1->second << endl; //最好用第二种++it1;}return 0;
}

以上的insert方法我们需要注意，还有迭代器的使用方法，运行结果为：

三：map的insert方法返回值

这里我们最需要注意的就是map的insert方法返回值：

返回的是一个pair类，第一个参数是iterator，第二个参数是bool。

这是什么意思呢？这里先说明第二个参数bool：当我们插入一个键时，如果当前键存在，则说明此键已经不能再次插入了，也就是插入失败，所以测试第二个参数为false；当前键不存在，返回true。

第二个参数是iterator，也就是迭代器，经过我们之前的学习(无中生有哈哈)，已经知道了iterator本就是指针，这个指针是什么类型的呢？对，是map中存储数据节点的类型。你已经知道map中存储的是pair，那么这个迭代器本质也就是pair的指针。

所以为了测试insert方法，我们需要拿iterator来接收它，因为insert返回的是pair，且第一个参数类型是iterator所以要像下面这样写：

int main()
{map<int, int> m;int a[] = { 1, 2, 3 };for (auto e : a){m.insert({ e, e });}map<int, int>::iterator it;it = m.insert({ 10, 1 }).first; //insert不能修改！cout << it->first << endl;cout << it->second << endl;return 0;
}

上面代码中我们插入了一个不存在的键，此时insert方法返回的就是{ iterator, true }，其中iterator是插入10位置的指针，true代表插入成功。所以结果如下：

之后我们再来尝试插入相同的值，再次插入10这个键：

int main()
{map<int, int> m;int a[] = { 1, 2, 3 };for (auto e : a){m.insert({ e, e });}map<int, int>::iterator it;it = m.insert({ 10, 1 }).first; //insert不能修改！//再次插入10 观察返回的pair中的值//因为iterator是指针 所以使用重载的->cout << "iterator指向的节点为：" << m.insert({10, 3}).first->first << endl;if (m.insert({ 10, 3 }).second)cout << "插入成功" << endl;elsecout << "插入失败" << endl;cout << "此时10对应的值为：" << m.insert({10, 3}).first->second << endl;return 0;
}

运行结果为：

可以看到，当10再次插入，已经无法插入，但是返回的iterator会指向10，所以对应的值也无法修改，且insert返回pair第二个参数为false；第一次插入返回10的位置，值为true。

那么我们如何改变对应的值呢？刚才不是说能修改对应的值吗？

四：map的[ ]的使用

这时我们要修改值不能使用insert，而要是用 [ ] ，这个 [ ] 充当着插入，修改，查找的功能(也就是说底层封装的insert，更加详细的解释可以先下一篇用红黑树实现map和set)。

int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));//插入 + 修改dict["left"] = "左边";//修改dict["left"] = "左边、剩余";//key不存在->插入 <"insert", "">dict["insert"];//key存在  -> 查找cout << dict["left"] << endl;  //使用[]要谨慎return 0;
}