【c++】STL-set和map的使用

hello~ 很高兴见到大家! 这次带来的是C++中关于map和set这部分的一些知识点,如果对你有所帮助的话,可否留下你宝贵的三连呢? 个 人 主 页: 默|笙

一、 序列式容器和关联式容器

1. 我们之前所学的像vector、list、queue、deque、array等容器它都是序列式容器，它们的逻辑结构为线性的数据结构（它的存储顺序取决于你在什么位置以什么顺序去插入元素，像排队插入），存储的元素彼此之间一般都没有什么很强的关联性，交换一下存储顺序，它依旧是序列式容器。
2. 而接下来所要学习的set/map都是关联式容器，是非线性结构，它们不是按照插入顺序存储，它会按照元素的键（key）的某种规则来进行存储或查找。存储的元素彼此之间有很强的关联关系，一旦进行交换，它的结构就会被破坏掉。
3. set和map的底层是红黑树，红黑树是一棵平衡二叉搜索树，set是key搜索场景的结构，map是key/value搜索场景的结构。

二、set

set文档内容

1. set的声明

在这里插入图片描述

1. 第一个模板参数T是底层关键字的名称，也就是我们所说的key，传需要进行存储的值的类型。第二个模板参数Compare是一个仿函数，set默认要求支持小于比较，如果需要按照自己的需求去走可以传自己设计的仿函数。第三个模板参数是内存池，set默认是从空间配置器里面申请空间的，如果有需求，可以传自己的内存池。一般情况下，我们不需要传递后面两个参数。
2. set 的底层是用红黑树实现，红黑树是一棵平衡二叉搜索树，增删查效率是logN，迭代器走的是中序，是有序的。
3. 接下来会挑一些与之前vector/list不同的接口或者特殊的地方进行讲解（毕竟它们的设计高度相似）。

2. set的遍历

1. set的迭代器是一个双向迭代器，它支持++与- - 操作，支持正向与反向遍历。支持迭代器同时也意味着可以使用范围for，set的iterator与const_iterator都不支持修改操作，因为修改关键字会破坏set的结构。

set<int> s = { 5,1,5,3,4,2,6,8,3,9,10,22 };//排序+去重
set<int>::iterator it1 = s.begin();
//正向遍历
while (it1 != s.end())
{
	cout << *it1 << " ";
	it1++;
}
cout << endl;
//反向遍历
set<int>::reverse_iterator it2 = s.rbegin();
while (it2 != s.rend())
{
	cout << *it2 << " ";
	it2++;
}
cout << endl;
//范围for
for (auto e : s)
{
	cout << e << " ";
}
cout << endl;
return 0;

在这里插入图片描述

在这里插入图片描述

3. find、erase函数返回值

在这里插入图片描述

1. find函数的返回值不是bool值，而是返回一个迭代器，若找到了，则返回找到的这个元素的迭代器，若没有找到，则返回set::end()。

在这里插入图片描述

1. 关于第二个版本，它的返回值是删除的这个元素的个数，其他版本返回的都是最后一个删除的元素后面的一个位置，比如最后删除的是最后一个元素，那么会返回set::end()。

4. count函数和lower_bound、upper_bound函数

在这里插入图片描述

1. count函数用来统计一个set里有多少个跟val值相等的元素，然后返回与它相等的元素的个数。它在set里也可以充当find使用。

在这里插入图片描述

1. 它会返回一个迭代器，这个迭代器指向第一个不小于val的元素（大于或等于）。
2. 如果val小于set里面所有的值，那么会返回begin()。

在这里插入图片描述

1. 它会返回一个迭代器，这个迭代器指向第一个大于它的元素，不是等于它的元素，右区间得是开区间。
2. 如果val大于set里面所有的值，那么会返回end()。
3. lower_bound 和upper_bound 可以共同完成一个左闭右开的区间，我们可以通过它们来删除在一个区间里面的元素。

set<int> s = { 5,1,5,3,4,2,6,8,3,9,10,22 };//排序+去重
set<int>::iterator it1 = s.begin();
for (auto e : s)
{
	cout << e << " ";
}
cout << endl;

