¿En qué escenario uso un contenedor STL particular?

He estado leyendo sobre contenedores STL en mi libro sobre C ++, específicamente la sección sobre STL y sus contenedores. Ahora entiendo que todos y cada uno de ellos tienen sus propias propiedades específicas, y estoy cerca de memorizarlos ... Pero lo que aún no entiendo es en qué escenario se usa cada uno de ellos.

¿Cuál es la explicación? Se prefiere mucho el código de ejemplo.

Esta hoja de trucos proporciona un resumen bastante bueno de los diferentes contenedores.

Vea el diagrama de flujo en la parte inferior como una guía para usar en diferentes escenarios de uso:

_{Creado por David Moore y con licencia CC BY-SA 3.0}

Aquí hay un diagrama de flujo inspirado en la versión de David Moore (ver arriba) que creé, que está actualizada (principalmente) con el nuevo estándar (C ++ 11). Esta es solo mi opinión personal al respecto, no es indiscutible, pero pensé que podría ser valioso para esta discusión:

Respuesta simple: usar std::vectorpara todo a menos que tenga una razón real para hacer lo contrario.

Cuando encuentre un caso en el que esté pensando: "Caramba, std::vectorno funciona bien por X", vaya sobre la base de X.

Mira Eficaz STL por Scott Meyers. Es bueno para explicar cómo usar el STL.

Si desea almacenar un número determinado / indeterminado de objetos y nunca va a eliminar ninguno, entonces lo que desea es un vector. Es el reemplazo predeterminado para una matriz C, y funciona como uno, pero no se desborda. Puede establecer su tamaño de antemano también con reserve ().

Si desea almacenar un número indeterminado de objetos, pero los agregará y eliminará, entonces probablemente desee una lista ... porque puede eliminar un elemento sin mover ninguno de los siguientes elementos, a diferencia del vector. Sin embargo, requiere más memoria que un vector, y no puede acceder secuencialmente a un elemento.

Si desea tomar un montón de elementos y encontrar solo los valores únicos de esos elementos, leerlos todos en un conjunto lo hará, y también los ordenará por usted.

Si tiene muchos pares clave-valor y desea ordenarlos por clave, entonces un mapa es útil ... pero solo tendrá un valor por clave. Si necesita más de un valor por clave, podría tener un vector / lista como su valor en el mapa, o usar un mapa múltiple.

No está en el STL, pero está en la actualización TR1 del STL: si tiene muchos pares clave-valor que va a buscar por clave, y no le importa su orden, puede desea usar un hash, que es tr1 :: unordered_map. Lo he usado con Visual C ++ 7.1, donde se llamaba stdext :: hash_map. Tiene una búsqueda de O (1) en lugar de una búsqueda de O (log n) para el mapa.

Rediseñé el diagrama de flujo para tener 3 propiedades:

1. Creo que los contenedores STL se dividen en 2 clases principales. Los contenedores básicos y aquellos que aprovechan los contenedores básicos para implementar una política.
2. Al principio, el diagrama de flujo debe dividir el proceso de decisión en las situaciones principales que debemos decidir y luego elaborar cada caso.
3. Algunos contenedores extendidos tienen la posibilidad de elegir diferentes contenedores básicos como su contenedor interno. El diagrama de flujo debe considerar las situaciones en las que se puede usar cada uno de los contenedores básicos.

El diagrama de flujo:

Más información proporcionada en este enlace .

Un punto importante sólo brevemente mencionado hasta ahora, es que si necesita memoria contigua (como una matriz C da), a continuación, sólo se puede utilizar vector, arrayo string.

Úselo arraysi el tamaño se conoce en tiempo de compilación.

Úselo stringsi solo necesita trabajar con tipos de caracteres y necesita una cadena, no solo un contenedor de uso general.

Uso vectoren todos los demás casos (de vectortodos modos, debería ser la opción predeterminada de contenedor).

Con estos tres puede usar la data()función miembro para obtener un puntero al primer elemento del contenedor.

Todo depende de lo que quieras almacenar y de lo que quieras hacer con el contenedor. Aquí hay algunos ejemplos (no muy exhaustivos) para las clases de contenedor que más uso:

vector: Diseño compacto con poca o ninguna sobrecarga de memoria por objeto contenido. Eficiente para repetir. Agregar, insertar y borrar puede ser costoso, particularmente para objetos complejos. Barato para encontrar un objeto contenido por índice, por ejemplo, myVector [10]. Use donde hubiera usado una matriz en C. Bueno donde tenga muchos objetos simples (por ejemplo, int). No olvide usar reserve()antes de agregar muchos objetos al contenedor.

list: Pequeña sobrecarga de memoria por objeto contenido. Eficiente para repetir. Agregar, insertar y borrar son baratos. Use donde hubiera usado una lista vinculada en C.

set(y multiset): Sobrecarga de memoria significativa por objeto contenido. Use donde necesite averiguar rápidamente si ese contenedor contiene un objeto determinado, o combine contenedores de manera eficiente.

map(y multimap): Sobrecarga de memoria significativa por objeto contenido. Use dónde desea almacenar pares clave-valor y busque valores por clave rápidamente.

El diagrama de flujo en la hoja de trucos sugerido por zdan proporciona una guía más exhaustiva.

Una de las lecciones que he aprendido es: trate de envolverlo en una clase, ya que cambiar el tipo de contenedor un buen día puede generar grandes sorpresas.

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

No cuesta mucho por adelantado, y ahorra tiempo en la depuración cuando desea interrumpir cada vez que alguien realiza la operación x en esta estructura.

Llegando a seleccionar la estructura de datos perfecta para un trabajo:

Cada estructura de datos proporciona algunas operaciones, que pueden variar en la complejidad del tiempo:

O (1), O (lg N), O (N), etc.

Esencialmente, tiene que adivinar qué operaciones se realizarán más y utilizar una estructura de datos que tenga esa operación como O (1).

Simple, no lo es (-:

Me expandí en el fantástico diagrama de flujo de Mikael Persson . Agregué algunas categorías de contenedor, el contenedor de matriz y algunas notas. Si desea su propia copia, aquí está el dibujo de Google. ¡Gracias Mikael por hacer el trabajo preliminar! Selector de contenedores C ++

Respondí esto en otra pregunta que está marcada como dup de esta. Pero creo que es bueno referirse a algunos buenos artículos sobre la decisión de elegir un contenedor estándar.

Como @David Thornley respondió, std :: vector es el camino a seguir si no hay otras necesidades especiales. Este es el consejo dado por el creador de C ++, Bjarne Stroustrup en un blog de 2014.

Aquí está el enlace para el artículo https://isocpp.org/blog/2014/06/stroustrup-lists

y cita de ese,

Y sí, mi recomendación es usar std :: vector de forma predeterminada.

En los comentarios, el usuario @NathanOliver también proporciona otro buen blog, que tiene medidas más concretas. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .