开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C++——map 和 multimap -> 正文阅读

[C++知识库]C++——map 和 multimap

?
?

??Map 和 multimap 将 key/value pair 当作元素进行管理。它们可根据 key 的排序准则自动为元素排序。Multimap 允许重复元素，map 不允许，如下图所示。
map和multimap
map 和 multimap 包含在头文件中：

#include <map>

在其中，map 和 multimap 被定义为命名空间 std 内的 class template：

namespace std {
	template <typename Key, typename T,
				typename Compare = less<Kay>,
				typename Allocator = allocator<pair<const Key, T> > >
			class map;
	template <typename Key, typename T,
				typename Compare = less<Kay>,
				typename Allocator = allocator<pair<const Key, T> > >
			class multimap;
}

第一个 template 实参将成为元素的 key 类型，第二个 template 实参将成为元素的 value 类型。Map 和 multimap 的元素类型 Key 和 T 必须满足以下两个条件：

Key 和 value 都必须是 copyable (可复制的)或 movable (可搬移的)。
对指定的排序准则而言，key 必须是comparable (可比较的)。

注意，元素类型(value_type)是个 pair < const Key，T>。
第三个 template 实参可有可无，用来定义排序准则。和 set 一样，这个排序准则必须定义为 strict weak ordering。元素的次序由它们的 key 决定和 value 无关。排序准则也可以用来检查相等性：如果两个元素的 key 彼此都不小于对方，两个元素被视为相等。
如果用户未传入某个排序准则，就使用默认的 less<> 排序准则——以 operator < 进行比较。
??关于multimap，我们无法预测所有“拥有等价 key ”的元素的彼此次序，不过它们的次序是稳固不变的。C++11保证 multimap 的安插和抹除动作都会保留等价元素的相对次序。
??第四个 template 实参也是可有可无，用来定义内存模型。默认的内存模型是 allocator，由 C++ 标准库提供。

??“排序准则”，必须定义 strict weak ordering，其意义如下：

必须是非对称的
对 operator < 而言，如果 x < y 为 true，则 y < x 为 false。
对判断式（predicate）op() 而言，如果 op(x, y) 为 true，则 op(y, x) 为 false。
必须是可传递的
对 operator < 而言，如果 x < y 为 true 且 y < z 为 true，则 x < z 为 true。
对判断式 op() 而言，如果 op(x, y) 为 true 且 op(y, z) 为 true，则 op(x, z) 为 true。
必须是非自反的
对 operator < 而言，x < x 永远为 false。
对判断式 op() 而言，op(x, x) 永远为 false。
必须有等效传递性。大体意义是：如果 a 等于 b 且 b 等于 c，那么 a 必然等于 c。
这意味着对于操作符 <，若 !(a<b) && !(b<a) 为 true 且 !(b<c) && !(c<b) 为 true，那么 !(a<c) && ! (c<a) 亦为 true。
这也意味着对于判断式 op()，若 op(a, b)、 op(b, a)、 op(b, c)和 op(c, b) 都为 false，那么 op(a, c)和 op(c, a) 为 false。

?
?

结构

和其他所有关联式容器一样， map/multimap 通常以平衡二叉树完成（红黑树），如下图所示。C++standard 并未明定这一点，但是从 map和 multimap各项操作的复杂度自然可以得出这一结论。通常set、 multiset、map 和 multimap 使用相同的内部结构，因此，你可以把因 set 和 multiset 视为特殊的 map 和 multimap，只不过 set 元素的 value 和 key 是同一对象。因此，map 和 multimap 拥有 set 和 multiset 的所有能力和所有操作。当然，某些细微差异还是有的：首先，它们的元素是 key/value pair，其次，map 可作为关联式数组（associative array）来运用。
内部结构

??Map 和 multimap 会根据元素的 key 自动对元素排序。这么一来，根据已知的 key 查找某个元素时就能够有很好的效率，而根据已知 value 查找元素时，效率就很糟糕。“自动排序”这一性质使得 map 和 multimap 身上有了一条重要限制：你不可以直接改变元素的 key，因为这会破坏正确次序。要修改元素的 key，必须先移除拥有该 key 的元素，然后插入拥有新 key/value 的元素。从迭代器的观点看，元素的 key 是常量。至于元素的 value 倒是可以直接修改，当然前提是 value 并非常量。

