Есть ли разница между map и unordered_map в c ++ с точки зрения использования памяти?

Question

Я решаю проблему на 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;
}

, и когда я заменил карту на 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;
}

Это означает, что карта занимает больше памяти, чем unordered_map.Кто-нибудь может объяснить, как это происходит?Почему карта занимает больше памяти, чем unordered_map?

Answer 1

1. Карты реализованы в виде деревьев двоичного поиска , и каждый узел (в дополнение к полезным данным) обычно хранит 3 указателя (налевый ребенок, правый ребенок и родитель).

2. Неупорядоченные карты реализованы в виде хеш-таблиц , где каждый узел находится в связанном списке.В случае односвязного списка (который принадлежит соответствующему сегменту) имеется только 1 указатель на узел. ОБНОВЛЕНИЕ : Однако для каждого сегмента также имеется дополнительный указатель.В идеальном случае, когда нет столкновений, будет 2 указателя на элемент, хранящийся в памяти.

Обратите внимание, что 2 int s обычно занимает 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), чтобы отразить все использованное пространство памяти, включая, например, данные обслуживания кучи.Результаты были следующими:

1. 48,344 кБ для std::map,
2. 50 888 кБ для std::unordered_map,
3. 40,932 кБ для std::unordered_map с reserve.

Обратите внимание, что потребление памяти для неупорядоченной карты (объявление 2) было выше из-за перераспределениясписки ведра.Для этого и предназначена reserve функция-член.Если кто-то заботится о потреблении памяти и заранее знает количество элементов, он / она должен всегда выделять заранее (это та же самая ситуация, что и для векторов).

Answer 2

Карта - это, по сути, двоичное дерево поиска, а unordered_map реализовано в виде хэш-карты. Если вы посмотрите на реализацию обоих, вы быстро заметите, что BST немного больше.

Это также означает, что карта намного медленнее, чем unordered_map.

                | map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |  

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search

Deletion time   | log(n) + Rebalance  | Same as search

BST:

struct node
{
    int data;
    node* left;
    node* right;
};

HashMap:

struct hash_node {
    int key;
    int value;
    hash_node* next;
}

Ссылка: https://www.geeksforgeeks.org/map-vs-unordered_map-c/