map型容器是（键-值）对的集合。map型容器通常可理解为关联数组（associative ar-ray），可使用键作为下标来获取对应的值，类似于内置数组类型。关联的本质在于元素的值与某个特定的键相联系，而不是通过在数组中的位置来实现关联的。
总而言之，map是由许多对的键值组成的排序结构体，且键值是独一无二的。
multimap型容器和map型容器基本是一致的。只是前者允许重复元素，而后者不允许。
map型容器和multimap型容器的示意图如图3-33所示。
图3-33 map型容器和multimap型容器的示意图
在STL中，这两种型别的模板为：
和
第一个template参数被当作容器中元素的key（键值），第二个template参数被当作元素的value（实值）。前两个参数键值和实值必须具备可赋值和可复制的性质。并且由于容器内部要排序，因此键值必须是可比较的。第三个参数可有可无，用于定义排序准则。元素的顺序仅由键值决定，和实值是无关的。默认排序准则是“less＜＞”。
由以上内容可知，map对象可以使程序按照次序存储一组数值。每个元素均由一个键实现排序和检索。在上一节介绍的set/multiset型容器中，元素既作为键值，又作为实值。而在map/multimap型容器中，键值和实值是以“数据对”（pair）的形式出现的。
1.map和multimap基础
使用map和multimap型容器时，必须包含头文件＜map＞。在内存中，map和multimap的对象均是以“数据对”的形式存放在二叉树中的。
（1）map和multimap的定义和初始化
map型容器和multimap型容器的构造函数见表3-1。
表3-1 map型容器和multimap型容器的构造函数
map型容器和multimap型容器的形式见表3-2。
表3-2 map型容器和multimap型容器的形式
通过学习上述内容，读者基本可以实现对map的定义。例如，
通常定义排序准则有两种方法：以模板参数定义；以构造函数参数定义。这些在表3-1和表3-2中已经有所体现，下面进行简单的阐述。
1）使用模板参数定义排序准则。
此时，排序准则是型别的一部分。而实际的排序准则是容器产生的函数对象（即仿函数）。
2）以构造函数参数定义排序准则。以构造函数参数定义排序准则时，只有当构造函数被执行时，排序准则才有效，即执行时才能获得排序准则，并且程序还可应用到多种的排序准则。
下面以例3-32来阐述以上内容。
例3-32
例3-32的执行效果如图3-34所示。
图3-34 例3-32的执行效果
总结
例3-22对map/multimap的多种定义形式均进行了尝试。在输出函数中，还用了格式化输出的方法。
（2）map的容量
map型容器和multimap型容器定义了两个成员函数size（）和max_size（），用来确定map型容器和multimap型容器中数据成员的数量。其原型为：
上述两个函数的使用方法见例3-33。
例3-33
例3-33的执行效果如图3-35所示。
图3-35 例3-33的执行效果
2.map和multimap型容器的基本成员函数
（1）判断容器是否为空
判断一个map/multimap型容器是否为空是很重要的。如果map/multimap型容器为空，成员函数empty（）返回true。其原型为：
（2）遍历容器
map和multimap型容器不支持元素直接存取。元素的存取需要经过迭代器实现，并且map和multimap的迭代器均是双向迭代器。此类成员函数包括begin（）、end（）、rbegin（）和rend（）。其函数原型为：
下面以例3-34为例，说明上述4个函数的使用。
例3-34
例3-34的执行效果如图3-36所示。
总结
例3-34主要讲述了4种和迭代器相关函数的使用方法。请读者关注数据类型pair的使用方法。
3.map和multimap的高级编程
map/multimap型容器还提供各种功能相应的成员函数，例如插入、删除、交换、统计元素个数统计、查找元素、元素的随机访问、元素大小比较以及如何获取内存配置器。
（1）map/multimap的插入和删除
map/multimap型容器的成员函数insert（）可用以插入一个对象、一个对象的若干副本或者某个范围内的对象。insert（）函数可把一个或多个元素插入到迭代器指示的位置。所插入的元素将出现在迭代器指示的位置之前。其原型为：
图3-36 例3-34的执行效果
第一种形式的功能是将元素x插入到map的末尾，第二种形式的功能是将元素x插入到迭代器it之前，第三种形式的功能是将迭代器（first，last）指定范围的元素插入到map中。
erase（）函数可以用来删除由一个迭代器或键值指定的元素，也可以删除某个范围的元素。
其原型为：
第一种形式的功能是将迭代器it所指向的元素删除；第二种形式的功能是将迭代器（first，end）所指范围中的元素全部删除；第三种形式的功能是将元素key删除。
此外，map型容器也提供了成员函数clear（）。其原型为：
clear（）函数可以删除容器中的所有元素，并且比erase（）函数功能强大且更加灵活。clear（）函数等效于：
(www.xing528.com)
下面使用例3-35来详细讲解对map/multimap型容器的插入和删除操作。
例3-35
例3-35的执行效果如图3-37所示。
图3-37 例3-35的执行效果
（2）元素交换
map和multimap型容器还提供了swap（）函数，用以实现元素交换。参与交换的两个对象必须类型一致。swap（）函数的原型为：
无论是在map型容器中还是在multimap型容器中，swap（）函数的使用方法是一致的。在实际编程中，需要把两个变量进行交换。swap（）函数一般包括两种形式：swap（m1，m2）和m1.swap（m2）。值得注意的是，第二种形式只是容器m1的内容发生改变，容器m2中的元素不变。在例3-35的基础上进行修改，即得到例3-36。
例3-36
之后，即可实现容器m1和容器m2之间的内容交换。
（3）元素个数统计、查找元素和元素的随机访问
实现元素个数统计功能的函数是count（）。count（）函数的功能是返回元素在map/multi- map型容器中重复出现的次数。map型容器中的元素具有唯一性，不能包含重复的元素。并且count（）函数的返回值只有两个：“0”或者“1”。对于multimap型容器，count（）函数的功能和map型容器中是一致的，两者的区别在于：multimap型容器中允许出现重复元素，count（）函数的返回值不仅局限于0和1，还会返回元素的重复个数。count（）函数的原型为：
实现查找元素功能的函数是find（）。其功能是返回指向key的迭代器，如果该迭代器定义的是常迭代器，返回的类型是const_iterator。若和键值key对应的元素不存在，则函数返回迭代器end（）。还可以使用STL的find（）和find_if（）函数。这两个函数可以使用迭代器。通常第一个迭代器指明开始处理的位置，第二个迭代器指明停止处理的位置。并且第二个迭代器指向的元素不被处理。对于multimap型容器，其中允许存在多个相同的元素。在使用find（）函数时，返回的是所查找到第一个出现的元素迭代器。其原型为：
实现元素的随机访问功能的函数包括upper_bound（）、lower_bound（）以及equal_range（）。
equal_range（）函数实现的功能是返回容器中元素上下限的两个迭代器，由于迭代器是常迭代器，因此equal_range（）函数可以返回map/multimap型容器元素中上下限的两个常迭代器，若元素没找到，则返回最后一个元素，函数返回的是迭代器end（）。函数返回的两个迭代器中，第一个迭代器和lower_bound（）函数的返回值相同；第二个返回值和upper_bound（）函数的返回值一样。
upper_bound（Key key）函数返回值是返回指向大于key元素的迭代器；lower_bound（）函数的返回值是指向key前面元素的迭代器，即key是“界限”。
上述3个函数的原型为：
下面以例3-37讲解上述几个函数的使用方法。
例3-37
例3-37的执行效果如图3-38所示。
图3-38 例3-37的执行效果
（4）元素大小比较
在序列式容器中，可采用＜、＞等算数操作符进行容器大小比较。map/multimap型容器同样提供了一系列算数或逻辑运算符：＝＝，＜，！＝，＞，＞＝，＜＝，还提供了特殊的函数，主要包括key_comp（）和value_comp（）。
1）键值比较。key_comp（）函数可用于进行键值的比较。其返回值为key_comp类型。key_comp决定了map中元素的排列顺序。key_comp（）函数的原型为：
下面使用例3-38对key_comp（）函数的使用方法进行阐释。
例3-38
在例3-38中，由于容器m1是按less规则排列，容器m2是按greater规则排列，因此kc1（）函数的返回值为true，kc2（）函数的返回值为false。
图3-39 例3-38的执行效果
2）实值比较。value_comp（）函数可用于进行实值的比较。其返回值为value_compare类型。value_compare决定了map中元素的排列顺序。value_compare（）函数的原型为：
其用法和key_comp（）函数类似，即先定义键值类型vc1和vc2，然后通过vc1和vc2进行排列顺序的测试。对于按less规则排序的map/multimap型容器，按greater规则排序的map/multimap型容器，该函数将分别产生不同的返回值。
例3-39
例3-39的执行效果如图3-40所示。
图3-40 例3-39的执行效果
总结
例3-38和例3-39主要讲述了和排序相关的两个函数key_comp（）和value_comp（）。这两个函数的使用方法大体类似，其主要作用是判断容器中元素的排序规则。
（5）获取内存配置器
get_allocator（）函数用于返回map型容器或multimap型容器的内存配置器。内存配置器类似于指针的首地址，用于指明对象的初始存储位置。因此，获取容器的内存配置器至关重要。get_allocator（）函数的原型为：
该函数只能读取内存配置器，不能改变内存配置器，即不能改变容器变量所存储的位置。下面使用例3-40对内存配置器进行简单介绍。
例3-40
例3-40的执行效果如图3-41所示。
图3-41 例3-40的执行效果
（6）map作为关联式数组
通常关联式容器不提供元素的直接存取，必须依靠迭代器。但map型容器提供下标操作符，支持元素的直接存取。下标操作符的索引值并非元素整数位置，而是元素的键值key。使用键值索引有时会带来诸多问题。例如，容器中不存在指定键值的元素，会导致自动插入该元素，并且新元素的默认value由构造函数提供。通常，所有基本数据类型都提供了默认的构造函数，并都以0为初值。
（7）通常数组可作为STL容器
大家都知道string可以被视为容器，其内元素均为字符。通常的数组不是类，也不可能提供成员函数。但是可以通过普通指针，使用STL的算法实现对普通数组的操作。
例3-41
例3-41的执行效果如图3-42所示。
图3-42 例3-41的执行效果
除了上述方法，还可以通过自定义类或者自定义类模板的形式，实现对数组的访问和操作。
总结
本节主要讲述了4种关联式容器：set、multiset、map和multimap，并详细讲述了这4种容器的各种成员与函数及其使用方法。此外，本节针对每个容器均详细讲述了其构造函数、容量大小，遍历容器，元素查找，插入和删除，交换等。在讲述知识点的同时，也适当补充了部分其他知识。例如for_each（）函数的使用、sort（）函数的使用等。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
