librerias - ¿Cómo puedo seleccionar eficientemente un contenedor de Biblioteca Estándar en C++ 11?

manual completo de c++ pdf (4)

Aquí está la versión C ++ 11 del diagrama de flujo anterior. [publicado originalmente sin atribución a su autor original, Mikael Persson ]

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

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

Esta es la anterior:

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 mucho 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 para potenciar, 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 pequeños y medianos, porque (A) eso es 99.99% de lo que manejamos en el código, y (B) Un gran número de elementos necesitan algoritmos personalizados, no contenedores diferentes.

Me gusta la respuesta de Matthieu, pero voy a replantear el diagrama de flujo así:

Cuándo NO usar std :: vector

Por defecto, si necesita un contenedor de cosas, use std::vector . Por lo tanto, cada otro contenedor solo se justifica al proporcionar alguna alternativa de funcionalidad a std::vector .

Constructores

std::vector requiere que sus contenidos sean modificables por movimiento, ya que necesita poder barajar los elementos. Esta no es una carga terrible para colocar en los contenidos (tenga en cuenta que los constructores por defecto no son necesarios , gracias a emplace etc.). Sin embargo, la mayoría de los otros contenedores no requieren ningún constructor en particular (de nuevo, gracias a emplace ). Entonces, si tienes un objeto donde no puedes implementar un constructor de movimiento, entonces tendrás que elegir algo más.

Un std::deque sería el reemplazo general, ya que tiene muchas de las propiedades de std::vector , pero solo se puede insertar en cualquiera de los extremos del deque. Las inserciones en el medio requieren movimiento. Una std::list estándar no impone ningún requisito sobre su contenido.

Necesita Bools

std::vector<bool> es ... no. Bueno, es estándar. Pero no es un vector en el sentido habitual, ya que las operaciones que std::vector normalmente permiten están prohibidas. Y ciertamente no contiene bool s .

Por lo tanto, si necesita un comportamiento vector real desde un contenedor de bool , no lo obtendrá de std::vector<bool> . Por lo tanto, deberá cumplir con un std::deque<bool> .

buscando

Si necesita encontrar elementos en un contenedor, y la etiqueta de búsqueda no puede ser simplemente un índice, entonces puede que necesite abandonar std::vector a favor de set y map . Tenga en cuenta la palabra clave " puede "; un std::vector clasificado es a veces una alternativa razonable. O Boost.Container''s flat_set/map , que implementa un std::vector ordenado.

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

Use un map cuando la etiqueta de búsqueda no es lo mismo que el elemento que está buscando. De lo contrario, use un set .
Use unordered cuando tenga muchos elementos en el contenedor y el rendimiento de búsqueda debe ser O(1) , en lugar de O(logn) .
Use multi si necesita varios elementos para tener la misma etiqueta de búsqueda.

Ordenando

Si necesita un contenedor de artículos para clasificar siempre en función de una operación de comparación en particular, puede usar un set . O un multi_set si necesita varios elementos para tener el mismo valor.

O puede usar un std::vector ordenado, pero deberá 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 el enfoque de std::vector para la invalidación puede no ser apropiado. Cualquier operación de inserción puede causar la invalidación, dependiendo del tamaño y la capacidad actuales.

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

Si esa es una garantía demasiado fuerte, std::deque ofrece una garantía más débil pero útil. Los resultados de invalidación de las inserciones en el centro, pero las inserciones en la cabecera o en la cola solo causan la invalidación de los iteradores , no los punteros / referencias a los elementos en el contenedor.

Desempeño de inserción

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

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

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

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

Sin asignaciones dinámicas

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

Dicho esto, usar std::vector y reserve un tamaño funcionaría igual de bien para un std::vector delimitado. De esta forma, el tamaño real puede variar, y solo obtiene una asignación de memoria (a menos que pierda la capacidad).

No es que yo sepa, sin embargo se puede hacer textualmente, supongo. Además, el gráfico está un poco apagado, porque la list no es un contenedor tan bueno 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 para 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 surgen cuando comienzas a manejar algunos miles (o más) de artículos.

Hay dos grandes categorías de contenedores:

Contenedores asociativos : tienen una operación de find
Contenedores de secuencia simple

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

Pregunta 1: ¿ Asociativo ?

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

Pregunta 1.1: ¿ ordenado ?

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

Pregunta 1.2: ¿ Clave separada ?

Si la clave está separada del valor, use un map ; de lo contrario, use un set

Pregunta 1.3: ¿ Duplicados ?

Si desea mantener duplicados, use un multi , de lo contrario, no.

Ejemplo:

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

Quiero una función de find , por lo tanto, un contenedor asociativo
1.1. No me importa el orden, por lo tanto un contenedor unordered_
1.2. Mi clave (ID) está separada del valor al que está asociada, por lo tanto, un map
1.3. La identificación es única, por lo tanto, no debe 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 el contenedor mismo se modifique), utilice una list
De lo contrario, salta a la pregunta 3.

Pregunta 2.1: ¿Cuál ?

Conformarse para una list ; un forward_list solo es útil para una menor huella de memoria.

Pregunta 3: tamaño dinámico ?

Si el contenedor tiene un tamaño conocido (en tiempo de compilación), y este tamaño no se verá alterado durante el curso del programa, y los elementos son predeterminados o puede proporcionar una lista de inicialización completa (utilizando la sintaxis { ... } ), luego usa una array . Sustituye a la matriz C tradicional, pero con funciones convenientes.
De lo contrario, salta a la pregunta 4.

Pregunta 4: doble final ?

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

Notarás que, de forma predeterminada, a menos que necesites un contenedor asociativo, tu elección será un vector . Resulta que también es la recomendación de Sutter y Stroustrup .