Cpp

unordered_map

scorlw 发布于

unordered_map

c++

1.std::unordered_map 的定义与特性

所在头文件：

std::unorederd_map 类模板：

1
2
3
4
5
6
template < class Key,                                   // unordered_map::key_type
           class T,                                     // unordered_map::mapped_type
           class Hash = hash<Key>,                      // unordered_map::hasher
           class Pred = equal_to<Key>,                  // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> > // unordered_map::allocator_type
           > class unordered_map;
  • 关联性：std::unorederd_map 是一个关联容器，其中的元素根据键来引用，而不是根据索引来引用。
  • 无序性：在内部，std::unordered_map中的元素不会根据其键值或映射值按任何特定顺序排序，而是根据其哈希值组织到桶中，以允许通过键值直接快速访问各个元素（常量的平均时间复杂度）。
  • 唯一性：std::unorederd_map中的元素的键是唯一的。

2.构造 std::unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// constructing unordered_maps
#include <iostream>
#include <string>
#include <unordered_map>

typedef std::unordered_map<std::string,std::string> stringmap;

stringmap merge (stringmap a,stringmap b) {//合并a和b
  	stringmap temp(a); 
  	temp.insert(b.begin(),b.end()); 
  	return temp;
}

int main () {
	  stringmap first;                              // empty

	  // 一个元素为：{key, value}
	  stringmap second ( {{"apple","red"}, {"lemon","yellow"}} );       // init list
	  stringmap third ( {{"orange","orange"}, {"strawberry","red"}, {"apple","green"}} );  // init list
	  stringmap fourth (second);                    // copy
	  stringmap fifth (merge(third,fourth));        // move
	  stringmap sixth (fifth.begin(),fifth.end());  // range
	
	  std::cout << "sixth contains:";
	  for (auto& x: sixth) 
	  		std::cout << " " << x.first << ":" << x.second;
	  std::cout << std::endl;
      system("pause");
	  return 0;
}

IO：

1
sixth contains: orange:orange lemon:yellow apple:green strawberry:red

3.赋值操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// assignment operator with unordered_map
#include <iostream>
#include <string>
#include <unordered_map>

typedef std::unordered_map<std::string,std::string> stringmap;

stringmap merge (stringmap a,stringmap b) {
  	stringmap temp(a); 
  	temp.insert(b.begin(),b.end()); 
  	return temp;
}

int main () {
	  stringmap first, second, third;
	  
	  first = {{"AAPL","Apple"}, {"MSFT","Microsoft"}};  // init list
	  second = {{"GOOG","Google"}, {"ORCL","Oracle"}};   // init list
	  third = merge(first,second);                       // move
	  first = third;                                     // copy
	
	  std::cout << "first contains:";
	  for (auto& elem: first) 
	  		std::cout << " " << elem.first << ":" << elem.second;
	  std::cout << std::endl;
	
	  return 0;
}

IO：

1
first contains: GOOG:Google MSFT:Microsoft ORCL:Oracle AAPL:Apple

4.迭代器操作

4.1 指向整个容器中的元素

即，“第一个”指整个容器中的第一个，“尾后”指整个容器中的尾后。

函数声明 解释
iterator begin() noexcept;
const_iterator begin() const noexcept;		 返回一个迭代器，指向第一个元素
iterator end() noexcept;
const_iterator end() const noexcept;		 返回一个迭代器，指向尾后元素
const_iterator cbegin() const noexcept; 返回一个常量迭代器，指向第一个元素
const_iterator cend() const noexcept; 返回一个常量迭代器，指向尾后元素 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// unordered_map::cbegin/cend example
#include <iostream>
#include <unordered_map>

int main () {
	  std::unordered_map<std::string,std::string> mymap;
	  mymap = {{"Australia","Canberra"},{"U.S.","Washington"},{"France","Paris"}};
	
	  std::cout << "mymap contains:";
	  for ( auto it = mymap.cbegin(); it != mymap.cend(); ++it )
	      std::cout << " " << it->first << ":" << it->second;  // cannot modify *it
	  std::cout << std::endl;
	
	  std::cout << "mymap's buckets contain:\n";
	  for ( unsigned i = 0; i < mymap.bucket_count(); ++i) {
	      std::cout << "bucket #" << i << " contains:";
	      for ( auto local_it = mymap.cbegin(i); local_it!= mymap.cend(i); ++local_it )
	          std::cout << " " << local_it->first << ":" << local_it->second;
	      std::cout << std::endl;
	  }
	
	  return 0;
}

IO:

1
2
3
4
5
6
7
mymap contains: France:Paris U.S.:Washington Australia:Canberra
mymap's buckets contain:
bucket #0 contains: U.S.:Washington
bucket #1 contains:
bucket #2 contains:
bucket #3 contains: France:Paris
bucket #4 contains: Australia:Canberra

5. 容量操作

