STL专题-map 映射

本文最后更新于：2021年4月16日凌晨

map映射，multimap，以及unordered_map哈希表。

map——映射

头文件 #include <map>

map是一个关联式容器，可以建立 key(即first) 到 value(即second) 的一对一的映射关系，由key映射到value。类似于函数的x到y，一对一。
map内部自建了一颗红黑二叉树，可以对数据进行自动排序，默认排序方式为字典序(从小到大)，故map内的数据都是有序的。

map声明与初始化

构造

1
2
3

map<int,string> map_student;

map<int,string,myCmp> map_student;//设定排序规则

这里构造了一个由int映射到string的map。这里key与value可以是任意数据类型，包括自定义的。

插入数据

//方法1.类似数组的方式插入
map_student[1] = "liming"; //1->"liming"
//方法2.insert()函数
map_student.insert(map<int,string>::value_type(2,"zhangsan"));
//方法3.insert()函数
map_student.insert(make_pair(3,"lisi"));
//方法4.insert()函数
map_student.insert(pair<int,string>(4,"wangwu"));

//方法2、方法3、方法4返回值都是pair<iterator,bool>类型的值，通过返回值.second可查看是否插入成功。

注意

insert()函数可以体现映射一一对应的特性，当map中的key值已经存在时，就不能再使用insert()插入数据了，即使代码存在也不会覆盖，但是使用数组的方式是可以覆盖原数据的。两种方式混合赋值时也是如此，数组方式可以覆盖。

并且如果通过数组方式即直接map_student[5]这中方式去访问不存在的值的话，map会自动把这个访问的key插入到map容器中，而对应的value值则取其的默认值。

如上原因，所以不建议使用数组的方式添加元素

map基本操作

begin()——返回首部迭代器
end()——返回尾部的下一位置的迭代器
size()——返回容器内的元素个数
empty()——判空，空返回1，非空返回0；
find(n)——返回指向元素n的迭代器，未找到返回end()指向的迭代器
count(n)——统计n的出现次数(0或者1)

insert(elem); //在容器中插入元素。

clear(); //清除所有元素

erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

erase(key); //删除容器中值为key的元素。

map遍历操作

#include <iostream>
#include <map>
using namespace std;
int main()
{
   map<string,int> map_student;
   map<string,int>::iterator iter;

   map_student["zhao"] = 0;//[]内这样放也可以
   map_student["qian"] = 1;
   map_student["sun"] = 2;
   map_student.insert(map<string,int>::value_type("sun",3));//不会覆盖
   for(iter = map_student.begin();iter!=map_student.end();iter++)
   {
       cout<<iter->first<<"-->"<<iter->second<<endl;
       //cout<<iter->key<<"-->"<<iter->value<<endl;map中没有key与value这两个变量！
   }
   cout<<"---"<<endl;
   cout<<map_student.find("sun")->first<<"-->"<<map_student.find("sun")->second<<endl;
   return 0;
}

//输出结果
qian-->1
sun-->2
zhao-->0
---
sun-->2

map应用

去重

利用映射一一对应的特性，将可能出现的重复数据设置为key值以达到去重的目的。

排序

map<>中有三个变量，第三个就是排序方式。如若不指定排序方式的话，map会默认按照less<Key>进行排序，从小到大！

进行降序排序输出

map<string,int,greater<string> >map_student;
map_student["zhao"] = 0;
map_student["qian"] = 1;
map_student["sun"] = 2;
for(iter = map_student.begin();iter!=map_student.end();iter++)
{
    cout<<iter->first<<"-->"<<iter->second<<endl;
}

//输出结果
zhao-->0
sun-->2
qian-->1

自定义按照string的长短进行输出

