libreria - stl c++ functions

Diferencia entre std:: list<std:: pair> y std:: map en C++ stl

Question

¿Puedes decirme la diferencia entre std :: list <std :: pair> y std :: map? ¿Puedo usar encontrar el método en la lista también?

Gracias.

-- Aclaración

Pregunta editada para ser más clara.

Answer 1

std::pair

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

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

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

std::map

std::map es un contenedor asociativo con plantillas, asociando 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 no editada.

Las funciones std::map 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.

Por lo tanto, a primera vista, un mapa de pares y una lista de pares parecería 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 colocaste. Esto hace que la inserción O (log n) para el mapa, mientras que la inserción cruda dentro de una lista es una complejidad constante (la búsqueda de dónde insertarlo es otro problema).

Puede simular de alguna manera el comportamiento de un mapa utilizando 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 de elementos encadenados. Por lo tanto, 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 impulso 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 artículos ordenados por un conjunto de los mismos artículos pedidos, y esto aumentó la performance. El conjunto tiene la misma estructura de árbol interno que el mapa, supongo que el mismo impulso se aplicaría aquí )

Answer 2

(Editado después de la aclaración)

std::map está optimizado para una búsqueda rápida. Tiene su propio método de find que usa su estructura interna para proporcionar un buen rendimiento. En general, solo inspeccionará las claves de log(N) , donde N es el número de elementos en el mapa.

std::list<std::pair> es una lista vinculada simple, por lo que solo admite el cruce elemento por elemento. Podría usar el algoritmo std::find separado, o std::find_if con un predicado personalizado que solo examine al first miembro para que coincida mejor con la semántica de std::map::find , pero sería muy lento. De hecho, tendrá que ver cada par en la lista para cualquier búsqueda fallida, y verá la mitad en promedio para cualquier exitosa.

Answer 3

El mapa puede proporcionar el mejor tiempo de búsqueda en el rango de O (log n), mientras que la lista puede tener el tiempo de búsqueda de O (n).

Answer 4

Los mapas STL son matrices asociativas, generalmente implementadas como hashmaps dentro. Si quieres iterar sobre un mapa STL, devolverá un par de STL.

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
        map<string, int> myMap;
        myMap["myKey"] = 1337;

        map<string, int>::iterator myIterator = myMap.begin();

        pair<string, int> myPair = *myIterator;

        cout<<"the key /""<<myPair.first<<"/" maps to the value of "<<myPair.second<<endl;
        cout<<"the key /"myKey"/" maps to the value of "<<myMap["myKey"]<<endl;
        return 0;
}

Sugeriría buscar en Google y leer la referencia completa de la API STL ya que STL (con la excepción de almacenar booleanos en vectores y otras rarezas como esa) implementa una gran cantidad de funcionalidad de estructura de datos que desearía usar en cualquier programa sin reinventar la rueda.

Answer 5

std :: pair es solo para agrupar exactamente 2 objetos (por ejemplo, "coordenadas en una página" están compuestas de X e Y).

std :: map es un mapeo de un conjunto de objetos a otro.

No tiene sentido tratar de usar un método de búsqueda en un par, ya que de lo que se trata es de encontrar algo en una lista de dos cosas que conoces para el orden, incluso si ese método de búsqueda existió en una clase de par y no es así.

Sin embargo, PUEDE usar std :: pair como un valor de mapa si eso es lo que quiere.

Answer 6

std::map<X, Y> :

• es una estructura ordenada con respecto a las claves (es decir, cuando itera sobre ella, las claves siempre aumentarán).
• solo admite claves únicas ( X s)
• ofrece el método rápido find() ( O(log n) ) que encuentra el par clave-valor por clave
• ofrece un map[key] operador de indexación map[key] , que también es rápido

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

• es una secuencia simple de pares emparejados X e Y s. Permanecen en el orden en que lo pones.
• puede contener cualquier cantidad de duplicados
• encontrar una clave en particular en una list es O(N) (sin método especial)
• ofrece el método de splice .

Answer 7

std:pair tiene exactamente dos objetos. std:map contiene una colección de objetos emparejados.

No puede usar find () en el par, porque no hay nada que encontrar. El objeto que desea es pair.First o pair.Second

ACTUALIZACIÓN: suponiendo que haya definido la diferencia entre map<> y list<pair<> > : se debe implementar Map para una búsqueda rápida en el miembro de la key . list tiene solo una lista lineal simple. Buscar un elemento en una lista requiere ejecutar toda la lista. Sin embargo, std :: find () funcionará en ambos.