Map和Multimap

Map和Multimap（下文统称Map）将key/value作为元素进行管理，逻辑上是一种键值映射关系，即数据结构中哈希表。它们可以根据key的排序规则进行自动元素排序，Multimap允许元素重复，而Map不允许。

　　在使用Map和Multimap之前， 必须引入头文件map

	#include
1

在其中，map和multimap在std中被定义为：

template<
    template Key,
    template T,
    template Compare = std::less,
    template Allocator = std::allocator >
> class map;

template<
    template Key,
    template T,
    template Compare = std::less,
    template Allocator = std::allocator >
> class multimap;
1
2
3
4
5
6
7
8
9
10
11
12
13

其中，第一个template，指定了key的类型，第二个template，指定了value的类型，key和value必须满足以下条件——
　　1. Key和value必须是可复制（copyable）的和可移动的（movable，移动语义）；
　　2. 对于指定的排序准则而言，key必须是可比较的（comparable）。
　　第三个template，用来指定排序准则。这点与Set相同，排序遵循strict weak ordering准则，如果没有指定，则默认为less<>排序准则。
　　第四个template则是指定内存模型，默认采用allocator，由C++标准库提供。
　　举个例子，我们使用multimap定义一个 映射关系——

	multimap mmp{
		pair(1,"jack"),
		pair(2,"jason"),
		pair(2,"joe"),
		pair(3,"stack"),
		{5,"test" },{5,"test"},{5,"test"}
	};

	for (auto elem : mmp) {
		cout << elem.first << " " << elem.second << endl;
	}
1
2
3
4
5
6
7
8
9
10
11

　　multimap的初始化必须是成双成对，可以用std::pair，或者直接使用大括号。然后你会发现，multimap会根据key值自动进行排序。

Map和Multimap的能力

和所有的关联式容器一样，Map和Multimap的内部是以平衡二叉树来实现的，Map和Set具有很多相似之处，Map具有和Set几乎相同的能力和操作，不同的是，其内部管理的元素是pair，且Map可作为关联数组来访问。

　　Map会根据元素的Key进行排序，如果已知元素的Key来查找元素，效率相当卓越。但如果根据value进行查找，效率将大打折扣。与Set相同，自动排序的规则，限制了其不能改变容器内的元素的Key（但是value可以）——
　　1. 修改元素的key，需要先移除，再插入；
　　2. 从迭代器的角度而言，Key是常量，无法通过迭代器修改Key；
　　3. value不作为排序准则，不会影响既定顺序，因此非常量value可以直接修改。

Map的操作函数

Map的操作函数满足通用STL容器标准，同时，Map也具有一定自己的特色——

创建、复制和销毁（Create、Copy and Destroy）

map的构造函数和析构函数，如下表所示——

序号

操作

效果

1

map c

Default构造函数，产生一个空map，没有任何元素

2

map c

建立一个空的map，并以op为排序规则

3

map c(c2)
map c=c2

Copy构造函数，建立c2同型map并成为c2的一份副本，该复制是深度复制

4

map c(rv)
map c=rv

Move构造函数，rv是一个map右值引用，那么这里的构造函数是一个Move构造函数，建立一个新的map，取右值内容（C++11新特性）

5

map c(beg,end)

