map和multimap将key/value pair当做元素，进行管理。它们根据key的排序准则自动将元素排序。multimap允许重复元素，map不允许。
使用map和multimap之前，必须包含头文件<map>，map和multimap被定义为命名空间std内的class template：
|
1 2 3 4 5 6 7 8 9 |
namespace std { template<class Key, class T, class Compare = less<Key>, class Allocator = allocate<pair<const Key,T> > > class map; template<class Key, class T, class Compare = less<Key>, class Allocator = allocate<pair<const Key,T> > > class multimap; } |
第一个template参数被当做元素的key，第二个template参数被当做元素的value。map和multimap的元素类型Key和T,必须满足以下两个条件：
- key/value必须具备assignable和copyable性质。
- 对排序准则而言，key必须是comparable。
第三个template参数可有可无，用来定义排序准则。元素的次序由它们的key决定，和value无关。
1.map和multimap的能力
（1）和所有标准的关联式容器一样，map/multimap通常以平衡二叉树完成，如下图：
（2）典型情况下，set,multiset,map,multimap使用相同的内部数据结构。因此你可以把set和multiset分别视为特殊的map和multimap，只不过set元素的value和key是指向同一对象。因此map和multimap拥有set和multiset的所有能力和操作函数。
（3）当然某些细微差异还是有的：首先，它们的元素是key/value pair，其次map可作为关联式数组来运用。
（4）“自动排序”这一性质使得map和multimap身上有了一条重要的限制：你不可以直接改变元素的key，因为这会破坏正确次序。要修改元素的key，你必须先移除拥有该key的元素，然后插入新的key/value元素。
2.map和multimap的操作函数
（1）map和multimap的构造函数和析构函数
|
1 2 3 4 5 6 7 8 9 10 11 12 |
map 产生一个空的map/multimap，其中不含任何元素 map c(op) 以op为准则，产生一个空的map/multimap map c1(c2) 产生某个map/multimap的副本，所有元素均被复制 map c(beg,end) 以区间[beg,end)内的元素产生一个map/multimap map c(beg,end,op) 以op为排序准则，利用[beg,end)内的元素生成一个map/multimap c.~map() 销毁所有元素，释放内存 其中，map可为下列形式： map<Key, Elem> 一个map，以less<>(operator<)为排序准则 map<Key, Elem, Op> 一个map，以op为排序准则 multimap<Key, Elem> 一个multimap,以... multimap<Key, Elem, Op> ... |
（2）有两种方式可以定义排序准则：
- 以template参数定义：
std::map<float, std::string, std::greater<float> >cloo; - 以构造函数参数定义：
你可以有一个“排序准则类型”并为它指定不同的排序准则。如果执行期才获得排序准则，而且程序需要用到不同的排序准则，此一方法可派上用场。一个典型的例子是在执行期指定“key的类型为string”的排序准则，见稍后的例子。
如果没有提供特定的排序准则，就采用缺省准则——仿函数less<>。
（3）map和multimap的非变动性操作
|
1 2 3 4 5 6 7 8 9 |
c.size() 返回容器大小 c.empty() 判断容器大小是否为0 c.max_size()返回可容纳的最大元素数量 c1 ==c2 判断c1是否等于c2 c1 != c2 ... c1 < c2 ... c1 > c2 ... c1 <= c2 ... c1 >= c2 ... |
（4）特殊的搜寻动作
1）就像set和multiset一样，map和multimap也提供特殊的搜寻函数，以便用内部树状结构获取较好的性能。
2）成员函数find()用来搜寻有用某个key的第一个元素，并返回一个迭代器，指向该位置。如果没有找到这样的元素，就返回容器的end()。但不能用find()搜寻拥有某个特定value的元素，这是必须改用算法find_if()，或干脆写一个显式循环。
|
1 2 3 4 |
for (pos = coll.begin(); pos != coll.end(); ++pos) { if (pos->second == value) do_something(); } |
3）map和multimap特殊搜寻操作函数
|
1 2 3 4 5 |
count<key) 返回“键值等于key”的元素个数 find(key) 返回“键值等于key”的第一个元素，找不到返回end() lower_bound(key) 返回“键值为key”之元素的第一个可插入位置，也就是“键值>=key”的第一个元素位置 upper_bound(key) 返回“键值为key”之元素的最后一个可插入位置，也就是“键值>key”的第一个元素位置 equal_range(key) 返回“键值为key”之元素的第一个可插入位置和最后一个可插入位置，也就是“键值==key”的元素区间 |
（4）map和multimap的赋值操作
|
1 2 3 |
c1 == c2 将c2中所有元素赋值给c1 c1.swap(c2） 将c1和c2元素互换 swap(c1,c2) 同上，此为全局函数 |
（5）map和multimap的迭代器相关操作函数
|
1 2 3 4 |
c.begin() 返回一个双向迭代器(key被视为常数）,指向第一个元素 c.end() 返回一个双向迭代器(key被视为常数)，指向最后元素的下一位置 c.rbegin() 返回一个逆向迭代器，指向逆向遍历时的第一个元素 c.rend() 返回一个逆向迭代器，指向逆向遍历时的最后元素的下一位置 |
1）和其它所有关联式容器类似，这里的迭代器是双向迭代器。所以，对于只能用于随机存取迭代器的STL算法，map和multimap就无福消受了。
2）更重要的是，在map和multimap中，所有元素的key都被视为常数，因此元素的实质类型为pair<const key,T>。这个限制是为了确保你不会因为变更元素的key而破坏已排好的元素次序。
3）所以，你不能针对map或multimap调用任何变动性算法。例如，不能调用remove()。
（6）map和multimap所支持的元素插入和删除函数
|
1 2 3 4 5 6 7 |
c.insert(elem) 插入一个elem副本，返回新元素位置(不论成功与否——对map而言) c.insert(pos,elem) 插入一个elem副本，返回新元素位置(pos是个提示，指出插入操作的搜寻起点) c.insert(beg,end) 将区间[beg,end)内所有元素的副本插入到c(无返回值) c.erase(elem) 移除“实值value与elem相等”的所有元素，返回移除元素个数 c.erase(pos) 移除迭代器pos所指位置上的元素，无返回值 c.erase(beg,end) 移除区间[beg,end)内的所有元素，无返回值 c.clear() 移除全部元素，将整个容器清空 |
注：C++11新标准，规定erase(pos)和erase(beg,end)动作之后，返回最后一个被删除的元素的下一个位置。
插入一个key/value pair的时候，一定要记住，在map和multimap内部，key被视为常数。有三个不同的方法可将value传入map：
1）运用value_type
为了避免隐式类型转换，可以利用value_type明白传递正确类型：
std::map<std::string, float> coll;
…
coll.insert(std::map<std::string, float>::value_type(“otto”, 22.3);
2）运用pair<>
std::map<std::string, float> coll;
…
//use implict conversion:
coll.insert(std::pair<std::string, float>(“otto”, 22.3));
//use no implicit conversion:
coll.insert(std::pair<const std::string, float>(“otto”, 22.3));
上述第一个insert()语句内的类型并不正确，所以会被转换成真正的元素类型。
3）运用make_pair()
最方便的办法是运用make_pair()函数。这个函数根据传入的两个参数构造出一个pair对象：
std::map<std::string, float> coll;
…
coll.insert(std::make_pair(“otto”, 22.3));
3.将map视为关联式数组
（1）通常，关联式容器并不提供元素的直接存取，你必须依靠迭代器。不过map是个例外。Non-const map提供下标操作符，支持元素的直接存取。
（2）不过，小标操作符的索引值并非元素整数位置，而是元素的key。也就是说，索引可以是任意类型，而非局限为整数类型。这种接口正是我们所说的关联式数组。
|
1 |
m[key] 返回一个reference，指向键值为key的元素。如果该元素尚未存在，就插入该元素 |
（3）和一般数组之间的区别还不仅仅在于索引类型。其他区别还包括：你不可能用上一个错误索引。如果你使用某个key作为索引，而容器中尚未存在对于元素，那么就会自动插入该元素。新元素的value有default构造函数构造。(提醒，所有基本数据类型都提供有default构造寒素，以零为初值)
（4）关联式数组的行为方式可以说是各有利弊：
1）有点是你可以透过更方便的接口对着map插入新元素：
std::map<std::string, float> coll;
coll[“otto”] = 7.7;
其中第二条语句的处理如下：
- 如果存在键值为“otto”的元素，以上式子返回该元素的reference。
- 如果不存在键值“otto”,以上式子便会为map自动插入一个新元素，键值key为“otto”，实值value则以default构造函数完成，并返回一个reference指向新元素。
- 紧接着，将7.7赋值给上述刚刚诞生的新元素
2）缺点是你可能会不小心误置新元素：
std::cout << coll[“ottto”];
它会插入一个键值为”ottto”的新元素，然后打印其实值，缺省情况下是0。然而，按道理它应该产生一条错误信息，告诉你你把”otto”拼写错了。
4.异常处理
就异常处理而言，map和multimap的行为与set和multiset一样。
5.map和multimap运用实例
（1）map.cpp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <map> #include <string> #include <algorithm> #include <iterator> using namespace std; int main() { typedef map<string,float> StringFloatMap; StringFloatMap stocks; stocks["BASF"] = 369.50; stocks["VW"] = 413.50; stocks["Daimler"] = 819.00; stocks["BMW"] = 834.00; stocks["Siemens"] = 842.20; StringFloatMap::iterator pos; for (pos = stocks.begin(); pos != stocks.end(); ++pos) { cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl; } cout << endl; for (pos = stocks.begin(); pos != stocks.end(); ++pos) { pos->second *= 2; } for (pos = stocks.begin(); pos != stocks.end(); ++pos) { cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl; } cout << endl; /*rename key from VM to Volkswagen, only provided by exchanging element */ stocks["Volkswagen"] = stocks["VW"]; stocks.erase("VW"); for (pos = stocks.begin(); pos != stocks.end(); ++pos) { cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl; } } |
输出：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
[root@VM_198_209_centos cppstl]# ./map stock: BASF price: 369.5 stock: BMW price: 834 stock: Daimler price: 819 stock: Siemens price: 842.2 stock: VW price: 413.5 stock: BASF price: 739 stock: BMW price: 1668 stock: Daimler price: 1638 stock: Siemens price: 1684.4 stock: VW price: 827 stock: BASF price: 739 stock: BMW price: 1668 stock: Daimler price: 1638 stock: Siemens price: 1684.4 stock: Volkswagen price: 827 |
（2）将multimap当做字典
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <map> #include <string> #include <algorithm> #include <iterator> #include <iomanip> using namespace std; int main() { typedef multimap<string, string>StrStrMMap; StrStrMMap dict; dict.insert(make_pair("day","Tag")); dict.insert(make_pair("strange","fremd")); dict.insert(make_pair("car","Auto")); dict.insert(make_pair("smart","elegant")); dict.insert(make_pair("trait","Merkmal")); dict.insert(make_pair("strange","seltsam")); dict.insert(make_pair("smart","raffiniert")); dict.insert(make_pair("smart","klug")); dict.insert(make_pair("clever","raffiniert")); StrStrMMap::iterator pos; cout.setf(ios::left, ios::adjustfield); cout << ' ' << setw(10) << "english " << "german " << endl; cout << setfill('-') << setw(20) << " " << setfill(' ') << endl; for (pos = dict.begin(); pos!= dict.end(); ++pos){ cout << ' ' << setw(10) << pos->first.c_str() << pos->second << endl; } cout << endl; string word("smart"); cout << word << ": " << endl; for (pos = dict.lower_bound(word); pos != dict.end(); ++pos) { cout << " " << pos->second << endl; } word = ("raffiniert"); cout << word << ": " << endl; for (pos = dict.begin(); pos != dict.end(); ++pos){ if (pos->second == word) cout << " " << pos->first << endl; } } |
输出：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
[root@VM_198_209_centos cppstl]# ./multimap english german ------------------- car Auto clever raffiniert day Tag smart elegant smart raffiniert smart klug strange fremd strange seltsam trait Merkmal smart: elegant raffiniert klug fremd seltsam Merkmal raffiniert: clever smart |
其中，函数setw()和setfill包含在头文件<iomanip>中。