C++ std :: pregunta del mapa sobre la orden del iterador

Question

Soy un novato en C++ tratando de usar un mapa para poder obtener búsquedas de tiempo constante para el método find().

El problema es que cuando uso un iterador para revisar los elementos en el mapa, los elementos no aparecen en el mismo orden en que se colocaron en el mapa.

Sin mantener otra estructura de datos, ¿hay alguna manera de lograr iteraciones en el orden manteniendo la capacidad de búsqueda de tiempo constante?

Háganme saber.

Gracias, JBU

Edit: Gracias por avisarme mapa :: find() no es constante de tiempo.

Answer 1

Los artículos se solicitan por operator< (de forma predeterminada) cuando se aplican a la tecla.

PS. std :: map no garantiza la búsqueda de tiempo constante.
Garantiza la complejidad máxima de O (ln (n))

Answer 2

En primer lugar, std::map no es la búsqueda de tiempo constante. Es O (log n). Solo pensé que debería aclararlo.

De todos modos, debe especificar su propia función de comparación si desea utilizar un pedido diferente. No hay una función de comparación incorporada que pueda ordenar por tiempo de inserción, pero, si su objeto contiene un campo de marca de tiempo, puede acordar establecer la marca de tiempo en el momento de la inserción y usar una comparación de fecha y hora.

Answer 3

En primer lugar, std::map garantiza O (log n) tiempo de búsqueda. Usted podría estar pensando en std::tr1::unordered_map. Pero eso por definiciones sacrifica cualquier orden para obtener la búsqueda de tiempo constante.

Tendría que dedicarle un tiempo, pero creo que puede bash boost::multi_index_container para hacer lo que quiera.

Answer 4

Sin tener que mantener otra estructura de datos, ¿hay alguna forma de lograr iteraciones en el orden manteniendo la capacidad de búsqueda de tiempo constante?

No, eso no es posible. Con el fin de obtener una búsqueda eficiente, el contenedor deberá ordenar los contenidos de una manera que permita una búsqueda eficiente. Para std :: map, ese será algún tipo de orden ordenado; para std :: unordered_map, que será un orden basado en el hash de la clave.

En cualquier caso, el orden será diferente al orden en que se agregaron.

Answer 5

El mapa no está destinado a colocar elementos en algún orden - use el vector para eso.

Si quieres encontrar algo en el mapa que debe "buscar" de la clave utilizando [el operador

Si necesita tanto: iteración y Search by ver esto topic

Answer 6

voy para realmente ... ir hacia atrás.

Si desea conservar el orden en que se insertan los elementos, o en general para controlar el pedido, inicie una secuencia que se va a controlar:

• std::vector (sí, hay otros, pero por defecto utilizar éste)

Usted puede utilizar el algoritmo std::find (de <algorithm>) para buscar un valor particular en el vector: std::find(vec.begin(), vec.end(), value);.

Oh sí, tiene complejidad lineal O(N), pero para colecciones pequeñas no debería importar.

De lo contrario, puede comenzar a buscar en Boost.MultiIndex como ya se ha sugerido, pero para un principiante probablemente le dificulte un poco.

Por lo tanto, omita el problema de la complejidad por el momento, y proponga algo que funcione. Te preocuparás por la velocidad cuando estés más familiarizado con el idioma.

Answer 7

Sí, puede crear dicha estructura de datos, pero no utilizando la biblioteca estándar ... el motivo es que los contenedores estándar pueden anidarse pero no mezclarse.

No hay ningún problema implementando por ejemplo una estructura de datos de mapa donde todos los nodos también están en una lista doblemente enlazada por orden de inserción, o por ejemplo un mapa donde todos los nodos están en una matriz. Me parece que una de estas estructuras podría ser lo que estás buscando (dependiendo de qué operación prefieras ser rápida), pero ninguna de ellas es trivial de construir usando contenedores estándar porque cada contenedor estándar (vector, list, set, ...) quiere ser la única forma de acceder a los elementos contenidos.

Por ejemplo, me pareció útil en muchos casos tener nodos que estaban al mismo tiempo en varias listas doblemente vinculadas, pero no se puede hacer eso usando std::list.

Answer 8

¿Qué tal el uso de un vector para las llaves en el orden original y un map para el acceso rápido a los datos?

Algo como esto:

vector<string> keys; 
map<string, Data*> values; 

// obtaining values 
... 
keys.push_back("key-01"); 
values["key-01"] = new Data(...); 
keys.push_back("key-02"); 
values["key-02"] = new Data(...); 
... 

// iterating over values in original order 
vector<string>::const_iterator it; 
for (it = keys.begin(); it != keys.end(); it++) { 
    Data* value = values[*it]; 
}