Рубрики

unordered_map в C ++ STL

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

// C ++ программа для демонстрации функциональности unordered_map
#include <iostream>
#include <unordered_map>

using namespace std;

  

int main()

{

    // Объявление umap типа <string, int>

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

    // быть двойного типа

    unordered_map<string, int> umap;

  

    // вставляем значения с помощью оператора []

    umap["GeeksforGeeks"] = 10;

    umap["Practice"] = 20;

    umap["Contribute"] = 30;

  

    // Обход неупорядоченной карты

    for (auto x : umap)

      cout << x.first << " " << x.second << endl;

  
}

Выход:

Contribute 30
GeeksforGeeks 10
Practice 20

unordered_map против unordered_set :
В unordered_set у нас есть только ключ, без значения, они в основном используются для просмотра наличия / отсутствия в наборе. Например, рассмотрим проблему подсчета частот отдельных слов. Мы не можем использовать unordered_set (или set), так как мы не можем хранить счетчики.

unordered_map vs map :
Карта (например, set ) представляет собой упорядоченную последовательность уникальных ключей, тогда как в unordered_map ключ может храниться в любом порядке, поэтому неупорядоченный.
Карта реализована в виде сбалансированной древовидной структуры, поэтому можно поддерживать порядок между элементами (путем конкретного обхода дерева). Временная сложность операций с картой составляет O (Log n), в то время как для unordered_set это в среднем O (1).

Методы на unordered_map
Доступно множество функций, которые работают с unordered_map. наиболее полезными из них являются — operator =, operator [], пустой и размер для емкости, начало и конец для итератора, поиск и подсчет для поиска, вставка и удаление для модификации.
Библиотека C ++ 11 также предоставляет функцию для просмотра внутренне используемых счетчиков, размера сегментов, а также используемой хэш-функции и различных хэш-политик, но они менее полезны в реальном приложении.
Мы можем перебрать все элементы unordered_map, используя Iterator. Инициализация, индексирование и итерация показаны в следующем примере кода:

// C ++ программа для демонстрации функциональности unordered_map
#include <iostream>
#include <unordered_map>

using namespace std;

  

int main()

{

    // Объявление umap типа <string, double>

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

    // быть двойного типа

    unordered_map<string, double> umap;

  

    // вставляем значения с помощью оператора []

    umap["PI"] = 3.14;

    umap["root2"] = 1.414;

    umap["root3"] = 1.732;

    umap["log10"] = 2.302;

    umap["loge"] = 1.0;

  

    // вставляем значение с помощью функции вставки

    umap.insert(make_pair("e", 2.718));

  

    string key = "PI";

  

    // Если ключ не найден в итераторе карты до конца, возвращается

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

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

  

    // Если ключ найден, возвращается итератор этого ключа

    else

        cout << "Found " << key << "\n\n";

  

    key = "lambda";

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

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

    else

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

  

    // перебираем все значения umap

    unordered_map<string, double>:: iterator itr;

    cout << "\nAll Elements : \n";

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

    {

        // itr работает как указатель на пару <string, double>

        // набираем itr-> сначала сохраняем ключевую часть и

        // itr-> second обводит часть значения

        cout << itr->first << "  " << itr->second << endl;

     }

}

Выход:

Found PI

lambda not found

All Elements : 
loge  1
e  2.718
log10  2.302
root3  1.732
PI  3.14
root2  1.414

Практическая задача на основе unordered_map — по заданной строке слов найти частоты отдельных слов.

Input :  str = "geeks for geeks geeks quiz practice qa for";
Output : Frequencies of individual words are
   (practice, 1)
   (for, 2)
   (qa, 1)
   (quiz, 1)
   (geeks, 3)

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

// C ++ программа для поиска частоты каждого слова, используя
// unordered_map
#include <bits/stdc++.h>

using namespace std;

  
// Печатает частоты отдельных слов в стр

void printFrequencies(const string &str)

{

    // объявляем карту типа <string, int>, каждое слово

    // отображается на его частоту

    unordered_map<string, int> wordFreq;

  

    // разбиваем ввод в слово, используя поток строк

    stringstream ss(str);  // Используется для разбиения слов

    string word; // Для хранения отдельных слов

    while (ss >> word)

        wordFreq[word]++;

  

    // теперь итерируем по слову, паре частот и печати

    // их в формате <,>

    unordered_map<string, int>:: iterator p;

    for (p = wordFreq.begin(); p != wordFreq.end(); p++)

        cout << "(" << p->first << ", " << p->second << ")\n";

}

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

int main()

{

    string str = "geeks for geeks geeks quiz "

                 "practice qa for";

    printFrequencies(str);

    return 0;

}

Выход:

(qa, 1)
(quiz, 1)
(practice, 1)
(geeks, 3)
(for, 2)

Методы unordered_map:

  • at () : эта функция в C ++ unordered_map возвращает ссылку на значение с элементом в качестве ключа k.
  • begin () : возвращает итератор, указывающий на первый элемент в контейнере в контейнере unordered_map.
  • end () : возвращает итератор, указывающий на позицию после последнего элемента в контейнере в контейнере unordered_map.
  • bucket (): возвращает номер сегмента, в котором элемент с ключом k находится на карте.
  • bucket_count: bucket_count используется для подсчета общего номера. ведер в unordered_map. Параметр не требуется передавать в эту функцию.
  • bucket_size: возвращает количество элементов в каждом сегменте unordered_map.
  • count () : Подсчитать количество элементов, присутствующих в unordered_map с данным ключом.
  • equal_range : возвращает границы диапазона, включающего все элементы в контейнере, с ключом, который сравнивается равным k.

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

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

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

unordered_map в C ++ STL

0.00 (0%) 0 votes