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

12 minutos de lectura

¿Como puedo seleccionar de manera eficiente un contenedor de biblioteca
BlakBat

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:
Elección del contenedor eC++

  • Nunca había visto esto antes. ¡Gracias!

    – comadreja zorro

    22 de mayo de 2012 a las 9:31

  • @WeaselFox: Ya es parte de C++-Faq aquí en SO.

    – Alok Guardar

    22 de mayo de 2012 a las 9:34

  • C ++ 11 solo introdujo un nuevo tipo de contenedor verdadero: los contenedores unordered_X. Incluirlos solo confundiría la mesa considerablemente, ya que hay una serie de consideraciones al decidir si una tabla hash es apropiada.

    – Nicolás Bolas

    22 de mayo de 2012 a las 9:55

  • James tiene razón, hay más casos para usar vector que los que muestra la tabla. La ventaja de la localidad de datos supera en muchos casos la falta de eficiencia en algunas operaciones (más pronto C++11). No encuentro el gráfico electrónico tan útil incluso para c ++ 03

    – David Rodríguez – dribeas

    22 de mayo de 2012 a las 11:15


  • Esto es lindo, pero creo que leer cualquier libro de texto común sobre estructuras de datos lo dejará en un estado en el que no solo podrá reinventar este diagrama de flujo en unos minutos, sino que también sabrá mucho más cosas útiles que este diagrama de flujo pasa por alto.

    – Andrés Tomazos

    22 de mayo de 2012 a las 11:51

1646970554 86 ¿Como puedo seleccionar de manera eficiente un contenedor de biblioteca
Matthieu M.

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.

  • +1, pero con algunas notas: 1) array no requiere un tipo construible predeterminado; 2) recoger el multis no se trata tanto de que los duplicados sean permitido pero más sobre si acuerdo ellos importa (puede poner duplicados en no-multi contenedores, sucede que solo se conserva uno).

    – R. Martinho Fernández

    22 de mayo de 2012 a las 11:57

  • El ejemplo está un poco fuera de lugar. 1) podemos “encontrar” (no la función miembro, la ““) en un contenedor no asociativo, 1.1) si necesitamos encontrar “eficientemente”, y unordered_ será O(1) y no O( registro n).

    – BlakBat

    22 de mayo de 2012 a las 12:15

  • @BlakBat: map.find(key) es mucho más apetecible que std::find(map.begin(), map.end(), [&](decltype(map.front()) p) { return p.first < key; })); aunque, por lo tanto, es importante, semánticamente, que find es una función miembro en lugar de la de <algorithm>. En cuanto a O(1) vs O(log n), no afecta la semántica; Eliminaré el “eficientemente” del ejemplo y lo reemplazaré con “fácilmente”.

    – Matthieu M.

    22 de mayo de 2012 a las 12:22

  • “Si los elementos deben ser estables en la memoria … entonces use alguna lista” … mmm, pensé deque tenía esta propiedad también?

    – Martín Ba

    5 de julio de 2013 a las 5:57

  • @MartinBa: Sí y no. en un deque los elementos son estables solamente si empuja/hace estallar en cualquiera de los extremos; si comienza a insertar/borrar en el medio, se barajan hasta N/2 elementos para llenar el espacio creado.

    – Matthieu M.

    5 de julio de 2013 a las 6:10

1646970555 947 ¿Como puedo seleccionar de manera eficiente un contenedor de biblioteca
Nicolás Bolas

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).

  • Bueno, también me gusta mucho tu respuesta 🙂 WRT manteniendo un vector ordenado, aparte de std::sorttambién hay std::inplace_merge lo cual es interesante para colocar fácilmente nuevos elementos (en lugar de un std::lower_bound + std::vector::insert llamada). bueno aprender sobre flat_set y flat_map!

    – Matthieu M.

    23 de mayo de 2012 a las 10:02


  • Tampoco puede usar un vector con tipos alineados de 16 bytes. También es un buen reemplazo para vector<bool> es vector<char>.

    – Inversa

    26 de mayo de 2012 a las 0:42

  • @Inverse: “Tampoco puede usar un vector con tipos alineados de 16 bytes”. ¿Dice quién? Si std::allocator<T> no admite esa alineación (y no sé por qué no lo haría), entonces siempre puede usar su propio asignador personalizado.

    – Nicolás Bolas

    26 de mayo de 2012 a las 3:04

  • @Inverso: C++11 std::vector::resize tiene una sobrecarga que no toma un valor (solo toma el nuevo tamaño; cualquier elemento nuevo se construirá de forma predeterminada en el lugar). Además, ¿por qué los compiladores no pueden alinear correctamente los parámetros de valor, incluso cuando se declara que tienen esa alineación?

    – Nicolás Bolas

    26 mayo 2012 a las 21:23


  • bitset para bool si sabes el tamaño por adelantado es.cppreference.com/w/cpp/utility/bitset

    – bendervader

    2 de julio de 2015 a las 6:05


1646970555 742 ¿Como puedo seleccionar de manera eficiente un contenedor de biblioteca
Wasim Thabrazé

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

1646970555 169 ¿Como puedo seleccionar de manera eficiente un contenedor de biblioteca

  • @NO_NAME Guau, me alegro alguien se molestó en citar una fuente.

    – subrayado_d

    10/09/2016 a las 23:17

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.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad