cpp jak porovnat s mapami


Odpověď 1:

Matematicky je mapa model, který má klíč a odpovídá hodnotou. Sada je specializovaný případ mapy, kde je klíč identický s hodnotou, na kterou se mapuje. Tento koncept se vztahuje na implementaci těchto dvou objektů v C ++.

Když je std :: map užitečné: Zvažte databázi, která ukládá uživatelské účty, řekněme, že jsou to účty Netflix. Mapa, která představuje tuto tabulku uživatelů netflixu, může obdržet ID uživatele a vrátit uživatelský objekt relevantní pro toto ID číslo. Poté můžeme použít ID k načtení uživatelského účtu v čase O (1) hašováním jedinečného ID uživatele k účtu a k vyhledání účtu vše, co byste potřebovali, je ID, abychom mohli načíst všechna tato uživatelská data.

Můžeme to udělat se std :: set? Jak bychom mohli implementovat tento předchozí příklad se sadou? Můžeme vložit uživatelské účty do naší std :: set, ale když chceme vyhledat uživatelský účet, budeme potřebovat celý uživatelský účet, abychom mohli vyhledat náš uživatelský záznam. Počkejte chvíli, pokud již máme informace o uživatelském účtu, proč bychom je museli hledat? Také co když máme pouze ID uživatele, nemůžeme již načíst účet v čase O (1), musíme iterovat celou tabulku, abychom našli účet, který odpovídá, a toto bude O (N).

Kdy byste chtěli použít std :: map vs. kdy byste chtěli použít std :: map pro primitiva? Zvažte strukturu určenou k uložení všech prvočísel pod nějakou libovolnou hodnotou N. Pokud prostě chceme vědět, jestli je číslo členem množiny prvočísel, pak má smysl std :: set, můžeme jednoduše chtít zkontrolovat, zda je libovolné celé číslo hodnota 'k' existuje v naší sadě a nemusí nás zajímat jakýkoli pojem indexu nebo klíče. Pokud nás však zajímá posloupnost prvočísel, můžeme chtít párování klíč-hodnota. Možná bychom chtěli modelovat posloupnost p = {2, 3, 5, 7, 11,…} a chtěli bychom vědět, jestli p [j] = k pro libovolné hodnoty j & k. V tomto druhém případě možná budeme chtít zvážit std :: map (i když std :: vector může být také dobrá volba).

Stručně řečeno:

  1. Datová struktura sady je specializovaný typ datové struktury mapy, kde key == hodnota a definice C ++ STL odrážejí tento koncept
  2. std :: map než std :: set je obecně užitečnější, protože std :: map poskytuje rychlé vyhledávání agregovaných hodnot podle klíče (celých objektů spíše než primitiv).
  3. std :: set je často užitečnější pro primitiva, protože mapování primitivní hodnoty k-> k je poněkud libovolné

Odpověď 2:

Mnoho z odpovědí se nedaří dotknout změny implementace mapových a nastavených kontejnerů pro C ++ 17, i když je to relevantní, takže to budu pokrývat výhradně.

Jak můžete přesunout uzel z jednoho kontejneru do druhého?

Jak můžete změnit klíč uzlu mapy?

Pokud jste do mapy nebo sady vložili pohyblivá, ale ne kopírovatelná data, jak je můžete znovu dostat zpět?

Na všechny v C ++ 17 odpovídá odpověď přidáním nové neprůhledné datové struktury… uzlový úchyt… a dvě nové členské funkce pro každou sadu nebo kontejner mapy, které pracují s uzlovými úchyty… extrakt, který extrahuje uzel z mapy nebo set into a handle handle, and a new overload of insert, which takes a node from a node handle and inserts it into a map or set. K dispozici je také nová výhodná metoda sloučení, která přesune všechny neduplicitní uzly na jedné mapě nebo nastaví na jinou.

Popisovač uzlu (C ++ 17)

Popisovač uzlu má více vlastností. Vlastní extrahovaný uzel přesně stejným způsobem jako std :: unique_ptr, takže je také pohyblivý, ale ne kopírovatelný. Pokud rukojeť uzlu vlastní uzel, když je zničen, uzel je zničen a uvolněn… což znamená, že také musí mít kopii alokátoru použitého v jeho kontejneru k provedení uvolnění. To znamená, že alokátory použité ve dvou kontejnerech musí porovnávat stejnou hodnotu (operator == vrací true), aby byl uzel přesunut z jednoho kontejneru do druhého. Všechny výchozí alokátory se porovnávají stejně, takže to obvykle není problém.

