基于C++11的Map和Multimap分析_c++ multimap访问

基本内容

1. Map和multimap将将键值对(key/value pair)当作元素进行管理。他们可以根据key的排序准则自动为元素排序。multimap允许元素重复，map不允许。

2. 使用map和multimap你必须包括头文件<map>

3. 其中，map和multimap被定义为命名空间std内的class template:

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

第一个template实参将成为容器的key类型，第二个template实参将成为元素的value类型。map和multimap的元素类型Key和T必须满足以下两个条件:

1. Key和value都是可复制的或可搬移的。

2. 对指定的排序准则，key必须是可比较的

第三个template实参可有可无，用来定义排序准则。和set一样买这个排序准则必须被定义为强弱准则。元素的次序由它们的key决定，和value无关。如果未传入某个排序准则，就使用默认的排序准则--less<>排序准则。

第四个template实参也是可有可无，用来定义内存模型。(以value_type的类型进行分配)

Map和Multimap的能力

和所有的关联式容器相似，map/multimap通常以AVL树实现，C++standard并未指明指点。通常set,multiset,map,multimap使用相同的内部结构，因此你可以把set和multiset视为特殊的map和multimap，只不过set元素的value和key是同一对象。当然细微的差距是有的，首先它们元素为key/value pair，其次，map可作为关联式数组来运用。

map和multimap会根据元素的key自动对元素排序。这样，根据已知的key查找某个元素就能有很好的效率，而根据已知value查找元素时效率就很糟糕。自动排序这一性质在map和multimap身上有了一条重要限制:你不可以直接改变元素的key。因此要修改元素的key，你必须先移除拥有该key的元素，然后再插入拥有新key/value的元素。

Map和Multimap的操作函数

创建,复制和销毁(Create,Copy,and Destory)

map c//Default构造函数，建立一个空的容器，不含任何元素
map c(op)//建立一个空的容器，以op()为排序准则
map c(c2)//Copy构造函数，建立一份c2的拷贝，所有元素均为复制
map c=c2//Copy构造函数，建立一份c2的拷贝，所有元素均为复制
map c(rv)//Move构造函数，建立一个取rv内容的新的容器
map c=rv//Move构造函数，建立一个取rv内容的新的容器
map c(beg,end)//以[beg,end)内的元素为初值，建立一个容器
map c(beg,end,op)//以[beg,end)内的元素为初值，以op为排序准则，建立一个容器
map c(initlist)//以初值列表中的元素为初值，建立一个容器
map c=initlist//以初值列表中的元素为初值，建立一个容器
c.~map()//销毁所有元素，释放内存

其中map为以下格式:

map<key,val>//一个map，以less<>为排序准则
map<key,val,op>//一个map，以op()为排序准则
multimap<key,val>//一个multimap，以less<>为排序准则
multimap<key,val,op>//一个multimap，以op()为排序准则

有两种方式可以定义排序准则:

1. 以template参数定义之。例如:

std::set<float,std::string,std::greater<float>>coll;

这种情况下排序准则就是类型的一部分。于是类型系统确保"只有排序准则相同的容器才能被合并"。更精确的说，第三参数是排序准则的类型。实际的排序准则是容器所产生的函数对象。

2. 以构造函数参数定义之。这种情况下，同一个类型可以运用不同的排序准则，而排序准则的初始值或状态也可以不同。如果运行期才获得排序准则，而且需要用到不同的排序准则，这一方式可以排上用场。

以下是运行期确定排序准则的例子:

#include<iostream>
#include<iomanip>
#include<map>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
 
class RuntimeStringCmp {
public:enum cmp_mode { normal, nocase };
private:cmp_mode mode;
       static bool nocase_compare(char c1, char c2) {
           return toupper(c1) < toupper(c2);
       }
public:RuntimeStringCmp(cmp_mode m = normal) :mode(m) {}
      bool operator () (const string& s1, const string& s2)const {
          if (mode == normal)return s1 < s2;
          else return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), nocase_compare);
      }
};
 
using StringStringMap = map<string, string, RuntimeStringCmp>;
void fillAndPrint(StringStringMap& coll);
 
int main() {
    StringStringMap coll1;
    fillAndPrint(coll1);
    RuntimeStringCmp ignorecase(RuntimeStringCmp::nocase);
    StringStringMap coll2(ignorecase);
    fillAndPrint(coll2);
}
 
void fillAndPrint(StringStringMap& coll) {
    coll["Deutschland"] = "Germany";
    coll["deutsch"] = "German";
    coll["Haken"] = "snag";
    coll["arbeiten"] = "work";
    coll["Hund"] = "dog";
    coll["gehen"] = "go";
    coll["Unternehmen"] = "enterprise";
    coll["unternehmen"] = "undertake";
    coll["gehen"] = "walk";
    coll["Bestatter"] = "undertaker";
 
    cout.setf(ios::left, ios::adjustfield);//处理流格式化
    for (const auto& elem : coll) {
        cout << setw(15) << elem.first << ""
            << elem.second << endl;
        cout << endl;
    }
}

