Boost.Intrusive e unordered_map

Question

Sto cercando di usare una intrusive unordered_map. Per qualche motivo c'è solo un unordered_set nella libreria. Esiste anche un hashtable invadente, ma non sono sicuro che abbia la stessa funzionalità, inoltre non ha la stessa interfaccia.
Sbaglio e ho perso il link unordered_map?
Se non lo sono, c'è un tutorial che mi aiuterà a implementarne uno?

Answer 1

È una domanda interessante. Boost.Intrusive non sembra fornire alcuna interfaccia della mappa, ordinata o non ordinata. Ha molti tipi di implementazione che funzioneranno bene sia come mappe ordinate (alberi rosso-neri, alberi AVL, alberi splay) che non ordinate (hashtabili). Ma niente mappe e non saprei dirti perché.

Hai due possibilità per come la vedo io:

1. Basta usare hashtable: i contenitori non ordinati sono implementati come hashtable (e l'unica ragione per cui non sono chiamati hash_map è evitare collisioni di nomi con librerie preesistenti che usano già quel nome ). Funzionerà se vuoi fare il tuo lavoro.
2. Se vuoi davvero implementare il tuo, vuoi dare un'occhiata alla descrizione dell'interfaccia per Boost.Intrusive < unordered_set . Non ho esaminato l'implementazione ma è quasi certamente un wrapper attorno a uno o più tipi di alberi. std::set e std::map sono entrambi tipicamente implementati come wrapper attorno a un albero rosso-nero (in tutte le implementazioni di librerie standard che ho visto: GCC, MSVC e Apache stdcxx). Prendi anche come libstdc ++ avvolge la loro implementazione dell'albero in <map> e in <set>. È un sacco di scaldavivande, molto noioso ma entrambi i tipi rimandano quasi tutto il lavoro all'albero. Qualcosa di analogo sta quasi certamente accadendo con Boost.Intrusive unordered_set. Dovrai esaminare le differenze tra la mappa e impostare le interfacce e utilizzarle come base per modificare unordered_map in map.

Ho fatto quest'ultimo. È un po 'noioso, e consiglio vivamente di scrivere test unit (o rubare quelli forniti con libstdc ++ o Boost.Intrusive). Ma è fattibile. Consiglio vivamente di leggere i documenti sui requisiti per set e mappe, sia su SGI ( set , mappa ) o per libstdc ++

Aggiornamento: ho capito perché non stanno realizzando mappe: i contenitori intrusivi richiedono che tu incorpori le informazioni sul nodo per la struttura dei dati nel tipo di valore che stai memorizzando in esso. Per le mappe dovresti farlo sia per i valori che per le chiavi . Non è che ciò non sia possibile, ma l'implementazione standard per un set usa lo stesso tipo interno di value_type. Ma quei tipi interni hanno solo una una <=> variabile: per memorizzare chiavi e valori copiano la chiave e il valore in quella variabile e la memorizzano nei nodi. Per farlo con un tipo invadente (cioè senza copiare) dovresti modificare quel tipo di implementazione per renderlo incompatibile con gli insiemi: deve memorizzare i riferimenti alle chiavi e ai valori separatamente . Quindi per farlo devi anche modificare l'implementazione che usi (probabilmente <=>). Ancora una volta non impossibile, ma i progettisti delle biblioteche stanno probabilmente cercando di evitare serie duplicazioni di codice, quindi in assenza di un modo semplice per implementarlo hanno probabilmente deciso di lasciare le mappe fuori.

Ha senso?

Answer 2

È passato molto tempo da quando questa domanda è stata posta, ma penso che le persone che vengono qui dovrebbero essere interessate a come utilizzare un unordered_set come mappa. La soluzione è utilizzare metodi di inserzione avanzati : è sufficiente memorizzare una chiave e il suo valore nella stessa value_type e inserirla utilizzando insert_check e insert_commit .