¿Cuál es la diferencia entre std :: list y std :: map en C ++ STL?

Solución:

std::map<X, Y>:

• es una estructura ordenada con respecto a las claves (es decir, cuando la iteras, las claves siempre aumentarán).
• admite claves únicas (Xs) solo
• ofertas rapido find() métodoO(log n)) que encuentra el par clave-valor por clave
• ofrece un operador de indexación map[key], que también es rápido

std::list<std::pair<X, Y> >:

• es una secuencia simple de pares Xarena Ys. Permanecen en el orden en que los colocaste.
• puede contener cualquier número de duplicados
• encontrar una clave en particular en un list es O(N) (sin método especial)
• ofrece el splice método.

std::pair

std::pair es una estructura de tupla con plantilla limitada a 2 elementos, llamados primero y segundo:

std::pair<int, std::string> myPair ;
myPair.first = 42 ;
myPair.second = "Hello World" ;

std::pair se utiliza como un “contenedor genérico” por el STL (y otro código) para agregar dos valores al mismo tiempo sin tener que redefinir otro struct.

std::map

std::map es un contenedor asociativo con plantilla, que asocia claves y valores. El ejemplo más fácil (pero no más eficiente) es:

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;
// ...
std::string strText ;  // strText is ""
strText = myMap[111] ; // strText is now "Hello World"
strText = myMap[42] ;  // strText is now "Fourty Two"
strText = myMap[23] ;  // strText is now "" (and myMap has
                       // a new value "" for key 23)

std::pair y std::map

Nota: Esta fue la respuesta a la pregunta original sin editar.

los std::map las funciones necesitan devolver iteradores a las claves y valores al mismo tiempo para seguir siendo eficientes … Entonces, la solución obvia es devolver iteradores a pares:

std::map<int, std::string> myMap ;
myMap[42] = "Fourty Two" ;
myMap[111] = "Hello World" ;

myMap.insert(std::make_pair(23, "Bye")) ;

std::map<int, std::string>::iterator it = myMap.find(42) ;
std::pair<int, std::string> keyvalue = *it ;    // We assume 42 does
                                                // exist in the map
int key = keyvalue.first ;
int value = keyvalue.second ;

std::list<std::pair<A,B> > y std::map<A,B>

Nota: Editado después de la edición de la pregunta.

Así, a primera vista, un mapa de pares y una lista de pares parecerían lo mismo. Pero este no es el caso:

El mapa está inherentemente ordenado por el funtor proporcionado, mientras que la lista mantendrá los pares de [A,B] justo donde los pones. Esto hace que la inserción sea O (log n) para el mapa, mientras que la inserción sin procesar dentro de una lista es una complejidad constante (buscar dónde insertarla es otro problema).

Puede simular un poco el comportamiento de un mapa usando una lista de pares, pero tenga en cuenta que el mapa generalmente se implementa como un árbol de elementos, mientras que la lista es una lista encadenada de elementos. Por lo tanto, un algoritmo como la dicotomía funcionará mucho más rápido en un mapa que en una lista.

Por lo tanto, encontrar un elemento en un mapa es O (log n), mientras que en una lista desordenada es O (n). Y si la lista está ordenada y desea utilizar la dicotomía, no obtendrá el aumento de rendimiento esperado, ya que el recorrido de la lista de elementos se realiza elemento por elemento de todos modos.

(En un proyecto en el que trabajé hace un año, reemplazamos una lista de elementos ordenados por un conjunto de los mismos elementos ordenados y mejoró el rendimiento. El conjunto tiene la misma estructura de árbol interna que el mapa, supongo que se aplicaría el mismo impulso aquí)

(Editado después de una aclaración)

std::map está optimizado para búsquedas rápidas. Tiene lo suyo find método que utiliza su estructura interna para proporcionar un buen rendimiento. En general, solo inspeccionará log(N) claves, donde N es el número de elementos en el mapa.

std::list<std::pair> es una lista enlazada simple, por lo que solo admite el recorrido elemento por elemento. usted podría usar el separado std::find algoritmo, o std::find_if con un predicado personalizado que solo examina el first miembro para que coincida mejor con la semántica de std::map::find, pero eso sería muy lento. De hecho, tendrá que mirar cada emparejar en la lista para cualquier búsqueda fallida, y buscará la mitad en promedio para cualquier búsqueda exitosa.

---

---

Utiliza Nuestro Buscador