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.
