1、结构

Map和multimap将key/value pair（键值/实值 队组）当作元素，进行管理。他们根据key的排序准则将元素排序。multimap允许重复元素，map不允许。

元素要求：

• key/value必须具有assigned（可赋值）和copyable（可复制的）性质。
• 对于排序而言，key必须具是comparable（可比较的）。

2、能力

典型情况下，set，multisets，map，multimap使用相同的内部结构，因此可以将set和multiset当成特殊的map和multimap，只不过set的value和key指向的是同一元素。

map和multimap会根据key对元素进行自动排序，所以根据key值搜寻某个元素具有良好的性能，但是如果根据value来搜寻效率就很低了。

同样，自动排序使得你不能直接改变元素的key，因为这样会破坏正确次序，要修改元素的key，必须先移除拥有key的元素，然后插入拥有新的key/value的元素，从迭代器的观点来看，元素的key是常数，元素的value是可以直接修改的。

3、操作函数

3.1 构造、析构、拷贝

3.2 非变动性操作

3.3 特殊搜寻函数

3.4 赋值

3.5 迭代器函数

map和multimap不支持元素直接存取，因此元素的存取通常是经过迭代器进行。不过例外的是，map提供下标操作，可直接存取元素。同样，他们的迭代器是双向迭代器，所有的元素的key都被视为常数，不能调用任何变动性操作，如remove()，要移除元素，只能用塔门提供的函数。

3.6 元素的安插和移除

有三个不同的方法将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，另一个作法是直接运用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));

上述第一个insert()语句内的型别并不正确，所以会被转换成真正的型别。

• 运用make_pair()

最方便的方法是直接运用make_pair()函数，这个函数根据传入的两个参数构造一个pair对象。

std::map<std::string,float> coll;
    ...
coll.insert(std::make_pair("otto",22.3));
下面是个简单例子，检查安插元素是否成功：
std::map<std::string,float> coll;
   ...
   if (coll.insert(std::make_pair("otto",22.3)).second) {
       std::cout << "OK, could insert otto/22.3" << std::endl;
   }
   else {
       std::cout << "Oops, could not insert otto/22.3 "
                 << "(key otto already exists)" << std::endl;
   }

如果要移除某个值为value的元素，使用erase()即可。

std::map<std::string,float> coll;
   ...
   //remove all elements with the passed key
   coll.erase(key);

如果multimap内喊重复元素，不能使用erase()来删除这些元素的第一个，但是可以这么做：

typedef multimap<string.float> StringFloatMMap;
   StringFloatMMap coll;
   ...
   //remove first element with passed key
   StringFloatMMap::iterator pos;
   pos = coll.find(key);
   if (pos != coll.end()) {
       coll.erase(pos);
   }

这里使用成员函数的find()而非STL里面的find(),因为成员函数更快，然而不能使用成员函数find()来移除拥有某个value（而非某个key）的元素。

移除元素时，要当心心意外发生，当移除迭代器所指对象时，可能使迭代器失效。

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不再成为一个有效的迭代器，如果此后未对pos重新设值就使用pos，会出现异常。++pos就能导致一个未定义行为。下面是正确的删除方法。

typedef std::map<std::string,float> StringFloatMap;
   StringFloatMap coll;
   StringFloatMap::iterator pos;
   ...
   //remove all elements having a certain value
   for (pos = c.begin(); pos != c.end(); ) {
       if (pos->second == value) {
           c.erase(pos++);
       }
       else {
           ++pos;
       }
   }

注意，pos++会指向下一个元素，但返回其原始值（指向原位置）的一个副本，因此，当erase()被调用，pos已经不指向那个即将被删除的元素了。

4、map视为关联数组

通常，关联数组不提供直接存取，必须依靠迭代器，不过map是个例外，map提供下标操作符，可以直接存取元素。不过下标操作符的索引不是元素整数位置，而是元素的key。也就是说，索引可以是任何型别，而非局限的整数型别。

