简介

map与multimap是键值对容器，支持根据键查找值。multimap可以储存重复的键，而前者只能储存唯一的键。使用两者之前要包含时头文件
为实现快速查找，map与multimap的内部结构看起来像二叉树，这意味着在map或multimap中插入数据时将对其进行排序；因此，位于map中特定位置的元素不能替换为值不同的新元素。

map及multimap的实例化

  • 实例化map和multimap的语法如下： 

    1
    2
    3
    4
    5
    #include <iostream>
    using namespace std;
    ...
    map<keyType, valueType, Predicate = std::less<keyType>> mapObject;
    multimap<keyType, valueType, Predicate = std::less<keyType>> multimapObject;

其中Predicate可图换为自定义谓词———一个实现了operator()的类或结构。例：

1
2
3
4
5
6
7
8
9
//实现从大到小排序的谓词
template<typename KeyType>
struct ReverseSort
{
	bool operator()(const KeyType& key1, const KeyType& key2)
	{
		return (key1 > key2);
	}
}

插入元素

在两种容器之中插入元素时，都可以使用成员函数insert:
map<int, string> mapInt_String
mapInt_String.insert(make_pair(0, "Number One"));
mapInt_String.insert(pair<int, string>(2, "Number Two"));

  • std::pair
    主要作用是将两个数据组合成一个数据，两个数据可以是同一类型或者不同类型。
    pair实质上是一个结构体，其主要的两个成员变量是first和second，这两个变量可以直接使用。
    初始化一个pair可以使用构造函数，也可以使用std::make_pair函数。
    make_pair函数的定义如下：
    template pair make_pair(T1 a, T2 b) { return pair(a, b); }
    在需要pair类型做参数的位置，可以直接调用make_pair生成pair对象。
    mark_pair可以接受隐式的类型转换，这样可以获得更高的灵活度。但是这样会出现如下问题：
    例如有如下两个定义： 
    `std::pair<int, float>(1, 1.1);`    
`std::make_pair(1, 1.1);`
    使用构造函数生成的pair对象的second变量是float类型，而用make_pair生成的pair对象的second变量将是double类型。

查找元素

可使用成员方法find在这两个容器中查找元素。find返回一个迭代器：
auto iPairFind = mapInt_String.find(key);
使用迭代器iPairFind之前，要检查该迭代器：
if(iPairFind != mapInt_String.end())

  • 注意：
    在multimap中，因为key值不唯一，因此在使用find查找元素时，返回的迭代器指向首次查找得到的元素。如果想得到所有值，应该使用multimap::count()确定有多少值与指定的key对应。

删除元素

使用成员函数erase对来删除元素。

  • 通过指定的key来删除元素：
    mapObject.erase(key);
  • 删除迭代器指向的元素：
    mapObject.erase(iElement);
  • 使用迭代器指定边界，删除指定范围内的所有元素：
    mapObject.erase(iLowBound, iUpperBound);

std::unordered_map与std::unordered_multimap

从C++11起，STL支持散列映射——std::unordered_map,使用时需包含头文件<unordered_map>
unordered_map的的平均插入和删除时间是固定的，查找元素的时间也是固定的。


 上一页

设计模式

 评论