?
?

构造操作

操作	描述
map c	Default 构造函数,建立一个空 map/multimap，不含任何元素
map c(op)	建立一个空 map/multimap，以 op 为排序准则
map c(c2)	Copy 构造函数，为相同类型之另一个 map/multimap 建立一份拷贝，所有元素均被复制
map c = c2	Copy 构造函数，为相同类型之另一个 map/multimap 建立一份拷贝，所有元素均被复制
map c(rv)	Move 构造函数，建立一个新的 map/multimap，有相同类型，取 rvalue rv 的内容（始自C++11）
map c = rv	Move 构造函数，建立一个新的 map/multimap，有相同类型，取 rvalue rv 的内容（始自C++11）
map c(beg, end)	以区间 [beg, end) 内的元素为初值，建立一个 map/multimap
map c(beg, end, op)	以区间 [beg, end) 内的元素为初值，并以 op 为排序准则，建立一个 map/multimap
map c(initlist)	建立一个 map/multimap，以初值列 initlist 的元素为初值（始自C++11）
map c = initlist	建立一个 map/multimap，以初值列 initlist 的元素为初值（始自C++11）
c.~map()	销毁所有元素，释放内存
其中，map 可为下列形式：
map	描述
–	–
map< Key, Val >	一个 map，以 less<>（operator <）为排序准则
map< Key, Val, Op >	一个 map，以 Op 为排序准则
multimap< Key, Val >	一个 multimap，以 less<>（operator <）为排序准则
multimap< Key, Val, Op >	一个 multimap，以 Op 为排序准则

#include <iostream>
#include <map>
#include <string>
using namespace std;

struct op{
	bool operator() (const string& a, const string& b) const{
		return a > b;
	}
};

