Vyřešeno: mapa vs unordered_map in

Úvod:

Map a unordered_map jsou oba asociativní kontejnery přítomné v C++ Standard Template Library (STL), které ukládají prvky tvořené kombinací hodnoty klíče a mapované hodnoty. Hlavní rozdíl mezi těmito dvěma je v tom, že zatímco mapa (jako sada) implementuje samovyvažující binární vyhledávací strom (BST) a ukládá klíče v seřazeném pořadí, unordered_map (jako unordered_set) používá pro interní implementaci hash tabulku a klíče nejsou seřazeny. .

Řešení problému:

Při programování v C++ může rozhodnutí, kdy použít mapu oproti neuspořádané mapě, významně ovlivnit efektivitu. Toto rozhodnutí do značné míry závisí na specifikacích vaší aplikace. Pokud je důležité řazení prvků, rozhodněte se pro mapu. Pokud však usilujete o rychlejší přístupové časy, unordered_map je správná cesta.

Zde diskutovaný kód bude demonstrovat rozdíl ve výkonu mezi mapou a unordered_map v C++:

#include
pomocí oboru názvů std;

void perf_test()
{
mapa Mapa;
neuspořádaná_mapa Neuspořádaná_mapa;

auto start = high_resolution_clock::now();
for (int i = 0; i < 1e6; i++) Map[i] += i; automatické zastavení = hodiny s vysokým_rozlišením::now(); automatické trvání = trvání_cast(stop – start);
cout << "Čas strávený mapou: "<< trvání.počet() << "mikrosekundy" << endl; start = hodiny s vysokým_rozlišením::nyni(); for (int i = 0; i < 1e6; i++) Neuspořádaná_mapa[i] += i; stop = hodiny s vysokým_rozlišením::nyni(); trvání = trvání_cast(stop – start);
cout << "Čas strávený Unordered_Map: "<< trvání.počet() << " mikrosekundy" << endl; } int main() { perf_test(); návrat 0; } [/code] Tento test výkonu obvykle odhalí, že unordered_map je rychlejší než mapa.

Pochopení mapy v C++

Mapa v C++ STL je asociativní kontejner, který ukládá prvky tvořené kombinací hodnoty klíče a namapované hodnoty. Klíčové hodnoty jsou seřazeny, což umožňuje snadné vyhledávání, přidávání a odebírání položek z mapy. Protože jsou však prvky v mapě uspořádány, je časová složitost operací vyhledávání, vkládání a mazání logaritmická ve velikosti mapy.

Ve výše uvedeném kódu vytvoříme mapu s názvem „Map“ a přidáme prvky pomocí smyčky a načasujeme operaci pomocí utility high_resolution_clock z knihovna.

Unordered_map v C++

Na rozdíl od mapy provádí unordered_map průměrná případová vyhledávání, vkládání a mazání v konstantním čase bez ohledu na velikost mapy. Tohoto působivého výkonu dosahuje pomocí hashovací tabulky pro svou základní implementaci.

V našem příkladu kódu vytvoříme unordered_map s názvem „Unordered_Map“ a stejně jako v případě mapy přidáme prvky pomocí smyčky a načasujeme operaci. Ve většině případů je čas potřebný pro operace unordered_map výrazně kratší než ty, které provádí mapa.

Pochopení rozdílů a charakteristik map a unordered_map v C++ umožní vývojářům využít jejich silné stránky a vytvořit efektivní aplikace přizpůsobené danému problému.

knihovna

V obou částech, map a unordered_map poskytnutého kódu, jsme použili knihovna. Tato knihovna v C++ STL nám poskytuje funkce a třídy pro výpočet času. C++ program pro výpočet trvání programu pomocí knihovny Chrono poskytuje jasné vysvětlení high_resolution_clock, který se používá k měření času v mikrosekundách, a Duration_cast(), který převádí jednotky vypočteného trvání na požadovaný typ.