 Ez a második része a C++23 nyelven a legmegfelelőbb asszociatív konténer (szótár) kiválasztásáról szóló sorozatnak.   , ebben a részben pedig a még nem rendelt konténerekről lesz szó. Az első részben a megrendelt konténerekkel foglalkoztunk  Rendeletlen konténerek  Ezek a tárolók nem biztosítanak meghatározott sorrendet a kulcsaikhoz. Sőt, a kulcsok sorrendje minden módosítással változhat, így a program soha ne hagyatkozzon rá. Az ilyen konténereket mindig hash-térképként valósítják meg.  Általánosságban elmondható, hogy kulcs hozzáadásakor, eltávolításakor vagy keresésekor a hash-leképezés először a hash-függvény segítségével számít ki valamilyen integrált hash-értéket a kulcsból. A hash-t (vagy inkább annak részét) ezután indexként használják a szomszédos előre lefoglalt tömbben. Ebben a tömbben minden bejegyzést   nevezünk. A tömb egyes bejegyzései üresek, némelyik egyetlen elemet tartalmaz, néhány pedig több elemre is leképezhet a hash ütközések miatt. Ez akkor fordul elő, ha a különböző kulcsok hash értékei ugyanarra a tömbindexre mutatnak. A hash-térképek különféle stratégiákat használnak a hash-ütközések kezelésére (lásd   ). A hash térkép elemeinek számát osztva a tömb teljes méretével   nevezzük. Minél nagyobb a terhelési tényező, annál több lehetséges hash-ütközés lehetséges minden egyes újonnan beillesztett elemnél. vödörnek ezt a Wikipédia-cikket terhelési tényezőnek  A rendezett konténerekkel ellentétben a hash térképek nem támogatják a tartománylekérdezéseket, a rangsorolási/kiválasztási műveleteket, a kulcsok sorrendjében történő iterációt és az adott kulcsnál kisebb/nagyobb kulcs keresését. Cserébe a hash térképek elérik az elérhető legjobb teljesítményt: a keresési/beszúrási/eltávolítási műveletek időbeli összetettsége     . Itt azt mondom, hogy "amortizált", mert amikor az elemek száma túl nagy lesz, akkor a hash térképnek újra kell olvasnia a tartalmát, hogy csökkentse a terhelési tényezőt (hatékonyan növelje a vödör tömböt). Az újrafeldolgozás időbonyolultsága   . Ez azonban várhatóan ritkán fordul elő, így átlagosan minden művelet még mindig   . A potenciálisan csökkent teljesítmény másik oka a rossz eloszlású hash függvény, amely növeli az ütközések gyakoriságát. amortizálódik O(1) O(n) O(1)  Szabványos hash térképek  A C++11-től kezdve a szabványos könyvtár a következő hash-leképezéseket biztosítja:   (   ),   (   ),   (   ) és   (   ).   kulcsot társít az értékhez, míg   csak a kulcsot tárolják, és hasznosak annak ellenőrzésére, hogy a kulcs megtalálható-e a tárolóban, de nem kéri le a társított értéket.   konténer lehetővé teszi több duplikált kulcs tárolását. std::unordered_map link std::unordered_set link std::unordered_multimap link std::unordered_multiset link A Maps a készletek A több  Minden szabványos rendezetlen konténer csomópont alapú, és   használ a hash ütközések kezelésére, ami azt jelenti, hogy minden kulcsot vagy kulcs-érték párt külön csatolt listacsomópontban tárolja. A memóriát minden új csomóponthoz külön-külön osztják ki, ami nem különösebben hatékony. Emiatt az adatstruktúra nem is CPU-gyorsítótár-barát, mert minden egyes kulcshoz való hozzáférés extra közvetettséget igényel. Így nézhet ki az   belső szerkezete:  külön láncolást unordered_map  A bal oldalon van egy sor gyűjtőhely, amely előre hozzá van rendelve valamilyen rögzített mérethez (példánkban   ). Kezdetben minden vödör üres. Amikor elkezdünk elemeket hozzáadni a hash térképhez, néhány gyűjtőhely foglalt lesz. A fenti példában van egy   kulcsú elem (amely   tárolóba került), valamint két   és   os kulcsú elem, mindkettő ugyanabba a   gyűjtőbe került, mert a hash értékeik ütköztek. Van egy   kulcsú elem is, amely   vödörben landolt. Minden vödör a hivatkozott listára mutat, amely ideális esetben legfeljebb egy elemet tartalmaz.   ,   ,   ,   és   csoport üres, és   -re mutat. 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr  Tegyük fel, hogy meg kell találnunk a   os kulcs értékét. 256  Először is, a térkép kiszámítja a kulcskivonatot, és megkapja a maradékot, amikor elosztja a hash értékét a gyűjtők teljes számával (esetünkben   ). Példánkban a maradék értéke   . 8 3  Ezután a térkép elkezdi olvasni a hivatkozott lista elemeit, amelyekre a vödör   mutat. 3  Az első elemen az   kulcs található, ami nem ugyanaz, mint a keresett   , így a térkép folytatja az iterációt. A következő elem a   kulcsot tartalmazza, amelyre pontosan szükségünk van. A megfelelő érték   . 50 256 256 xyz  Ha a kulcs nem lenne a szótárban, a térkép vagy egy üres vödörbe ütközne, vagy a linkelt listán a végéig iterálna. Mindkét esetben a térkép egy   ad vissza, jelezve, hogy a kulcs nem létezik. end  Észreveheti, hogy az egyes listák utolsó eleme a következő lista első elemére mutat. Ezt egyes megvalósításokban az iteráció hatékonyságának javítása érdekében teszik. Ahelyett, hogy vödrönként ellenőriznénk, amikor az összes hash-térkép elemet iteráljuk, ezeket a kapcsolatokat használhatjuk arra, hogy az egyik nem üres hivatkozási listáról sokkal gyorsabban ugorjunk át a másikra.  Ha továbbra is további elemeket adunk a fenti hash-térképhez, egy ponton a   túl magas lesz (például 80%), és a hash-térkép az újrakivonatolás mellett dönt. Növeli az előre lefoglalt tömböt (pl.   -ról   elemre), újraszámítja az összes meglévő elem hash-jét, és az elemeket az új gyűjtőhelyekbe helyezi. terhelési tényező 8 16  A szabványos konténerek referencia- és iterátor-stabilitási garanciákat nyújtanak, de gyengébbek, mint a megrendelt konténerek. A meglévő elemekre való hivatkozások soha nem érvénytelenek. A meglévő elemek iterátorai csak akkor érvényteleníthetők, ha egy új elem hozzáadása újrafeldolgozást okoz, vagy ha az újrakivonatolást manuálisan indítják el:   #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; }  A C++17 óta a rendezetlen konténerek lehetővé teszik a csomópontok manipulálását: lehetséges egy csomópontot az egyik térképről áthelyezni egy másik térképre anélkül, hogy a kulcsot és az értéket másolnánk:   #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } }  Ez történik a fenti programban:   Egy másik stratégia a hash ütközések kezelésére a   címzés. A nyílt címzésű hash-térképekben minden gyűjtőzóna legfeljebb egy elemet tárol. Ha a vödör már foglalt, akkor az azonos hash értékkel rendelkező elem egy másik szabad tárolóba kerül. Az ilyen hash-leképezések megpróbálják az elemeket összefüggő memóriablokkokban csoportosítani, hogy javítsák a hatékonyságot és az adatstruktúrát CPU-gyorsítótár-barátabbá tegyék. A C++ szabványos könyvtár nem biztosít nyílt címzési hash-térképeket, de számos harmadik féltől származó alternatíva létezik. nyílt  Harmadik féltől származó hash térképek    egy fantasztikus könyvtár, amely a hash-térkép-megvalósítások széles skáláját kínálja. A Boost.Unordered  Vannak   ,   ,   és   , amelyek az   konténerek analógjai, és minden, ami fent van, vonatkozik rájuk. Ezek a konténerek egy kicsit bonyolultabb belső struktúrát használnak "vödörcsoportokkal" az iterációs hatékonyság javítása érdekében.  boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std  A könyvtár   ,   ,   és   szolgáltatást is tartalmazza, amelyek nyitott címzési tárolók. A belső szerkezet eltér a nyílt címzési változatoktól:  boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map  A belső felépítésről bővebben   olvashat. ebben a blogbejegyzésben  A csomópont alapú konténerek (   ,   ) továbbra is használnak csomópontokat, amelyekre a gyűjtőhelyek mutatnak. Ezek a tárolók ugyanazt az iterátor és referencia stabilitást biztosítják, mint az   konténerek, és ugyanazt az API-t biztosítják a csomópontok manipulálásához (azaz   módszerhez). boost::unordered_node_set boost::unordered_node_map std extract  Lapos tárolókban (   ,   ) a kulcsok és értékek közvetlenül a vödörtömbben tárolódnak. A lapos konténerek a leghatékonyabbak, de a leggyengébb garanciákat nyújtják: az iterátorok és az összes elemre való hivatkozás érvénytelenítésre kerül, amikor újrafeldolgozás történik. Csomópont-manipulációs API egyáltalán nem biztosított. A lapos tárolók több memóriát igényelhetnek, mint a csomópont-alapúak, különösen akkor, ha a kulcs vagy a   nagy. boost::unordered_flat_set boost::unordered_flat_map sizeof  Egy másik, nyílt címzésű konténereket megvalósító, harmadik féltől származó könyvtár a   (a Meta szolgáltatója). Van néhány szótárváltozat, amelyek nagyon közel állnak a fent leírt Boost könyvtári tárolókhoz: Folly F14    ugyanaz, mint   ,   ugyanaz, mint   . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map    ugyanaz, mint   , és   ugyanaz, mint   . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map    /   a kulcsokat/értékeket egy összefüggő tömbbe csomagolva tartja, és a gyűjtőhelyek indexeket tartalmaznak ebbe a tömbbe. folly::F14VectorMap folly::F14VectorSet    /   egy esernyőosztály. Kiválasztja a leghatékonyabb megvalósítást (   vagy   ) az Ön által megadott paraméterek (például kulcs- és értéktípusok) alapján. folly::F14FastMap folly::F14FastSet F14Value F14Vector  Az F14 hash térképek érdekes extra hatékonysági jellemzője   . Például, ha többször kell keresni ugyanazt a kulcsot, és a kivonatolása drága (pl. egy kulcs egy karakterlánc), akkor egyszer előzetesen kivonatozhatja, majd később az   minden hash map hívásnál használhatja, hogy elkerülje az újra ugyanazt a kulcsot többször is kivonatolja. A kiindulópont a   módszer (   ). az előkivonatolás F14HashToken prehash link  Az F14 hash konténerek belső felépítéséről   olvashat bővebben. ebben az FB blogbejegyzésben      (a Google által biztosított) nyílt címzésű csomópont-alapú és lapos hash-tárolókat is megvalósít:   ,   ,   ,   . Hasonlóak a Boosthoz és az F14-hez. Bővebben   és   olvashat róluk. Az Abseil Swiss Tables könyvtár absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set itt itt  Egy kevésbé ismert   könyvtár (   ) azt állítja, hogy a legtöbb esetben nagyon hatékony. Ennek a könyvtárnak a szerzője kiterjedt benchmark eredményeket kínál számos hash-térképhez különböző használati esetekben (   ). Követheti ezeket az eredményeket, de vegye őket egy szem sóval. Mindig tesztelje a kiválasztott hash térképet az éles környezetben. A benchmarkok mindig szintetikusak, és nem fedik le azokat az eseteket, amikor a CPU és a memória a hash-leképezési műveleteken kívül más munkát is végez. A benchmarkok nem fedik le azokat az eseteket sem, amikor a hash térképmemória egyes részei nincsenek a CPU gyorsítótárában, ami gyakran előfordul valós programokban. ankerl github blogbejegyzés  Hash függvény minősége  A hash függvény minősége fontos az   keresési műveletek időbeli összetettségének megőrzéséhez. A lapos hash térképek különösen érzékenyek a hash függvény minőségére. Egy ideális hash függvényt így definiálhatunk: ha a kulcs egyetlen bitje megváltozik, a megfelelő hash érték a bitek felét véletlenszerűen megváltoztatja. Az ilyen hash függvényt   nevezzük.  O(1) lavinázásnak  Sajnos egyes C++ szabványos könyvtári megvalósítások az egész számok és a mutató hash függvényei nem lavinaszerűek. Például   egyszerűen visszaadja a mutatót vagy az egész értéket, további átalakítások nélkül:   . libstdc++ github  A speciális hash táblák, például   és   implementációk a   tulajdonság bevezetésével kezelik ezt a problémát. Ha a hash függvény nem lavinaként írja ki magát, a hash tábla további keverési lépést hajt végre a hash minőségének javítása érdekében. Ez külön költséggel jár. Ha egyéni hash-függvényt valósít meg, és tudja, hogy az megfelelő minőségű, akkor lavinaként jelölheti meg, amint az   látható . A Boost az   tulajdonságnevet használja, az F14 tulajdonság neve pedig   . Ideális esetben mindkettőt hozzá kell adni. boost F14 hash_is_avalanching ebben a példában is_avalanching folly_is_avalanching  Ha a gyárilag támogatott kulcstípusokat (pl.   ,   , pointers) és a   vagy   által biztosított alapértelmezett hash függvényeket használod, akkor ezek már szükség szerint megfelelően meg lesznek jelölve, és nem kell ezen gondolkodnod, hacsak nem úgy dönt, hogy egyéni kulcstípust implementál, amelyhez egyéni hash függvényre lesz szükség. string int boost F14  Menetbiztonság  A fenti tárolók általában nem szálbiztosak, és külső szinkronizálást kell végrehajtania (például mutexek használatával), ha az egyik szál módosíthatja a hash-leképezést, amikor egy másik szál hozzáfér.  Ha az összes szál csak a térképet olvassa, nincs szükség szinkronizálásra. Ügyeljen arra, hogy csak   jellel jelölt metódusokat hívja meg. Minden nem   metódus módosíthatja a tárolót. Ne feledje, hogy   nem   , és módosítja a tárolót. A többszálú kód gyakori buktatója: const const operator[] const   std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... }  A fenti kódban a cél annak ellenőrzése, hogy a   megfelelő érték   e.   azonban   a   a   , ha még nincs ott. Az újonnan hozzáadott érték alapértelmezettre lesz állítva (   a fenti példában). Ez azt jelenti, hogy az ilyen kód nem szálbiztos, és nem túl optimális. Egy hatékonyabb és szálbiztosabb módszer ugyanazon állapot ellenőrzésére a következő: key true map["key"] hozzáadja key map false   if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... }  Itt először eljuttatjuk az iterátort a "kulcs" által azonosított elemhez.  Ezután ellenőrizzük, hogy az elem létezik-e a térképen (   ). it != map.end()  Ha igen, akkor végül ellenőrizzük az értékét (   ). it->second == true  Ebben a példában   és   nem módosítja a térképet, és a keresés szálbiztossá válik. Ha csak az volt a cél, hogy ellenőrizze, hogy a kulcs létezik-e a térképen, egyszerűen meghívhatja   . find end map.contains("key")  Szálbiztos rendezetlen térképek  A szálbiztos hash-térképeknek van néhány megvalósítása.  Az egyik lehetőség   és   a     . A Boost tárolók látogatásalapú API-t biztosítanak, amely nagymértékben különbözik a C++ szabványkönyvtár által biztosított API-tól. boost::concurrent_flat_set boost::concurrent_flat_map Boost.Unordered könyvtárból  Egy másik lehetőség a   (   ). A Folly igyekszik az API-ját a lehető legközelebb tartani a C++ szabványos rendezetlen konténerekhez. folly::ConcurrentHashMap github    egy nagy, zárolás nélküli konténerkönyvtár, amely számos zárolásmentes hash-leképezést biztosít (pl.   ,   ,   ,   ,   ). Ez a könyvtár egy ideje nem frissült, és nem nyújt részletes dokumentációt, de továbbra is megosztom, mert az általa kínált tárolók egyediek. Ha az Ön használati esete nagy versengésre utal egy hash térképen, próbálja ki ezeket a zárolás nélküli szótárakat, amelyeket   kínál. A libcds MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds  Ha a hatékonyság nem aggodalomra ad okot, mutexek segítségével szinkronizálhatja a hozzáférést a nem szálbiztos térképekhez. Alternatív megoldásként teljesen elkerülheti az egyidejű hozzáféréseket, ami gyakran hatékonyabb, mint a szálbiztos tárolók használata vagy a szinkronizálás hozzáadása.  Melyiket használjam?  Nézzük meg azokat az összefoglaló pontokat, amelyek elmagyarázzák, hogyan válasszuk ki a legmegfelelőbb tartályt.  Ha kulcsot kell társítania az értékhez, válasszon egy   , ellenkező esetben használjon egy   . térképet készletet  Ha duplikált kulcsokat kell tartani a térképen, használjon   tárolót. több  Ha a lehető legszigorúbb iterátor- és referenciastabilitási garanciákra van szüksége, használjon   ,   ,   vagy   csomópont alapú tárolókat (például   ,   ,   vagy   ).   és   valószínűleg a leghatékonyabb. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly  Ha az iterátor és a referencia stabilitása nem fontos (ami azt jelenti, hogy nem tárolja az iterátorokat, hivatkozásokat vagy mutatókat külső leképezési/beállítási elemekhez, vagy nem várja el, hogy a térkép módosítása után is érvényesek maradjanak), akkor válasszon egy lapos tárolót (pl. mint   vagy   ). boost::unordered_flat_map folly::F14FastMap  A lapos tárolók több memóriát használnak, mint a csomópont-alapúak, különösen akkor, ha a kulcs   és/vagy az érték nagy. Ha a memóriahasználat aggodalomra ad okot, használjon helyette csomópont-alapú tárolókat. sizeof  Az F14 konténerek előtörlő funkciót biztosítanak az extra hatékonyság érdekében. Ha ugyanazokat a kulcsokat többször keresi/adja hozzá/eltávolítja, az F14 lehetővé teszi a kivonatolási költségek megtakarítását a kulcsok előzetes tördelésével.  A fenti pontok mindegyike az egyszálú tárolóhasználatra vonatkozik (vagy többszálú olvasási hozzáférésre, párhuzamos módosítások nélkül). Ha többszálas módosításokra van szükség, válassza ki a fent felsorolt szálbiztos opciók egyikét. Változó teljesítményt mutathatnak a valós gyártási kódban, ezért fontolja meg, hogy tesztelje őket az alkalmazásban, és hasonlítsa össze az eredményeket.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Ez a hanganyag a történet eredeti nyelvén készült!

A legjobb szótár kiválasztása C++ nyelven. 2. rész: Rendeletlen konténerek

About Author

HOZZÁSZÓLÁSOK

HANG TAGOK

EZT A CIKKET BEMUTATTA

Related Stories

On OpenAI Failed Board Coup of Sam Altman & the Danger of Leaving AI Fate in the Hands of a Few

Of The First and Last Things: Part 4

HackerNoon Social Media Presence: A Complete Guide

The Little Shop at Fishbourne

On OpenAI Failed Board Coup of Sam Altman & the Danger of Leaving AI Fate in the Hands of a Few

Of The First and Last Things: Part 4

HackerNoon Social Media Presence: A Complete Guide

The Little Shop at Fishbourne

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps