一、概述

map和multimap是STL里面的关联式容器，map的特性是所有元素会根据元素的键值被自动排序，map的所有元素都是pair，同时拥有实值和键值。pair的第一元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值。下面是<stl_pair.h>中pair的定义：

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) {}
};

map不允许修改元素的键值，允许修改元素的实值。由于红黑树是一种平衡二叉搜索树，自动排序的效果很不错，所以标准STL map以红黑树作为底层结构。几乎所有的map操作接口，红黑树都提供了，所以map操作基本都是转调红黑树的操作行为。红黑树的每个节点内容是一个pair，pair的第一元素是键值，第二元素是实值。map的排序缺省使用递增排序。multimap的特性及用法和map完全相同，唯一的不同点是multimap允许键值重复，因此底层插入操作采用的是红黑树的insert_equal()而非insert_unique()。使用map和multimap之前须先含入头文件<map>。在这个头文件中，上述两个容器被定义为std里面的class templates：

namespace std ｛
    template <class Key, class T,
              class Compare = less<T>,
              class Allocator = allocator<pair<const Key, T> > >
    class map;

    template <class Key, class T,
              class Compare = less<T>,
              class Allocator = allocator<pair<const Key, T> > >
    class multimap;
｝

第一个template参当作元素的key，第二个template参数当作元素的value。key/value必须是可赋值和可比较的。可有可无的第三个参数用来定义排序准则，元素次序由他们的键值决定，和value无关。第四个参数定义内存模型，缺省的内存模型是allocator，由C++标准程序库提供。

二、map和multimap的操作函数

1 .生成、复制和销毁

其中map可以下列形式：

2 .非变动性操作

元素的比较操作只能用于型别相同的容器，即key，value，排序准则都必须相同的型别，否则编译期会产生型别方面的错误。

3 .特殊的搜寻函数

4 .赋值函数
这些操作函数中，赋值操作的两端容器必须具有相同型别。如果排序准则不同，准则本身也会被赋值或交换。

5 .迭代器相关函数

对迭代器操作而言，所有元素的key都被视为常数，因此元素的实质型别是pair<const key,T>。这个限制是为了确保不会因为变更元素的key而破坏已排序好的元素次序。以下是一个迭代器实现遍历的例子：

std::map<std::string, float> coll;
'''
std::map<std::string, float>::iterator pos;
for (pos = coll.begin(); pos != coll.end(); ++pos) {
    std::cout << "key: " << pos->first << "\t"
              << "value: " << pos->second << std::endl;
}

6 .元素的安插、移除函数

安插移除多个元素时，单一调用比多次调用快得多。

这里的元素elem都是key/value pair型别，稍微复杂一点。将value传入map的方法有三：

• 运用value_type

为避免隐式型别转换，利用value_type明白传递正确型别，value_type是容器本身提供的型别定义。

std::map<std::string,float> coll;
'''
coll.insert(std::map<std::string,float>::value_type("otto",22.3));

• 运用pair<>

std::map<std::string,float> coll;
'''
// use implicit 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));

• 运用make_pair<>
  会根据传入的参数构造出一个pair对象。

std::map<std::string,float> coll;
'''
coll.insert(std::make_pair("otto",22.3));

关于元素的移除操作

typedef std::map<std::string,float> StringFloatMap;
StringFloatMap coll;
StringFloatMap::iterator pos;
'''
for (pos = coll.begin(); pos != coll.end(); ++pos) {
    if (pos->second == value) {
        coll.erase(pos); //runtime error
    }
}

对pos所指元素实施erase()，会使pos不再成为一个有效的coll迭代器。++pos操作会导致未定义行为。
元素移除的正确做法：

typedef std::map<std::string,float> StringFloatMap;
StringFloatMap coll;
StringFloatMap::iterator pos;
'''
for (pos = coll.begin(); pos != coll.end(); ) {
    if (pos->second == value) {
        coll.erase(pos++); 
    }
    else {
        ++pos;
    }
}

7 .元素的直接存取
map支持元素的直接存取，不过下标操作符的索引值并非元素位置整数，而是元素的key。multimap不支持此操作。

若元素尚未存在，则以default构造函数创建，所有基本数据型别以零为初值。

三、程序示例

//example of map
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    typedef map<string, float> StringFloatMap;
    StringFloatMap stocks;

    stocks["BASF"] = 369.50;
    stocks["VW"] = 413.50;
    stocks["Daimler"] = 815.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;

    stocks["Volkswagen"] = stocks["VW"];
    stocks.erase("VW");

    for (pos = stocks.begin(); pos != stocks.end(); ++pos){
        cout << "stock: " << pos->first << "\t"
            << "price: " << pos->second << endl;
    }
    cout << endl;

    stocks["Volk"];
    for (pos = stocks.begin(); pos != stocks.end(); ++pos){
        cout << "stock: " << pos->first << "\t"
            << "price: " << pos->second << endl;
    }
    return 0;
}

输出结果：

//example of multimap
#include <iostream>
#include <map>
#include <string>
#include <iomanip>
using namespace std;

int main()
{
    typedef multimap<string, string> StrStrMMap;

    StrStrMMap dict;

    dict.insert(StrStrMMap::value_type("day", "Tag"));
    dict.insert(StrStrMMap::value_type("strange", "fremd"));
    dict.insert(StrStrMMap::value_type("car", "Auto"));
    dict.insert(pair<string,string>("smart", "elegant"));
    dict.insert(pair<string, string>("trait", "Merkmal"));
    dict.insert(pair<string, string>("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.upper_bound(word); ++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;
        }
    }
    cout << endl;

    dict.erase("car");
    for (pos = dict.begin(); pos != dict.end();) {
        if (pos->second == "klug") {
            dict.erase(pos++);
        }
        else {
            ++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;
    return 0;
}

输出结果：