Zatímco uzel je vlastněn uzlem handle nh, lze jej provozovat způsoby, které nejsou možné, když je v mapě nebo sadě. Například extrahovaný uzel mapy může mít svůj klíč změněn přiřazením k nh.key () a nechat kopírovat nekopírovatelnou mapovanou hodnotu pomocí std :: move (nh.mapped ()). Extrahovaný uzel sady může mít přesunutou nekopírovatelnou hodnotu pomocí std :: move (nh.value ()).


Odpověď 3:

V současné době C ++ nabízí 8 standardů

asociativní kontejnery

v tomto prostoru:

  • std :: set
  • std :: multiset
  • std :: unordered_set
  • std :: unordered_multiset
  • std :: mapa
  • std :: multimap
  • std :: unordered_map
  • std :: unordered_multimap

Můžete si všimnout, že zde existují 3 variační osy:

  • set vs. mapa.
  • objednané vs. neuspořádané.
  • jedinečný klíč vs. více klíčů.

Ptali jste se na set vs. mapa; ale stojí za to vědět, jak vybírat mezi všemi 8 kombinacemi.

set vs. mapa

Sada obsahuje sadu klíčů. Můžete vložit a odebrat klíče ze sady, vyzkoušet, zda je klíč v sadě, a iterovat přes sadu všech klíčů. Jakmile je klíč vložen do sady, je neměnný. Jakmile je klíč vložený, nemůžete jej změnit. Chcete-li změnit stávající klíč, musíte jej smazat a vložit nový klíč.

Mapa spojuje hodnotu s každým klíčem. Hodnoty mohou být odlišným typem od samotného klíče. Hodnoty jsou obvykle také měnitelné. Můžu vyhledat hodnotu podle jejího klíče a změnit ji, jakmile ji najdu.

Chcete použít sadu, když vás zajímá pouze sada klíčů, které máte. Chcete-li použít mapu, pokud máte zájem o sledování řady hodnot, které mají klíče spojené s nimi.

Předpokládejme například, že jsem chtěl sledovat všechny lidi účastnící se schůzky. K tomu by mohla stačit sada. Každý účastník je členem sady a můžu iterovat přes všechny členy sady a vygenerovat seznam účastníků.

Předpokládejme, že moje schůzka je zajištěna, a chci sledovat stravovací preference všech lidí, kteří se mé schůzky zúčastní. Teď chci mapu preferencí účastníka k jídlu. Klíčem v tomto případě je účastník a hodnotou je preference jídla. Předvolby jídla každého účastníka můžete upravit, aniž byste museli upravovat samotného účastníka. (Takto je to méně trapné ...)

objednané vs. neuspořádané

Asociativní kontejnery bez

neuspořádaný

v nabídce názvu

O (\ lg n)

přístupová doba. Vyžadují klíče, které jsou

Srovnatelný

a

Přísně slabé nařízeno.

Obvykle jsou postaveny z vyvážených binárních vyhledávacích stromů. Pokud iterujete všechny prvky, navštívíte klíče v neklesajícím pořadí. (Nebo nerostoucí pořadí, pokud používáte reverzní iterátory.)

Asociativní kontejnery s neuspořádanými v názvu nabízejí amortizovaný čas přístupu O (1) za předpokladu, že pro svůj klíč můžete vytvořit hashovací funkci O (1). Hovorově se jedná o hashovací tabulky. Abyste mohli neuspořádané kontejnery pracovat efektivně, potřebujete efektivní hashovací funkci. Pokud iterujete všechny prvky, navštívíte klíče v libovolném pořadí.

Kdy byste měli použít objednané vs. neuspořádané? Záleží na několika věcech:

  • Potřebujete často navštěvovat všechny klíče v deterministickém pořadí? Pokud ano, objednaný kontejner může být rozumnou volbou.
  • Je srovnání rychlejší nebo pomalejší než hašování? Pokud je to mnohem rychlejší, objednané může být lepší. Pokud je to mnohem pomalejší, neuspořádané může být rychlejší.
  • Znáte přibližnou celkovou velikost kontejneru předem? Změna velikosti neuspořádaného kontejneru může být nákladná, zatímco vložení do objednaného kontejneru nemá tendenci mít divoké výkyvy výkonu.
  • Jakou paměťovou stopu můžete tolerovat? Neuspořádané kontejnery mají tendenci vyměňovat velikost za rychlost.