//删除区间[3,9]的值
auto it3 = s.lower_bound(3);
auto it4 = s.upper_bound(9);
s.erase(it3, it4);
for (auto e : s)
{
	cout << e << " ";
}
cout << endl;

在这里插入图片描述

5. multiset和set的差异

1. multiset和set的使用方式基本完全类似，主要差异在于multiset支持存储冗余数据，而set不支持。它们在insert/erase/find/count围绕着是否支持冗余这一点都有所差异。
2. 对于insert，multiset是支持插入相同的值的。

在这里插入图片描述

3. 对于erase的第二个版本，multiset会删除所有等于val的元素，并返回删除的个数。 4. 对于find，multiset会返回指向它找到的第一个（中序第一个）等于val值的元素的迭代器，没有找到则会返回multiset::end()。 5. 对于count，相比于set，返回的不再只是0或1，可以有更多的值，毕竟multiset支持存储冗余数据。

三、map的使用

map参考文档

1. map的声明

在这里插入图片描述

1. 其中Key是map底层关键字类型的类型，T是map底层value的类型，其他的就跟set差不多了。
2. map底层的红黑树节点使用pair<Key, T>存储数据，也就是说map直接存储的实际是pair类型的值，而pair里面存储的是Key与T，Key和T被绑定在了一起，通过找到K，可以映射到T（value)。

2. pair类型介绍

pair文档

在这里插入图片描述

1. pair是c++模板库里一个非常实用的模板类，它用于将两个值（可以是同类型，也可以是不同类型）组合成一个单一对象。

在这里插入图片描述

1. 它有两个成员变量，一个是first，它对应pair里面存储的第一个值，一个是second，对应pair里面存储的第二个值。

3. map的遍历

1. map的迭代器也是一个双向迭代器，支持正向和反向迭代。支持范围for，不支持修改key值，为了不破坏底层搜索树结构，支持修改value值。

map<string, string> m = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } };
auto it1 = m.begin();
//正向迭代
while (it1 != m.end())
{
	cout << it1->first << " " << it1->second  << endl;
	it1++;
}
cout << endl;
auto it2 = m.rbegin();
//反向迭代
while (it2 != m.rend())
{
	cout << it2->first << " " << it2->second << endl;
	it2++;
}
cout << endl;
//范围for
for (auto e : m)
{
	cout << e.first << " " << e.second << endl;
}
cout << endl;

在这里插入图片描述

在这里插入图片描述

4. insert函数

在这里插入图片描述

1. 第一个版本下insert的返回值是pair<iterator,bool>，一个pair类型的对象，它的第一个成员变量存储的是iterator类型数据，若插入成功，这个迭代器会指向刚完成插入的那个元素，若插入失败，就代表key已经存在，这个迭代器会指向已经存在的key所在的元素。bool代表的是插入成功与否。set里的insert的返回值也是这样。
2. 增：使用insert成员函数插入一个键值对。

m.insert({"insert1", "1"});//隐式类型转换
m.insert(make_pair("insert2", "2"));//使用make_pair构造
m.insert(pair<string, string>("insert3", "3"));//调用pair构造函数

1. 推荐使用第一种隐式类型转换的方法，多参数要使用花括号。

在这里插入图片描述

1. 对于make_pair函数，它返回的是一个pair类型的值。make_pair函数还是一个内联函数。

5. operator[]函数

1. map重载了[]，使得我们可以通过输入key值来访问对应的value值，还可以对value值进行修改。
2. 如果set里存在输入的key，那么它会返回它对应value值的引用，实现查找+修改的功能。如果不存在，它会进行一个插入操作，插入此key。

在这里插入图片描述

6. map与multimap的区别

1. multimap和map的使用高度相似，就是multimap支持存储冗余数据，关于围绕支持存储冗余数据这一点造成的差异跟set与multimap之间并无不同。multimap不支持operator[]，因为支持插入新的key，就不能支持修改了（无论key是否存在都要进行插入）。

今天的分享就到此结束啦,如果对读者朋友们有所帮助的话,可否留下宝贵的三连呢~~ 让我们共同努力, 一起走下去!