¿En qué situación utilizo un contenedor STL particular?

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

¿Cuál es la explicación? El código de ejemplo es mucho preferido.

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

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

http://linuxsoftware.co.nz/containerchoice.png

Creado por David Moore y licenciado por CC BY-SA 3.0

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

enter image description here

Respuesta simple: utilice el vector <> para todo a menos que tenga una razón real para hacerlo de otra manera.

Cuando encuentre un caso en el que esté pensando: “Gee, vector <> no funciona bien aquí debido a X”, vaya sobre la base de X.

Mira Effective 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 un vector es lo que desea. Es el reemplazo predeterminado para una matriz C, y funciona como uno, pero no se desborda. También puede establecer su tamaño de antemano con reserva ().

Si desea almacenar un número indeterminado de objetos, pero los agregará y los eliminará, es probable que desee una lista … porque puede eliminar un elemento sin mover 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 en un conjunto lo hará y los clasificará también 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 / list como su valor en el mapa, o usar un multimap.

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, es posible que quiere 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.

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

vector : Diseño compacto con poca o ninguna carga de memoria por objeto contenido. Eficiente para iterar Agregar, insertar y borrar puede ser costoso, particularmente para objetos complejos. Barato para encontrar un objeto contenido por índice, por ejemplo myVector [10]. Úselo donde habría utilizado una matriz en C. Bueno, donde tiene muchos objetos simples (por ejemplo, int). No olvides usar reserve() antes de agregar muchos objetos al contenedor.

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

set (y multiset ): carga de memoria significativa por objeto contenido. Úselo donde necesite averiguar rápidamente si ese contenedor contiene un objeto determinado o combine contenedores eficientemente.

map (y multimap ): carga de memoria significativa por objeto contenido. Úselo donde desee almacenar pares clave-valor y busque valores por clave rápidamente.

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

Un punto importante solo mencionado brevemente hasta ahora, es que si requiere memoria contigua (como una matriz C), entonces solo puede usar vector , array o string .

Use array si se conoce el tamaño en tiempo de comstackción.

Use string si solo necesita trabajar con tipos de caracteres y necesita una cadena, no solo un contenedor de propósito general.

Use el vector en todos los demás casos (el vector debe ser la opción predeterminada de contenedor en la mayoría de los casos de todos modos).

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

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

 class CollectionOfFoo { Collection 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.

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

Cada estructura de datos proporciona algunas operaciones, que pueden ser de complejidad de tiempo variable:

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

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

Simple, ¿verdad? (-:

Me expandí en el fantástico diagtwig 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 las bases. C ++ Contenedor de contenedores