C++标准程序库之map,multimap

map和multimap将key/value pair当做元素,进行管理。它们根据key的排序准则自动将元素排序。multimap允许重复元素,map不允许。

使用map和multimap之前,必须包含头文件<map>,map和multimap被定义为命名空间std内的class template:

第一个template参数被当做元素的key,第二个template参数被当做元素的value。map和multimap的元素类型Key和T,必须满足以下两个条件:

  • key/value必须具备assignable和copyable性质。
  • 对排序准则而言,key必须是comparable。

第三个template参数可有可无,用来定义排序准则。元素的次序由它们的key决定,和value无关。

1.map和multimap的能力

(1)和所有标准的关联式容器一样,map/multimap通常以平衡二叉树完成,如下图:map内部结构

(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的构造函数和析构函数

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

  • 以template参数定义:
    std::map<float, std::string, std::greater<float> >cloo;
  • 以构造函数参数定义:
    你可以有一个“排序准则类型”并为它指定不同的排序准则。如果执行期才获得排序准则,而且程序需要用到不同的排序准则,此一方法可派上用场。一个典型的例子是在执行期指定“key的类型为string”的排序准则,见稍后的例子。

如果没有提供特定的排序准则,就采用缺省准则——仿函数less<>。

(3)map和multimap的非变动性操作

(4)特殊的搜寻动作

1)就像set和multiset一样,map和multimap也提供特殊的搜寻函数,以便用内部树状结构获取较好的性能。

2)成员函数find()用来搜寻有用某个key的第一个元素,并返回一个迭代器,指向该位置。如果没有找到这样的元素,就返回容器的end()。但不能用find()搜寻拥有某个特定value的元素,这是必须改用算法find_if(),或干脆写一个显式循环。

3)map和multimap特殊搜寻操作函数

(4)map和multimap的赋值操作

(5)map和multimap的迭代器相关操作函数

1)和其它所有关联式容器类似,这里的迭代器是双向迭代器。所以,对于只能用于随机存取迭代器的STL算法,map和multimap就无福消受了。
2)更重要的是,在map和multimap中,所有元素的key都被视为常数,因此元素的实质类型为pair<const key,T>。这个限制是为了确保你不会因为变更元素的key而破坏已排好的元素次序。
3)所以,你不能针对map或multimap调用任何变动性算法。例如,不能调用remove()。

(6)map和multimap所支持的元素插入和删除函数

注: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。也就是说,索引可以是任意类型,而非局限为整数类型。这种接口正是我们所说的关联式数组。

(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

输出:

(2)将multimap当做字典

输出:

其中,函数setw()和setfill包含在头文件<iomanip>中。

发表评论

电子邮件地址不会被公开。 必填项已用*标注