main()构建出两个容器，并对它们调用fillAndPrint()，此函数以相同元素值填充上述两个容器，然后打印其内容。两个容器的排序准则不同:

1. coll1使用一个默认函数对象，其类型为RumtimeStringCmp。

2. coll2使用一个类型为RumtimeStringCmp的函数对象，并以nocase为初值。

对于coll1的输出结果:

Bestatter      undertaker
Deutschland    Germany
Haken          snag
Hund           dog
Unternehmen    enterprise
arbeiten       work
deutsch        German
gehen          walk
unternehmen    undertake

对于coll2的输出结果:

arbeiten       work
Bestatter      undertaker
deutsch        German
Deutschland    Germany
gehen          walk
Haken          snag
Hund           dog
Unternehmen    undertake

某些构造函数使用区间的起点和终点作为实参，它们的初值可以来自不同类型的容器，array或标准输入设备。然而由于元素的类型是key/value pair，因此你必须确定源区间的元素类型是pair<const key,val>。

非更易型操作(Nonmodifying Operation)

c.key_comp()//返回比较准则
c.value_comp()//返回针对value的"比较准则"(这是一个对象，用来在一个key/value pair中比较key)
c.empty() //返回是否容器为空(相当于size()==0但也许较快)
c.size()  //返回元素的数量
c.max_size() //返回元素个数之最大可能量
c1==c2   //返回c1是否等于c2
c1!=c2   //返回c1是否不等于c2
c1>c2    //返回c1是否大于c2
c1<c2    //返回c1是否小于c2
c1>=c2   //返回c1是否大等于c2
c1<=c2   //返回c1是否小等于c2

比较采用字典顺序比较，前提是比较的双方容器类型必须相同，否则会在编译器发生类型方面的错误。

特殊的查找动作(Special Search Operation)

都是以key为查找基础

c.count(val)//返回key值为val的个数
c.find(val)//返回key第一个值为val的位置，找不到就返回end()
c.lower_bound(val)//返回key>=val的第一个元素的位置(第一个可安插位置)
c.upper_bound(val)//返回key>val的第一个元素的位置(最后一个可安插位置)
c.equal_range(val)//返回key==val的区间，(第一个和最后一个可安插位置)

赋值(Assignment)

c=c2              //将c2的全部元素赋值给c
c=rv              //将rv的所有元素都已move assign的方式给予c
c=initlist        //将初始值列表的所有元素赋值给c
c1.swap(c2)       //置换c1和c2的值
swap(c1,c2)       //置换c1和c2的值

这些操作函数中，赋值动作的两端容器必须拥有相同类型。尽管"比较准则"本身可能不同，但其类型必须相同。如果准则不同，准则本身会随着容器被赋值或交换。

迭代器相关函数和元素访问(Iterator Function and Element Access)

map和multimap的迭代器相关操作

c.begin()      //返回一个指向首处 bidirectional iterator
c.cbegin()     //返回一个const bidirectional iterator
c.end()        //返回一个指向末尾下一个位置的 bidirectional iterator
c.cend()       //返回一个指向末尾下一个位置的const bidirectional iterator
c.rbegin()     //返回一个reverse bidirectional iterator，指向末尾的下一个位置
c.rend()       //返回一个reverse bidirectional iterator，指向首处的位置
c.crend()      //返回一个const reverse bidirectional iterator，指向首处的位置
c.crbegin()    //返回一个const reverse bidirectional iterator，指向末尾的下一个位置

map和multimap的元素安插和移除

c.insert(val)//安插一个val的拷贝，返回新元素的位置
c.insert(pos,val)//插入val的一个拷贝，并且返回新元素的位置(pos只是起到了提示和加快速度的参数)
c.insert(beg,end)//插入[begin,end)区间的拷贝，无返回值
c.insert(initlist)//插入初始化列表的拷贝，无返回值
c.emplace(args...)//插入以args作为初值的元素，并且返回新元素的位置
c.erase(pos)//移除pos位置上的元素，无返回值(C++11后总是返回一个迭代器指向其后继元素)
c.erase(val)//移除值为val的所有元素，返回被移除元素的个数
c.erase(beg,end)//移除区间[beg,end)内的所有元素，无返回值
c.clear()//移除所有元素，将容器清空

这里的迭代器类型为双向迭代器。对于只接受随机访问迭代器的STL算法，该容器便无福消受了。重要的是，由于所有元素的key都被视为常量，因此你无法调用任何更易型算法。如果你想移除其中的元素，你只能使用它们所提供的成员函数。

如果你使用算法或lambda来操作map元素,你必须很明确的声明元素类型:

std::map<std::string,float>coll;
std::for_each(coll.begin(),coll.end(),[](std::pair<const std::string,float>&elem){elem.second+=10;});

