C++11:unordered_map

发表于

Unordered Map

Basic Usage Detail and Example

Unordered map是C++11新出的特性，它提供了一种map的实现机制，可以存储键值对。Unordered map内部实现了哈希函数，当我们插入一个新的元素时：

  • 首先对key做哈希函数处理，然后选择一个合适的bucket；
  • 比较该bucket下的key是否重复；
  • 在不重复的情况下，添加该元素到bucket中；

因此Unordered map时无序的，并且其搜索元素的时间复杂度为O(1)。

Different Ways to initialize an unordered_map

unordered map提供了三种不同的重载构造器：

  • 通过initializer_list初始化
1
2
3
4
std::unordered_map<std::string, int> wordMap({
												  { "First", 1 },
												  { "Second", 2 },
												  { "Third", 3 } });
  • 使用iterable range初始化
1
std::unordered_map<std::string, int> wordMap_2(wordMap.begin(), wordMap.end());
  • 使用另一个unordered_map初始化
1
std::unordered_map<std::string, int> wordMap_3(wordMap);

Searching in unordered_map

unordered_map提供了一个成员函数find()，改函数接受一个key作为参数，在找到元素的时候就会返回一个相对应的迭代器，否则会返回map的尾部迭代器。

1
iterator find ( const key_type& k );

Different ways to insert elements in an unordered_map

unordered_map提供了多种insert()成员函数的重载版本，我们来一一讨论：

  • 通过initializer_list插入多个元素；
1
2
3
4
5
6
void insert ( initializer_list<value_type> il );

// Example
std::unordered_map<std::string, int> wordMap;
// Inserting elements through an initializer_list
wordMap.insert({ {"First", 1}, {"Second", 2}, {"Third", 3} } );

这种插入方式有一个缺点，因为insert()返回的是void类型，因此在添加重复key的元素时，用户无法确定插入是否成功。

  • unordered_map提供了一个重载版本，它接受std::pair of key – value 作为参数，并返回一对迭代器和bool变量，通过该bool变量我们就可以判断插入是否成功；
1
2
3
4
5
6
7
8
9
10
pair<iterator,bool> insert ( const value_type& val );

typedef std::unordered_map<std::string, int>::iterator UOMIterator;
// Pair of Map Iterator and bool value
std::pair< UOMIterator , bool> result;
 
// Inserting an element through pair
result = wordMap.insert(std::make_pair<std::string, int>("Second", 6));
if(result.second == false)
      std::cout<<"Element 'Second' not inserted again"<<std::endl;

Erasing an element

要想从unordered_map中删除元素，其提供了两种方式，如下：

  • 通过提供key类型，即可删除该元素；
1
size_type erase ( const key_type& k );

它的返回值为0或1，对应的是被删除的元素数量

  • 通过迭代器删除元素；
1
iterator erase ( const_iterator pos );

改函数接收一个迭代器对象，并删除其对应的元素。在删除1，返回指向被删除元素对应的下一个元素的迭代器。因此需要注意的是，在遍历迭代器的过程中删除元素，其返回值是一个有效的迭代器，为被删除元素的下一个。

std::map vs std::unordered_map

本节主要讨论std::map与std::unordered_map的区别，它们虽然都是存储键值对与实现了有效插入、搜索和删除操作，但有着以下的不同：

  • 内部实现：与std::unordered_map不同，std::map是通过二叉搜索树存储元素的，因此它能通过key进行排序；
  • 内存使用：std::unordered_map需要更多的内存来存储哈希表；
  • 搜索的时间复杂度：由于std::map是树的结构，因此其时间复杂度为O(log n)，而std::unordered_map最好的时间复杂度是O(1)，最坏的情况是O(n)，即所有元素在同一个bucket；
  • 自定义key的使用方法：使用自定义key时，对于std::map来说，需要重载<操作符或者传入外部的comparator比较器，对于std::unordered_map则需要提供std::hash<K>，同时我们还需要重载==操作符；