Рубрики

unordered_multimap и его применение

Позволяет дубликаты:
Мы обсуждали unordered_map в нашем предыдущем посте , но есть ограничение: мы не можем хранить дубликаты в unordered_map, то есть если у нас есть пара ключ-значение уже в нашем unordered_multimap и вставлена другая пара, то оба будут там, тогда как в В случае unordered_map предыдущее значение, соответствующее ключу, обновляется новым значением, которое будет только там. Даже может существовать в unordered_multimap дважды.

Внутреннее Представительство:
Внутренняя реализация unordered_multimap такая же, как и у unordered_map, но для дублирующих ключей другое значение счетчика поддерживается с каждой парой ключ-значение. Поскольку пары хранятся в хеш-таблице, между ними нет определенного порядка, но пары с одинаковыми ключами объединяются в структуре данных, тогда как пары с одинаковыми значениями не гарантируются.

Сложность времени:
Все операции с unordered_multimap занимают в среднем постоянное количество времени, но в худшем случае время может переходить к линейному, в зависимости от используемой внутри хэш-функции, но в долгосрочной перспективе unordered_multimap превосходит мультикарту (многокарта на основе дерева).

Функции:
unorderd_multimap поддерживает множество функций, которые продемонстрированы в следующем коде:

// C ++ программа для демонстрации различных функций
// unordered_multimap
#include <bits/stdc++.h>

using namespace std;

  
// делаем typedef для короткого объявления

typedef unordered_multimap<string, int>::iterator umit;

  
// Утилита для печати unordered_multimap

void printUmm(unordered_multimap<string, int> umm)

{

    // begin () возвращает итератор к первому элементу карты

    umit it = umm.begin();

  

    for (; it != umm.end(); it++)

        cout << "<" << it->first << ", " << it->second

             << ">  ";

  

    cout << endl;

}

  
// Программа драйвера для проверки всех функций

int main()

{

    // пустая инициализация

    unordered_multimap<string, int> umm1;

  

    // Инициализация бу список инициализатора

    unordered_multimap<string, int> umm2 ({{"apple", 1},

                                           {"ball", 2},

                                           {"apple", 10},

                                           {"cat", 7},

                                           {"dog", 9},

                                           {"cat", 6},

                                           {"apple", 1}});

  

    // Инициализация с помощью операции присваивания

    umm1 = umm2;

    printUmm(umm1);

  

    // empty возвращает true, если контейнер пуст, иначе возвращает

    // ложный

    if (umm2.empty())

        cout << "unordered multimap 2 is empty\n";

    else

        cout << "unordered multimap 2 is not empty\n";

  

    // размер возвращает общее количество элементов в контейнере

    cout << "Size of unordered multimap 1 is " << umm1.size()

         << endl;

  

    string key = "apple";

  

    // найти и вернуть любую пару, связанную с ключом

    umit it = umm1.find(key);

    if (it != umm1.end())

    {

        cout << "\nkey " << key << " is there in unordered "

             << " multimap 1\n";

        cout << "\none of the value associated with " << key

             << " is " << it->second << endl;

    }

    else

        cout << "\nkey " << key << " is not there in unordered"

             << " multimap 1\n";

  

    // count возвращает общее количество связанных пар

    // с ключом

    int cnt = umm1.count(key);

    cout << "\ntotal values associated with " << key << " are "

         << cnt << "\n\n";

  

    printUmm(umm2);

  

    // одна вставка путем явного создания пары

    umm2.insert(make_pair("dog", 11));

  

    // вставка по списку инициализатора

    umm2.insert({{"alpha", 12}, {"beta", 33}});

    cout << "\nAfter insertion of <apple, 12> and <beta, 33>\n";

    printUmm(umm2);

  

    // стереть удаляет все пары, соответствующие ключу

    umm2.erase("apple");

    cout << "\nAfter deletion of apple\n";

    printUmm(umm2);

  

    // очистить удаляет все пары из контейнера

    umm1.clear();

    umm2.clear();

  

    if (umm2.empty())

        cout << "\nunordered multimap 2 is empty\n";

    else

        cout << "\nunordered multimap 2 is not empty\n";

}

