【 C++ 】map、multimap的介绍和使用

目录

1、map

        map的介绍

        map的定义

        insert插入函数

        map的迭代器

        [ ]运算符重载

        find查找函数

        erase删除函数

        其它函数

        总结

2、multimap

        multimap的介绍

        multimap的使用

---

1、map

map的介绍

• 1、map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
• 2、在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;
• 3、在内部，map中的元素总是按照键值key进行比较排序的。
• 4、map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
• 5、map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
• 6、map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

• key: 键值对中key的类型
• T： 键值对中value的类型
• Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
• Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

注意：在使用map时，需要包含头文件。

---

map的定义

• 1、指定key和value构造一个空map

map<int, string> m1;

• 2、拷贝构造同类型map

map<int, string> m2(m1);

• 3、使用迭代器区间构造一块内容

map<int, string> m3(m2.begin(), m2.end());

• 4、构造一个指定大于的比较方式的map

map<int, string, greater<int>> m4;

---

insert插入函数

• insert函数声明：

pairbool> insert (const value_type& x );

• 接口说明：

在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功。x的类型为value_type，而value_type即pair的别名：

typedef pair<const Key, T> value_type;

• 解释键值对：

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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)
	{}
};

因此，后续在使用insert时，首先用key和value构造一个pair对象，再把pair对象作为参数传入insert函数。

• 插入方式如下：

1、借助pair构造函数：

void test_map1()
{
	map dict;
    pair kv("byte", "字节");
	dict.insert(kv);
}

2、借助pair构造匿名对象插入：

void test_map1()
{
	map dict;
	dict.insert(pair("sort", "排序"));
}

3、调用make_pair函数模板插入：

void test_map1()
{
	map dict;
	dict.insert(make_pair("left", "左边"));//make_pair是库里的，不需要自己写
}

库里的make_pair源码如下：

template <class T1, class T2>
pair make_pair(T1 x, T2 y)
{
	return (pair(x, y));
}

4、使用{}

 
void test_map1()
{
	map dict;
	dict.insert({ "right", "右边" });//C++11支持的写法，后续详谈
}

• insert函数返回值说明：

pairbool> insert (const value_type& val);

insert函数的返回值是一个pair对象，该pair对象中第一个成员的类型（pair::first）为指向新插入元素的迭代器或者没有插入成功（数据冗余），返回指向跟key相等的位置结点的迭代器，第二个成员的类型为一个bool类型，具体含义如下：

• 若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回插入后元素的迭代器和true。
• 若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回map当中键值为key的元素的迭代器和false。

示例：

void test()
{
	map dict;
	auto ret1 = dict.insert(make_pair("left", "左边"));
	auto ret2 = dict.insert(make_pair("left", "剩余"));
}

监视窗口如下：

---

map的迭代器

函数声明	功能介绍
begin()和end()	begin:首元素的位置，end最后一个元素的下一个位置
cbrgin()和cend()	与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()	反向迭代器，rbegin在end位置，rend在begin位置，其++和--操作与begin和end操作移动相反
crbegin()和crend()	与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

接下来即可对map进行遍历操作：

void test_map2()
{
	//插入
	map dict;
	dict.insert(make_pair("left", "左"));
	dict.insert(make_pair("right", "右"));
	dict.insert(make_pair("front", "前"));
	dict.insert(make_pair("back", "后"));
	//遍历
	map::iterator it = dict.begin();
	while (it != dict.end())
	{
		//cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;
	//范围for
	for (const auto& e : dict)
		cout << e.first << ":" << e.second << endl;
}

• 实例：统计各水果出现的次数

void test_map3()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	mapint> countMap;
	for (auto& str : arr)
	{
		mapint>::iterator it = countMap.find(str);
		if (it != countMap.end())
		{
			it->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}
	for (const auto& kv : countMap)
		cout << kv.first << ":" << kv.second << endl;
}

根据insert的特性，我们可以针对其进行优化：

void test_map3()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//优化1：
	/*map countMap;
	for (auto& str : arr)
	{
		//pair::iterator, bool> ret = countMap.insert(make_pair(str, 1));
		auto ret = countMap.insert(make_pair(str, 1));
		if (ret.second == false)
		{
			ret.first->second++;
		}
	}*/
 
//优化2：
	mapint> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}
	for (const auto& kv : countMap)
		cout << kv.first << ":" << kv.second << endl;
}

这里优化2的方式仅仅用了[]的运算符重载即可完成，接下来详细讲解[]运算符重载

---

[ ]运算符重载

• [ ]运算符重载函数原型声明：

mapped_type& operator[] (const key_type& k);

• 针对返回类型mapped_type 和 参数类型key_type的定义如下：

成员类型	定义
key_type	The first template parameter (Key)
mapped_type	The second template parameter (T)

• [ ]运算符重载函数的具体源码实现如下：

mapped_type& operator[] (const key_type& k)
{
	return (*((this->insert(make_pair(k, mapped_type()))).first)).second;
}

针对该返回值，其主要是进行了两大步骤：

1. 首先调用insert函数插入键值对返回迭代器ret
2. 通过返回的迭代器ret调用元素值value

对应代码如下：

