转载自：【C++】undered_map的用法总结(1) - 我得去图书馆了 - 博客园

1.介绍

unordered_map是一个关联容器，内部采用的是hash表结构，拥有快速检索的功能。

1.1 特性

关联性：通过key去检索value，而不是通过绝对地址（和顺序容器不同）
无序性：使用hash表存储，内部无序
Map : 每个值对应一个键值
键唯一性：不存在两个元素的键一样
动态内存管理：使用内存管理模型来动态管理所需要的内存空间

1.2 Hashtable和bucket

由于unordered_map内部采用的hashtable的数据结构存储，所以每个特定的key会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable是可能存在冲突的（多个key通过计算映射到同一个位置），在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的（像桶子一样，可以装多个元素）。

所以unordered_map内部其实是由很多哈希桶组成的，每个哈希桶中可能没有元素，也可能有多个元素。

2. 模版

1 template < class Key,                           　　　　　 //unordered_map::key_type
2            class T,                             　　　　　 //unordered_map::mapped_type
3            class Hash = hash<Key>,    　　　　　　　　　　　 //unordered_map::hasher 
4            class Pred = equal_to<Key>,   　　　　 　　　　　//unordered_map::key_equal
5            class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
6            > class unordered_map;

主要使用的也是模板的前2个参数<键，值>

1 unordered_map<const Key, T> map;

2.1 迭代器

unordered_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值。

1 unordered_map<Key,T>::iterator it;
2 (*it).first;             // the key value (of type Key)
3 (*it).second;            // the mapped value (of type T)
4 (*it);                   // the "element value" (of type pair<const Key,T>) 

它的键值分别是迭代器的first和second属性。

1 it->first;               // same as (*it).first   (the key value)
2 it->second;              // same as (*it).second  (the mapped value) 

3. 函数

3.1 构造函数

unordered_map的构造方式有几种： 

• 构造空的容器 
• 复制构造  
• 范围构造 
• 用数组构造

运行结果：

3.2 容量操作

3.2.1 size

1 size_type size() const noexcept;

返回unordered_map的大小。

3.2.2 empty

1 bool empty() const noexcept;

• 为空返回true 
• 不为空返回false，和用size() == 0判断一样。

3.3 元素操作

3.3.1 find

1 iterator find ( const key_type& k );          // 根据key获取value

查找key所在的元素。

• 找到：返回元素的迭代器。通过迭代器的second属性获取值。
• 没找到：返回unordered_map::end。

3.3.2 insert

插入有几种方式：

• 复制插入(复制一个已有的pair的内容)
• 数组插入（直接插入一个二维数组）
• 范围插入（复制一个起始迭代器和终止迭代器中间的内容）
• 数组访问模式插入(和数组的[]操作很相似)

具体的例子可以看后面示例代码。

3.3.3 at

1 mapped_type& at ( const key_type& k );       //根据key获得value

查找key所对应的值

• 如果存在：返回key对应的值，可以直接修改，和[]操作一样。
• 如果不存在：抛出 out_of_range 异常.

mymap.at(“Mars”) = 3396; //mymap[“Mars”] = 3396

3.3.4 erase

擦除元素也有几种方式：

• 通过位置（迭代器）

1 iterator erase ( const_iterator position );

• 通过key

1 size_type erase ( const key_type& k );

• 通过范围（两个迭代器）

1 iterator erase ( const_iterator first, const_iterator last );

3.3.5 clear

1 void clear() noexcept

清空unordered_map

3.3.6 swap

1 void swap ( unordered_map& ump );

交换两个unordered_map（注意，不是交换特定元素，是整个交换两个map中的所有元素）

3.3.7 示例代码

运行结果：

3.4 迭代器和bucket操作

3.4.1 begin

1 iterator begin() noexcept;
2   local_iterator begin ( size_type n );

• begin() : 返回开始的迭代器（和你的输入顺序没关系，因为它的无序的）
• begin(int n) : 返回n号bucket的第一个迭代器

3.4.2 end

1  iterator end() noexcept;
2   local_iterator end( size_type n );

• end(): 返回结束位置的迭代器
• end(int n) : 返回n号bucket的最后一个迭代器

3.4.3 bucket

1 size_type bucket ( const key_type& k ) const;

返回通过哈希计算key所在的bucket（注意：这里仅仅做哈希计算确定bucket，并不保证key一定存在bucket中！）

3.4.4 bucket_count

1 size_type bucket_count() const noexcept;

返回bucket的总数

3.4.5 bucket_size

1 size_type bucket_size ( size_type n ) const;

返回第i个bucket的大小（这个位置的桶子里有几个元素，注意：函数不会判断n是否在count范围内）

3.4.6 示例代码

 

运行结果：