STL之Map

map是标准关联式容器（associative container）之一，一个map是一个键值对序列，即（key ,value）对。它提供基于key的快速检索能力，在一个map中key值是唯一的。map提供双向迭代器，即有从前往后的（iterator），也有从后往前的（reverse_iterator）。

map要求能对key进行<操作，且保持按key值递增有序，因此map上的迭代器也是递增有序的。如果对于元素并不需要保持有序，可以使用hash_map。

map中key值是唯一的，如果马匹中已存在一个键值对(昵称,密码):("skynet",407574364)，而我们还想插入一个键值对("skynet",472687789)则会报错（不是报错，准确的说是，返回插入不成功！）。而我们又的确想这样做，即一个键对应多个值，幸运的是multimap可是实现这个功能。

下面我们用实例来深入介绍map、multimap，主要内容如下：

1、例子引入

2、map中的类型定义

3、map中的迭代器和键值对

4、map中的构造函数与析构函数

5、map中的操作方法

6、再议map的插入操作

7、[]不仅插入

8、multimap

9、总结

有一个服务器manager维护着接入服务器的client信息，包括clinetid、scanrate、socketaddr等等。我们定义一个结构体保存scanrate、socketaddr信息。如下：

<code>typedef</code> <code>int</code> <code>clientid;</code>

<code>typedef</code> <code>struct</code><code>{</code>

<code> </code><code>int</code> <code>scanrate;</code>

<code> </code><code>string socketaddr;</code>

<code>}clientinfo;</code>

我们用map保存这些信息：clientid为键key，clientinfo为值。这样我们可以通过clientid快速检索到client的相关信息，我们可以这样定义：

<code>map<clientid,clientinfo> clientmap;</code>

这样我们定义了一个clientmap，如果我们要定义多个这样的map，需要多次写map<clientid,clientinfo> 变量名。为了避免这样情况，我们通常为map<clientid,clientinfo>定义个别名，如：

<code>typedef</code> <code>map<clientid,clientinfo> clientedp;</code>

<code>clientedp clientmap;</code>

之后我们就可以像定义clientmap一样定义map<clientid,clientinfo>对象，这样的好处还有：如果我们需要修改map的定义，只需要在一处修改即可，避免修改不彻底造成的不一致现象。

我们这就完成了需要的map的定义，如果不定义或没有在它上面的操作的话，就像定义类而没有方法一样，意义不大或毫无意义。幸运的是，stl提供了

这些常用操作：排序（注：map是不能也不要排序的，因为map本身已经排好序了）、打印、提取子部分、移除元素、添加元素、查找对象，就像数据库的增删

改查操作！现在我们详细介绍这些操作，并逐步引入hash_map、multimap。

关联数组（associative array）是最有用的用户定义类型之一，经常内置在语言中用于文本处理等。一个关联数组通常也称为map，有时也称字典（dictionary），保存一对值。第一个值称为key、第二个称为映射值mapped-value。

标准map是定义在std命名空间中的一个模板，并表示为<map>。它首先定义了一组标准类型名字：

<code>template</code><code><</code><code>class</code> <code>key,</code><code>class</code> <code>t,</code><code>class</code> <code>cmp=less<key>,</code>

<code> </code><code>class</code> <code>a=allocator<pair<</code><code>const</code> <code>key,t>></code>

<code>class</code> <code>std::map</code>

<code>public</code><code>:</code>

<code> </code><code>//types</code>

<code> </code><code>typedef</code> <code>key key_type;</code>

<code> </code><code>typedef</code> <code>t mapped_type;</code>

<code> </code><code>typedef</code> <code>pair<</code><code>const</code> <code>key,t> value_type;</code>

<code> </code><code>typedef</code> <code>cmp key_compare;</code>

<code> </code><code>typedef</code> <code>a allocator_type;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::reference reference;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::const_reference const_reference;</code>

<code> </code><code>typedef</code> <code>implementation_define1 iterator;</code>

