map和set用法详解
上一节我们讲解了二叉搜索树,在讲解之前我们先来讲一下set和map,因为set和map的底层是AVL树和红黑树,而AVL树和红黑树又是一种二叉搜索树,所以我们先熟悉一下map的set及其用法,也为后面的模拟实现做铺垫。
一,关联式容器
在前面的STL容器中,我们学习了string,vector,list等,这些都是这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
而map和set是关联式容器,关联式容器也是用来存储数据的,存储数据时可不是随便存放的,还要与其他数据进行关联,而且与序列式容器不同的是,其里面存储的是 <key, value>结构的键值对,在数据检索时比序列式容器效率更高。
二,键值对pair
在关联式容器中存储的不单单只是元素,而是一种键值对结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。
其代码是这样的:
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)
{}
};
STL总共实现了两种不同结构的管理式容器:
树型结构与哈希结构
。树型结构的关联式容器主要有四种:map、set、multimap、multiset
。
这四种容器的共同点是:使用 平衡搜索树(即红黑树) 作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器:
三,set
先来看set,set是一个K模型的结构,不能有重复元素。
set是按照一定次序存储元素的容器,其中序遍历可以得到升序序列,这是因为其内部仿函数是less,上图可以看到默认的是less。set中的元素不能修改,set在底层是用二叉搜索树(红黑树)实现的。
所以set实际上是排序+去重
1. set的用法
下面来看set的用法
先来看构造:
set可以构造为空,也可以用迭代器区间构造
set<int> s1;
vector<int> v(10,1);
set<int> s2(v.begin(),v.end());
set<int> s3(s2);
然后来看下set的迭代器:
迭代器部分的使用和之前的其他容器没有什么区别
set<int> s;
set<int>::iterator it = s.begin();
while(it != s.end()){
cout<<*it<<" ";
++it;
}
当然也支持范围for,但是注意尽量加上引用,因为其内部存储的是键值对,加上引用可以减少拷贝
for(auto &e : s){
cout<<e<<" ";
}
set不能对数据做修改,只能插入和删除
我们看一下插入:
set可以值插入,也可以传入迭代器位置插入,也可以传入迭代器区间。
set<int> s;
s.insert(1);
set<int>::iterator it = s.begin();
s.insert(it,2);
int a[] = {1,2,3,4};
s.insert(a.begin(),a.end());
来看删除之前先看一下find
find会返回要查找值的迭代器位置,如果找不到,则返回最后一个位置
find一般会和erase搭配使用
现在来看set的删除
可以传入迭代器位置,也可以传入值来删除,也可以传入迭代器区间。
这里删除时传入值和迭代器位置的删除方式略有不同,
set<int> s;//set排序+去重
int a[] = { 1,3,5,2,4,8,5,6,7 };
for (auto &e : a) {
s.insert(e);
}
auto pos = s.find(3);
if (pos != s.end()) {
cout << "找到了" << endl;
s.erase(pos);
}
s.erase(1);
如果删除的值不存在呢,当传入的是迭代器位置时,不存在会报错,而传入的是值时则不做处理。
auto poss = s.find(10);
s.erase(poss); //
s.erase(10);
报错:
下面来看看count函数,这个接口的作用就是返回set中值的个数,没有则为0 。一般用来检查一个值在不在
再来看下这两个接口,这两个接口是用来确定一段区间,比如要删除set中2~5之间的数,要找到这个区间就传入这个区间的两端的值,会返回这两个位置的迭代器。
具体的使用场景看下面来理解:
可以看到 lower_bound 和 upper_bound 返回的值
void test_set2()
{
// 排序+去重
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
// [60, 70]
// [)
auto start = s.lower_bound(3); // >=val
cout << *start << endl;
auto finish = s.upper_bound(5); // >val
cout << *finish << endl;
//s.erase(start, finish);
while (start != finish)
{
cout << *start << " ";
++start;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
所以可以得知,lower_bound 返回的是>=所要查找的值,upper_bound 返回的是 >呀查找的值,其实为的是返回的是一个左闭右开的区间
。
2. multiset的用法
现在来看multiset
,multiset在底层中存储的是<value, value>的键值对
multiset
和set
的区别是这个可以存放重复的值。
其他的接口和set相差不大:
multiset也是默认升序的,这里也体现出count接口的作用,统计某个值出现了几次。
void test_set3()
{
// 排序
multiset<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
s.insert(5);
s.insert(1);
s.insert(1);
s.insert(5);
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(7);
s.insert(10);
multiset<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
cout << s.count(5) << endl;
cout << s.count(1) << endl;
}
但是对于find接口,当一个值出现多次的时候,要返回哪一个呢,我们可以来验证一下
it = s.find(5);
while (it != s.end() && *it == 5)
{
// *it += 100;
cout << *it << " ";
++it;
}
cout << endl;
其实find找到后会返回中序的第一个值。
四,map
map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
从上图可以看到,map的默认比较器Compare也是less,当其中序遍历时,是按照Key的值来升序排列的。
也就是说map中存储的是一种键值对结构,和set不同的是map里面有两个值,也就是KV模型结构,map也不能存储Key相同的节点。
在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:
typedef pair<const key, T> value_type;
1. 键值对pair的介绍
在讲map的用法之前先说一下键值对pair,什么是键值对呢?
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量
key和value
,key代表键值,value表示与key对应的信息
。比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义
下面是SGI-STL中关于键值对的定义:
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)
{}
};
其中pair中的first就对应的是map中的Key,second对应的是map的Value。
2. map用法
来看一下map的构造
这里和set的差别不大
map的迭代器用法也和set一样,也支持范围for,同样也要注意加上
&
我们直接来看insert
map的插入时和set不同,这里的value_type是一个pair。
返回值也是一个pair
插入时可以用匿名对象:
map<string, string> m;
m.insert(pair<string, string>("sort", "排序"));
m.insert(pair<string, string>("apple", "苹果"));
m.insert(pair<string, string>("BMW", "宝马"));
当然最推荐的方式是 make_pair
m.insert(make_pair("jeep", "吉普"));
也可以支持隐式类型转换,这里是因为C++11 支持多参数构造函数的隐式类型转换
m.insert({ "apple", "苹果" });
插入后我们也可以验证map存储的是pair,查看pair里面的值:
for (auto& kv : m)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
map也可以在迭代器位置插入和迭代器区间插入
map是支持
[]
的,这里的[]
和平时我们用的可不一样,
在讲[]
之前我们先来想想如何用map来统计每种水果出现的次数:
一般的方法我们是这样:
string s[] = {"apple","binina","jim","tom","apple","jerry","jim","apple"};
map<string, int> m;
//统计水果个数
for (auto &e : s) {
map<string, int>::iterator it = m.find(e);//map的find如果找到会返回其迭代器位置,找不到会返回end()
if (it != m.end()) {
it->second++;
}else{
m.insert(make_pair(e, 1));
}
}
for (auto& e : m) {
cout << e.first << ":" << e.second << endl;
}
cout << endl;
但是我们要是用[],那么就方便很多:
//用[]统计
for (auto& e : s) {
m[e];
}
for (auto& e : m) {
cout << e.first << ":" << e.second << endl;
}
可以看到两种方法的结果是一样的!
这是为什么呢?因为当我们定义map为<string, int>时,
[]
既可以在没有这种水果的时候进行插入,又可以在水果存在的时候统计其出现的次数,并且分别存储在map的Key和Value中。
从下图可以看到这里传入的是map中的Key,返回的是Value。
在其内部其实是调用了insert的,
而为什么要调用insert呢?
这就要先来看看insert的返回值了
这里插入的时候,返回的是也一个pair结构,但是里面存储的一个是iterator迭代器位置,一个是bool值,这里注意:返回的pair和map存储的pair不是同一个
- 当检测到要插入的值不存在时,这个返回的pair中iterator是插入后的位置,bool为true,
- 当检测到要插入的值存在时,这个返回的pair中iterator是要插入的原位置,bool为false,
知道了insert的返回值我们来看[]如何调用insert的
map的erase和set也一样
知道了[]的原理后,[]不仅可以统计次数,还可以插入元素,修改Value值,
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("sort", "xxx"));
dict["left"]; // 插入
cout << dict["sort"] << endl; // 查找
dict["sort"] = "xxx"; // 修改
dict["right"] = "右边"; // 插入+修改
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
3. multimap用法
multimap和multiset一样,和map和set的区别就是可以存储重复的值,但是这里的multimap不支持[]
五,总结
知道了set和map后,我们还是要多做练习才可以更深入的理解。下节我会讲解AVL树,终于要上难度了,希望大家可以在我的讲解下能轻松掌握!!
标签:map,set,进阶,迭代,insert,C++,键值,pair From: https://blog.csdn.net/weixin_64906519/article/details/136475264