c++ 11标准模板（STL） std::map(四）

定义于头文件<map>

template<     class Key,     class T,     class Compare = std::less<Key>,     class Allocator = std::allocator<std::pair<const Key, T> > > class map;	(1)
namespace pmr {     template <class Key, class T, class Compare = std::less<Key>>     using map = std::map<Key, T, Compare,                          std::pmr::polymorphic_allocator<std::pair<const Key,T>>> }	(2)	(C++17 起)

std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。

在每个标准库使用比较 (Compare) 概念的位置，以等价关系检验唯一性。不精确而言，若二个对象 a 与 b 互相比较不小于对方 ： !comp(a, b) && !comp(b, a) ，则认为它们等价（非唯一）。

std::map 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。

元素访问

访问指定的元素，同时进行越界检查

std::map<Key,T,Compare,Allocator>::at

T& at( const Key& key );	(1)	(C++11 起)
const T& at( const Key& key ) const;	(2)	(C++11 起)

返回到拥有等于 key 的关键的元素被映射值的引用。若无这种元素，则抛出 std::out_of_range 类型异常。

参数

key

-

要找到的元素的关键

返回值

到请求元素的被映射值的引用

异常

若容器无拥有指定 key 的元素则为 std::out_of_range

复杂度

与容器大小成对数。

访问或插入指定的元素

std::map<Key,T,Compare,Allocator>::operator[]

T& operator[]( const Key& key );	(1)
T& operator[]( Key&& key );	(2)	(C++11 起)

返回到映射到等于 key 的关键的值的引用，若这种关键不存在则进行插入。

1) 若关键不存在则插入 value_type(key, T()) 。此函数等价于 return insert(std::make_pair(key, T())).first->second; - key_type 必须满足可复制构造 (CopyConstructible) 的要求。 - mapped_type 必须满足可复制构造 (CopyConstructible) 和 可默认构造 (DefaultConstructible) 的要求。 若进行插入，则值初始化被映射值（对类类型为默认构造，否则为零初始化）并返回到它的引用。

(C++11 前)

1) 若关键不存在，则插入从 std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>() 原位构造的 value_type 对象。此函数等价于 return this->try_emplace(key).first->second; 。 (C++17 起) 使用默认分配器时，这导致从 key 复制构造关键，并值初始化被映射值。 - value_type 必须从 std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>() 可就位构造 (EmplaceConstructible) 。使用默认分配器时，这表明 key_type 必须可复制构造 (CopyConstructible) 而 mapped_type 必须可默认构造 (DefaultConstructible) 。 2) 若关键不存在，则插入从 std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>() 原位构造的 value_type 对象。此函数等价于 return this->try_emplace(std::move(key)).first->second; 。 (C++17 起) 使用默认分配器时，这导致从 key 移动构造关键，并值初始化被映射值。 - value_type 必须从 std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>() 可就位构造 (EmplaceConstructible) 。使用默认分配器时，这表明 key_type 必须可移动构造 (MoveConstructible) mapped_type 必须可默认构造 (DefaultConstructible) 。

(C++11 起)

没有迭代器或引用被非法化。

参数

key

-

要寻找的元素关键

返回值

若不存在拥有关键 key 的元素，则为到新元素被映射值的引用。否则为到既存的关键等价于 key 的元素的被映射值的引用。

异常

若任何操作抛出异常，则插入无效果。

复杂度

与容器大小成对数。

注意

出版的 C++11 和 C++14 标准中，指定此函数要求 mapped_type 为可默认插入 (DefaultInsertable) 且 key_type 为可复制插入 (CopyInsertable) 或可移动插入 (MoveInsertable) 到 *this 。此规定有缺陷并为 LWG 问题 2469 所修复，而上面的描述合并了该问题的解决方案。

然而，已知一个实现（ libc++ ）通过二个分离的分配器 construct() 调用构造 key_type 和 mapped_type 对象，可认为如发布时的标准所要求，而非原位构造 value_type 对象。

operator[] 非 const ，因为若不关键不存在则它插入关键。若此行为非所欲或容器为 const ，则可用 at() 。

insert_or_assign() 返回的信息多于 operator[] ，而且不要求 mapped_type 可默认构造。

(C++17 起)

 

调用示例

#include <iostream>
#include <forward_list>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <map>
#include <time.h>using namespace std;struct Cell
{int x;int y;Cell() = default;Cell(int a, int b): x(a), y(b) {}Cell &operator +=(const Cell &cell){x += cell.x;y += cell.y;return *this;}Cell &operator +(const Cell &cell){x += cell.x;y += cell.y;return *this;}Cell &operator *(const Cell &cell){x *= cell.x;y *= cell.y;return *this;}Cell &operator ++(){x += 1;y += 1;return *this;}bool operator <(const Cell &cell) const{if (x == cell.x){return y < cell.y;}else{return x < cell.x;}}bool operator >(const Cell &cell) const{if (x == cell.x){return y > cell.y;}else{return x > cell.x;}}bool operator ==(const Cell &cell) const{return x == cell.x && y == cell.y;}
};struct myCompare
{bool operator()(const int &a, const int &b){return a < b;}
};std::ostream &operator<<(std::ostream &os, const Cell &cell)
{os << "{" << cell.x << "," << cell.y << "}";return os;
}std::ostream &operator<<(std::ostream &os, const std::pair<const int, Cell> &pCell)
{os << pCell.first << "-" << pCell.second;return os;
}int main()
{auto genKey = [](){return std::rand() % 10 + 100;};auto generate = [](){int n = std::rand() % 10 + 100;Cell cell{n, n};return cell;};std::map<int, Cell> map1;for (size_t index = 0; index < 5; index++){map1.insert({genKey(), generate()});}std::cout << "map1:    ";std::copy(map1.begin(), map1.end(),std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));std::cout << std::endl;std::cout << std::endl;//返回到拥有等于 key 的关键的元素被映射值的引用。//若无这种元素，则抛出 std::out_of_range 类型异常。std::cout << "T& at( const Key& key );" << std::endl;for (const std::pair<int, Cell> it : map1){Cell cell = generate();map1.at(it.first) = cell;std::cout << "map1.at( " << it.first << " ) = " << cell << std::endl;}std::cout << std::endl;std::cout << "const T& at( const Key& key ) const;" << std::endl;for (const std::pair<int, Cell> it : map1){std::cout << "map1.at( " << it.first << " ) : " << map1.at(it.first) << std::endl;}std::cout << std::endl;std::cout << std::endl;//返回到映射到等于 key 的关键的值的引用，若这种关键不存在则进行插入。std::cout << "T& operator[]( const Key& key );" << std::endl;std::map<int, Cell> map2;while (map2.size() < 5){//1) 若关键不存在则插入 value_type(key, T()) 。//此函数等价于 return insert(std::make_pair(key, T())).first->second;map2[genKey()] = generate();}std::cout << "map2:    ";std::copy(map2.begin(), map2.end(),std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));std::cout << std::endl;std::cout << std::endl;std::cout << "T& operator[]( Key&& key );" << std::endl;std::map<int, Cell> map3;while (map3.size() < 5){//1) 若关键不存在则插入 value_type(key, T()) 。//此函数等价于 return insert(std::make_pair(key, T())).first->second;map3[std::move(genKey())] = generate();}std::cout << "map3:    ";std::copy(map3.begin(), map3.end(),std::ostream_iterator<std::pair<const int, Cell>>(std::cout, " "));std::cout << std::endl;std::cout << std::endl;return 0;
}

输出