¿Cómo puedo seleccionar de manera eficiente un contenedor de biblioteca estándar en C++ 11?

Hay una imagen bien conocida (hoja de trucos) llamada “Elección de contenedor C ++”. Es un diagrama de flujo para elegir el mejor contenedor para el uso deseado.

¿Alguien sabe si ya hay una versión C++ 11?

Este es el anterior:

No que yo sepa, sin embargo, se puede hacer textualmente, supongo. Además, el gráfico está ligeramente desviado, porque list no es tan buen contenedor en general, y tampoco lo es forward_list. Ambas listas son contenedores muy especializados para aplicaciones de nicho.

Para construir un gráfico de este tipo, solo necesita dos pautas simples:

• Elija primero la semántica
• Cuando hay varias opciones disponibles, elija la más simple

Preocuparse por el rendimiento suele ser inútil al principio. Las grandes consideraciones de O solo se activan realmente cuando comienza a manejar unos pocos miles (o más) de artículos.

Hay dos grandes categorías de contenedores:

• De asociación contenedores: tienen un find operación
• Secuencia sencilla contenedores

y luego puedes construir varios adaptadores encima de ellos: stack, queue, priority_queue. Dejaré los adaptadores aquí, son lo suficientemente especializados para ser reconocibles.

Pregunta 1: De asociación ?

• Si necesita buscar fácilmente por una clave, entonces necesita un contenedor asociativo
• Si necesita ordenar los elementos, entonces necesita un contenedor asociativo ordenado
• De lo contrario, salta a la pregunta 2.

Pregunta 1.1: Ordenado ?

• Si no necesita un pedido específico, utilice un unordered_ contenedor, de lo contrario, use su contraparte ordenada tradicional.

Pregunta 1.2: Clave separada ?

• Si la clave está separada del valor, utilice un mapde lo contrario utilice un set

Pregunta 1.3: Duplicados ?

• Si desea conservar duplicados, utilice un multide lo contrario no lo hagas.

Ejemplo:

Supongamos que tengo varias personas con una identificación única asociada a ellas y me gustaría recuperar los datos de una persona de su identificación de la manera más simple posible.

1. quiero un find función, por lo tanto, un contenedor asociativo

1.1. No podría importarme menos el orden, por lo tanto, un unordered_ envase

1.2. Mi clave (ID) está separada del valor con el que está asociada, por lo tanto, un map

1.3. El ID es único, por lo que no debería aparecer ningún duplicado.

La respuesta final es: std::unordered_map<ID, PersonData>.

Pregunta 2: Memoria estable ?

• Si los elementos deben ser estables en la memoria (es decir, no deben moverse cuando se modifica el contenedor en sí), entonces use algunos list
• De lo contrario, pase a la pregunta 3.

Pregunta 2.1: Cual ?

• conformarse con un list; a forward_list solo es útil para una huella de memoria menor.

Pregunta 3: Tamaño dinámico ?

• Si el contenedor tiene un tamaño conocido (en el momento de la compilación), y este tamaño no se modificará durante el transcurso del programa, y los elementos son construibles por defecto o puede proporcionar una lista de inicialización completa (usando el { ... } sintaxis), luego use un array. Reemplaza el C-array tradicional, pero con funciones convenientes.
• De lo contrario, pase a la pregunta 4.

Pregunta 4: Doble punta ?

• Si desea poder eliminar elementos tanto del frente como de la parte posterior, utilice un dequede lo contrario utilice un vector.

Notará que, por defecto, a menos que necesite un contenedor asociativo, su elección será un vector. resulta que también La recomendación de Sutter y Stroustrup.

Me gusta la respuesta de Matthieu, pero voy a reformular el diagrama de flujo de la siguiente manera:

Cuándo NO usar std::vector

De forma predeterminada, si necesita un contenedor de cosas, use std::vector. Por lo tanto, cualquier otro contenedor solo se justifica proporcionando alguna funcionalidad alternativa a std::vector.

Constructores

std::vector requiere que su contenido se pueda mover y construir, ya que necesita poder barajar los elementos. Esta no es una carga terrible para colocar en los contenidos (tenga en cuenta que los constructores predeterminados son no requeridogracias a emplace Etcétera). Sin embargo, la mayoría de los otros contenedores no requieren ningún constructor en particular (nuevamente, gracias a emplace). Así que si tienes un objeto en el que absolutamente no poder implementar un constructor de movimiento, entonces tendrá que elegir otra cosa.

A std::deque sería el reemplazo general, teniendo muchas de las propiedades de std::vector, pero solo puede insertar en cualquiera de los extremos de la deque. Las inserciones en el medio requieren movimiento. A std::list no establece ningún requisito sobre su contenido.

Necesita libros

std::vector<bool> no es. Bueno, es estándar. pero no es un vector en el sentido usual, como operaciones que std::vector normalmente permite están prohibidos. Y ciertamente no contiene bools.