可以不写std::pair<const std::string,float>

而改为 std::map<std::string,float>::value_type;

元素的安插和移除(Inserting and Removing)

上一节列出该容器支持的元素安插和删除函数。和之前关于set和multiset的说明此处依然使用。上述操作函数的返回类型有些差异，这与set和multiset之间的情况完全相同。

对于multimap，C++保证insert(),emplace()和erase()都会保留等价元素的相对次序，新增的元素则一定被安插在既有的等价元素的末尾。

自C++11起，安插元素的最方便做法就是把它们即初值列的形式传进去。

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

有三种不同的方法可以将val传入map或multimap内:

1. 运用value_type:为了避免隐式类型定义，你可以利用value_type明白传递正确类型。value_type是容器本身提供的类型定义。如下:

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

2.运用pair<>。另一个做法是直接利用pair<>。如下:

std::map<std::string,float>coll;
//下方需要隐式转换
coll.insert(std::pair<std::string,float>("otto",22.3));
//下方不需要隐式转换
coll.insert(std::pair<const std::string,float>("otto",22.3));

为了做到这种隐式转换，insert()成员函数被定义为memeber template

3.运用make_pair()。C++11面世之前最方便的方法是用make_pair()函数。它根据收到的两个实参构建出一个pair对象。

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

关于insert()等返回值的讨论，请参照set和multiset,也适用于map和multimap

移除元素时，当心发生意外状况。移除迭代器所指对象时，有一个非常大的危险:

std::map<std::stirng,float>coll;
for(auto pos=coll.begin();pos!=coll.end();++pos){
   if(pos->second==value)coll.erase(pos);
}   //RUMTIME ERROR!

对pos所指元素调用erase()，会使pos不再成为coll的一个有效迭代器。如果你未重新设置就直接使用pos是一个未定义的行为。

C++11后的解决方案很容易，因为erase()总是返回一个迭代器指向其后继的元素:

std::map<std::stirng,float>coll;
for(auto pos=coll.begin();pos!=coll.end();){
   if(pos->second==value)coll=coll.erase(pos);
   else ++pos;
}   

将Map视为关联式数组(Associative Array)

通常，关联式容器并不提供元素的直接访问，你必须依赖迭代器。不过map是例外。Non-const map提供下标操作符，支持元素的直接访问。C++11提供另一个成员函数at()，可用于const map和non-const map

c[key] //安插一个带着key的元素--如果尚未存在于容器内。返回一个reference指向带着key的元素
c.at(key)//返回一个reference指向带着key的元素

at()会根据它收到的"元素的key"取得元素的value；如果不存在这样的元素则抛出out_of_range异常

对于operator []如果选择某key作为索引，容器内没有相应元素，map会自动安插一个新元素，其value将会被其类型的default构造函数初始化。因此，你不可以指定一个"不具有default构造函数"的value类型。注意基础类型都有一个的default构造函数，设初值为0。

这种关联式数组的行为有缺点也有优点:

1. 优点是你可以通过更方便的接口对map安插新元素。

2. 缺点是你有可能不小心误置新元素。

std::cout<<coll["otto"];

它会安插一个key为"otto"的新元素，然后打印其value，默认值为0。但是当你把里面的字母拼错了的时候，你想让编译器报错，但实际上它把你这个行为理解成安插新元素，因而不会报错。

注意:这样的安插方式比一般map安插方式慢，因为新元素必须先使用default构造函数将value初始化，而该初始值马上又被真正的value覆盖。

异常处理(Exception Handing)

就异常处理而言，其行为与set和multiset一样。

Map和Multimap运用实例

将Multimap 当作字典（Dictionary)

下面的例子展示了如何将multimap当成一个字典使用：

#include <map>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
int main(){
     multimap<string,string> dict;
     dict.insert ( { {"day","Tag"}, {"strange","fremd"},
                     {"car","Auto"},{"smart","elegant"},
                     {"trait","Merkmal"},{"strange","seltsam"},
                     {"smart","raffiniert"},{"smart","klug"},
                     {"clever","raffiniert"} } );
     cout.setf (ios::left, ios::adjustfield);
 
     cout <<' '<< setw(10) << "english "
          << "german " << endl;
 
     cout << setfill('-')<< setw(20) << ""
          << setfill(' ')<< endl;
 
      for ( const auto& elem : dict ){
          cout <<' '<< setw(10) << elem.first
               << elem.second << endl;
          cout << endl;
          }
 
      string word("smart");
      cout << word << ":" << endl;
      for (auto pos = dict.lower_bound(wora);
                pos != dict.upper_bound(word);
                    ++pos){
       cout << " " << pos->second << endl;
 
        word =("raffiniert");
       cout << word << ":" << endl;
       for (const auto& elem :dict){
        if (elem.second == word) {
        cout << " " << elem.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