c++ - 就内存使用而言，C++中的map和unordered_map有什么区别？

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

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

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;
}

当我将 map 替换为unorderd_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好吗？

最佳答案

映射被实现为二进制搜索树，并且每个节点(除有用数据外)通常都存储3个指针(指向左子，右子和父)。

无序映射被实现为哈希表，其中每个节点都在链接列表中。如果是单链接列表(属于相关存储桶)，则每个节点只有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;
  ...

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

通常，很难说哪个容器消耗的总内存更少。但是，我创建了一个基准测试，将1M随机数插入两个容器中，并测量了最大常驻大小(MaxRSS)，以反射(reflect)所有消耗的内存空间，包括堆内部数据。结果如下:

48,344 kB 用于std::map，

50 888 kB for std::unordered_map，

40,932 kB 用于std::unordered_map和reserve。

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

关于c++ - 就内存使用而言，C++中的map和unordered_map有什么区别？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56438738/