Por lo tanto, si necesita real vector comportamiento de un contenedor de bools, no lo vas a obtener de std::vector<bool>. Así que tendrás que arreglártelas con un std::deque<bool>.

buscando

Si necesita encontrar elementos en un contenedor y la etiqueta de búsqueda no puede ser solo un índice, es posible que deba abandonar std::vector a favor de set y map. Tenga en cuenta la palabra clave “mayo“; ordenado std::vector es a veces una alternativa razonable. O Boost.Container flat_set/mapque implementa una clasificación std::vector.

Ahora hay cuatro variaciones de estos, cada uno con sus propias necesidades.

• Utilizar una map cuando la etiqueta de búsqueda no es lo mismo que el elemento que está buscando. De lo contrario, utilice un set.
• Utilizar unordered cuando usted tiene una lote de elementos en el contenedor y el rendimiento de la búsqueda debe ser absolutamente O(1)en vez de O(logn).
• Utilizar multi si necesita que varios artículos tengan la misma etiqueta de búsqueda.

ordenar

Si necesita que un contenedor de elementos se clasifique siempre en función de una operación de comparación particular, puede usar un set. o un multi_set si necesita que varios artículos tengan el mismo valor.

O puede usar un ordenado std::vectorpero tendrás que mantenerlo ordenado.

Estabilidad

Cuando los iteradores y las referencias se invalidan, a veces es una preocupación. Si necesita una lista de elementos, de modo que tenga iteradores / punteros a esos elementos en varios otros lugares, entonces std::vectorEl enfoque de invalidación puede no ser apropiado. Cualquier operación de inserción puede causar la invalidación, según el tamaño y la capacidad actuales.

std::list ofrece una garantía firme: un iterador y sus referencias/indicadores asociados solo se invalidan cuando el elemento en sí se elimina del contenedor. std::forward_list está ahí si la memoria es una preocupación seria.

Si eso es una garantía demasiado fuerte, std::deque ofrece una garantía más débil pero útil. La invalidación resulta de las inserciones en el medio, pero las inserciones en la cabeza o la cola solo causan la invalidación de iteradoresno punteros/referencias a elementos en el contenedor.

Rendimiento de inserción

std::vector solo proporciona una inserción económica al final (e incluso entonces, se vuelve costosa si se agota la capacidad).

std::list es costoso en términos de rendimiento (cada elemento recién insertado cuesta una asignación de memoria), pero es consistente. También ofrece la capacidad ocasionalmente indispensable de barajar artículos prácticamente sin costo de rendimiento, así como intercambiar artículos con otros std::list contenedores del mismo tipo sin pérdida de rendimiento. Si necesitas barajar las cosas muchoutilizar std::list.

std::deque proporciona inserción/extracción en tiempo constante en la cabeza y la cola, pero la inserción en el medio puede ser bastante costosa. Entonces, si necesita agregar/eliminar cosas tanto del frente como de la parte posterior, std::deque podría ser lo que necesitas.

Cabe señalar que, gracias a la semántica de movimiento, std::vector el rendimiento de inserción puede no ser tan malo como solía ser. Algunas implementaciones implementaron una forma de copia de elementos basada en la semántica de movimiento (la llamada “intercambio”), pero ahora que el movimiento es parte del lenguaje, es obligatorio por estándar.

Sin asignaciones dinámicas

std::array es un buen contenedor si desea la menor cantidad posible de asignaciones dinámicas. Es solo un envoltorio alrededor de una matriz C; esto significa que su tamaño debe ser conocido en tiempo de compilación. Si puedes vivir con eso, entonces usa std::array.

Dicho esto, usando std::vector y reserveing un tamaño funcionaría igual de bien para un acotado std::vector. De esta manera, el tamaño real puede variar y solo obtiene una asignación de memoria (a menos que extienda la capacidad).

Aquí está la versión C++ 11 del diagrama de flujo anterior. [originally posted without attribution to its original author, Mikael Persson]

Aquí hay un giro rápido, aunque probablemente necesite trabajo

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

Puede notar que esto difiere salvajemente de la versión C++03, principalmente debido al hecho de que realmente no me gustan los nodos vinculados. Los contenedores de nodos vinculados generalmente pueden ser superados en rendimiento por un contenedor no vinculado, excepto en algunas situaciones excepcionales. Si no sabe cuáles son esas situaciones y tiene acceso a impulsar, no use contenedores de nodos vinculados. (std::list, std::slist, std::map, std::multimap, std::set, std::multiset). Esta lista se enfoca principalmente en contenedores de lados pequeños y medianos, porque (A) eso es el 99,99 % de lo que tratamos en el código, y (B) una gran cantidad de elementos necesitan algoritmos personalizados, no contenedores diferentes.