Boost.Intrusivo y unordered_map

Question

Estoy buscando a utilizar un intrusivo unordered_map.Por alguna razón no es sólo un unordered_set en la biblioteca.También hay una intrusa hashtable pero no estoy seguro de que tiene el mismo functunality, también no tiene la misma interfaz.
Estoy equivocado y me he perdido el unordered_map enlace?
Si no estoy es que hay un tutorial que me ayude a implementar uno?

Answer 1

Es una pregunta interesante.Boost.Intrusivo no parece ofrecer ninguna interfaz de mapa, ordenadas o no.Tiene un montón de tipos de implementación que va a funcionar bien como mapas ordenado (rojo-negro árboles, árboles AVL, separación de los árboles) y desordenada (tablas hash).Pero no hay mapas y no puedo decirte por qué.

Usted tiene dos opciones como yo lo veo:

1. Sólo uso hashtable:la desordenada de los contenedores se implementan como tablas hash (y la única razón por la que no llama hash_map es para evitar colisiones de nombres con pre-existentes de las bibliotecas con ese nombre ya).Que va a trabajar si usted desea conseguir su trabajo hecho.
2. Si usted realmente desea implementar su propio, usted quiere tomar un vistazo a la descripción de la interfaz para el Impulso.Intrusivos del unordered_set.No he mirado en la aplicación, pero es casi seguro que un contenedor de uno o más de los tipos de árbol. std::set y std::map ambos son típicamente implementado como envolturas alrededor de un árbol rojo-negro (en todos los de la biblioteca estándar de las implementaciones que he mirado:GCC, MSVC, y Apache stdcxx).También tomar en cómo libstdc++ envuelve su árbol de aplicación en <map> y en <set>.Es muy repetitivo, muy tedioso, pero ambos tipos de aplazar casi todo el trabajo para el árbol.Algo análogo es casi seguro que ocurra con Boost.Intrusivos del unordered_set.Usted tendrá que mirar a las diferencias entre el mapa y el conjunto de interfaces, y usar esto como base para la modificación de unordered_set en unordered_map.

Me he hecho el último.Es un poco tedioso lado, y yo altamente recomiendo escribir pruebas unitarias (o el robo de los que vienen con libstdc++ o Impulso.Intrusiva).Pero es factible.Yo también recomiendo la lectura de los requisitos de los documentos para los conjuntos y los mapas, ya sea en SGI (conjunto, mapa) o por libstdc++

Actualización: Me di cuenta de por qué ellos no están haciendo mapas:el intrusiva de contenedores requieren que se incorpora la información de los nodos de la estructura de datos en el tipo de valor que se va a almacenar en él.Para los mapas que usted tendría que hacer esto para los valores y las llaves.No es que esto no es posible, pero la implementación estándar para un map utiliza el mismo tipo interno como el sets hacer.Pero los tipos internos sólo han uno value_type variable:para almacenar las claves y valores que copiar la clave y el valor a esa variable y la tienda que en los nodos.Para hacer eso con un intrusivo tipo (es decir,sin copiar) tendrías que modificar que la aplicación del tipo de ser incompatible con los conjuntos:se tiene que almacenar referencias a las claves y valores por separado.Así que para hacer esto usted también tendrá que modificar la aplicación que uso (probablemente hashtable).De nuevo, no imposible, pero la biblioteca de diseñadores probablemente tratando de evitar graves duplicación de código por lo que en ausencia de forma sencilla de implementar esto lo más probable es que haya decidido dejar de mapas a cabo.

¿Que sentido?

Answer 2

Ha pasado mucho tiempo desde que se hizo esta pregunta, pero creo que las personas que vienen aquí deberían estar interesadas en cómo usar un unordered_set como mapa. La solución es utilizar métodos de inserción avanzados : uno solo tiene que almacenar una clave y su valor en el mismo value_type, e insértelo usando insert_check y insert_commit .