STL之Map.doc

STL之Map

概述
Map是标准关联式容器(associative container)之一,一个map是一个键值对序列,即(key ,value)对。它提供基于key的快速检索能力,在一个map中key值是唯一的。map提供双向迭代器,即有从前往后的(iterator),也有从后往前的(reverse_iterator)。
map要求能对key进行<操作,且保持按key值递增有序,因此map上的迭代器也是递增有序的。如果对于元素并不需要保持有序,可以使用hash_map。
map中key值是唯一的,如果马匹中已存在一个键值对(昵称,密码):("",407574364),而我们还想插入一个键值对("",472687789)则会报错(不是报错,准确的说是,返回插入不成功!)。而我们又的确想这样做,即一个键对应多个值,幸运的是multimap可是实现这个功能。
下面我们用实例来深入介绍map、multimap,主要内容如下:
1、例子引入
2、map中的类型定义
3、map中的迭代器和键值对
4、map中的构造函数与析构函数
5、map中的操作方法
6、再议map的插入操作
7、[]不仅插入
8、multimap
9、总结
1、例子引入
有一个服务器manager维护着接入服务器的client信息,Id、scanRate、socketAddr等等。我们定义一个结构体保存scanRate、socketAddr信息。如下:
1
2
3
4
5
typedef    int    clientId;
typedef struct{
    int scanRate;
    string socketAddr;
}clientInfo;
我们用map保存这些信息:clientId为键key,clientInfo为值。这样我们可以通过clientId快速检索到client的相关信息,我们可以这样定义:
1
map<clientId,clientInfo> clientMap;
这样我们定义了一个clientMap,如果我们要定义多个这样的map,需要多次写map<clientId,clientInfo> 变量名。为了避免这样情况,我们通常为map<clientId,clientInfo>定义个别名,如:
1
2
typedef map<clientId,clientInfo> clientEdp;
clientEdp clientMap;
之后我们就可以像定义clientMap一样定义map<clientId,clientInfo>对象,这样的好处还有:如果我们需要修改map的定义,只需要在一处修改即可,避免修改不彻底造成的不一致现象。
我们这就完成了需要的map的定义,如果不定义或没有在它上面的操作的话,就像定义类而没有方法一样,意义不大或毫无意义。幸运的是,STL提供了这些常用操作:排序(注:map是不能也不要排序的,因为map本身已经排好序了)、打印、提取子部分、移除元素、添加元素、查找对象,就像数据库的增删改查操作!现在我们详细介绍这些操作,并逐步引入hash_map、multimap。
2、map中的类型定义
关联数组(associative array)是最有用的用户定义类型之一,经常内置在语言中用于文本处理等。一个关联数组通常也称为map,有时也称字典(dictionary),保存一对值。第一个值称为key、第二个称为映射值mapped-value。
标准map是定义在std命名空间中的一个模板,并表示为<map>。它首先定义了一组标准类型名字:
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
template<class Key,class T,class Cmp=less<key>,
    class A=allocator<pair<const Key,T>>
class std::map
{
public:
    //types
    typedef Key    key_type;
    typedef T    mapped_type;
 
    typedef pair<const Key,T>    value_type;
 
    typedef    Cmp    pare;
    typedef A    allocator_type;
 
    typedef    typename    A::reference    r