¿Cómo puedo seleccionar de manera eficiente un contenedor de biblioteca estándar en C++ 11?
Hay una imagen muy conocida (hoja de referencia) llamada "Elección de contenedor C++". Es un diagrama de flujo para elegir el mejor contenedor para el uso deseado.
¿Alguien sabe si ya existe una versión C++ 11?
Este es el anterior:
No que yo sepa, sin embargo, supongo que se puede hacer textualmente. Además, el gráfico está ligeramente fuera de lugar, porque listno es un contenedor tan bueno en general, y tampoco lo es forward_list. Ambas listas son contenedores muy especializados para aplicaciones específicas.
Para crear un gráfico de este tipo, sólo necesita dos pautas sencillas:
- Elija primero la semántica
- Cuando haya varias opciones disponibles, opte por la más sencilla.
Preocuparse por el rendimiento suele ser inútil al principio. Las consideraciones de la gran O sólo entran en vigor cuando empiezas a manejar unos cuantos miles (o más) de elementos.
Hay dos grandes categorías de contenedores:
- Contenedores asociativos : tienen una
findoperación - Contenedores de secuencia simple
y luego puedes construir varios adaptadores encima de ellos: stack, queue, priority_queue. Dejaré los adaptadores aquí, están lo suficientemente especializados como para ser reconocibles.
Pregunta 1: ¿ Asociativo ?
- 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, pase a la pregunta 2.
Pregunta 1.1: ¿ Ordenado ?
- Si no necesita un pedido específico, utilice un
unordered_contenedor; en caso contrario, utilice su homólogo ordenado tradicional.
Pregunta 1.2: ¿ Clave separada ?
- Si la clave está separada del valor, use a
map; de lo contrario, use aset
Pregunta 1.3: ¿ Duplicados ?
- Si desea conservar duplicados, utilice un
multi; de lo contrario, no lo haga.
Ejemplo:
Supongamos que tengo varias personas con una identificación única asociada y me gustaría recuperar los datos de una persona a partir de su identificación de la manera más simple posible.
- Quiero una
findfunción, por lo tanto un contenedor asociativo.
1.1. No podría importarme menos el orden, por eso un unordered_contenedor.
1.2. Mi clave (ID) está separada del valor al que está asociada, por lo quemap
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), entonces use algunos
list - De lo contrario, pase a la pregunta 3.
Pregunta 2.1: ¿ Cuál ?
- Conformarse con un
list; aforward_listsolo es útil para ocupar menos memoria.
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 se pueden construir de forma predeterminada o puede proporcionar una lista de inicialización completa (usando la
{ ... }sintaxis), entonces use unarray. Reemplaza al tradicional C-array, pero con funciones convenientes. - De lo contrario, pase a la pregunta 4.
Pregunta 4: ¿ Doble extremo ?
- Si desea poder eliminar elementos tanto del frente como de la parte posterior, use un
deque; de lo contrario, use unvector.
Notarás que, de forma predeterminada, a menos que necesites un contenedor asociativo, tu elección será un archivo vector. Resulta que también es 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::vectorrequiere que su contenido sea construible en movimiento, ya que necesita poder mezclar los elementos. Esto no es una carga terrible para los contenidos (tenga en cuenta que los constructores predeterminados no son necesarios , gracias a emplaceetc.). Sin embargo, la mayoría de los demás contenedores no requieren ningún constructor en particular (nuevamente, gracias a emplace). Entonces, si tienes un objeto en el que no puedes implementar en absoluto un constructor de movimientos, tendrás que elegir otra cosa.
A std::dequesería el reemplazo general, ya que tendría muchas de las propiedades de std::vector, pero solo se puede insertar en cualquiera de los extremos del deque. Los insertos en el medio requieren movimiento. A std::listno impone ningún requisito sobre su contenido.
Necesita herramientas
std::vector<bool>no es. Bueno, es estándar. Pero no es vectoren el sentido habitual, ya que las operaciones que std::vectornormalmente permiten están prohibidas. Y ciertamente no contiene bools .
Por lo tanto, si necesita vectorun comportamiento real de un contenedor de bools, no lo obtendrá de std::vector<bool>. Así que tendrás que conformarte 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, es posible que deba abandonarla std::vectoren favor de sety map. Tenga en cuenta la palabra clave " mayo "; a veces una opción ordenada std::vectores una alternativa razonable. O Boost.Container's flat_set/map, que implementa un archivo std::vector.
Actualmente existen cuatro variaciones de estos, cada una con sus propias necesidades.
- Utilice a
mapcuando la etiqueta de búsqueda no sea lo mismo que el elemento que está buscando. De lo contrario utilice unset. - Úselo
unorderedcuando tenga muchos elementos en el contenedor y el rendimiento de la búsqueda sea absolutamente necesarioO(1), en lugar deO(logn). - Úselo
multisi necesita que varios elementos tengan la misma etiqueta de búsqueda.
Realizar pedidos
Si necesita que un contenedor de elementos siempre se ordene según una operación de comparación particular, puede utilizar un archivo set. O multi_setsi necesita que varios artículos tengan el mismo valor.
O puedes usar un ordenado std::vector, pero tendrás que mantenerlo ordenado.
Estabilidad
A veces es motivo de preocupación cuando se invalidan los iteradores y las referencias. Si necesita una lista de elementos, de modo que tenga iteradores/punteros a esos elementos en otros lugares, entonces std::vectorel enfoque de invalidación de 's puede no ser apropiado. Cualquier operación de inserción puede causar invalidación, dependiendo del tamaño y la capacidad actuales.
std::listofrece una garantía firme: un iterador y sus referencias/punteros asociados solo se invalidan cuando el elemento en sí se elimina del contenedor. std::forward_listestá ahí si la memoria es una preocupación seria.
Si esa es una garantía demasiado fuerte, std::dequeofrece una garantía más débil pero útil. La invalidación resulta de inserciones en el medio, pero las inserciones en la cabeza o la cola solo causan la invalidación de iteradores , no punteros/referencias a elementos en el contenedor.
Rendimiento de inserción
std::vectorsolo proporciona una inserción barata al final (e incluso entonces, se vuelve costoso si se gasta capacidad).
std::listEs 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 mezclar elementos prácticamente sin costo de rendimiento, así como intercambiar elementos con otros std::listcontenedores del mismo tipo sin pérdida de rendimiento. Si necesita cambiar mucho las cosas , utilice std::list.
std::dequeproporciona 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 o quitar cosas tanto del frente como de la parte posterior, std::dequepodría ser lo que necesita.
Cabe señalar que, gracias a la semántica de movimientos, std::vectores posible que el rendimiento de la inserción no sea tan malo como solía ser. Algunas implementaciones implementaron una forma de copia de elementos basada en la semántica del movimiento (la llamada "swaptimización"), pero ahora que el movimiento es parte del lenguaje, es obligatorio por el estándar.
Sin asignaciones dinámicas
std::arrayes un buen contenedor si desea la menor cantidad de asignaciones dinámicas posibles. Es sólo 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::vectore reserveintroducir un tamaño funcionaría igual de bien para un archivo acotado std::vector. De esta manera, el tamaño real puede variar y solo obtienes una asignación de memoria (a menos que agotes la capacidad).
Aquí está la versión C++11 del diagrama de flujo anterior. [publicado originalmente sin atribución a su autor original, 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 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 no tiene acceso al impulso, no utilice contenedores de nodos vinculados. (std::list, std::slist, std::map, std::multimap, std::set, std::multiset). Esta lista se centra principalmente en contenedores 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.
