C++ Map 和 UnorderedMap 的使用和区别 |21xrx.com

C++ Map 和 UnorderedMap 的使用和区别

2023-07-03 08:00:41 深夜i -- --

C++ Map UnorderedMap 使用区别

在C++语言中，Map（映射表）和UnorderedMap（无序映射表）都是关联容器，它们可以根据键值对(key-value)快速地进行查找和插入。这两个容器非常类似，但是它们之间有几个重要的区别。

一、Map和UnorderedMap的内部实现方式不同

Map的底层实现是红黑树，其元素是有序的。在查找或插入元素的时候，Map会自动按照键值进行排序，并维护树的平衡。因此，Map适用于需要按键值进行排序或者需要保证元素有序的场景。

UnorderedMap的底层实现是哈希表，其元素是无序的。在查找或插入元素的时候，UnorderedMap是通过哈希函数来计算键值的存储位置，因此查找或插入元素的时间复杂度是O(1)的，但是无序也是其不足之处。

二、访问元素的方式不同

Map是通过key访问元素的，因此可以使用迭代器或者find函数来访问和修改元素，操作比较灵活；而UnorderedMap是通过hash值来访问元素的，因此只能使用迭代器来访问和修改元素，find函数只能返回一个迭代器指向元素，不能直接返回元素。

三、元素的查找效率不同

Map由于是有序的，查找一个元素平均需要O(logn)的时间；而UnorderedMap由于是无序的，查找一个元素平均需要O(1)的时间。

四、Map和UnorderedMap的插入效率不同

Map每次插入元素都需要重新平衡，而且由于需要维护其有序性，插入速度比较慢；而UnorderedMap每次插入元素只需要调整一下哈希表，插入速度比较快。

总之，在需要有序存储时应该使用Map，在对查找效率高要求较高时，可以使用UnorderedMap。

示例代码：


#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
int main()
{
  // 使用Map
  map<int, string> m;
  m.insert(pair<int, string>(1, "one"));
  m.insert(make_pair(2, "two"));
  m[3] = "three";
  for (auto iter = m.begin(); iter != m.end(); iter++)
    cout << iter->first << ": " << iter->second << endl;
  
  cout << endl;
  // 使用UnorderedMap
  unordered_map<int, string> u;
  u.insert(pair<int, string>(1, "one"));
  u.insert(make_pair(2, "two"));
  u[3] = "three";
  for (auto iter = u.begin(); iter != u.end(); iter++)
    cout << iter->first << ": " << iter->second << endl;
  
  cout << endl;
  return 0;
}

上一篇: idea打包java可执行jar包

下一篇: 推荐C++版的数据结构与算法教材

评论区

()

相似文章