和一般数组的区别不仅仅是索引型别，你不能使用一个错误的索引，如果你是用某个key为索引，容器尚未存在该元素，会自动安插该元素，新元素由default构造，所有基本型别都提供default构造函数，以零为初始值。

关联数组的行为方式有优点，也有缺点：

优点是可以透过方便的接口向map安插新元素。

std::map<std::string,float> coll;     // empty collection
   /*insert "otto"/7.7 as key/value pair
    *-first it inserts "otto"/float()
    *-then it assigns 7.7
    */
   coll["otto"] = 7.7;

其中的语句：coll["otto"] = 7.7;处理如下：

1.处理coll["otto"]：

--如果存在键值为“otto”的元素，以上式子返回该元素的reference。

--如果没有任何元素的键值为“otto”，以上式子便为map自动安插一个新元素，键值key为“otto”，value通过default构造函数完成，并返回一个reference指向新元素。

2.将7.7赋值给value：

--紧接着，将7.7赋值给刚才返回的元素。

这样，map之内就包含了一个键值（key）为“otto”的元素，其值（value）为7.7。

缺点就是你可能不小心误置新元素。例如你想打印key为“otto”的元素值：

std::cout << coll[“ottto”] << endl;

它会安插一个键值为“ottto”的元素，然后打印其值，缺省情况下是0。它并不会告诉你拼写错误，并且插入一个你可能不需要的元素。

这种插入方式比一般的map安插方式来得慢，因为在生成新元素的时候，需要使用default构造函数将新元素初始化，而这个值马上又会被真正的value覆盖。

5、示例代码

5.1 map

// cont/mapl.cpp

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

   int main()
   {
       /*create map/associative array
        *-keys are strings
        *-values are floats
        */
       typedef map<string,float> StringFloatMap;

       StringFloatMap stocks;      // create empty container

       //insert some elements
       stocks["BASF"] = 369.50;
       stocks["VW"] = 413.50;
       stocks["Daimler"] = 819.00;
       stocks["BMW"] = 834.00;
       stocks["Siemens"] = 842.20;

       //print all elements
       StringFloatMap::iterator pos;
       for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
           cout << "stock: " << pos->first << "t"
                << "price: " << pos->second << endl;
       }
       cout << endl;

       //boom (all prices doubled)
       for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
           pos->second *= 2;
       }

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

       /*rename key from "VW" to "Volkswagen"
        *-only provided by exchanging element
        */
       stocks["Volkswagen"] = stocks["VW"];
       stocks.erase("VW");

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

输出：

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

5.2 multimap

// cont/mmap1.cpp

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

   int main()
   {
       //define multimap type as string/string dictionary
       typedef multimap<string,string> StrStrMMap;

       //create empty dictionary
       StrStrMMap dict;

       //insert some elements in random order
       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"));

       //print all elements
       StrStrMMap::iterator pos;
       cout.setf (ios::left, ios::adjustfield);
       cout << ' ' << setw(10) << "english "
            << "german " << endl; 
       cout << setfil('-') << setw(20) << ""
            << setfil(' ') << endl;
       for (pos = dict.begin(); pos != dict.end(); ++pos) {
           cout << ' ' << setw(10) << pos->first.c_str()
                << pos->second << endl;
       }
       cout << endl;

       //print all values for key "smart"
       string word("smart");
       cout << word << ": " << endl;

       for (pos = dict.lower_bound(word);
            pos != dict.upper_bound(word); ++pos) {
               cout << " " << pos->second << endl;
       }

       //print all keys for value "raffiniert"
       word = ("raffiniert");
       cout << word << ": " << endl;
       for (pos = dict.begin(); pos != dict.end(); ++pos) {
           if (pos->second == word) {
               cout << " " << pos->first << endl;
           }
       }
   }

输出：

english   german
   --------------------
    car       Auto
    clever    raffiniert
    day       Tag
    smart     elegant
    smart     raffiniert
    smart     klug
    strange   fremd
    strange   seltsam
    trait     Merkmal

   smart:
       elegant
       raffiniert
       klug
   raffiniert:
       clever
       smart

原文链接: https://www.cnblogs.com/ChinaHook/p/6985518.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