¿En qué escenario uso un contenedor STL particular?

185

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.

Daniel Sloof
fuente
¿te refieres a mapa, vectot, set, etc.?
Thomas Tempelmann el
Incluso mirando este diagrama, no puedo decir cuál sería el mejor para usar en mi quastion stackoverflow.com/questions/9329011/…
sergiol
2
@sbi: Eliminando la etiqueta de Preguntas Frecuentes de C ++ de esta y agregándola a la más reciente y C ++ 11 inclusive ¿Cómo puedo seleccionar eficientemente un contenedor de biblioteca Estándar en C ++ 11?
Alok Save

Respuestas:

338

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:

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

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

zdan
fuente
14
Este diagrama de flujo es dorado, desearía tener algo así en c #
Bruno
2
Enlace actualizado: C ++ Containers Cheat Sheet .
Bill Door
3
El punto de partida debe ser vectormás bien que vacío. stackoverflow.com/questions/10699265/…
eonil
55
Ahora tiene unordered_mapy unordered_set(y sus múltiples variantes) que no están en el diagrama de flujo pero son buenas opciones cuando no le importa el orden pero necesita encontrar elementos por clave. Su búsqueda suele ser O (1) en lugar de O (log n).
Aidiakapi
2
@ shuttle87 no solo ese tamaño nunca variará, sino más importante aún, ese tamaño se determina en el momento de la compilación y nunca variará.
YoungJohn
188

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:

ingrese la descripción de la imagen aquí

Mikael Persson
fuente
44
¿Puedes hacer que el original esté disponible? Es un excelente cuadro. ¿Quizás pegarse en un blog o GitHub?
kevinarpe
1
Este es un excelente cuadro. Sin embargo, ¿alguien puede explicarme qué se entiende por "posiciones persistentes"?
IDDQD
3
@STALKER Las posiciones persistentes significan que si tiene un puntero o iterador a un elemento en el contenedor, ese puntero o iterador seguirá siendo válido (y apuntando al mismo elemento) independientemente de lo que agregue o elimine del contenedor (siempre que no es el elemento en cuestión).
Mikael Persson
1
Este es realmente un gran gráfico, sin embargo, creo que vector (sorted)es un poco inconsistente con el resto. No es un tipo diferente de contenedor, es el mismo std::vectorpero está ordenado. Aún más importante, no veo por qué uno no podría usar una std::setiteración ordenada si ese es el comportamiento estándar de iterar a través de un conjunto. Claro, si la respuesta es hablar sobre el acceso ordenado a los valores del contenedor [], entonces está bien, solo puede hacerlo con un punteado std::vector. Pero en cualquier caso, la decisión debe tomarse justo después de la pregunta "se necesita orden"
RA
1
@ user2019840 Quería restringir el gráfico a contenedores estándar. Lo que debería aparecer en lugar de "vector ordenado" es "flat_set" (de Boost.Container ), o equivalente (cada biblioteca principal o base de código tiene un equivalente de flat_set, AFAIK). Pero estos no son estándar, y una omisión flagrante de la STL. Y la razón por la que no desea iterar a través de std :: set o std :: map (al menos no con frecuencia) es que es muy ineficiente hacerlo .
Mikael Persson
41

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.

David Thornley
fuente
1
Sin embargo ... tenga cuidado de no eliminar / insertar elementos al iterar ... use const_iterator en la medida de lo posible para evitar esto ...
vrdhn
11
Hmm ... Creo que la gente está usando demasiado el vector. La razón es que el caso "no funciona" no sucederá fácilmente, por lo que las personas se adhieren al contenedor más utilizado y lo usan mal para almacenar listas, colas, ... En mi opinión, que coincide con el diagrama de flujo, uno debe elegir el contenedor en función del uso previsto en lugar de aplicar el "uno parece encajar en todos".
Negro
13
@Black Point es que el vector suele ser más rápido incluso en operaciones que, en teoría, deberían funcionar más lentamente.
Bartek Banachewicz
1
@Vardhan std::remove_ifes casi siempre superior al enfoque de "eliminar durante la iteración".
fredoverflow
1
Algunos puntos de referencia realmente ayudarían a que esta discusión sea menos subjetiva.
Felix D.
11

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.

Mark Krenitsky
fuente
He escuchado un par de anécdotas que sugieren que Microsoft hash_mapno es una muy buena implementación. Espero que les haya ido mejor unordered_map.
Mark Ransom
3
De listas: "no se puede acceder secuencialmente a un elemento". - Creo que quiere decir que no puede acceder aleatoriamente o indexarse ​​directamente a un elemento ...
Tony Delroy
^ Sí, porque el acceso secuencial es precisamente lo que listhace. Un error bastante evidente allí.
underscore_d
7

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: ingrese la descripción de la imagen aquí

Más información proporcionada en este enlace .

Ebrahim
fuente
5

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.

Jonathan Wakely
fuente
3

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.

Ofertas
fuente
"Sobrecarga de memoria pequeña por objeto contenido" no es cierto para la lista. std :: list se implementa como una lista doblemente vinculada y, por lo tanto, mantiene 2 punteros por objeto almacenado que no se debe descuidar.
Hanna Khalil
Seguiría contando dos punteros por objeto almacenado como "pequeño".
Ofertas
¿comparado con que? std :: forward_list es un contenedor que se sugirió principalmente para tener menos metadatos almacenados por objeto (solo un puntero). Mientras que std :: vector contiene 0 metadatos por objeto. Así que 2 punteros no son negociables en comparación con otros contenedores
Hanna Khalil
Todo depende del tamaño de tus objetos. Ya he dicho que el vector tiene un "diseño compacto con poca o ninguna sobrecarga de memoria por objeto contenido". Todavía diría que la lista tiene una pequeña sobrecarga de memoria en comparación con el conjunto y el mapa, y una sobrecarga de memoria ligeramente mayor que el vector. ¡No estoy realmente seguro de qué punto estás tratando de hacer TBH!
Ofertas del
Todos los contenedores basados ​​en modo tienden a tener una sobrecarga significativa debido a la asignación dinámica, que rara vez es gratis. A menos que, por supuesto, esté utilizando un asignador personalizado.
MikeMB
2

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 (-:

vrdhn
fuente
55
¿No es por eso que usamos iteradores?
Platinum Azure
@PlatinumAzure Incluso los iteradores deben ser miembros typedef .. Si cambia el tipo de contenedor también tiene que ir y cambiar todas las definiciones de iterador ... ¡aunque esto se solucionó en c ++ 1x!
vrdhn
44
Para los curiosos, esta es la solución en C ++ 11: auto myIterator = whateverCollection.begin(); // <-- immune to changes of container type
Black
1
¿ typedef Collection<Foo*> CollectionOfFoo;Sería suficiente?
Craig McQueen
55
Es bastante improbable que pueda cambiar de opinión más tarde y simplemente delegar en un contenedor diferente:
tenga
1

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 ++

John DiFini
fuente
1

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 .

CS Pei
fuente