nieuporządkowana_mapa to powiązany kontener, w którym przechowywane są elementy utworzone przez kombinację wartości klucza i wartości mapowanej. Wartość klucza służy do jednoznacznej identyfikacji elementu, a mapowana wartość to treść powiązana z kluczem. Zarówno klucz, jak i wartość mogą być dowolnego typu, predefiniowanego lub zdefiniowanego przez użytkownika. W prostych słowach, nieuporządkowana_mapa przypomina strukturę danych typu słownikowego, która przechowuje w sobie elementy. Zawiera kolejne pary (klucz, wartość), co umożliwia szybkie odnalezienie pojedynczego elementu na podstawie jego unikalnego klucza.
rekha indyjski
Wewnętrznie unordered_map jest zaimplementowany przy użyciu Hash Table , klucz dostarczony do mapy jest mieszany z indeksami tablicy mieszającej, dlatego wydajność struktury danych w dużym stopniu zależy od funkcji skrótu, ale średnio koszt wyszukaj, wstaw i usuń z tablicy skrótów to O(1).
Notatka: W najgorszym przypadku jego złożoność czasowa może wzrosnąć od O(1) do O(n), szczególnie w przypadku dużych liczb pierwszych. W tej sytuacji zdecydowanie zaleca się użycie mapy, aby uniknąć błędu TLE (przekroczenie limitu czasu).
Składnia:
składnia unordered_map
Poniżej znajduje się program C++ demonstrujący nieuporządkowaną mapę:
C++
// C++ program to demonstrate> // functionality of unordered_map> #include> #include> using> namespace> std;> > // Driver code> int> main()> {> >// Declaring umap to be of> >// type key> >// will be of STRING type> >// and mapped VALUE will> >// be of int type> >unordered_mapint>umapa; // wstawianie wartości za pomocą operatora [] umap['techcodeview.com'] = 10; umap['Ćwiczenie'] = 20; umap['Wspieraj'] = 30; // Przemierzanie nieuporządkowanej mapy dla (auto x: umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Wyjście
Contribute 30 Practice 20 techcodeview.com 10>
unordered_map Dane wyjściowe
Wyjaśnienie: Specyficzną rzeczą, którą uzasadnia ten wynik, jest to, że wartość wyniku unordered_map jest generowana w sposób losowy, klucz do wartości, podczas gdy mapa wyświetla wartość i klucz w uporządkowany sposób.
unordered_map vs unordered_set
| Nieuporządkowana_mapa | Nieuporządkowany_zestaw |
|---|---|
| Unordered_map zawiera elementy tylko w postaci par (klucz-wartość). | Unordered_set niekoniecznie zawiera elementy w postaci par klucz-wartość, są one używane głównie do sprawdzania obecności/braku zestawu. |
| Operator „ []' aby wyodrębnić odpowiednią wartość klucza obecnego na mapie. | Wyszukiwanie elementu odbywa się za pomocą a znajdować () funkcja. Więc nie ma potrzeby stosowania operatora []. |
Notatka: Rozważmy na przykład problem liczenia częstotliwości występowania poszczególnych słów. Nie możemy używać unordered_set (lub set), ponieważ nie możemy przechowywać liczników, podczas gdy możemy używać unordered_map.
unordered_map vs map
| Nieuporządkowana_mapa | Mapa |
|---|---|
| Klucz unordered_map można przechowywać w dowolnej kolejności. | Mapa jest uporządkowaną sekwencją unikalnych kluczy |
| Unordered_Map implementuje niezrównoważoną strukturę drzewa, przez co nie jest możliwe utrzymanie porządku pomiędzy elementami | Mapa implementuje zrównoważoną strukturę drzewa, dzięki czemu możliwe jest zachowanie porządku pomiędzy elementami (poprzez określone przechodzenie przez drzewo) |
| Złożoność czasowa operacji unordered_map wynosi średnio O(1). | Złożoność czasowa operacji na mapie wynosi O(log n) |
Metody na unordered_map
Dostępnych jest wiele funkcji, które działają na unordered_map. Najbardziej przydatne z nich to:
- operator = operator [] pusty rozmiar początku i końca pojemności iteratora. znajdź i policz podczas wyszukiwania. wstaw i usuń w celu modyfikacji.
Poniższa tabela przedstawia pełną listę metod unordered_map:
| Metody/funkcje | Opis |
|---|---|
| Na() | Ta funkcja w C++ unordered_map zwraca odwołanie do wartości z elementem jako kluczem k |
| zaczynać() | Zwraca iterator wskazujący pierwszy element w kontenerze w kontenerze unordered_map |
| koniec() | Zwraca iterator wskazujący pozycję za ostatnim elementem w kontenerze w kontenerze unordered_map |
| wiaderko() | Zwraca numer segmentu, w którym na mapie znajduje się element z kluczem k |
| liczba_wiader | Bucket_count służy do zliczania całkowitej liczby. segmentów w unordered_map. Aby przejść do tej funkcji, nie jest wymagany żaden parametr |
| rozmiar_wiadra | Zwraca liczbę elementów w każdym segmencie unordered_map |
| liczyć() | Policz liczbę elementów obecnych w unordered_map z danym kluczem |
| równy_zakres | Zwróć granice zakresu obejmującego wszystkie elementy w kontenerze za pomocą klucza równego k |
| znajdować() | Zwraca iterator do elementu |
| pusty() | Sprawdza, czy kontener w kontenerze unordered_map jest pusty |
| usuwać() | Usuń elementy w kontenerze w kontenerze unordered_map |
Biblioteka C++ 11 udostępnia również funkcje umożliwiające sprawdzenie liczby i rozmiaru segmentów używanych wewnętrznie, a także używanej funkcji skrótu i różnych zasad mieszania, ale są one mniej przydatne w rzeczywistych aplikacjach. Możemy iterować po wszystkich elementach unordered_map za pomocą Iteratora.
C++
// C++ program to demonstrate> // Initialization, indexing,> // and iteration> #include> #include> using> namespace> std;> > // Driver code> int> main()> {> >// Declaring umap to be of> >// type key> >// will be of string type and> >// mapped value will be of double type> >unordered_mapdouble>umap = { //wstawienie elementu bezpośrednio na mapie {'Jeden', 1}, {'Dwa', 2}, {'Trzy', 3} }; // wstawianie wartości za pomocą operatora [] umap['PI'] = 3.14; umap['root2'] = 1,414; umap['root3'] = 1,732; umap['log10'] = 2,302; umap['loge'] = 1,0; // wstawienie wartości za pomocą funkcji wstawiania umap.insert(make_pair('e', 2.718)); klucz ciągu = 'PI'; // Jeśli klucz nie został znaleziony w iteratorze mapy // zwracane jest polecenie end if (umap.find(key) == umap.end()) cout<< key << ' not found
'; // If key found then iterator to that // key is returned else cout << 'Found ' << key << '
'; key = 'lambda'; if (umap.find(key) == umap.end()) cout << key << ' not found
'; else cout << 'Found ' << key << endl; // iterating over all value of umap unordered_mapdouble>::iterator itr; cout<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->najpierw przechowuje część kluczową i // itr->drugi przechowuje część wartości cout ' '<< itr->drugi<< endl; } }> |
>
>Wyjście
Found PI lambda not found All Elements : e 2.718 loge 1 log10 2.302 Two 2 One 1 Three 3 PI 3.14 root2 1.414 root3 1.732>
Znajdź częstotliwości poszczególnych słów
Mając dany ciąg słów, zadaniem jest znalezienie częstości występowania poszczególnych słów:
Wejście: str = maniacy dla maniaków maniacy quiz ćwicz qa dla;
Wyjście: Częstotliwości poszczególnych słów są
(praktyka, 1)
(dla 2)
(qa, 1)
(quiz, 1)
(maniaków, 3)
Poniżej znajduje się program C++ realizujący powyższe podejście:
C++
// C++ program to find freq> // of every word using unordered_map> #include> using> namespace> std;> > // Prints frequencies of> // individual words in str> void> printFrequencies(>const> string &str)> {> >// declaring map of type,> >// each word is mapped to its frequency> >unordered_mapint>słowoCzęstotliwość; // dzielenie danych wejściowych na słowa za pomocą // string stream // Używane do dzielenia słów stringstream ss(str); // Do przechowywania pojedynczych słów string word; while (ss>> słowo) wordFreq[słowo]++; // teraz iterujemy po word, freq pair // i drukujemy je w formacie unordered_mapint>:: iterator p; for (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->drugi<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
Sree Ramanujan
>Wyjście
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Najnowsze artykuły na unordered_map