c++ - 在内存使用方面，c++ 中的 map 和 unordered_map 有什么区别吗？

Question

我正在 InterviewBit 上解决问题并遇到一个问题，这是链接 https://www.interviewbit.com/problems/diffk-ii/ .当我使用 C++ STL map 解决这个问题时，它显示了消息

超出内存限制。您的提交未在分配的内存限制内完成。这是我的代码

int Solution::diffPossible(const vector<int> &A, int B) {
    int n = A.size();
    map< int , int > mp;
    for(int i =0;i<n; i++)
        mp[A[i]] = i;
    int k = B;
    for(int i =0; i<n; i++){
        if(mp.find(A[i]+k) != mp.end() && mp[A[i]+k] != i){
            return 1;
        }
        if(mp.find(A[i]-k) != mp.end() && mp[A[i]-k] != i){
            return 1;
        }
    }

    return 0;
}

当我用 unorderd_map 解决方案替换 map 时。这是代码

int Solution::diffPossible(const vector<int> &A, int B) {
    int n = A.size();
    unordered_map< int , int > mp;
    for(int i =0;i<n; i++)
        mp[A[i]] = i;
    int k = B;
    for(int i =0; i<n; i++){
        if(mp.find(A[i]+k) != mp.end() && mp[A[i]+k] != i){
            return 1;
        }
        if(mp.find(A[i]-k) != mp.end() && mp[A[i]-k] != i){
            return 1;
        }
    }

    return 0;
}

这意味着 map 占用的内存比 unordered_map 多。谁能解释这是怎么回事？为什么 map 占用更多内存空间比 unordered_map?

Answer 1

1. map 被实现为二叉搜索树并且每个节点(除了有用数据之外)通常存储3 个指针(指向左 child ，右 child 和 parent )。

2. 无序映射作为哈希表实现，其中每个节点都在链表中。在单链表(属于相关桶)的情况下，每个节点只有 1 个指针。 更新:但是，每个桶还有一个额外的指针。在没有冲突的理想情况下，内存中存储的每个元素将有 2 个指针。

请注意，2 个 int 通常会占用 8 个字节，与单个指针相同。

---

例如，查看 GNU libstdc++ 实现。 RB树的节点定义如下:

struct _Rb_tree_node_base
{
  typedef _Rb_tree_node_base* _Base_ptr;
  typedef const _Rb_tree_node_base* _Const_Base_ptr;

  _Rb_tree_color    _M_color;
  _Base_ptr     _M_parent;
  _Base_ptr     _M_left;
  _Base_ptr     _M_right;
  ...

在那里，您可以观察到这 3 个指针。

---

一般来说，很难说哪个容器会消耗更少的整体内存。然而，我创建了一个基准测试，将 1M 随机数插入两个容器并测量最大驻留大小 (MaxRSS) 以反射(reflect)所有消耗的内存空间，包括，例如，堆管理数据。结果如下:

1. 48,344 kB for std::map,
2. 50 888 kB for std::unordered_map,
3. 40,932 kB for std::unordered_map with reserve。

请注意，由于存储桶列表的重新分配，无序映射(广告 2.)的内存消耗较高。这就是 reserve 成员函数的用途。如果一个人关心内存消耗并且事先知道元素的数量，他/她应该总是预分配(这与 vector 的情况相同)。