Рубрики

Неупорядоченные множества в стандартной библиотеке шаблонов C ++

Unordered_set реализован с использованием хеш-таблицы, где ключи хэшируются в индексы хеш-таблицы, так что вставка всегда рандомизирована. Все операции над unordered_set занимают в среднем постоянное время O (1), которое в худшем случае может доходить до линейного времени O (n), которое зависит от хэш-функции, используемой внутри, но практически они работают очень хорошо и обычно обеспечивают постоянное время операция поиска.
Unordered_set может содержать ключ любого типа — предопределенную или определяемую пользователем структуру данных, но когда мы определяем ключ типа user, определяем тип, нам нужно указать нашу функцию сравнения, в соответствии с которой будут сравниваться ключи.

Наборы против неупорядоченных наборов
Set — это упорядоченная последовательность уникальных ключей, тогда как unordered_set — это набор, в котором ключ может храниться в любом порядке, поэтому неупорядоченный. Набор реализован в виде сбалансированной древовидной структуры, поэтому можно поддерживать порядок между элементами (путем конкретного обхода дерева). Временная сложность операций над множествами составляет O (log n), а для unordered_set — O (1).

Методы на неупорядоченных множествах:
Для unordered_set определены многие функции, среди которых большинство пользователей имеют размер и пустые по емкости, находят для поиска ключа, вставляют и стирают для модификации.
Unordered_set допускает только уникальные ключи, для дубликатов ключей следует использовать unordered_multiset.

Пример объявления, поиска, вставки и итерации в unordered_set приведен ниже:

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

using namespace std;

  

int main()

{

    // объявляем набор для хранения строкового типа данных

    unordered_set <string> stringSet ;

  

    // вставляем различную строку, эта же строка будет сохранена

    // один раз в наборе

  

    stringSet.insert("code") ;

    stringSet.insert("in") ;

    stringSet.insert("c++") ;

    stringSet.insert("is") ;

    stringSet.insert("fast") ;

  

    string key = "slow" ;

  

    // find возвращает end итератор, если ключ не найден,

    // иначе он возвращает итератор к этому ключу

  

    if (stringSet.find(key) == stringSet.end())

        cout << key << " not found" << endl << endl ;

    else

        cout << "Found " << key << endl << endl ;

  

    key = "c++";

    if (stringSet.find(key) == stringSet.end())

        cout << key << " not found\n" ;

    else

        cout << "Found " << key << endl ;

  

    // теперь перебираем весь набор и печатаем его

    // содержание

    cout << "\nAll elements : ";

    unordered_set<string> :: iterator itr;

    for (itr = stringSet.begin(); itr != stringSet.end(); itr++)

        cout << (*itr) << endl;

}

Выход:

slow not found

Found c++

All elements : 
is
fast
c++
in
code

find , insert и erase занимают в среднем постоянное количество времени. Функция find() возвращает итератор для end() если ключ не указан в наборе, в противном случае возвращается итератор для позиции ключа. Итератор работает как указатель на значения ключа, поэтому мы можем получить ключ, разыменовав их с помощью оператора *.

Практическая задача, основанная на unordered_set — учитывая набор целых чисел, найдите среди них все дубликаты.

Input  : arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5}
Output : Duplicate item are : 5 2 1 

Ниже представлено решение C ++ с использованием unordered_set.

// C ++ программа для поиска дубликатов из массива с использованием
// unordered_set
#include <bits/stdc++.h>

using namespace std;

  
// Печать дубликатов в arr [0..n-1] с использованием unordered_set

void printDuplicates(int arr[], int n)

{

    // объявляем неупорядоченные множества для проверки и хранения

    // дубликаты

    unordered_set<int> intSet;

    unordered_set<int> duplicate;

  

    // цикл по элементам массива

    for (int i = 0; i < n; i++)

    {

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

        if (intSet.find(arr[i]) == intSet.end())

            intSet.insert(arr[i]);

  

        // если элемент уже существует, вставить в

        // дубликат набора

        else

            duplicate.insert(arr[i]);

    }

  

    // печать результата

    cout << "Duplicate item are : ";

    unordered_set<int> :: iterator itr;

  

    // цикл итератора itr от begin () до end ()

    for (itr = duplicate.begin(); itr != duplicate.end(); itr++)

        cout << *itr << " ";

}

  
// Код драйвера

int main()

{

    int arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5};

    int n = sizeof(arr) / sizeof(int);

  

    printDuplicates(arr, n);

    return 0;

}

Выход :

Duplicate item are : 5 2 1 

Методы unordered_set:

  • insert () — вставить новый {element} в контейнер unordered_set.
  • begin () — возвращает итератор, указывающий на первый элемент в контейнере unordered_set.
  • end () — возвращает итератор, указывающий на элемент last-the-end.
  • count ()Количество вхождений определенного элемента в контейнере unordered_set.
  • find () — Поиск элемента в контейнере.
  • clear () — удаляет все элементы из unordered_set и очищает его.
  • cbegin () — возвращает const_iterator, указывающий на первый элемент в контейнере unordered_set.
  • cend () — Возвращает const_iterator, указывающий на последний элемент в контейнере unordered_set или в одном из его сегментов.
  • bucket_size () — возвращает общее количество элементов, присутствующих в определенном сегменте в контейнере unordered_set.
  • erase () — удаляет либо один элемент из диапазона элементов, начиная от начала (включительно) до конца (исключая).
  • size () — Возвращает количество элементов в контейнере unordered_set.
  • swap () — Обмен значениями двух контейнеров unordered_set.
  • emplace ()вставляет элемент в контейнер unordered_set.
  • max_size () — возвращает максимальное количество элементов, которое может содержать контейнер unordered_set.
  • empty () — Проверить, пуст ли контейнер unordered_set или нет.
  • equal_range — возвращает диапазон, который включает все элементы, равные данному значению.
  • operator = — Копирует (или перемещает) unordered_set в другой unordered_set, а unordered_set :: operator = является соответствующей операторной функцией.
  • hash_function () — эта хеш-функция является унарной функцией, которая принимает только один аргумент и возвращает уникальное значение типа size_t на его основе.
  • Reserve () — Используется для запроса изменения емкости unordered_set.
  • bucket () — возвращает номер корзины определенного элемента.
  • bucket_count () — возвращает общее количество сегментов, присутствующих в контейнере unordered_set.
  • load_factor () — возвращает текущий коэффициент загрузки в контейнере unordered_set.
  • rehash () — устанавливает количество сегментов в контейнере unordered_set для заданного размера или более.
  • max_load_factor () — возвращает (или устанавливает) текущий максимальный коэффициент загрузки контейнера с неупорядоченным набором.
  • emplace_hint () — вставляет новый элемент в unordered_set только в том случае, если значение для вставки является уникальным, с заданной подсказкой.
  • == оператор — '==' является оператором в C ++. STL выполняет операцию сравнения на равенство между двумя неупорядоченными множествами, а unordered_set :: operator == является соответствующей операторной функцией для того же самого.
  • key_eq () — возвращает логическое значение в соответствии со сравнением. Он возвращает ключевой предикат сравнения эквивалентности, используемый unordered_set.
  • оператор! = -! = — это реляционный оператор в C ++ STL, который сравнивает равенство и неравенство между контейнерами unordered_set.
  • max_bucket_count () — Найти максимальное количество сегментов, которое может иметь unordered_set.

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

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

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

Неупорядоченные множества в стандартной библиотеке шаблонов C ++

0.00 (0%) 0 votes