//与自定义sort()的方法类似
struct cmp
{
    bool operator()(string a,string b)
    {
        if(a.length()!=b.length())
        {
            return a.length()<b.length();//从小到大
        }
        return a<b;
    }
};
map<string,int,cmp> map_student;
map_student["zhao"] = 0;
map_student["qian"] = 1;
map_student["sun"] = 2;
for(iter = map_student.begin();iter!=map_student.end();iter++)
{
    cout<<iter->first<<"-->"<<iter->second<<endl;
}

//输出结果
sun-->2
qian-->1
zhao-->0

计数

假设定义map<string,int> s_map;输入一个数据s，就可以将其对应的map[s]++。通过这样来进行计数。

map特点与使用场景

自动建立key->value的对应关系，key与value可以使任何数据类型。
可以快速查找、删除记录，根据key值查找的复杂度很低。
key与value一一对应的关系可以用于去重操作。

可用于去重计数类题目，可打乱重新排列的问题，以及有清晰的一对一关系的问题。

multimap

multimap与map均使用头文件<map>，两者的差距不太大，map容器之中不允许有重复的key值，但是multimap容器中却允许有重复的key值。

当然，insert函数就不再返回一个pair而是插入位置的迭代器了。

就像set与multiset那样。

multimap遍历与查找！

upper_bound(key) 返回一个迭代器，指向不大于key的第一个元素
lower_bound(key)返回一个迭代器，指向不小于key的第一个元素！

int main() {

	multimap<int, string,greater<int>> mulmap;

	mulmap.insert(make_pair(1,"Bob"));
	mulmap.insert(make_pair(1,"Tom"));
	mulmap.insert(make_pair(1,"Ani"));
	mulmap.insert(make_pair(2,"Cou"));
	mulmap.insert(make_pair(3,"Las"));
	mulmap.insert(make_pair(0,"Bob"));
	mulmap.insert(pair<int, string>(-1,"Bob"));
	//mulmap[1] = "Bob"; 不可以！！！
	mulmap.insert(multimap<int, string, greater<int>>::value_type(1,"Unc"));

	for (auto i : mulmap) {
		cout << i.first << " " << i.second << endl;
	}

	auto it = mulmap.find(1);
	cout << "find:" << it->first << " " << it->second << endl;

	auto it1 = mulmap.lower_bound(1);
	auto it2 = mulmap.upper_bound(1);
	cout << "lower:" << it1->first << " " << it1->second << endl;
	cout << "upper:" << it2->first << " " << it2->second << endl;

	auto ii = mulmap.insert(make_pair(1,"Sam"));
	cout << "insert:" << ii->first << " " << ii->second << endl;
	ii = mulmap.insert(make_pair(1, "Dam"));
	cout << "insert:" << ii->first << " " << ii->second << endl;
	ii = mulmap.insert(make_pair(1, "Aam"));
	cout << "insert:" << ii->first << " " << ii->second << endl;
	ii = mulmap.insert(make_pair(1, "Bam"));
	cout << "insert:" << ii->first << " " << ii->second << endl;


	//现象：原先的迭代器不会失效，这样遍历仍然能够输出所有的节点！！！
	for (; it1 != it2; it1++) {
		cout << "遍历:" << it1->first << " " << it1->second << endl;
	}

	return 0;
}

unordered_map

unordered_map需要引入头文件<unordered_map>。

同理，还有一个unordered_multimap。

它与map的内部实现不同，不过外部使用的函数没有什么差别。

map内部是红黑树实现的，会对数据进行自动排序。
unordered_map内部是一个哈希表实现的，其元素的排列顺序是无序的。

map：

优点：

有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高
缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

优点：因为内部实现了哈希表，因此其查找速度非常的快
缺点：哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

map、multimap、unordered_map使用对比

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

void test0() {

	//map
	map<int, string> person;

	person.insert(make_pair(3,"张三"));
	person.insert(make_pair(2,"李四"));
	person.insert(make_pair(3,"王五"));
	person.insert(make_pair(1,"马街"));

	//遍历
	map<int, string>::iterator it = person.begin();

	cout << "map:" << endl;

	for (; it != person.end(); it++) {
		cout << it->first << " - " << it->second << endl;
	}

}