mapped_type& operator[] (const key_type& k)
{
    //1、调用insert返回迭代器区间
	pairbool> ret = insert(make_pair(k, mapped_type()));
    //2、利用ret调用value值
	return ret.first->second;//return (*(ret.first)).second;
}

前面我们已知mapped_type为第二个模板参数，也就是value，而mapped_type()就是构造了一个匿名对象，接下来主要分两种情况讨论：

1. 如果k在map对象中，则插入失败，返回的bool类型为false，返回的迭代器为k所在结点的迭代器，而迭代器解引用*(ret.first)获得的就是pair，最后再通过pair访问到value值，整体可优化成ret.first->second，这里返回引用的好处为查找k对应v，修改k对应v。
2. 如果k不在map对象中，则插入成功，返回的bool类型为true，返回的迭代器为新插入的k所在结点的迭代器位置，接着调用ret.first获得pair的迭代器，再通过->second获得value，这里返回引用的好处为插入和修改。

接下来回头看看前面统计水果出现次数的代码：

void test_map3()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	mapint> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}
	for (const auto& kv : countMap)
		cout << kv.first << ":" << kv.second << endl;
}

这里就很容易感悟到这里仅仅一行代码完成了主要逻辑，归根揭底在于[ ]运算符重载内部封装了一层insert，这样满足了遇到不同的key值就插入，对应的value更新为1，若遇到相同的key值就查找，对应的value累计++从而统计次数，而这又归功于[ ]运算符重载内部返回引用的缘故。

这里再给出一组[ ]的例子：

void test()
{
	map dict;
	auto ret1 = dict.insert(make_pair("left", "左边"));
	auto ret2 = dict.insert(make_pair("left", "剩余"));
	dict["operator"] = "重载";//插入 + 修改
	dict["left"] = "左边、剩余";//修改
	dict["erase"];//插入
	cout << dict["left"] << endl;//左边、剩余
}

这里就足矣体现出[ ]运算符重载的好处，既可以遇到新key像insert一样插入，又满足了insert未有的功能，查找并修改。

---

find查找函数

• 函数原型如下：

iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

• 原理如下：

根据k值在map中寻找，找到后，返回对应k值位置的迭代器，若未找到，则返回map::end的迭代器。

• 示例：

void test_map()
{
	map dict;
	dict.insert(make_pair("left", "左"));
	dict.insert(make_pair("right", "右"));
	dict.insert(make_pair("front", "前"));
	dict.insert(make_pair("back", "后"));
	string str;
	cin >> str;//输入left
	map::iterator pos = dict.find(str);
	if (pos != dict.end())
	{
		cout << pos->first << " : " << pos->second << endl;//left : 左
	}
	else
	{
		cout << "没找到" << endl;
	}
}

---

erase删除函数

函数原型声明如下：

(1)	void erase (iterator position);
(2)	size_type erase (const key_type& k);
(3) void erase (iterator first, iterator last);

这里和set中的erase原理相册不大，下面直接给出测试用例：

void test_map()
{
	map<int, string> m;
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(3, "three"));
	m.insert(make_pair(4, "four"));
	m.insert(make_pair(5, "five"));
	m.insert(make_pair(6, "six"));
	//指定key值删除
	cout << m.erase(3) << endl;
	map<int, string>::iterator pos = m.find(5);
    //删除迭代器区间
	if (pos != m.end())
	{
		m.erase(pos, m.end());//删除5到6的数字
	}
	for (const auto& kv : m)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}

---

其它函数

• 1、map的容量与元素访问

函数声明	功能简介
empty	检测map中的元素是否为空，是返回true，否则返回false
size	返回map中有效元素的个数

• 2、map中元素的修改

函数声明	功能简介
swap	交换两个map中的元素
clear	清空map中的元素
count	返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

---

总结

• 1、map中的的元素是键值对
• 2、map中的key是唯一的，并且不能修改
• 3、默认按照小于的方式对key进行比较
• 4、map中的元素如果用迭代器去遍历，可以得到一个有序的序列
• 5、map的底层为平衡搜索树(红黑树)，查找效率比较高O(logN)
• 6、支持[]操作符，operator[]中实际进行插入查找。

---

2、multimap

multimap的介绍

• 1、Multimap是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的。
• 2、在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:typedef pair value_type;
• 3、在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
• 4、multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
• 5、multimap在底层用二叉搜索树(红黑树)来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以
重复的。

---

multimap的使用

multimap中的接口可以参考map，功能都是类似的。

注意：

• 1、multimap中的key是可以重复的。
• 2、multimap中的元素默认将key按照小于来比较
• 3、multimap中没有重载operator[]操作（因为multimap允许冗余，导致key和value面临一对多的关系）
• 4、使用时与map包含的头文件相同：

示例：

void test_multimap()
{
	multimap dict;
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "剩余"));
	dict.insert(make_pair("left", "左边"));
}

监视窗口如下：

multimap允许冗余，这也就导致其内部的find和count函数和map中的有所区别，如下：

成员函数count	功能说明
map对象	值为key的元素存在则返回1，不存在则返回0
multimap对象	返回set中值为key的元素的个数

成员函数find	功能说明
map对象	返回键值为key的元素的迭代器位置
multimap对象	返回底层搜索树中序的第一个值为key的元素的迭代器