Выход:

<apple, 1>  <apple, 10>  <apple, 1>  <ball, 2>  <cat, 6>  <cat, 7>  <dog, 9>  
unordered multimap 2 is not empty
Size of unordered multimap 1 is 7

key apple is there in unordered  multimap 1

one of the value associated with apple is 1

total values associated with apple are 3

<apple, 1>  <apple, 10>  <apple, 1>  <ball, 2>  <cat, 6>  <cat, 7>  <dog, 9>  

After insertion of <apple, 12> and <beta, 33>
<beta, 33>  <alpha, 12>  <apple, 1>  <apple, 10>  <apple, 1>  <ball, 2>
<cat, 6>  <cat, 7>  <dog, 11>  <dog, 9>  

After deletion of apple
<beta, 33>  <alpha, 12>  <ball, 2>  <cat, 6>  <cat, 7>  <dog, 11>  <dog, 9>  

unordered multimap 2 is empty

Как мы можем видеть в приведенном выше коде, большинство операций работают аналогично unordered_map, но некоторые вещи, на которые следует обратить внимание:
Мы можем использовать список инициализаторов для инициализации и вставки множества пар одновременно.
Для unordered_multimap нет оператора [], поскольку значения, соответствующие ключу, не являются уникальными, может быть много значений, связанных с одним ключом, поэтому оператор [] не может быть применен к ним.
Функция стирания удаляет все экземпляры значений, связанных с предоставленным ключом.
Функция Find возвращает итератор для любого экземпляра пары ключ-значение среди всех пар, связанных с этим ключом.

Как получить доступ / удалить, если определенное значение для ключа?
Если мы хотим проверить, существует ли конкретный объект или нет, нам нужно перебрать все пары ключ-значение, соответствующие k, аналогичным образом мы можем стереть одну копию конкретного из структуры данных. Не существует определенного порядка, в котором хранятся все значения ключа.

// C ++ программа для реализации поиска и удаления для конкретных
// пара ключ-значение для unordered_multimap
#include <bits/stdc++.h>

using namespace std;

  
// делаем typedef для короткого объявления

typedef unordered_multimap<string, int>:: iterator umit;

  
// функция, чтобы проверить, есть ли p на карте или нет

bool find_kv(unordered_multimap<string, int>& umm,

             pair<string, int> p)

{

    // equal_range возвращает пару итераторов первого и последнего

    // позиция, связанная с ключом

    pair<umit, umit> it = umm.equal_range(p.first);

    umit it1 = it.first;

  

    pair<string, int> tmp;

  

    // цикл по всем значениям, связанным с ключом

    while (it1 != it.second)

    {

        tmp = *it1;

        if (tmp == p)

            return true;

        it1++;

    }

    return false;

}

  
// функция для удаления одной копии пары p с карты

void erase_kv(unordered_multimap<string, int>& umm,

              pair<string, int> p)

{

    // equal_range возвращает пару итераторов первого и

    // последняя позиция, связанная с ключом

    pair<umit, umit> it = umm.equal_range(p.first);

    umit it1 = it.first;

    pair<string, int> tmp;

  

    // цикл по всем значениям, связанным с ключом

    while (it1 != it.second)

    {

        tmp = *it1;

        if (tmp == p)

        {

            // версия итератора erase: удаляет пару

            // только в этой позиции

            umm.erase(it1);

            break;

        }

        it1++;

    }

}

  
// Утилита для печати unordered_multimap

void printUmm(unordered_multimap<string, int> umm)