<code> </code><code>typedef</code> <code>implementation_define2 const_iterator;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::size_type size_type;</code>

<code> </code><code>typedef</code> <code>typename</code> <code>a::difference_type difference_type;</code>

<code> </code><code>typedef</code> <code>std::reverse_iterator<iterator> reverse_iterator;</code>

<code> </code><code>typedef</code> <code>std::reverse_iterator<const_iterator> const_reverse_iterator;</code>

注意：map的value_type是一个(key,value)对，映射值的被认为是mapped_type。因此，一个map是一个

pair<const key,mapped_type>元素的序列。从const key可以看出，map中键key是不可修改的。

不得不提的是map定义中cmp和a都是可选项。cmp是定义在元素之间的比较方法，默认是<操作；a即allocator用来分配和释放map总键值对所需使用的内存，没有指定的话即默认使用的是stl提供的，也可以自定义allocator来管理内存的使用。多数情况，我们不指定这两个选项而使用默认值，这样我们定义map就像下面这样：

<code>map<</code><code>int</code><code>,clientinfo> clientmap;</code>

cmp和a都缺省。通常，实际的迭代器是实现定义的，因为map很像使用了树的形式，这些迭代器通常提供树遍历的某种形式。逆向迭代器是使用标准的reverse_iterator模板构造的。

map提供惯常的返回迭代器的一组函数，如下所示：

<code>public</code><code>: </code>

<code> </code><code>//iterators</code>

<code> </code><code>iterator begin();</code>

<code> </code><code>const_iterator begin() </code><code>const</code><code>;</code>

<code> </code><code>iterator end();</code>

<code> </code><code>const_iterator end() </code><code>const</code><code>;</code>

<code> </code><code>reverse_iterator rbegin();</code>

<code> </code><code>const_reverse_iterator rbegin() </code><code>const</code><code>;</code>

<code> </code><code>reverse_iterator rend();</code>

<code> </code><code>const_reverse_iterator rend() </code><code>const</code><code>;</code>

map上的迭代器是pair<const key,mapped_type>元素序列上简单的迭代。例如，我们可能需要打印出所有的客户端信息，像下面的程序这样。为了实现这个，我们首先向《例子引入》中定义的clientedp中插入数据，然后打印出来：

<code>#include<iostream></code>

<code>#include<map></code>

<code>#include<string></code>

<code>using</code> <code>namespace</code> <code>std;</code>

<code> </code><code>typedef</code> <code>map<clientid,clientinfo> clientedp;</code>

<code> </code><code>typedef</code> <code>map<clientid,clientinfo>::const_iterator iterator;</code>

<code> </code><code>clientedp clients;</code>

<code> </code><code>clientinfo client[100];</code>

<code> </code><code>string straddr(</code><code>"socket addr client "</code><code>);</code>

<code> </code><code>client[i].scanrate=i+1; </code>

<code> </code><code>//convert int to char*</code>

<code> </code><code>//concatenate straddr and str</code>

<code> </code><code>client[i].socketaddr=straddr+str;</code>

<code> </code><code>clients.insert(</code>

<code> </code><code>make_pair(i+1,client[i])); </code>

<code> </code><code>delete</code> <code>str;</code>

<code> </code><code>for</code><code>(iterator i=clients.begin();i!=clients.end();i++)</code>

<code> </code><code>cout<<</code><code>"clientid:"</code><code><<i->first<<endl;</code>

<code> </code><code>cout<<</code><code>"scanrate:"</code><code><<i->second.scanrate<<endl;</code>

<code> </code><code>cout<<</code><code>"socketaddr:"</code><code><<i->second.socketaddr<<endl;</code>

一个map迭代器以key升序方式表示元素，因此客户端信息以cliendid升序的方式输出。运行结果可以证明这一点，运行结果如下所示：

图1、程序运行结果

我们以first引用键值对的key，以second引用mapped value，且不用管key和mapped value是什么类型。其实pair在std的模板中是这样定义的：

