Boost.Intrusive y unordered_map

Question

Estoy buscando utilizar un intrusive unordered_map. Por alguna razón, solo hay un conjunto no ordenado en la biblioteca. También hay una tabla hash intrusa pero no estoy seguro de que tenga la misma funcionalidad, tampoco tiene la misma interfaz.
¿Me equivoco y eché de menos el enlace desordenados?
Si no, ¿hay algún tutorial que me ayude a implementar uno?

Answer 1

Es una pregunta interesante. Boost.Intrusive no parece proporcionar ninguna interfaz de mapa, ordenada o desordenada. Tiene muchos tipos de implementación que funcionarán bien como los mapas ordenados (árboles rojo-negro, árboles AVL, árboles splay) y desordenado (hashtables). Pero no hay mapas y no podría decirte por qué.

tiene dos opciones como lo veo:

1. sólo tiene que utilizar hashtable: los contenedores no ordenadas se implementan como tablas hash (y la única razón por la que no están llamados hash_map es evitar conflictos de nombres con pre -existentes bibliotecas que ya usan ese nombre). Eso funcionará si quieres hacer tu trabajo.
2. Si realmente desea implementar uno propio, desea echar un vistazo a la descripción de la interfaz para unordered_set de Boost.Intrusive. No he estudiado la implementación, pero es casi seguro que se trata de uno o más de los tipos de árbol. std::set y std::map ambos se implementan como envoltorios alrededor de un árbol rojo-negro (en todas las implementaciones de bibliotecas estándar que he visto: GCC, MSVC y Apache's stdcxx). También vea cómo libstdC++ ajusta su implementación de árbol en <map> y en <set>. Es un montón de repetitivo, mucho tedioso, pero ambos tipos difieren casi todo el trabajo para el árbol. Algo similar está sucediendo con Boost.Intrusive unordered_set. Tendrá que observar las diferencias entre el mapa y establecer las interfaces, y usar eso como base para modificar unordered_set en unordered_map.

He hecho esto último. Es un poco tedioso, y recomiendo escribir pruebas unitarias para ello (o robar los que vienen con libstdC++ o Boost.Intrusive). Pero es factible. También recomiendo encarecidamente la lectura de los documentos de los requisitos para conjuntos y mapas, ya sea en la SGI (set, map) o para libstdc++

Actualización: me di cuenta de por qué no están haciendo mapas: los contenedores intrusivos requieren que incrusta el información de nodo para la estructura de datos en el tipo de valor que está almacenando en ella. Para los mapas, debe hacer esto para los valores y las claves. No es que esto no sea posible, pero la implementación estándar para un map usa el mismo tipo interno que el set s. Pero esos tipos internos solo tienen una variablevalue_type: para almacenar claves y valores, copian la clave y el valor en esa variable y la almacenan en los nodos. Para hacer eso con un tipo intrusivo (es decir, sin copiar), tendría que modificar ese tipo de implementación para que sea incompatible con los conjuntos: tiene que almacenar las referencias a las claves y los valores por separado. Entonces, para hacerlo también debe modificar la implementación que usa (probablemente hashtable). Una vez más, no es imposible, pero los diseñadores de la biblioteca probablemente intentan evitar la duplicación de código grave, por lo que, en ausencia de una forma sencilla de implementarlo, lo más probable es que hayan decidido dejar los mapas.

¿Tiene sentido?

Answer 2

Ha pasado mucho tiempo desde que se hizo esta pregunta, pero creo que las personas que vengan aquí deberían estar interesadas en cómo usar un unordered_set como mapa. La solución es usar advanced insertions methods: uno solo tiene que almacenar una clave y su valor en el mismo value_type, e insertarlo usando insert_check y insert_commit.