{

    // begin () возвращает итератор к первому элементу карты

    umit it = umm.begin();

    for (; it != umm.end(); it++)

        cout << "<" << it->first << ", " << it->second << "> ";

    cout << endl;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    // инициализация мультикарты списком инициализаторов

    unordered_multimap<string, int> umm ({{"apple", 1},

        {"ball", 2},

        {"apple", 10},

        {"cat", 7},

        {"dog", 9},

        {"cat", 6},

        {"apple", 1}

    });

  

    cout << "Initial content\n";

    printUmm(umm);

    pair<string, int> kv = make_pair("apple", 1);

  

    cout << "\nAfter insertion of one more <apple, 1>\n";

    printUmm(umm);

  

    if (find_kv(umm, kv))

        erase_kv(umm, kv);

    else

        cout << "key-value pair is not there in unordered multimap\n";

  

    cout << "\nAfter deletion one occurrence of <apple, 1>\n";

    printUmm(umm);

}

Выход:

Initial content
<apple, 1> <apple, 10> <apple, 1> <ball, 2> <cat, 6> <cat, 7> <dog, 9> 

After insertion of one more <apple, 1>
<apple, 1> <apple, 10> <apple, 1> <ball, 2> <cat, 6> <cat, 7> <dog, 9> 

After deletion one occurrence of <apple, 1>
<apple, 10> <apple, 1> <ball, 2> <cat, 6> <cat, 7> <dog, 9> 

Методы unordered_multimap:

  • begin () — возвращает итератор, указывающий на первый элемент в контейнере или на первый элемент в одном из его сегментов.
  • end () — возвращает итератор, указывающий на позицию после последнего элемента в контейнере или на позицию после последнего элемента в одном из его сегмента.
  • count () — Возвращает количество элементов в контейнере, ключ которых равен ключу, переданному в параметре.
  • cbegin () — возвращает постоянный итератор, указывающий на первый элемент в контейнере или на первый элемент в одном из его сегментов.
  • cend () — возвращает постоянный итератор, указывающий на позицию после последнего элемента в контейнере или на позицию после последнего элемента в одном из его сегмента.
  • clear () — очищает содержимое контейнера unordered_multimap.
  • size () — возвращает размер unordered_multimap. Он обозначает количество элементов в этом контейнере.
  • swap () — Меняет местами содержимое двух контейнеров unordered_multimap. Размеры могут отличаться для обоих контейнеров.
  • find () — возвращает итератор, который указывает на один из элементов, имеющий ключ k.
  • bucket_size () — возвращает количество элементов в корзине n.
  • empty () — возвращает true, если контейнер unordered_multimap пуст. В противном случае возвращается false.
  • equal_range () — возвращает диапазон, в котором все ключи элемента равны ключу.
  • operator = — Копировать / Назначить / Переместить элементы из другого контейнера.
  • max_size () — возвращает максимальное количество элементов, которое может содержать контейнер unordered_multimap.
  • load_factor () — возвращает текущий коэффициент загрузки в контейнере unordered_multimap.
  • key_eq () — возвращает логическое значение в соответствии со сравнением.
  • emplace () — вставляет новый {ключ, элемент} в контейнер unordered_multimap.
  • emplace_hint () — вставляет новый {key: element} в контейнер unordered_multimap.
  • bucket_count () — возвращает общее количество сегментов в контейнере unordered_multimap.
  • bucket () — возвращает номер корзины, в которой находится данный ключ.
  • max_load_factor () — возвращает максимальный коэффициент загрузки контейнера unordered_multimap.
  • rehash () — Устанавливает количество контейнеров в контейнере равным N или более.
  • reserve () — Устанавливает количество контейнеров в контейнере (bucket_count) на наиболее подходящее число, чтобы оно содержало не менее n элементов.
  • hash_function () — эта хеш-функция является унарной функцией, которая принимает только один аргумент и возвращает уникальное значение типа size_t на его основе.
  • max_bucket_count () — возвращает максимальное количество сегментов, которое может иметь неупорядоченный контейнер с несколькими картами.

Последние статьи на unordered_multimap

Эта статья предоставлена Уткаршем Триведи. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

unordered_multimap и его применение

0.00 (0%) 0 votes