int main(){
	map<string, float> c;
	c.insert(pair<string, float>("qw", 6.6));
	c.insert(pair<string, float>("qy", 6.6));
	c.insert(pair<string, float>("qwjy", 66.6));
	map<string, float> c1;
	map<string, float> c2(op);
	map<string, float> c3(c);
	map<string, float> c4 = c;
	 
	
	
	printf("map_c4:\n");
	for(map<string, float>::iterator p = c4.begin(); p != c4.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	
	return 0;
}

运行结果

?
?

非更易型操作

操作	描述
c.key_comp()	返回“比较准则”(comparison criterion)
c.value_comp()	返回针对 value 的“比较准则”（那是个对象，用来在一个 key/value pair 中比较 key）
c.empty()	返回是否容器为空（相当于 size() == 0 但也许较快）
c.size()	返回目前的元素个数
c.max_size()	返回元素个数之最大可能量
c1 == c2	返回 c1 是否等于 c2（对每个元素调用==）
c1 != c2	返回 c1 是否不等于 c2（相当于 !(c1 == c2)）
c1 < c2	返回 c1 是否小于 c2
c1 > c2	返回 c1 是否大于 c2（相当于c2 < c1）
c1 <= c2	返回 c1 是否小于等于 c2（相当于!(c2 < c1)）
c1 >= c2	返回 c1 是否大于等于 c2（相当于!(c1 < c2)）

#include <iostream>
#include <map>
#include <string>
using namespace std;

struct op{
	bool operator() (const string& a, const string& b) const{
		return a > b;
	}
};

int main(){
	map<string, float, op> c;
	c.insert(pair<string, float>("qw", 6.6));
	c.insert(pair<string, float>("qy", 6.6));
	c.insert(pair<string, float>("qwjy", 66.6));
	map<string, float, op> c1 = c;
	map<string, float, op> c2;
	c2.insert(pair<string, float>("qwjy", 66.6));
	c2.insert(pair<string, float>("qy", 6.6));
	c2.insert(pair<string, float>("qw", 6.6));
	
	printf("map_c:\n");
	for(map<string, float>::iterator p = c.begin(); p != c.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	printf("key_comp: %s\n", c.key_comp()("qw", "qa") ? "true" : "false");
	printf("key_comp: %s\n", c.key_comp()("qa", "qw") ? "true" : "false");
	printf("value_comp: %s\n", c.value_comp()(pair<string, float>("qw", 0.6), pair<string, float>("qy", 66.6)) ? "true" : "false");
	printf("value_comp: %s\n", c.value_comp()(pair<string, float>("qy", 0.6), pair<string, float>("qw", 66.6)) ? "true" : "false");
	printf("empty: %s\n", c.empty() ? "true" : "false");
	printf("size: %d\n", c.size());
	printf("max_size: %lld\n", c.max_size());
	printf("c1 == c2: %s\n", c1 == c2 ? "true" : "false");
	return 0;
}

运行结果

?
?

查找操作

操作	描述
c.count(val)	返回“key 为 val”的元素个数：如果 key 存在于容器中，则返回1，因为映射仅包含唯一 key 。如果键在Map容器中不存在，则返回0。
c.find(val)	返回“key 为 val”的第一个元素，找不到就返回 end()。该函数返回一个迭代器或常量迭代器，该迭代器或常量迭代器引用键在映射中的位置。
c.lower_bound(val)	返回“key 为 val”之元素的第一个可安插位置，也就是“key >= val”的第一个元素位置
c.upper_bound(val)	返回“key 为 val”之元素的最后一个可安插位置，也就是“key > val”的第一个元素位置
c.equal_range(val)	返回“key 为 val”之元素的第一个可安插位置和最后一个可安插位置，也就是“key == val”的元素区间

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
	map<string, float> c;
	c.insert(pair<string, float>("qw", 6.6));
	c.insert(pair<string, float>("qy", 6.6));
	c.insert(pair<string, float>("qwjy", 66.6));
	
	printf("map_c:\n");
	for(map<string, float>::iterator p = c.begin(); p != c.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	printf("count: %d\n", c.count("qw"));
	printf("find: key-%s value-%.1f\n", c.find("qwjy")->first.c_str(), c.find("qwjy")->second);
	printf("lower_bound: key-%s value-%.1f\n", c.lower_bound("q")->first.c_str(), c.lower_bound("q")->second);
	printf("upper_bound: key-%s value-%.1f\n", c.upper_bound("qw")->first.c_str(), c.upper_bound("qw")->second);
	cout << "equal_range: " << c.equal_range("qw").first->first << "\t" <<
								c.equal_range("qw").second->first << endl;
	return 0;
}

运行结果

?
?

赋值

操作	描述
c = c2	将 c2 的全部元素赋值给 c
c = rv	将 rvalue rv 的所有元素以 move assign 方式给予 c (始自C++11)
c = initlist	将初值列 initlist 的所有元素赋值给 c (始自C++11)
c1.swap(c2)	置换 c1 和 c2 的数据
swap(c1, c2)	置换 c1 和 c2 的数据

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
	map<string, float> c;
	c.insert(pair<string, float>("qw", 6.6));
	c.insert(pair<string, float>("qy", 6.6));
	c.insert(pair<string, float>("qwjy", 66.6));
	map<string, float> c1 = c;
	map<string, float> c2;
	
	printf("map_c1:\n");
	for(map<string, float>::iterator p = c1.begin(); p != c1.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	swap(c1, c2);
	printf("map_c2:\n");
	for(map<string, float>::iterator p = c2.begin(); p != c2.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	return 0;
}

运行结果

?
?

元素访问

??关联式容器并不提供元素的直接访问，你必须依靠 range-based for 循环或迭代器进行访问。但 map 是个例外，提供了如下表所述的方法直接访问元素。

先看看 range-based for 循环（C++11新特性）：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
	map<string, float> coll;
	coll.insert(pair<string, float>("qw", 6.6));
	for(auto elem : coll){
		cout << "key: " << elem.first << "\t"
				<< "value: " << elem.second << endl;
	}
	return 0;
}

其中的 elem 是个 reference，指向“容器 coll 中目前正被处理的元素”。因此 elem 的类型是 pair<string, float>。表达式

elem.first 取得元素的 key，而表达式 elem.second 取得元素的 value。

下面看看迭代器访问（C++11之前使用的方法）：（迭代器操作的详细操作方法见下节）

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
	map<string, float> coll;
	coll.insert(pair<string, float>("qw", 6.6));
	
	for(map<string, float>::iterator p = coll.begin(); p != coll.end(); p ++)
		cout << "key: " << p->first << "\t"
				<< "value: " << p->second << endl;
	return 0;
}

在这里，迭代器 pos 被用来迭代穿越整个由“以 const string 和 float 组成的 pair”所构成的序列，你必须使用 operator -> 访问每次访问的那个元素的 key 和 value。所以 key （first）值是无法改变的，会引发错误；value（second）值是可以改变的。
??如果你一定得改变元素的 key，只有一条路:以一个“value 相同”的新元素替换掉旧元素。
运行结果

?
?

操作	描述
c[key]	安插一个带着 key 的元素——如果尚未存在于容器内。返回一个 reference 指向带着 key 的元素( only for nonconstant maps )
c.at(key)	返回一个 reference 指向带着 key 的元素(始自C++11)
??at() 会依据它收到的“元素的 key”取得元素的 value；如果不存在这样的元素则抛出 out_of_range 异常。
??至于operator [ ]，其索引就是 key。这意味着 operator [ ] 的索引可能属于任何类型，不一定是整数。如此的接口就是所谓的关联式数组(associative array)接口。“operator [ ] 的索引类型不必然是整数”。
??如果你选择某 key 作为索引，容器内却没有相应元素，那么 map 会自动安插一个新元素，其 value 将被其类型的 default 构造函数初始化。因此，你不可以指定一个“不具 default 构造函数”的 value 类型。注意，基础类型都有一个 default 构造函数，设立初值 0。

提供类似数组的访问方式有好也有坏：

优点是你可以通过更方便的接口对map安插新元素。例如：

map<string, float> coll;
coll["otto"] = 6.6;

语句：coll[“otto”] = 6.6; 处理过程如下：

处理 coll[“otto”]：
①如果存在 key 为"otto"的元素，上式会返回元素的 reference。
②如果没有任何元素的 key 是"otto"，上式便为 map 自动安插一个新元素，令其 key 为"otto"，其 value 则以, default 构造函数完成，并返回一个 reference 指向新元素。
将 6.6 赋值给 value：
接下来便是将 7.7 赋值给上述刚刚诞生的新元素。

这样, map 之内就包含了一个 key 为"otto"的元素，其 value 为 7.7。

缺点是你有可能不小心误置新元素。例如以下语句可能会做出意想不到的事情：

cout << coll["ottto"];

它会安插一个 key 为"ottto"的新元素，然后打印其 value，默认值是 0。然而按道理它其实应该产生一条报错信息，告诉你你把"otto"拼写错了。
??同时亦请注意，这种元素安插方式比惯常的 map 安插方式慢，原因是新元素必须先使用 default 构造函数将 value 初始化，而该初值马上又被真正的 value 覆盖。

?
?

迭代器相关操作

操作	描述
c.begin()	返回一个 bidirectional iterator 指向第一元素
c.end()	返回一个 bidirectional iterator 指向最末元素的下一位置
c.cbegin()	返回一个 const bidirectional iterator 指向第一元素(始自C++11)
c.cend()	返回一个 const bidirectional iterator 指向最末元素的下一位置(始自C++11)
c.rbegin()	返回一个反向的（reverse) iterator 指向反向迭代的第一元素
c.rend()	返回一个反向的（reverse) iterator 指向反向迭代的最末元素的下一位置
c.crbegin()	返回一个 const reverse iterator 指向反向迭代的第一元素(始自C++11)
c.crend()	返回一个 const reverse iterator 指向反向迭代的最末元素的下一位置(始自C++11)

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
	map<string, float> coll;
	coll.insert(pair<string, float>("qw", 6.6));
	coll.insert(pair<string, float>("qy", 6.6));
	coll.insert(pair<string, float>("qwjy", 66.6));
	
	for(map<string, float>::iterator p = coll.begin(); p != coll.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	
	printf("\n\n");
	for(map<string, float>::reverse_iterator p = coll.rbegin(); p != coll.rend(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	return 0;
}

运行结果

?
?

插入和移除

操作	描述
c.insert(val)	安插一个 val 拷贝，返回新元素位置，不论是否成功——对 map 而言
c.insert(pos , val)	安插一个 val 拷贝，返回新元素位置（pos 是个提示，指出安插动作的查找起点。若提示恰当可加快速度)
c.insert(beg , end)	将区间 [beg, end) 内所有元素的拷贝安插到 c (无返回值)
c.insert(initlist)	安插初值列 initlist 内所有元素的一份拷贝(无返回值；始自C++11)
c.emplace(args . . .)	安插一个以 args 为初值的元素，并返回新元素的位置，不论是否成功——对 map 而言(始自C++11)
c.emplace_hint(pos , args . . .)	安插一个以 args 为初值的元素，并返回新元素的位置(pos 是个提示，指出安插动作的查找起点。若提示恰当可加快速度)
c.erase(val)	移除“与 val 相等”的所有元素，返回被移除的元素个数
c.erase(pos)	移除 iterator 位置 pos 上的元素，无返回值
c.erase(beg , end)	移除区间 [beg, end) 内的所有元素，无返回值
c.clear()	移除所有元素，将容器清空

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
	map<string, float> c;
	c.insert(pair<string, float>("qw", 6.6));
	c.insert(pair<string, float>("qy", 6.6));
	c.insert(pair<string, float>("qwjy", 66.6));
	
	
	printf("map_c:\n");
	for(map<string, float>::iterator p = c.begin(); p != c.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	c.insert(c.end(), pair<string, float>("qz", 666.6));
	printf("c插入map_c:\n");
	for(map<string, float>::iterator p = c.begin(); p != c.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	map<string, float> c1(c.begin(), c.end());
	printf("c1插入c中所有元素-map_c1:\n");
	for(map<string, float>::iterator p = c1.begin(); p != c1.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	c1.erase("qw");
	printf("c1删除‘qw’-map_c1:\n");
	for(map<string, float>::iterator p = c1.begin(); p != c1.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	c1.erase(c1.begin());
	printf("删除c1第一个-map_c1:\n");
	for(map<string, float>::iterator p = c1.begin(); p != c1.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	c1.erase(c1.begin(), c1.end()) ;
	printf("删除c1第一个到最后一个-map_c1:\n");
	for(map<string, float>::iterator p = c1.begin(); p != c1.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	
	c.clear();
	printf("清空c-map_c:\n");
	for(map<string, float>::iterator p = c.begin(); p != c.end(); p ++)
		cout << "key: " << p->first << "\t\t"
				<< "value: " << p->second << endl;
	printf("\n\n");
	return 0;
}

运行结果

?
?

自定义排序规则

按 key 值排序

默认按照 less< key > 升序排列
定义 map 时，用greater< key >实现按 key 值降序排列

map<int,int,greater<int> > c;

可以通过定义结构体（或类），并在其中重载()运算符，来自定义排序函数。然后，在定义set的时候，将结构体加入其中例如如下代码中的 map<int, int, op> 或 map< int, int > c(op)。

//结构体
struct op{
	bool operator() (const int& a, const int& b) const{
		return a > b;
	}
};
//类
class op1{
public:
	bool operator() (const int& a, const int& b) const{
		return a > b;
	}
};

若 key 为结构体，也可以在自定义结构体中重载< 也可以实现默认排序，示例代码如下：

struct Student{
	string id;
	string college;
	int age;
	
	bool operator <(const Student& a) const{
		if(college != a.college)
			return college < a.college;
		else if(id != a.id)
			return id < a.id;
		else
			return age < a.age;
			
	}
};

?
?

按 value 值排序

map 无法使用 sort 函数排序，所以将 map 存入可以用 sort 函数排序的容器之中。

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<string, float> PAIR;

bool cmp(const PAIR& a, const PAIR& b){
	return a.second > b.second;
}

int main(){
	map<string, float> c;
	c.insert(pair<string, float>("qw", 6.6));
	c.insert(pair<string, float>("qy", 16.6));
	c.insert(pair<string, float>("qwjy", 66.6));
	
	vector<PAIR> v(c.begin(), c.end());
	sort(v.begin(), v.end(), cmp);
	 
	for(int i = 0; i < v.size(); i ++)
		printf("key: %s    value: %.1f\n", v[i].first.c_str(), v[i].second);
	return 0;
}