Pokud svůj kód napíšete opatrně, můžete zkusit přepínat mezi objednanými a neuspořádanými kontejnery na srovnávací test, který lépe funguje pro konkrétní pracovní zátěž.

Jedna aplikace, kterou jsem napsal, skončila se zajímavou kombinací objednaných a neuspořádaných kontejnerů založených právě na takovém benchmarkingu. Trochu mě překvapilo, které kontejnery kde zvítězily a jak se to změnilo, když jsem změnil vlastnosti klíčů. Zejména přesun z std :: string do tabulky řetězců indexovaných celými čísly výrazně změnil náklady na hashovací funkce.

jedinečný klíč vs. více klíčů

Asociativní kontejnery bez vícenásobného názvu umožňují pouze jednu instanci každého klíče v kontejneru. To znamená, že každý klíč musí být jedinečný. To poskytuje podobnou sémantiku jako 1-D pole, kde každý index obsahuje jeden prvek. Vložení klíče, který již v kontejneru existuje, je logická chyba.

Asociativní kontejnery s více v názvu umožňují více instancí každého klíče. Každý klíč můžete vložit tolikrát, kolikrát chcete. Opakované klávesy jsou udržovány v pořadí vkládání.

Poznámka: To je důležité i pro multiset, protože srovnávací kritéria rozlišují ekvivalent od rovného. Dva klíče jsou ekvivalentní, pokud žádný z nich neporovnává méně než ten druhý; Porovnávací funkce však není vyžadována, aby byla zohledněna všechna pole klíčového objektu.

Který byste si měli vybrat? Opravdu to záleží na problému, který se snažíte vyřešit. Anekdoticky jsem zřídka potřeboval multisety nebo multimapy.

Pokud potřebujete sledovat všechny instance „klíčů“, které vidíte, ať už se některé z nich srovnávají jako rovnocenné, pak je multiset nebo multimap tou správnou volbou. Jinak budete pravděpodobně chtít jiné sady nebo mapy.

Jedno zajímavé použití pro std :: multiset nebo std :: multimap je jako prioritní fronta. Jako prioritu použijte prioritu. Prvek vrácený funkcí begin () je vaší položkou s nejvyšší prioritou. Seznam položek je udržován v seřazeném pořadí, takže vzhledem k iterátoru, který ukazuje na položku, můžete rychle určit, co je těsně před a těsně po něm. Zejména pokud je priorita ve skutečnosti reprezentována časem - to znamená, že tato prioritní fronta je ve skutečnosti časově seřazená fronta událostí -, můžete levně určit, jaké události jsou naplánovány v blízkosti určitého času.

To však funguje pouze s objednaným multisetem a objednaným multimapem.

std :: priority_queue

může být lepší volbou, pokud potřebujete pouze rychlý přístup k položce s nejvyšší prioritou a nevyužíváte plně tříděného charakteru multisetu nebo multimapy. (Vidět

std :: priority_queue

Více podrobností.)


Odpověď 4:

Na to mohu odpovědět.

Mapy

Mapy vyžadují klíče. Pro každý klíč máte určitý druh hodnoty.

Klíčem nyní může být cokoli, celé číslo, řetězec nebo dokonce objekt (poskytnutý s dalšími funkcemi porovnání). Stejně tak mohou být i hodnoty.

Podívejte se na toto:

mapa M; // celočíselný klíč - celočíselná hodnotaM [3] = 2;mapa S; // řetězec klíč - celočíselná hodnotaS ["ahar"] = 26;

To je fascinující.

Předpokládejme, že chcete uložit narozeniny svých přátel. Právě deklarujete mapu a ukládat jejich jména a data narození jednoduchým přiřazením. Je to jako slovník v Pythonu.

Sady

To neplatí pro sady. Sady nepotřebují párování (klíč, hodnota). Prostě obsahují jakýkoli druh hodnot (samozřejmě s funkcemi porovnání nebo přetížením operátora v případě potřeby), které mají obsahovat. Například:

soubor S;S. vložka (13);soubor T;S. vložení ("ahar");soubor X;S. vložení (váš objekt);

