C++学习笔记 —— 关联容器map

2018-09-08 本文已影响2人 Leung_ManWah

一、关联容器

关联容器（associative container）是对容器概念的另一个改进。关联容器将值与键关联在一起，并使用键来查找值。例如，值可以是表示雇员信息（如姓名、地址、电话）的结构，而键可以是唯一的员工编号。为获取雇员信息，程序将使用键查找雇员结构。对容器X，表达式X::key_type指出了键的类型。

关联容器的优点在于，它提供了对元素的快速访问。与序列相似，关联容器也允许插入新元素，但不能指定元素的插入位置。原因是关联容器通常有用于确定数据放置位置的算法，以便能够快速检索信息。

二、map

2.1 简介

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

在map中，值与键的类型不同，键是唯一的，每个键只对应一个值。multimap与map相似，只是一个键可以与多个值相关联。

2.2 头文件

#include	<map>（以前的map.h）

2.3 构造函数

map对象是模板类，需要关键字和存储对象两个模板参数：
std:map<int, string> personnel;
这样就定义了一个用int作为索引,并拥有相关联的指向string的指针。

为了使用方便，可以对模板类进行一下类型定义，
typedef map<int, CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;

2.4 基本操作函数

函数	作用
begin()	返回指向map头部的迭代器
clear()	删除所有元素
count()	返回指定元素出现的次数
empty()	如果map为空则返回true
end()	返回指向map末尾的迭代器
equal_range()	返回特殊条目的迭代器对
erase()	删除一个元素
find()	查找一个元素
get_allocator()	返回map的配置器
insert()	插入元素
key_comp()	返回比较元素key的函数
lower_bound()	返回键值>=给定元素的第一个位置
max_size()	返回可以容纳的最大元素个数
rbegin()	返回一个指向map尾部的逆向迭代器
rend()	返回一个指向map头部的逆向迭代器
size()	返回map中元素的个数
swap()	交换两个map
upper_bound()	返回键值>给定元素的第一个位置
value_comp()	返回比较元素value的函数

2.4.1 遍历元素

2.4.1.1 迭代器遍历

反相迭代器：

Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));

map<int, string>::reverse_iterator iter;
for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
{
    cout<<iter->first<<"   "<<iter->second<<endl;
}

2.4.1.2 数组遍历

Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));

int nSize = mapStudent.size();
for(int nIndex = 1; nIndex <= nSize; nIndex++) 
{
    cout<<mapStudent[nIndex]<<endl;
}

2.4.1.3 基于范围的for循环（C++11）

Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));

for(auto & iter : mapStudent)
{
     cout<<iter->second<<endl;
}

在这种for循环中，括号内的代码声明一个类型与容器存储的内容相同的变量，然后指出了容器的名称。接下来，循环体使用指定的变量依次访问容器的每个元素。

2.4.2 插入元素

2.4.2.1 用数组方式插入数据

Map<int, string> mapStudent;
mapStudent[1] =  “one”;
mapStudent[2] =  “two”;

这样非常直观，但存在一个性能的问题。插入2时,先在mapStudent中查找主键为2的项，没发现，然后将一个新的对象插入mapStudent，键是2，值是一个空字符串，插入完成后，将字符串赋为"two"; 该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。我们可以用以下方法来避免开销：
mapStudent.insert(map<int, string> :: value_type(2, "two"));

2.4.2.2 用insert函数插入value_type数据

#include <map>
#include <string>
#include <iostream>

using namespace std;

Int main()
{
    Map<int, string> mapStudent;
    mapStudent.insert(map<int, string>::value_type (1, “student_one”));
    mapStudent.insert(map<int, string>::value_type (2, “student_two”));
    mapStudent.insert(map<int, string>::value_type (3, “student_three”));

    map<int, string>::iterator  iter;
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
    {
        cout<<iter->first<<”   ”<<iter->second<<endl;
    }
}

2.4.2.3 用insert函数插入pair数据

Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));

可用make_pair代替为：

Map<int, string> mapStudent;
mapStudent.insert(make_pair(1, “student_one”));
mapStudent.insert(make_pair(2, “student_two”));

2.4.3 删除元素

这里要用到erase函数，它有三个重载了的函数，下面在例子中详细说明它们的用法
首先，

Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));

2.4.3.1 用迭代器删除

map<int, string>::iterator iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);

2.4.3.2 用关键字删除

int n = mapStudent.erase(1);  // 如果删除了会返回1，否则返回0

2.4.3.3 用迭代器，成片的删除

mapStudent.earse(mapStudent.begin(), mapStudent.end());
// 成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合

相当于clear()

2.4.4 查找元素

2.4.4.1 count函数

用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了。

2.4.4.2 find函数

用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器，程序说明：

map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));

map<int, string>::iterator iter;
iter = mapStudent.find(1);
if(iter != mapStudent.end())
{
    cout<<"Find, the value is "<<iter->second<<endl;
}
else
{
    cout<<"Do not Find"<<endl;
}

2.4.4.3 lower_bound和upper_bound函数

成员函数lower_bound()和upper_bound()将键作为参数，且工作原理与处理set时相同。

2.4.4.4 equal_range函数

成员函数equal_range函数用键作为参数，且返回两个迭代器，它们表示的区间与该键匹配。为返回两个值，该方法将它们封装在一个pair对象中，这里pair的两个模板参数都是迭代器。

map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));

pair<map<int, string>::iterator, map<int, string>::iterator> range = mapStudent.equal_range(2);
std::map<int, string>::iterator it;
for (it = range.first; it != range.second; ++it)
    cout << (*it).second << endl;

在声明中可使用C++11自动类型推断功能，简化代码如下：

auto range = mapStudent.equal_range(2);
for (auto it = range.first; it != range.second; ++it)
    cout << (*it).second << endl;

三、pair

C++标准程序库中凡是“必须返回两个值”的函数，也都会利用pair对象。

pair可以将两个值视为一个单元。容器类别map和multimap就是使用pairs来管理其健值/实值(key/value)的成对元素。

pair被定义为struct,因此可直接存取pair中的个别值。

两个pairs互相比较时，第一个元素正具有较高的优先级。
例：

namespace std
{ 
  template <class T1, class T2> 
  bool operator< (const pair<T1, T2>&x, const pair<T1, T2>&y)
  { 
    return x.first<y.first || ((y.first<x.first)&&x.second<y.second); 
  } 
}

3.1 pair的应用

pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

四、make_pair

无需写出型别，就可以生成一个pair对象
例：
std::make_pair(42, '@');
而不必费力写成：
std::pair<int, char>(42, '@')

当有必要对一个接受pair参数的函数传递两个值时， make_pair()尤其显得方便，

void f(std::pair<int, const char*>);

void foo
{ 
  f(std::make_pair(42, '@')); //pass two values as pair 
}

4.1 make_pair函数

template pair make_pair(T1 a, T2 b) { return pair(a, b); }
很明显，我们可以使用pair的构造函数也可以使用make_pair来生成我们需要的pair。一般make_pair都使用在需要pair做参数的位置，可以直接调用make_pair生成pair对象很方便，代码也很清晰。另一个使用的方面就是pair可以接受隐式的类型转换，这样可以获得更高的灵活度。灵活度也带来了一些问题如：
std::pair<int, float>(1, 1.1);
std::make_pair(1, 1.1);
是不同的，第一个就是float，而第2个会自己匹配成double。

• 由 Leung 写于 2018 年 9 月 8 日

• 参考：C++ map的基本操作和使用
　　　　 stl map用法和make_pair函数
　　　　C++ Primer Plus(第6版)