void test1() {

	//multimap
	multimap<int, string> person;

	person.insert(make_pair(3, "张三"));
	person.insert(make_pair(2, "李四"));
	person.insert(make_pair(3, "王五"));
	person.insert(make_pair(1, "马街"));

	//遍历
	multimap<int, string>::iterator it = person.begin();

	cout << "multimap:" << endl;

	for (; it != person.end(); it++) {
		cout << it->first << " - " << it->second << endl;
	}
}

void test2() {

	//unordered_map
	unordered_map<int, string> person;

	person.insert(make_pair(3, "张三"));
	person.insert(make_pair(2, "李四"));
	person.insert(make_pair(3, "王五"));
	person.insert(make_pair(1, "马街"));

	//遍历
	unordered_map<int, string>::iterator it = person.begin();

	cout << "unordered_map:" << endl;

	for (; it != person.end(); it++) {
		cout << it->first << " - " << it->second << endl;
	}
}

int main() {

	test0();
	test1();
	test2();

	return 0;
}

执行结果：

map://有序且不重复
1 - 马街
2 - 李四
3 - 张三
multimap://有序，但有重复
1 - 马街
2 - 李四
3 - 张三
3 - 王五
unordered_map://无序，无重复
3 - 张三
2 - 李四
1 - 马街

例题：蓝桥杯2015年-密文搜索

题目描述：

福尔摩斯从X星收到一份资料，全部是小写字母组成。
他的助手提供了另一份资料：许多长度为8的密码列表。福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。
请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。

输入：

输入第一行：一个字符串s，全部由小写字母组成，长度小于1024*1024
紧接着一行是一个整数n,表示以下有n行密码，1<=n<=1000
紧接着是n行字符串，都是小写字母组成，长度都为8

输出：

一个整数, 表示每行密码的所有排列在s中匹配次数的总和。

样例输入：

aaaabbbbaabbcccc

2

aaaabbbb

abcabccc

样例输出：

4

思路

题目意思是对后面输入的密码进行打乱重组，只要能与原串的代码的连续的一部分相匹配就合格。考虑两点

提取主串连续的8位去构建新的字符串。

string( string &str, size_type index, size_type length );
//构建一个新的字符串，从str中的以index为索引开始的子串，长度为length
两处字符串相互匹配。以为只要保证输入的密码能重组成为前面的资料(原串)就可以，所以不妨直接sort()排序，再比较两者的差异。
对输入的密码存储入 map<string,int> 之中，便于计数。

点击查看代码

```c++ //测试环境 Code::Blocks 17.12 //本代码没有在OJ测试过，因为找不到。。。 #include #include #include #include using namespace std;

int main()
{
    int n;
    string s;
    int sum = 0;//最后的和值
    string nstr[1000];
    map<string,int> s_map;
    map<string,int>::iterator iter;
    cin>>s;//输入首串字母
    cin>>n;//输入密码数量
    for(int i=0;i<n;i++)
    {
        cin>>nstr[i];
        s_map[nstr[i]] = 0;
    }
    for(int i = 0;i<s.length()-8+1;i++)
    {
        string s1 = string(s,i,8);//截取部分string构建新的字符串
        sort(s1.begin(),s1.end());

        for(iter = s_map.begin();iter!=s_map.end();iter++)
        {
            string s2 = iter->first;
            sort(s2.begin(),s2.end());

            if(s1 == s2) s_map[iter->first]++;
        }
    }
    for(iter = s_map.begin();iter!=s_map.end();iter++)
    {
        sum += s_map[iter->first];
    }
    cout<<sum<<endl;
    return 0;
}

以上就是这道题的思路。

C/C++

C++ 蓝桥杯 STL

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

STL专题-set 集合上一篇

C++操作符重载 operator 下一篇