usando boost multi_index_container para conservar la orden de inserción

Inicialmente comencé usando std::multimap para almacenar muchos valores con la misma clave, pero luego descubrí que no conserva el orden de inserción entre valores con la misma clave. This answer afirma que se puede hacer con boost::multi_index::multi_index_container, pero no da ningún ejemplo. Mirando a través de los documentos, no hay ejemplos de ese uso, y no puedo entender cómo se supone que debes usar esta cosa. He llegado a esperar documentación deficiente de las bibliotecas de refuerzo menos utilizadas, pero esto se lleva la palma. ¿Alguien puede indicarme un tutorial o ejemplo que demuestre que se usó de la manera que yo quiero, o tal vez incluso darme un ejemplo?usando boost multi_index_container para conservar la orden de inserción

Fuente

2010-07-13 rmeador

¿Es necesario que sea un mapa múltiple? – doublep

sí, lo hago. Tengo múltiples valores con la misma clave. – rmeador

Puede lograr esto utilizando boost::multi_index con dos índices: ordered_non_unique (que permite valores con la misma clave) y random_access (que mantendrá el orden de inserción).

struct some { 
    long key; 
    int data; 
    int more_data; 
    // etc. 
}; 

typedef multi_index_container< 
    some, 
    indexed_by<  
    random_access<>, // keep insertion order 
    ordered_non_unique< member<some, long, &some::key> > 
    > 
> some_mic_t;

Fuente

2010-07-13 20:03:37

Compatible con esta respuesta, a partir de la documentación de impulso: ** Los índices de acceso aleatorio son secuencias de orden libre con acceso posicional de tiempo constante e iteradores de acceso aleatorio. Los elementos en un índice de acceso aleatorio se clasifican por defecto de acuerdo con su orden de inserción ** –

¿Qué tal un

map<int, vector<string> >

map<int, list<string> >

@Kirill: Buena respuesta. Sospecho que el acceso aleatorio de Boost puede ser bastante lento, ya que obligará a todas las cadenas de todas las claves a mantenerse en una sola estructura contigua. Mientras que el que pregunta simplemente quiere conservar el orden dentro del conjunto de valores mapeados de cada tecla.

Fuente

2010-07-14 00:01:16

'random_access' es un índice adicional. Usted usa 'ordered_non_unique' para la búsqueda, luego' random_access' para iterar a través del rango resultante. No es lento –

(He usado muchos índices múltiples, pero no random_index, así que no estoy seguro de nada de esto) @Kirill: Dos puntos: @rmeador quiere poder "conservar el orden de inserción entre los valores con la misma llave ". Dada una sola clave, ¿cómo se puede usar todo el índice aleatorio para lograr esto rápidamente? Sospecho que la estructura que sugerí puede ser la única forma de hacer esto. y Quiero decir que la inserción de nuevos elementos puede ser más lenta de lo necesario, ya que todo el índice aleatorio está potencialmente desactualizado. –

@Kirill: para aclarar, una vez que ordered_non_unique ha identificado un rango de valores (sin clasificar) que corresponden a una sola clave, ¿cómo se usa (rápidamente) el acceso aleatorio para ordenar ese conjunto de valores? Ese conjunto de valores puede distribuirse uniformemente a lo largo de un gran índice de acceso aleatorio. La iteración a través del rango random_access no mantendrá las claves en orden. –

usando boost multi_index_container para conservar la orden de inserción

Respuesta

Cuestiones relacionadas