Z hlediska výkonu mají podobnosti. Vyhledávání, vkládání, mazání atd. Jsou v pořadí

O (logn)

v obou (díky patří

Červený černý strom

, čeho jste se ve svém kurzu Datové struktury báli: P). Ale kvůli rozdílům v implementaci a použití mohou existovat určité režijní náklady.

Další poznámka:

Pokud provedete pozorování, zjistíte, že ze základní strukturální perspektivy se sady a mapy liší. Takže otázka, kterou jste položili, může být trochu zajímavější, pokud o ní přemýšlíte tak, že můžete použít sady jako alternativu map a naopak.

To nás může vést k zajímavé otázce: jaký je rozdíl mezi množinou > a mapa ? To je docela platná otázka, protože v tomto scénáři můžete myslet na první prvek dvojice v sadě ekvivalentní klíči na mapě!

Například:

mapa M;M.insert ({"motta", 13});soubor > S;S. vložení ({"motta", 13});

Vidíte, že výše napsaná sada může být potenciální alternativou k mapě.

Jsou tedy rovnocenné? No, ne.

Za prvé, mapa nemůže obsahovat různé celé číslo pro stejný klíč, jak jsme deklarovali výše. Ale sada může.

Tak,

M.insert ({"ahar", 13)};S.insert ({"ahar", 13});M.insert ({"ahar", 26});S.insert ({"ahar", 26});

dělá velikost sady rovnou 2, ale pro mapu je to 1.

Za druhé, měli byste již vědět, že tyto kontejnery C ++ používají iterátory, které se používají k nasměrování prvků v těchto kontejnerech. Abychom si to jednoduše mysleli, iterátory jsou to, co potřebujete pro přístup k datům v těchto kontejnerech.

Nyní se podívejte na toto:

soubor > S;S.insert ({"ahar", 26});auto it = S.begin (); // nyní je iterátor pro ("ahar", 26)

Z nějakého důvodu máte v úmyslu změnit hodnotu příslušného iterovaného páru z 26 na 13. Zkuste to:

it-> druhý = 13;

Hmm ... nah. To nemůžeš udělat.

Důvod je poněkud komplikovaný. Jednoduše řečeno, iterátory pro sadu C ++ jsou jako konstantní iterátory. Nemůžete tedy pouze upravit odpovídající hodnotu dat na místě. Musíte ji vymazat ze sady a poté přidat novou hodnotu, například takto:

S.erase (it);pár p = {"ahar", 13};S. vložení (p);

: |

V případě map to platí úplně:

mapa M;M.insert ({"motta", 13});auto it = M.begin ();it-> druhý = 26;

Doufám, že mám všechno v pořádku. : P

Děkuji za přečtení.


Odpověď 5:

Mapa je datová struktura používaná k vyhledávání hodnot pomocí klíčů, zatímco sada je pouze soubor hodnot.

Z hlediska implementace nejsou obvykle implementovány odlišně a oba obvykle používají červeno-černé stromy pod kapotou k získání logaritmické časové složitosti pro většinu operací. Jedním rozdílem, v závislosti na implementacích, je, že sada by byla červeno-černým stromem prvků, zatímco mapa by byla červeno-černým stromem (klíč, hodnota) n-tice prvků seřazených podle prvního prvku (klíč) v n-tice.


Odpověď 6:

Mapa mapuje jeden objekt na jiný. Sada je uspořádaná sada objektů. Mapa se často používá k přístupu k objektům indexem takovým způsobem, že objectMap [i] obsahuje objekt s indexem i. Sada může být použita k ukládání objektů s další výhodou, že sada identifikuje, zda je objekt již v něm obsažen, a ukládá pouze jednu entitu objektů. K objektům v sadě však můžete přistupovat pouze její iterací nebo získáním prvního nebo posledního prvku sady.


Odpověď 7:

std :: map je asociativní, uspořádané pole. To znamená, že ukládá párů a klíčem se dostanete k hodnotě. Můžete také iterovat nad páry a iterace bude následovat po dobrém uspořádání klíčů.

std :: set je pouze kolekce hodnot. Znovu to můžete iterovat a iterace bude opět sledovat dobré pořadí hodnot. Neexistuje však žádná asociace jako výše, můžete klást pouze otázky typu „je tato hodnota v sadě?“ A k tomu už musíte mít příslušnou hodnotu.