建立一个map，并以迭代器所指向的区间[beg,end）作为元素值，该构造函数支持从其他容器类型接收元素

6

map c(beg,end,op)

建立一个map，并以迭代器所指向的区间[beg,end）作为元素值，同时以op作为排序准则

7

map c(initlist)
map c=initlist

建立一个map，以初值列initlist元素为初值（C++11新特性）

8

c.~map()

销毁所有元素，释放内存

其中，上表中map的形式可以置换为以下任意一种——

序号

map

效果

1

map

使用默认排序准则，以Key-Val作为元素类型的map

2

map

使用op作为排序准则，以Key-Val作为元素类型的map

3

multimap

使用默认排序规则，以Key-Val作为元素类型的multimap

4

multimap

使用op作为排序准则，以Key-Val作为元素类型的multimap

非更易型操作（Nonmodifying Operation）

Map也提供元素比较、查询大小等操作——

序号

操作

效果

1

c.empty()

容器为空返回true，不为空返回false，相当于size()==0

2

c.size()

返回当前元素的个数

3

c.max_size()

返回元素个数之最大可能量

4

c1==c2

对每个元素调用c1==c2，全部相等返回true

5

c1！=c2

只要有一个元素相等，返回true，相当于!(c1==c2)

6

c1>c2,c1>=c2,c1

同上，依次类推

7

c.key_comp()

返回比较准则

8

c.value_comp()

返回针对value的比较准则

map的元素比较只适用于类型相同的元素，这里的类型相同包括Key类型，Value类型和排序准则，这3个类型只要有一个不相同，就无法进行比较，否则会编译错误，比如——

	map m1;
	map m2;
	if (m1 == m2) {

	}
1
2
3
4
5

特殊查找函数（Special Search Operation）

Map在元素查找方面与Set完全相同——

序号

map

效果

1

c.count(val)

返回Key为val的个数

2

c.find(val)

返回Key为val的第一个位置，注意这里返回的是一个迭代器

3

c.lower_bound(val)

返回Key为val第一个可插入的位置，即第一个元素值<=val的位置

4

c.upper_bound(val)

返回Key为val最后一个可插入的位置，即第一个元素值

5

c.equal_range(val)

返回Key为val可以被插入的第一个位置和最后一个位置的范围

值得一提的是，Map所有的查找函数都是基于Key的操作，如果想根据value进行操作，则会麻烦很多。比如使用find函数进行value的查找，只能进行遍历进行查找——

	multimap mmp{
		pair(1,"jack"),
		pair(2,"jason"),
		pair(2,"joe"),
		pair(3,"stack"),
		{5,"test" },{5,"test"},{5,"jason"}
	};

	for (auto elem : mmp) {
		if (elem.second == "jason") {
			cout << "Key = " << elem.first << endl;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

赋值（Assignment）

Map只提供任何容器都提供的基本赋值操作：

序号

操作

效果

1

c = c2

将c2的全部元素赋值给c

2

c = rv

将rv右值语义所有元素以Move assign的方式赋值给c(C++11新特性)

3

c = initlist

将初值列所有元素赋值给c（C++11新特性）

4

c1.swap(c2)
swap(c1,c2)

置换c1和c2的数据

同样，赋值操作必须满足两端容器具有相同的类型，包括Key、Value和比较准则。

迭代器和元素访问（Iterator Function and Element Access）

Map和Multimap不提供元素访问，所以只能采用range-based for循环，迭代器的使用就尤为常见，尤其注意的是，在使用迭代器的时候，Key是作为一种常量处理，因此，这意味着，无法通过迭代器更改Key，这也保证了排序的顺序：

序号

操作

效果

1

c.begin()

返回一个bidirectional iterator指向第一个元素

2

c.end()

返回一个bidirectional iterator指向的之后一个元素

3

c.cbegin()

返回一个const bidirectional iterator指向的第一个元素（C++11新特性）

4

c.cend()

返回一个const bidirectional iterator指向的最后一个元素（C++11新特性）

5

c.rbegin()

返回一个反向迭代器（reverse iterator）指向的第一个元素

6

c.rend()

返回一个reverse iterator指向的最后一个元素

7

c.crbegin()

返回一个const reverse iterator指向的第一个元素（C++新特性）

8

c.crend()

返回一个const reverse iterator指向的最后一个元素（C++11新特性）

插入和删除（Inserting and Removing）

Map的所有插入和移除操作如下表所示——。

序号

操作

效果

1

c.insert(val)

插入val元素，并返回新元素的位置，不论是否成功

2

c.insert(pos,val)

在iterator指向的pos位置的前方插入一个元素val的副本，并返回新元素的位置（pos只是一个提示，该提示恰当会加快查找过程）

3

c.insert(beg,end)

插入区间[beg,end)内所有元素的副本，无返回值

4

c.insert(initilist)

插入initilist的所有元素的副本，无返回值（C++11新特性）

5

c.emplace(args…)

插入一个以args为初值的元素，并返回新元素的位置，无论是否成功（C++11新特性）

6

c.emplace_hint(pos,args…)

插入一个以args为初值的元素，并返回新元素的位置，pos是个位置提示，如果恰当，将大大提高插入效率

7

c.erase(val)

移除与val相等的所有元素，返回被移除的个数

8

c.erase(pos)

移除迭代器iterator指向的元素，无返回值

9

c.erase(beg,end)

移除区间[beg,end)内的所有元素，无返回值

10

c.clear()

移除所有元素，并将容器清空

注意，Map的所有插入操作都是基于pari的，即必须成双成对——

	multimap mmp{
		pair(1,"jack"),
		pair(2,"jason"),
		pair(2,"joe"),
		pair(3,"stack"),
		{5,"test" },{5,"test"},{5,"jason"}
	};

	mmp.insert(pair(10,"hello"));

	for (multimap::iterator it = mmp.begin(); it != mmp.end();it++) {
		cout << it->first << "," << it->second << endl;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

异常处理

就异常处理而言，Map具有Set完全相同的规则，即对于单一元素的操作，遵循“要么成功，要么没有任何作用”的原则，对于多元素插入操作，在保证排序准则不抛出异常的情况下，同样遵循这一点。

总结

作为关联容器，Map具有Set几乎完全相同的接口和函数名，甚至使用场景和方式都一模一样。最大的不同是Map是一种key-value关系，而Set只是一种value集合，从这种角度来看，Set可以看做是Map中key=value的特殊情况。
　　Map的使用场景比Set更广泛，map可以作为一种索引而使用，multiset作为数据字典而使用，两者都是为了提高查询效率而存在，毕竟关联容器内部都是以平衡二叉树实现，先天决定了其独一无二的高效查询特性。