map(映射)
- $map$ 是更强大的数组。
- 之所以说它强大,有两点原因:
- 第一,$map$ 可以当作数组使用,但下标不仅局限于数字。
- 第二,$map$ 的内部元素是$\color{#ff0000}{\text{有序}}$的。
1.定义
- $map$ 又被称为映射,是从 $key$ 到 $value$ 的映射,给定 $key$ 就能确定 $value$。
- 实际上数组也可以看作是从 $key$ 到 $value$ 的映射,其中 $key$ 是整数下标,$value$ 是数组中存储的值
- 要定义一个 $map$,就要指明 $key$ 和 $value$ 的数据类型,定义格式如下:
map<key_t,value_t>名字;
- 例如:
map<string,double>sd;
2.map的使用
- $map$ 可以像数组一样进行调用、赋值。
#include <bits/stdc++.h>
using namespace std;
map<string,double>f;
int main(){
f["nihao"]=3.1415926;
cout<<f["nihao"]<<endl;
f["byebye"]=666.789;
cout<<f["byebye"]<<endl;
}
3.迭代器
- 它是用来遍历的,在 $STL$ 的容器中如
vector、map、set
中我们经常要用迭代器去遍历其中的元素,尤其是在 $map$ 和 $set$ 中。 - 定义:
map<key_t,value_t>::iterator 迭代器名;
- 首先定义一个
map<string,double>
的迭代器 - 例如:
map<string,double>::iterator it;
4.map中的元素——pair
- 在 $map$ 中,存储的元素有 $key$ 和 $value$,对应的是 $STL$ 中的 $pair$ 类型。
- $pair$ 类型可以单独定义。
pair<key_t,value_t>变量名;
- 它可以理解为含有两个变量 $first$ 和 $second$ 的结构体。
- $\color{#ff0000}{\text{初始化方法:}}$
pair<key_t,value_t>(key,value)
#include <bits/stdc++.h>
using namespace std;
pair<int,int>p;
int main(){
p=pair<int,int>(1,1);
cout<<p.first<<" "<<p.second;
return 0;
}
5.迭代器遍历
- 迭代器像指针一样,可以用
->
符号取出元素。 - 迭代器是 $pair$ 的指针,对应有两个元素。
it->first
是 $key$,it->second
是 $value$。f.begin()
是 $f$ 开头对应的迭代器,f.end()
是 $f$ 结尾位置对应的迭代器(但结尾是没有元素的)。
#include <bits/stdc++.h>
using namespace std;
map<string,double>f;
map<string,double>::iterator it;
int main(){
f["nihao"]=3.1415926;
cout<<f["nihao"]<<endl;
f["byebye"]=666.789;
cout<<f["byebye"]<<endl;
for(it=f.begin();it!=f.end();it++)
cout<<(it->first)<<" "<<(it->second);
}
- 在 $map$ 中,所有元素是 $\color{#ff0000}{\text{按}key\text{从小到大排列}}$ 的。
- 我们用迭代器进行遍历时,遍历到的元素的 $key$ 也是从小到大的。
6.查找map中的元素
- 使用下列方法查找 $map$ 中是否有 $key$ 对应的 $value$。
.find(key);
- 返回值:如果存在,返回元素对应的迭代器,否则返回
.end()
。 - 判断一个键是否存在的方法如下:
if(f.find("byebye") != f.end()){
//存在
}
else{
//不存在
}
- 在不确定 $map$ 中存在 $key$ 对应的 $value$ 时,必须使用 $find$ 先查找,否则如果直接使用下标索引,会导致运行时错误!(和数组下标越界类似)
set
- $set$,顾名思义,是一个集合,
- 在 C++ 中,$set$ 是一个$\color{#ff0000}{\text{有序集合}}$,其内的元素是按$\color{#ff0000}{\text{从小到大}}$的顺序排好序的。
1.定义
-
在定义一个 $set$ 时,要指明这个集合中的元素的数据类型。
-
定义格式为:
set<数据类型>名字;
-
例如,如果我们维护一个整数的有序序列,名为 $S$:
set<int> S;
- 集合必须是不
2.元素的插入
将一个数据插入到集合中,需要调用函数 .insert()
#include <bits/stdc++.h>
using namespace std;
set<int>S;
int main(){
S.insert(10);
S.insert(6);
S.insert(9);
}
3.set的遍历
- 与 $map$ 类似,遍历 $set$ 中的元素需要用到迭代器。
- 每个迭代器指向 $set$ 中的一个元素,用
*
可以取出对应的数据。
#include <bits/stdc++.h>
using namespace std;
set<int>S;
set<int>::iterator it;
int main(){
S.insert(10);
S.insert(6);
S.insert(9);
for(it=S.begin();it!=S.end();it++)
cout<<*it<<endl;
}
4.multiset
- 当我们需要统计$\color{#ff0000}{\text{重复}}$元素时,我们可以使用”另一个版本“:
multiset
- 定义格式为:
multiset<数据类型>名字;
- 例如,如果我们需要维护一个整数的有序可重复集合,名为MS:
multiset<int>MS;
(在其他方面,例如函数和迭代器,multiset
均与set
用法一致)
5.查找set中的元素
- 使用下列方法查找 $set$ 中是否有某个元素。
.find(值)
- 返回值:如果存在,返回元素对应的迭代器,否则返回
.end()
。 - 判断一个键是否存在:
if(s.find(1000) != s.end()){
//存在
}
else{
//不存在
}
- 在 $set$ 中,由于元素不可重复,一旦找到,个数一定为 $1$。
6.查找multiset中的元素
- 因为 $multiset$ 是可重集合,怎么才能确定等于 $key$ 的元素有多少个呢
- 使用下面的方法统计等于 $key$ 的元素的个数:
.count(key)
map和set小结
- $map$ 是键值对,和数组一样,有键值对映射时使用。
- $set$ 是不可重集合,可以自动去重。
- 如果想要有重复元素,可换用 $multiset$。
- $map$ 和 $set$ 都是保持有序的,都可以用迭代器遍历。
# 说的太好了
## 讲得好