函数声明 解释
bool empty() const noexcept; unordered_map 是否为空
size_type size() const noexcept; 获取unordered_map 中元素的数量

6. 访问操作

访问方式 函数声明 解释
使用方括号（[]） mapped_type& operator[] (key_type&& k); 如果 k 匹配容器中某个元素的键，则该函数返回该映射值的引用。
如果 k 与容器中任何元素的键都不匹配，则该函数将使用该键插入一个新元素，并返回该映射值的引用。
使用 at() mapped_type& at (const key_type& k);
const mapped_type& at (const key_type& k) const;		 如果 k 匹配容器中某个元素的键，则该函数返回该映射值的引用。
如果 k 与容器中任何元素的键都不匹配，则该函数将抛出 out_of_range 异常。

注意：const std::unordered_map 不能使用 operator[] 操作！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// unordered_map::at
#include <iostream>
#include <string>
#include <unordered_map>

int main () {
	  std::unordered_map<std::string,int> mymap = {
	                { "Mars", 3000},
	                { "Saturn", 60000},
	                { "Jupiter", 70000 } };
	
	  mymap.at("Mars") = 3396;
	  mymap.at("Saturn") += 272;
	  mymap.at("Jupiter") = mymap.at("Saturn") + 9638;
	
	  for (auto& x: mymap) {
	    std::cout << x.first << ": " << x.second << std::endl;
	  }
	
	  return 0;
}

IO：

1
2
3
Jupiter: 69910
Saturn: 60272
Mars: 3396

8. 删除操作

删除方式 函数声明 说明
根据元素位置 iterator erase (const_iterator position); 返回一个迭代器，指向被删除元素的后一个元素
根据元素的键 size_type erase (const key_type& k); 返回被删除元素的数目，此处为1
由一对范围迭代器指定删除的范围 iterator erase (const_iterator first, const_iterator last); 返回一个迭代器，指向最后一个被删除元素的后一个元素
删除所有元素 void clear() noexcept; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// unordered_map::erase
#include <iostream>
#include <string>
#include <unordered_map>

int main () {
	  std::unordered_map<std::string,std::string> mymap;
	
	  // populating container:
	  mymap["U.S."] = "Washington";
	  mymap["U.K."] = "London";
	  mymap["France"] = "Paris";
	  mymap["Russia"] = "Moscow";
	  mymap["China"] = "Beijing";
	  mymap["Germany"] = "Berlin";
	  mymap["Japan"] = "Tokyo";
	
    for ( auto& x: mymap )
	      std::cout << x.first << ": " << x.second << std::endl;
        std::cout << std::endl; 
	  // erase examples:
	  mymap.erase ( mymap.begin() );      // erasing by iterator
	  mymap.erase ("France");             // erasing by key
	  mymap.erase ( mymap.find("U.S."), mymap.end() ); // erasing by range
	
	  // show content:
	  for ( auto& x: mymap )
	      std::cout << x.first << ": " << x.second << std::endl;
	system("pause");
	  return 0;
}

IO：

1
2
3
4
5
6
7
8
9
10
U.K.: London
Russia: Moscow
Germany: Berlin
U.S.: Washington
France: Paris
Japan: Tokyo
China: Beijing

Russia: Moscow
Germany: Berlin

9. 查找操作

函数声明 说明
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;		 在容器中搜索键值等于 k 的元素，如果找到，则返回一个指向该元素的迭代器，否则返回一个指向unordered_map :: end的迭代器。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// unordered_map::find
#include <iostream>
#include <string>
#include <unordered_map>

int main () {
	  std::unordered_map<std::string,double> mymap = {
	     {"mom",5.4},
	     {"dad",6.1},
	     {"bro",5.9} };
	
	  std::string input;
	  std::cout << "who? ";
	  getline (std::cin,input);
	
	  // 查找
	  std::unordered_map<std::string,double>::const_iterator got = mymap.find (input);
	
	  if ( got == mymap.end() )
	      std::cout << "not found";
	  else
	      std::cout << got->first << " is " << got->second;
	
	  std::cout << std::endl;
	
	  return 0;
}

10. 桶操作

函数声明 说明
size_type bucket_count() const noexcept; 获取容器中桶的数目
size_type bucket_size ( size_type n ) const; 获取第 n 个桶中元素的数量
size_type bucket ( const key_type& k ) const; 获取键为 k 的元素所在桶的序号

11.c++ map与unordered_map区别

需要引入的头文件不同

map: #include < map >

unordered_map: #include < unordered_map >

内部实现机理不同

map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。

优缺点以及适用处

map：

优点：

有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高

缺点：

空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

优点：

因为内部实现了哈希表，因此其查找速度非常的快

缺点：

哈希表的建立比较耗费时间

适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

总结：

内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。

但是unordered_map执行效率要比map高很多

对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的

map和unordered_map的使用

unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。

原文地址：https://blog.csdn.net/fcku_88/article/details/88353431

https://blog.csdn.net/qq_21997625/article/details/84672775