Рубрики

unordered_multiset и его использование

Мы обсуждали unordered_set в нашем предыдущем посте, проблема с unordered_set заключается в том, что в этой структуре данных невозможно хранить повторяющиеся записи. Например, если у нас уже есть какое-то значение v в unordered_set, повторная вставка v не будет иметь никакого эффекта.
Для обработки этого дублирования следует использовать unordered_mulitset, он также может хранить дублирующиеся элементы. Внутренне, когда вставляется существующее значение, структура данных увеличивает свой счет, который связан с каждым значением. Поскольку счетчик каждого значения хранится в unordered_multiset, он занимает больше места, чем unordered_set (если все значения различны).
Внутренняя реализация unordered_multiset такая же, как и у unordered_set, и также использует хеш-таблицу для поиска, только значение счетчика связано с каждым значением в предыдущей. Из-за хэширования элементов у него нет определенного порядка хранения элементов, поэтому все элементы могут располагаться в любом порядке, но дублирующий элемент объединяется. Все операции с unordered_multiset в среднем занимают постоянное время, но в худшем случае могут перейти в линейный режим.
Unordered_multiset поддерживает множество функций, которые продемонстрированы в следующем коде:

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

using namespace std;

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

typedef unordered_multiset<int>::iterator umit;

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

void printUset(unordered_multiset<int> ums)

{

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

    umit it = ums.begin();

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

        cout << *it << " ";

    cout << endl;

}

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

int main()

{

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

    unordered_multiset<int> ums1;

  

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

    unordered_multiset<int> ums2 ({1, 3, 1, 7, 2, 3,

                                   4, 1, 6});

  

    // Инициализация по присваиванию

    ums1 = {2, 7, 2, 5, 0, 3, 7, 5};

  

    // функция empty () возвращает true установлено пусто

    // иначе ложь

    if (ums1.empty())

        cout << "unordered multiset 1 is empty\n";

    else

        cout << "unordered multiset 1 is not empty\n";

  

    // функция size () возвращает общее количество элементов

    // в структуре данных

    cout << "The size of unordered multiset 2 is : "

         << ums2.size() << endl;

  

    printUset(ums1);

  

    ums1.insert(7);

  

    printUset(ums1);

  

    int val = 3;

  

    // функция find возвращает итератор на первую позицию

    // из val, если существует, в противном случае возвращает итератор

    // до конца

    if (ums1.find(val) != ums1.end())

        cout << "unordered multiset 1 contains "

             << val << endl;

    else

        cout << "unordered multiset 1 does not contains "

             << val << endl;

  

    // функция count возвращает общее количество вхождений в наборе

    val = 5;

    int cnt = ums1.count(val);

    cout << val << " appears " << cnt

         << " times in unordered multiset 1 \n";

  

    val = 9;

  

    // если возвращаемое количество> 0, то элемент существует иначе

    if (ums1.count(val))

        cout << "unordered multiset 1 contains "

             << val << endl;

    else

        cout << "unordered multiset 1 does not contains "

             << val << endl;

  

    val = 1;

  

    // equal_range возвращает пару, где first - итератор

    // в первую позицию val и второй итератор в

    // последняя позиция до val

    pair<umit, umit> erange_it = ums2.equal_range(val);

    if (erange_it.first != erange_it.second)

        cout << val << " appeared atleast once in "

                        "unoredered_multiset \n";

  

  

    printUset(ums2);

  

    // функция стирания удаляет все экземпляры val

    ums2.erase(val);

  

    printUset(ums2);

  

    // функция очистки удаляет все записи из набора

    ums1.clear();

    ums2.clear();

  

    if (ums1.empty())

        cout << "unordered multiset 1 is empty\n";

    else

        cout << "unordered multiset 1 is not empty\n";

}

Выход :

unordered multiset 1 is not empty
The size of unordered multiset 2 is : 9
3 0 5 5 7 7 2 2 
3 0 5 5 7 7 7 2 2 
unordered multiset 1 contains 3
5 appears 2 times in unordered multiset 1 
unordered multiset 1 does not contains 9
1 appeared atleast once in unoredered_multiset 
6 4 2 7 3 3 1 1 1 
6 4 2 7 3 3 
unordered multiset 1 is empty

Как мы видим, большинство операций работают аналогично unordered_set, но некоторые вещи, на которые следует обратить внимание:
Функция equal_range (val) возвращает пару типа, где первый итератор указывает на первую позицию val, а второй — на последнюю позицию val в структуре данных.
Функция erase (val) удаляет все свои экземпляры из структуры данных, например, если какое-то значение v встречалось t раз в unordered_multiset и когда вызывается erase, v удаляется полностью, что не является ожидаемым поведением много раз.

