Cómo convertir un std :: list ordenado de std :: pair a un std :: map

Question

Tengo un std::list< std::pair<std::string,double> >, que sé que está ordenado según el std::string element.

Dado que me gustaría hacer un montón de std::find_if basado en el elemento std::string, creo que un std::map<string,double,MyOwnBinaryPredicate> con lower_bound y upper_bound sería más adecuada.

El hecho es que quiero insert elementos en el std::map de una manera eficiente. Así que quiero usar un iterador adicional para hacer que el insert sea más rápido.

Creo que la manera más fácil sería utilizar un const_reverse_iterator que pasar por el std::list y utilizar el begin() del std::map.

¿Lo harías de esta manera, o es una mala idea?

Gracias!

Answer 1

Si ya tiene una lista ordenada, que se clasifica de acuerdo con el predicado Predicate, sólo puede hacer lo siguiente:

std::list< std::pair<std::string, double> > sorted_list; 
std::map<string, double, Predicate> map(sorted_list.begin(), sorted_list.end()); 

El constructor map ha complejidad del tiempo lineal si la lista está ya clasificado, O (n * log n) de lo contrario. Luego puede trabajar directamente con el mapa como lo haría con cualquier otro.

Si más adelante desea que los resultados de vuelta en su lista usted podría hacer lo contrario:

sorted_list.assign(map.begin(), map.end());

Answer 2

Puede utilizar std :: copia y std :: insertor:

std::copy(the_list.begin(),the_list.end(),std::inserter(the_map,the_map.begin())); 

porque el iterador para un par lista <> tiene un tipo de valor compatibles para mapear < X, Y> 's iteradores.

Answer 3

Me gustaría simplemente iterar en la lista e insertar cada par en un mapa o utilizar el método ordenado que Luther Blissett ha descrito.
El hecho de que no obtenga lo que intenta hacer significa que dará como resultado un código ilegible o que está muy lejos.
¿Por qué lo haces de esta manera?
¿Puede cambiar el código para devolverle un mapa en lugar de una lista en primer lugar?