<code>template</code> <code><</code><code>class</code> <code>t1,</code><code>class</code> <code>t2></code><code>struct</code> <code>std::pair{</code>

<code> </code><code>typedef</code> <code>t1 first_type;</code>

<code> </code><code>typedef</code> <code>t2 second_type;</code>

<code> </code><code>t1 first;</code>

<code> </code><code>t2 second;</code>

<code> </code><code>pair():first(t1()),second(t2()){}</code>

<code> </code><code>pair(</code><code>const</code> <code>t1& x,</code><code>const</code> <code>t2& y):first(x),second(y){}</code>

<code> </code><code>template</code><code><</code><code>class</code> <code>u,</code><code>class</code> <code>v></code>

<code> </code><code>pair(</code><code>const</code> <code>pair<u,v>& p):first(p.first),second(p.second){}</code>

即map中，key是键值对的第一个元素且mapped value是第二个元素。pair的定义可以在<utility>中找到，pair提供了一个方法方便创建键值对：

<code>template</code> <code><</code><code>class</code> <code>t1,</code><code>class</code> <code>t2>pair<t1,t2></code>

<code> </code><code>std::make_pair(</code><code>const</code> <code>t1& t1,</code><code>const</code> <code>t2& t2)</code>

<code> </code><code>return</code> <code>pair<t1,t2>(t1,t2);</code>

上面的例子中我们就用到了这个方法来创建(clientid,clientinfo)对，并作为insert()方法的参数。每个pair默认初始化每个元素的值为对应类型的默认值。

map类惯常提供了构造函数和析构函数，如下所示：

<code> </code><code>//construct/copy/destroy</code>

<code> </code><code>explicit</code> <code>map(</code><code>const</code> <code>cmp&=cmp(),</code><code>const</code> <code>a&=a());</code>

<code> </code><code>template</code><code><</code><code>class</code> <code>in>map(in first,in last,</code>

<code> </code><code>const</code> <code>com&=cmp(),</code><code>const</code> <code>a&=a());</code>

<code> </code><code>map(</code><code>const</code> <code>map&);</code>

<code> </code><code>map& operator=(</code><code>const</code> <code>map&);</code>

复制一个容器意味着为它的每个元素分配空间，并拷贝每个元素值。这样做是性能开销是很大的，应该仅当需要的时候才这样做。因此，map传的是引用。

前面我们已经说过，如果map中仅定义了一些key、mapped

value类型的信息而没有操作方法，就如定义个仅有字段的类意义不大甚至毫无意义。由此可见map中定义操作方法非常重要！前面的例子我们就用到了不少

方法，如返回迭代器的方法begin()、end()，键值对插入方法insert()。下面我们对map中的操作方法做个全面的介绍：

<code> </code><code>//map operations</code>

<code> </code><code>//find element with key k</code>

<code> </code><code>iterator find(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>const_iterator find(</code><code>const</code> <code>key_type& k)</code><code>const</code><code>;</code>

<code> </code><code>//find number of elements with key k</code>

<code> </code><code>size_type count()</code><code>const</code><code>;</code>

<code> </code><code>//find first element with key k</code>

<code> </code><code>iterator lower_bound(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>const_iterator lower_bound(</code><code>const</code> <code>key_type& k)</code><code>const</code><code>;</code>

<code> </code><code>//find first element with key greater than k</code>

<code> </code><code>iterator upper_bound(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>const_iterator upper_bound(</code><code>const</code> <code>key_type& k)</code><code>const</code><code>;</code>

<code> </code><code>//insert pair(key,value)</code>

<code> </code><code>pair<iterator,</code><code>bool</code><code>>insert(</code><code>const</code> <code>value_type& val);</code>

<code> </code><code>iterator insert(iterator pos,</code><code>const</code> <code>value_type& val);</code>

<code> </code><code>template</code><code><</code><code>class</code> <code>in></code><code>void</code> <code>insert(in first,in last);</code>

<code> </code><code>//erase element</code>

<code> </code><code>void</code> <code>erase(iterator pos);</code>

<code> </code><code>size_type erase(</code><code>const</code> <code>key_type& k);</code>

<code> </code><code>void</code> <code>erase(iterator first,iterator last);</code>

<code> </code><code>void</code> <code>clear();</code>

<code> </code><code>//number os elements</code>

<code> </code><code>size_type size()</code><code>const</code><code>;</code>

<code> </code><code>//size of largest possible map</code>

<code> </code><code>size_type max_size()</code><code>const</code><code>;</code>

<code> </code><code>bool</code> <code>empty()</code><code>const</code><code>{</code><code>return</code> <code>size()==0;}</code>

上面这些方法基本都能顾名思义（ps.由此可见，命名有多重要，我们平时要养成好的命名习惯，当然注释也必不可少！）。虽然已经非常清楚了了，但我还是想讲解一下以消除不惜要的误解和更好地应用这些方法。

find(k)方法简单地返回键值为k的元素的迭代器；如果没有元素的键值为k，则返回map的end()迭代器。由于map是按键key升序排列，所有查找的复杂度只有o(logn)。因此，我们通常会这样用这个方法：

<code><code>"color: #ff0000;"</code><code>> <code>"color: #ff0000;"</code><code>>clientid id=10;</code>

<code> </code><code>iterator i=clients.find(id);</code>

<code> </code><code>if</code><code>(i!=clients.end()){</code>

<code> </code><code>cout<<</code><code>"clientid: "</code><code><<id</code>

<code> </code><code><<</code><code>" exists in clients"</code><code><<endl;</code>

<code> </code><code><<</code><code>" doesn't exist in clients"</code><code><<endl;</code>

insert()方法

试图将一个（key,t）键值对加入map。因为键时唯一的，所以仅当map中不存在键值为k的键值对时插入才成功。该方法的返回值为

pair<iterator,bool>，如果插入成功bool值为true，iterator指向插入map中后的键值对。如下代码：

<code> </code><code>clientid id=110;</code>

<code> </code><code>clientinfo cltinfo;</code>

<code> </code><code>cltinfo.scanrate=10;</code>

<code> </code><code>cltinfo.socketaddr=</code><code>"110"</code><code>;</code>

<code> </code><code>pair<clientid,clientinfo> p110(id,cltinfo);</code>

<code> </code><code>pair<iterator,</code><code>bool</code><code>> p=clients.insert(p110);</code>

<code> </code><code>if</code><code>(p.second){</code>

<code> </code><code>cout<<</code><code>"insert success!"</code><code><<endl;</code>

<code> </code><code>cout<<</code><code>"insert failed!"</code><code><<endl;</code>

<code> </code><code>//i points to clients[110];</code>

<code> </code><code>iterator i=p.first;</code>

<code> </code><code>cout<<i->first<<endl;</code>

<code> </code><code>cout<<i->second.scanrate<<endl;</code>

<code> </code><code>cout<<i->second.socketaddr<<endl;</code>

上面我们看出，这里我们插入键值对是首先声明一个键值对pair<clientid,clientinfo> p110(id,cltinfo); 然后再插入，这个我们之前make_pair方法不一样，make_pair方法用的比较多。

erase()方法用法比较简单，比如像清除clientid为110的键值对，我们只需要对clients调用erase方法：clients.erase(clients.find(110));或者我们想清除clientid从1到10的键值对，我们可以这样调用erase()方法：clients.erase(clients.finds(1),clients.find(10));简单吧！别得意，你还需要注意，如果find(k)返回的是end()，这样调用erase()方法则是一个严重的错误，会对map造成破坏操作。

前面我们介绍了利用map的插入方法insert()，声明键值对pair或make_pair生成键值对然后我们可以轻松的将键值对插入map中。其实map还提供了更方便的插入操作利用下标（subscripting，[]）操作，如下：

<code>clientinfo cltinfo;</code>

<code>cltinfo.scanrate=10;</code>

<code>cltinfo.socketaddr=</code><code>"110"</code><code>;</code>

<code>clients[110]=cltinfo;</code>

这样我们就可以简单地将键值对插入到map中了。下标操作在map中式这样定义的：

<code> </code><code>//access element with key k</code>

<code> </code><code>mapped_type& operator[](</code><code>const</code> <code>key_type& k);</code>

我们来分析一下应用[]操作，插入键值对的过程：检查键k是否已经在map里。如果不，就添加上，以v作为它的对应值。如果k已经在map

里，它的关联值被更新成v。这里首先，查找110不在map中则创建一个键为110的键值对，并将映射值设为默认值，这里scanrate为

0，socketaddr为空；然后将映射值赋为cltinfo。如果110在map中已经存在的话，则只是更新以110为键的映射值。

从上面的分析可知：如果大量这样插入数据，会严重影响效率！如果你考虑效率问题，请使用insert操作。insert方法，节省了三次函数调用：一个建立临时的默认映射值的对象，一个销毁那个临时的对象和一个对映射值的赋值操作。

note1：如果k已经存在map中，[]效率反而比insert的效率高，而且更美观！如果能够兼顾这两者那岂不是很美妙！其实我们重写map中的[]操作：首先判断k是否已经在map中，如果没有则调用insert操作，否则调用内置的[]操作。如下列代码：

<code>///@param maptype-map的类型参数</code>

<code>///@param keyargtype-键的类型参数</code>

<code>///@param valueargtype-映射值的类型参数</code>

<code>///@return 迭代器，指向键为k的键值对</code>

<code>template</code><code><</code><code>typename</code> <code>maptype,</code>

<code> </code><code>typename</code> <code>keyargtype,</code>

<code> </code><code>typename</code> <code>valueargtype></code>

<code>typename</code> <code>maptype::iterator</code>

<code> </code><code>efficientaddorupdate(maptype& m,</code>

<code> </code><code>const</code> <code>keyargtype& k,</code>

<code> </code><code>const</code> <code>valueargtype& v)</code>

<code> </code><code>typename</code> <code>maptype::iterator ib = m.lower_bound(k);</code>

<code> </code><code>if</code><code>(ib != m.end()&&!(m.key_comp()(k,ib->first))) {</code>

<code> </code><code>//key已经存在于map中做更新操作</code>

<code> </code><code>ib->second = v; </code>

<code> </code><code>return</code> <code>ib; </code>

<code> </code><code>//key不存在map中做插入操作</code>

<code> </code><code>typedef</code> <code>typename</code> <code>maptype::value_type mvt;</code>

<code> </code><code>return</code> <code>m.insert(ib, mvt(k, v)); </code>

note2：我们视乎还忽略了一点，如果映射值mapped value的类型没有默认值，怎么办？这种情况请勿使用[]操作插入。

通过[]操作不仅仅是插入键值对，我们也可以通过键key检索出映射值mapped value。而且我们利用[]操作可以轻松地统计信息，如有这样这样一些键值对（book-name，count）对：

(book1,1)、(book2,2)、(book1,2)、(book3,1)、(book3,5)

我们计算每种book的数量总和。我们可以这样做：将它们读入一个map<string,int>：

<code> </code><code>map<string,</code><code>int</code><code>> bookmap;</code>

<code> </code><code>string book;</code>

<code> </code><code>int</code> <code>count;</code>

<code> </code><code>int</code> <code>total=0;</code>

<code> </code><code>while</code><code>(cin>>book>>count)</code>

<code> </code><code>bookmap[book]+=count;</code>

<code> </code><code>map<string,</code><code>int</code><code>>::iterator i;</code>

<code> </code><code>for</code><code>(i=bookmap.begin();i!=bookmap.end();i++)</code>

<code> </code><code>total+=i->second;</code>

<code> </code><code>cout<<i->first<<</code><code>'\t'</code><code><<i->second<<endl;</code>

<code> </code><code>cout<<</code><code>"total count:"</code><code><<total<<endl;</code>

结果如下所示：（注意按住ctrl+z键结束输入）

图2、程序运行结果

前面介绍了map，可以说已经非常清晰了。如果允许clientid重复的话，map就无能为力了，这时候就得multimap上场了！multimap允许键key重复，即一个键对应多个映射值。其实除此之外，multimap跟map是很像的，我们接下来在map的基础上介绍multimap。

multimap在std中的定义跟map一样只是类名为multimap，multimap几乎有map的所有方法和类型定义。

multimap不支持[]操作；但map支持

multimap的insert方法返回的是一个迭代器iterator，没有bool值；而map值（iterator，bool）的元素对

对应equal_range()、方法：

虽然在map和multimap都有，显然对multimap有更多的意义！equal_range()方法返回一个键key对应的多个映射值的上界和下

界的键值对的迭代器、lower_bound()方法返回键multimap中第一个箭为key的键值对迭代器、upper_bound()方法返回比

key大的第一个键值对迭代器。

假设我们想取出键为key的所有映射值，我们可以这样做：

<code>typedef</code> <code>int</code> <code>clientid;</code>

<code> </code><code>typedef</code> <code>multimap<clientid,clientinfo> clientedp;</code>

<code> </code><code>typedef</code> <code>multimap<clientid,clientinfo>::const_iterator iterator;</code>

<code> </code><code>clientinfo client[20];</code>

<code> </code><code>make_pair(10,client[i])); </code>

<code> </code><code>delete</code> <code>str,straddr;</code>

<code> </code><code>//find elements with key 10</code>

<code> </code><code>iterator lb=clients.lower_bound(10);</code>

<code> </code><code>iterator ub=clients.upper_bound(10);</code>

<code> </code><code>for</code><code>(iterator i=lb;i!=ub;i++)</code>

（说明：实际上，一般是不允许clientid重复的，这里只是为了举例。）这样是不是感觉很丑呢！事实上，我们可以更简单的这样：

<code>//find elements with key 10</code>

<code>pair<iterator,iterator> p=clients.equal_range(10);</code>

<code>for</code><code>(iterator i=p.first;i!=p.second;i++)</code>

<code> </code><code>cout<<</code><code>"clientid:"</code><code><<i->first<<endl;</code>

<code> </code><code>cout<<</code><code>"scanrate:"</code><code><<i->second.scanrate<<endl;</code>

<code> </code><code>cout<<</code><code>"socketaddr:"</code><code><<i->second.socketaddr<<endl;</code>

map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。

map的功能：

自动建立key －value的对应。key 和value可以是任意你需要的类型。

根据key值快速查找记录，查找的复杂度基本是log(n)。

快速插入key - value 记录。

快速删除记录

根据key 修改value记录。

遍历所有记录。

展望：本文不知不觉写了不少字了，但仍未深入涉及到map定义的第3个和第4个参数，使用的都是默认值。

template<class key,class t,class cmp=less<key>,

class a=allocator<pair<const key,t>>

感兴趣者，请查找相关资料or下面留言希望看到单独开篇介绍map第3个和第4个参数。您的支持，我的动力！ps：在此文的原因，在与公司做项目用到了map特此总结出来与大家共享，不过在进行个人总结过程中，难免会有疏漏或不当之处，请不吝指出。

STL之Map

继续阅读

C语言第四章自述2第四章选择结构程序设计

面试题:vector和map的区别，异同。空间分布，100万数据存哪个比较合适。一、迭代器区别二、vector三、Map、Set四、vector_map 为什么比map效率高五、如何选择六、容器选择原则七、效率对比

C++ 多线程用条件变量确定线程的执行顺序而不是使用 sleep(1)

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

成员函数初始化列表

2021-08-13c++——类之操作符重载

swmm与lisflood-fp源码如何一起编译 CMake命令

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

C++ 第十五周报告1--《冒泡法排序》

C++实现简单顺序表

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述