Мы можем удалить только одну копию некоторого значения, используя функцию поиска и версию итератора erase, так как функция find возвращает итератор в первую позицию найденного значения, мы можем передать этот итератор, чтобы стереть вместо фактического значения, чтобы удалить только одну копию, код для это показано ниже:

// C ++ программа для удаления одной копии из неупорядоченного набора
#include <bits/stdc++.h>

using namespace std;

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

typedef unordered_multiset<int>::iterator umit;

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

void printUset(unordered_multiset<int> ums)

{

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

    // устанавливать

    umit it = ums.begin();

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

        cout << *it << " ";

    cout << endl;

}

  
// функция для удаления одной копии val из набора

void erase_one_entry(unordered_multiset<int>& ums,

                    int val)

{

    // find возвращает итератор на первую позицию

    umit it = ums.find(val);

  

    // если элемент есть, то стираем

    if (it != ums.end())

       ums.erase(it);

}

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

int main()

{

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

    unordered_multiset<int> ums ({1, 3, 1, 7, 2, 3,

                                 4, 1, 6});

  

    int val = 1;

    printUset(ums);

    erase_one_entry(ums, val);

    printUset(ums);

}

Выход :

6 4 2 7 3 3 1 1 1 
6 4 2 7 3 3 1 1 

Методы unordered_multiset:

  • insert () — вставляет новые элементы в unordered_multiset. Таким образом увеличивается размер контейнера.
  • begin () — возвращает итератор, указывающий на первый элемент в контейнере или на первый элемент в одном из его сегментов.
  • end () — возвращает итератор, указывающий на позицию сразу после последнего элемента в контейнере или на позицию сразу после последнего элемента в одном из его сегмента.
  • empty () — возвращает true, если контейнер unordered_multiset пуст. В противном случае возвращается false.
  • find () — возвращает итератор, который указывает на позицию с элементом val.
  • cbegin () — возвращает постоянный итератор, указывающий на первый элемент в контейнере или на первый элемент в одном из его сегментов.
  • cend () — возвращает постоянный итератор, указывающий на позицию сразу после последнего элемента в контейнере или на позицию сразу после последнего элемента в одном из его сегментов.
  • equal_range () — возвращает диапазон, в котором все элементы равны заданному значению.
  • emplace () — вставляет новый элемент в контейнер unordered_multiset.
  • clear () — очищает содержимое контейнера unordered_multiset.
  • count () — Возвращает количество элементов в контейнере unordered_multiset, которое равно заданному значению.
  • size () — Метод size () метода unordered_multiset используется для подсчета количества элементов unordered_set, с которым он вызывается.
  • max_size — max_size () unordered_multiset принимает максимальное количество элементов, которое может содержать контейнер unordered_multiset.
  • swap () — Меняет местами содержимое двух контейнеров unordered_multiset.
  • erase () — используется для удаления либо одного элемента, либо всех элементов с определенным значением, либо диапазона элементов, начиная от начала (включительно) до конца (исключая).
  • bucket () — возвращает номер корзины, в которой находится данный элемент. Размер корзины варьируется от 0 до bucket_count-1.
  • bucket_size () — возвращает количество элементов в корзине, в которой есть элемент val.
  • Reserve () — Функция reverse () в unordered_multiset устанавливает количество сегментов в контейнере (bucket_count) наиболее подходящим, чтобы оно содержало не менее n элементов.
  • max_bucket_count () — возвращает максимальное количество сегментов, которое может иметь неупорядоченный контейнер из нескольких множеств.
  • load_factor () — возвращает текущий коэффициент загрузки в контейнере unordered_multiset.
  • max_load_factor () — возвращает максимальный коэффициент загрузки контейнера unordered_multiset.
  • bucket_count () — возвращает общее количество сегментов в контейнере unordered_multiset.
  • hash_function () — эта хеш-функция является унарной функцией, которая принимает только один аргумент и возвращает уникальное значение типа size_t на его основе.
  • rehash () — Устанавливает количество контейнеров в контейнере равным N или более.
  • key_eq () — возвращает логическое значение в соответствии со сравнением.
  • emplace_hint () — вставляет новый элемент в контейнер unordered_multiset.
  • get_allocator — эта функция получает сохраненный объект распределителя и возвращает объект распределителя, который используется для создания контейнера.
  • operator = — '=' — это оператор в C ++ STL, который копирует (или перемещает) unordered_multiset в другой unordered_multiset, а unordered_multiset :: operator = является соответствующей операторной функцией.

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

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

unordered_multiset и его использование

0.00 (0%) 0 votes