【学习笔记】《STL使用入门教程》第五讲：容器map、multimap

晓石头的博客
邮箱：[e-mail]
转载请注明出处，原文链接：http://blog.csdn.net/qiulanzhu/article/details/50493044

1. map/multimap的介绍

①、map是标准的关联式容器，一个map是一个键值对序列，即（key,value)对。它提供基于key的快速检索能力。

 

②、map中key值是唯一的。集合中的元素按一定的序列排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

 

③、map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比ector快。

 

④、map可以直接存取key所对应的value,支持[]操作符，如map[key]=value

 

⑤、multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。但multimao不支持[]操作符。

 

2. map/multimap对象的默认构造函数

map/multimap采用模版类实现，对象的默认构造形式：

map<T1,T2> mapTT;

multimap<T1,T2> multimapTT;

如：

map<int, char> mapA;

map<string, float> mapB;

//其中T1,T2还可以用各种指针类型或自定义类型

 

3. map对象的拷贝构造与赋值

map(const map &mp);//拷贝构造函数

map& operator=(const map &map);//重载等号操作符

如：

map<T1, T2> mapIntA,mapIntC;

map<T1, T2> mapIntB(mapIntA);

 

map<T1, T2> mapIntD;

mapIntD = mapIntC;

4. map的插入与迭代器

在map中插入元素的三种方式：

map.insert(...);//往容器插入元素，返回pair<iterator,bool>

 

1、通过pair的方式插入对象

mapStu.insert( pair<int,string>(3, ”小张") )；

 

2、通过value_type的方式插入对象

mapStu.insert( map<int, string>::value_type(1, "小李") );

 

3、通过数组的方式插入值

mapStu[3] = "小刘"；

mapStu[5] = "小王"；

 

前两种方法，采用的是insert()方法，该方法返回值为pair<iterator,bool>

pair< map<int, string>::iterator, bool> pairResult = mapStu.insert(pair<int, string>(3, "小张"));

如果插入成功，则：

(pairResult.first)->first == 3

(pairResult.first)->second == "小张"

pairResult.second == ture。

 

第三种方式非常直观，但存在性能问题。

插入3时，先在mapStu中查找主键为3的项，若没有，则将一个键为3,值为初始值的对组插入到mapStu中，然后再将值修改成“小刘”。若发现已存在3这个键，则修改这个键对应的value。

 

5. map的取值

string strName = mapStu[2];//取操作

//只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。

 

6. map的排序

map<T1, T2, less<T1>> mapA;//该容器是按键的升序方式排列元素。

//未指定函数对象，默认采用less<T1>函数对象。

 

map<T1, T2, greater<T1>> mapB;//该容器是按键的降序方式排列元素。

less<T1>与greater<T1> 可以替换成其它的函数对象functor。

可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。

 

7. map的大小

map.size();//返回容器中元素的数目

map.empty();//判断容器是否为空

 

8. map的删除---删

map.clear();//删除所有元素

map.erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器

map.erase(beg,end);//删除区间[beg, end)所有元素，返回下一个元素的迭代器。

map.erase(keyElem);//删除容器中key为keyElem的对组。

 

9.map容器元素的交换---改

map.swap(mp);//交换两个集合容器

9. map的查找---查

map.find(key);查找键key是否存在，如存在，返回该键的元素的迭代器；若不存在，返回map.end();

map.count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么为0，要么为1；对multimap来说返回值>=0。

 

map.lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器 

map.upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器

map.equal_range(keyElem);//返回一个pair，

//pair.first为第一个key>=keyElem元素的迭代器

//pair.second为第一个key>keyElem元素的迭代器

 

10. mulmap多元素相同关键字的查找---查

在multimap中，同一个键关联的元素必然相邻存放。基于这个事实，就可以将某个键对应的值一一输出。

1、使用find和count函数。count函数求出某个键出现的次数，find函数返回一个迭代器，指向第一个拥有正在查找的键的实例。

2、使用lower_bound(key)和upper_bound(key)

      lower_bound(key)返回一个迭代器，指向键不小于k的第一个元素

      upper_bound(key)返回一个迭代器，指向键不大于k的第一个元素

3、使用equat_range(key)

      返回一个迭代器的pair对象，first成员等价于lower_bound(key)，second成员等价于upper_bound(key)

 

例：

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

int main()
{
    multimap<string,int> m_map;
    string s("中国"),s1("美国");
    m_map.insert(make_pair(s,50));
    m_map.insert(make_pair(s,55));
    m_map.insert(make_pair(s,60));
    m_map.insert(make_pair(s1,30));
    m_map.insert(make_pair(s1,20));
    m_map.insert(make_pair(s1,10));
    //方式1
    int k;
    multimap<string,int>::iterator m;
    m = m_map.find(s);
    for(k = 0;k != m_map.count(s);k++,m++)
        cout<<m->first<<"--"<<m->second<<endl;
    //方式2
    multimap<string,int>::iterator beg,end;
    beg = m_map.lower_bound(s1);
    end = m_map.upper_bound(s1);
    for(m = beg;m != end;m++)
        cout<<m->first<<"--"<<m->second<<endl;
    //方式3
    beg = m_map.equal_range(s).first;
    end = m_map.equal_range(s).second;
    for(m = beg;m != end;m++)
        cout<<m->first<<"--"<<m->second<<endl;
    return 0;
}