Aquesta és la segona part de la sèrie sobre l'elecció del contenidor associatiu (diccionari) més adequat en C++23. i, en aquesta part, parlarem dels contenidors no ordenats amb detall. A la primera part, vam cobrir els contenidors ordenats Contenidors no ordenats Aquests contenidors no proporcionen cap ordre definit per a les seves claus. A més, l'ordre de les claus pot canviar amb cada modificació, de manera que el programa mai no hauria de confiar-hi. Aquests contenidors sempre s'implementen com a mapes hash. Generalment, quan s'afegeix, s'elimina o es cerca una clau, un mapa hash primer calcula algun valor hash integral a partir d'aquesta clau mitjançant la funció hash. El hash (o més aviat la seva part) s'utilitza com a índex a la matriu pre-assignada contigua. Cada entrada d'aquesta matriu s'anomena . Algunes entrades d'aquesta matriu estaran buides, algunes contindran un sol element i algunes podrien mapar a més d'un element a causa de col·lisions hash. Això passa quan diferents claus tenen valors hash que apunten al mateix índex de matriu. Els mapes hash utilitzen diverses estratègies per fer front a les col·lisions hash (vegeu ). El nombre d'elements del mapa hash dividit per la mida total de la matriu s'anomena . Com més gran sigui el factor de càrrega, més possibles col·lisions es produiran amb cada element nou inserit. cub aquest article de la Viquipèdia factor de càrrega A diferència dels contenidors ordenats, els mapes hash no admeten consultes d'interval, operacions de classificació/selecció, iteració de claus en ordre i cerqueu la clau més petita/més gran que la clau donada. A canvi, els mapes hash aconsegueixen el millor rendiment possible: la complexitat temporal de les operacions de cerca/inserció/eliminació . Dic "amortitzat" aquí, perquè quan el nombre d'elements es fa massa gran, un mapa hash ha de repetir el seu contingut per reduir el factor de càrrega (augmentant de manera efectiva la matriu de cubs). La complexitat temporal de la repetició és . Tanmateix, s'espera que succeeixi poques vegades, de manera que, de mitjana, cada operació encara és . Un altre motiu del rendiment potencialment reduït és una funció hash amb una distribució deficient, que augmentarà la freqüència de col·lisions. s'amortitza O(1) O(n) O(1) Mapes hash estàndard A partir de C++11, la biblioteca estàndard proporciona els mapes hash següents: ( ), ( ), ( ) i ( ). associen una clau amb el valor, mentre que només emmagatzemen la clau i són útils per comprovar si la clau està present al contenidor, però no recuperar el valor associat. Els contenidors permeten emmagatzemar múltiples claus duplicades. std::unordered_map enllaç std::unordered_set enllaç std::unordered_multimap enllaç std::unordered_multiset enllaç Els mapes els conjunts múltiples Tots els contenidors estàndard no ordenats es basen en nodes i utilitzen per fer front a les col·lisions hash, el que significa que emmagatzemen cada parell clau o valor-clau en un node de llista enllaçat independent. La memòria per a cada nou node s'assigna individualment, cosa que no és especialment eficient. Això també fa que l'estructura de dades no sigui amigable amb la memòria cau de la CPU, perquè cada accés de clau requereix una indirecta addicional. Així és com pot semblar l'estructura interna : l'encadenament separat unordered_map A l'esquerra, hi ha una matriu de cubs, que s'assignen prèviament a una mida fixa ( al nostre exemple). Inicialment, tots els cubs estan buits. Quan comencem a afegir elements al mapa hash, alguns cubs estaran ocupats. A l'exemple anterior, hi ha un element amb la clau (que va entrar al cub ) i dos elements amb les claus i , tots dos van acabar al mateix cub perquè els seus valors hash van xocar. També hi ha un element amb la clau , que va aterrar a la galleda . Cada cub apunta a la llista enllaçada, que idealment no conté més d'un element. Els cubs , , , i estan buits i apunten a . 8 10 1 50 256 3 3 6 0 2 4 5 7 nullptr Suposem que hem de trobar el valor de la clau . 256 En primer lloc, el mapa calcula el hash de la clau i obté la resta quan es divideix el valor hash pel nombre total de cubs ( en el nostre cas). En el nostre exemple, el valor de la resta és . 8 3 Aleshores, el mapa comença a llegir els elements de la llista enllaçada apuntada pel cub . 3 El primer element té la clau , que no és la mateixa que la que busquem, de manera que el mapa continuarà iterant. El següent element té la clau , que és exactament la que necessitem. El valor corresponent és . 50 256 256 xyz Si la clau no estigués al diccionari, el mapa tocava un cub buit o repetiria la llista enllaçada fins al final. En ambdós casos, el mapa retornaria un iterador , indicant que la clau no existeix. end Podeu observar que l'últim element de cada llista apunta al primer element de la llista següent. Això es fa en algunes implementacions per millorar l'eficiència de la iteració. En lloc de comprovar cub per cub en iterar tots els elements del mapa hash, podem utilitzar aquestes connexions per saltar d'una llista enllaçada no buida a una altra molt més ràpid. Si continuem afegint més elements al mapa hash anterior, en algun moment el es farà massa alt (per exemple, el 80%) i el mapa hash decidirà repetir. Creixerà la matriu prèviament assignada (per exemple, de a elements), tornarà a calcular hash per a tots els elements existents i posarà elements als nous cubs. factor de càrrega 8 16 Els contenidors estàndard ofereixen garanties d'estabilitat de referència i iterador, però són més febles que els que ofereixen els contenidors demanats. Les referències als elements existents mai són invalidades. Els iteradors dels elements existents només es poden invalidar quan l'addició d'un element nou provoca un refresc o quan el repetit s'activa manualment: #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"; } Des de C++17, els contenidors no ordenats permeten la manipulació de nodes: és possible agafar un node d'un mapa i moure'l a un altre mapa sense copiar la clau i el valor: #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"; } } Això és el que passa en el programa anterior: Una altra estratègia per fer front a les col·lisions hash s'anomena . En els mapes hash d'adreçament obert, cada cub emmagatzema com a màxim un element. Si el cub ja està ocupat, l'element amb el mateix valor hash passa a un altre cub lliure. Aquests mapes hash intenten agrupar elements en blocs de memòria contigus per millorar l'eficiència i fer que l'estructura de dades sigui més amigable amb la memòria cau de la CPU. La biblioteca estàndard de C++ no ofereix mapes hash d'adreces obertes, però hi ha moltes alternatives de tercers. adreçament obert Mapes hash de tercers és una biblioteca fantàstica que ofereix una àmplia gamma d'implementacions de mapes hash. Boost.Unordered Hi ha , , i , que són anàlegs per als contenidors , i tot el que s'ha escrit anteriorment s'aplica a ells. Aquests contenidors utilitzen una estructura interna una mica més complexa amb "grups de cubs" per millorar l'eficiència de la iteració. boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap std La biblioteca també proporciona , , i , que són contenidors d'adreçament oberts. L'estructura interna és diferent de les variants d'adreçament obert: boost::unordered_node_set boost::unordered_node_map boost::unordered_flat_set boost::unordered_flat_map Podeu llegir més sobre l'estructura interna . en aquesta entrada del blog Els contenidors basats en nodes ( , ) encara utilitzen nodes, als quals assenyalen els cubs. Aquests contenidors proporcionen el mateix iterador i estabilitat de referència garantida que els contenidors i també proporcionen la mateixa API per a la manipulació de nodes (és a dir, el mètode ). boost::unordered_node_set boost::unordered_node_map std extract En contenidors plans ( , ), les claus i els valors s'emmagatzemen directament a la matriu de cubs. Els contenidors plans són els més eficients, però ofereixen les garanties més febles: els iteradors i les referències a tots els elements queden invalidats quan es produeix el refresc. L'API de manipulació de nodes no es proporciona en absolut. Els contenidors plans poden utilitzar més memòria que els basats en nodes, especialment si la clau o el valor és gran. boost::unordered_flat_set boost::unordered_flat_map sizeof Una altra biblioteca de tercers que implementa contenidors d'adreçament obert és (proporcionat per Meta). Hi ha algunes variants de diccionari molt properes als contenidors de la biblioteca Boost descrits anteriorment: Folly F14 és el mateix que , és el mateix que . folly::F14NodeSet boost::unordered_node_set folly::F14NodeMap boost::unordered_node_map és el mateix que , i és el mateix que . folly::F14ValueSet boost::unordered_flat_set folly::F14ValueMap boost::unordered_flat_map / manté les claus/valors empaquetats en una matriu contigua i els cubs contenen índexs en aquesta matriu. folly::F14VectorMap folly::F14VectorSet / és una classe paraigua. Tria la implementació més eficient (ja sigui o ) en funció dels paràmetres que especifiqueu (com ara els tipus de clau i valor). folly::F14FastMap folly::F14FastSet F14Value F14Vector Una característica extra d'eficiència interessant dels mapes hash F14 és . Per exemple, si necessiteu cercar la mateixa clau diverses vegades i el seu hash és car (p. ex., una clau és una cadena), podeu fer-ne un prehash una vegada i, a continuació, utilitzar el en totes les trucades de mapes hash més tard per evitar que es repeteixi. fent hash la mateixa clau diverses vegades. El punt de partida és el mètode ( ). el prehash F14HashToken prehash enllaç Podeu llegir més sobre l'estructura interna dels contenidors hash F14 en . aquesta publicació del bloc de FB (proporcionada per Google) també implementa contenidors de hash pla i basats en nodes d'adreçament obert: , , , . Són semblants als Boost i F14. Podeu llegir més sobre ells i . La biblioteca Abseil Swiss Tables absl::flat_hash_map absl::flat_hash_set absl::node_hash_map absl::node_hash_set aquí aquí Una biblioteca menys coneguda ( ) afirma ser molt eficient en la majoria dels escenaris. L'autor d'aquesta biblioteca proporciona amplis resultats de referència per a molts mapes hash en diferents casos d'ús ( ). Podeu seguir aquests resultats, però preneu-los amb un gra de sal. Proveu sempre el mapa hash que trieu a l'entorn de producció. Els benchmarks són sempre sintètics i no cobreixen els casos en què la CPU i la memòria fan altres tasques a més de les operacions de mapes hash. Els punts de referència tampoc cobreixen els casos en què diverses parts de la memòria del mapa hash no es troben a la memòria cau de la CPU, cosa que passa sovint en programes reals. ankerl github entrada al bloc Qualitat de la funció hash La qualitat de la funció hash és important per mantenir la complexitat temporal de les operacions de cerca . Els mapes hash plans són especialment sensibles a la qualitat de la funció hash. Una funció hash ideal es pot definir així: si un sol bit a la clau canvia, el valor hash corresponent canviarà la meitat dels seus bits aleatòriament. Aquesta funció hash s'anomena . O(1) allaus Malauradament, algunes implementacions de biblioteques estàndard de C++ de funcions hash d'enter i punter no són avalançant. Per exemple, simplement retorna el punter o el valor enter directament sense cap transformació addicional: . libstdc++ github Les taules hash avançades, com ara les implementacions i , tracten aquest problema introduint el tret . Si la funció hash no s'indica com a allau, la taula hash realitzarà un pas addicional de barreja per millorar la qualitat del hash. Això té un cost addicional. Si implementeu una funció hash personalitzada i sabeu que és de qualitat decent, podeu marcar-la com a allau com es mostra en . Boost utilitza el nom de la propietat i la propietat F14 s'anomena . Idealment, hauríeu d'afegir tots dos. boost F14 hash_is_avalanching aquest exemple is_avalanching folly_is_avalanching Si utilitzeu els tipus de clau admesos fora de la caixa (per exemple, , , punters) i les funcions hash per defecte proporcionades per o , ja estaran marcades correctament segons sigui necessari, i no haureu de pensar en això tret que decidiu implementar un tipus de clau personalitzat, que necessitarà una funció hash personalitzada. string int boost F14 Seguretat del fil Tots els contenidors anteriors no són segurs per a fils en general, i haureu d'implementar la sincronització externa (per exemple, utilitzant mutex) si un fil pot modificar el mapa hash quan un altre fil hi accedeix. Si tots els fils només llegeixen el mapa, no cal sincronitzar. Assegureu-vos que només truqueu als mètodes marcats amb . Tots els mètodes no poden modificar el contenidor. Tingueu en compte que no és i modificarà el contenidor. Un error comú en el codi multifil és: const const operator[] const std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... } Al codi anterior, l'objectiu és comprovar si el valor corresponent a la és . Tanmateix, la al si encara no hi és. El valor afegit recentment s'establirà com a predeterminat ( a l'exemple anterior). Això vol dir que aquest codi no és segur per a fils i no és massa òptim. Una manera més eficient i segura de comprovar la mateixa condició és la següent: key true map["key"] afegirà key map false if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... } Aquí, primer obtenim l'iterador a l'element identificat per la "clau". A continuació, comprovem si l'element existeix al mapa ( ). it != map.end() Si ho fa, finalment comprovem el seu valor ( ). it->second == true En aquest exemple, i no modifiquen el mapa i la cerca esdevé segura. Si l'objectiu era només comprovar si la clau existeix al mapa, simplement podríeu trucar a . find end map.contains("key") Mapes no ordenats sense fils Hi ha algunes implementacions de mapes hash segurs per a fils. Una opció és i de la . Els contenidors Boost proporcionen una API basada en visites que és molt diferent de l'API proporcionada per la biblioteca estàndard de C++. boost::concurrent_flat_set boost::concurrent_flat_map biblioteca Boost.Unordered Una altra opció és ( ). Folly intenta mantenir la seva API el més a prop possible dels contenidors no ordenats estàndard de C++. folly::ConcurrentHashMap github és una gran biblioteca de contenidors sense bloqueig que proporciona diverses implementacions de mapes hash sense bloqueig (per exemple, , , , , ). Aquesta biblioteca fa temps que no s'actualitza i no ofereix documentació detallada, però encara la comparteixo perquè els contenidors que ofereix són únics. Si el vostre cas d'ús implica una gran contenció en un mapa hash, proveu aquests diccionaris sense bloqueig que ofereix . libcds MichaelHashMap SkipListMap SkipListSet FeldmanHashMap FeldmanHashSet libcds Si l'eficiència no és una preocupació, podeu sincronitzar els accessos a mapes que no són segurs per a fils mitjançant mutex. Alternativament, podeu evitar completament els accessos concurrents, que sovint són més eficients que utilitzar contenidors segurs per a fils o afegir sincronització. Quin faig servir? Vegem els punts resumits que expliquen com escollir el contenidor més adequat. Si necessiteu associar una clau amb el valor, trieu un , en cas contrari, utilitzeu un . mapa conjunt Si és necessari mantenir les claus duplicades al mapa, utilitzeu contenidors. diversos Si necessiteu les garanties d'iteració i estabilitat de referència més estrictes possibles, utilitzeu contenidors basats en nodes , , o (com ara , , o ). i probablement serà la més eficient. std boost folly abseil std::unordered_map boost::unordered_map boost::unordered_node_map folly::F14NodeMap boost::unordered_node_... folly Si l'estabilitat de l'iterador i de la referència no és important (és a dir, no emmagatzemeu iteradors, referències o punters per a mapes/establir elements externament o no espereu que siguin vàlids després de modificar el mapa), trieu un contenidor pla (com ara com o ). boost::unordered_flat_map folly::F14FastMap Els contenidors plans utilitzen més memòria que els basats en nodes, especialment quan de la clau i/o el valor és gran. Si l'ús de la memòria és un problema, utilitzeu contenidors basats en nodes. sizeof Els contenidors F14 proporcionen una funcionalitat de prehashing per obtenir una eficiència addicional. Si cerqueu/afegiu/elimineu claus idèntiques diverses vegades, F14 us permetrà estalviar en el cost de la funció hash fent prehashing les claus. Tots els punts anteriors s'apliquen a l'ús de contenidors d'un sol fil (o a l'accés de lectura de diversos fils sense modificacions concurrents). Si calen modificacions de diversos fils, seleccioneu una de les opcions de seguretat de fils que s'indiquen més amunt. Poden mostrar un rendiment variable en el codi de producció real, així que considereu provar-los a la vostra aplicació i comparar-ne els resultats.
