c++ - example - ¿Por qué std:: vector es mucho más popular que std:: deque?

queue c++ (5)

Posible duplicado:
¿Por qué preferiría usar vector para deque

Tengo curiosidad por saber por qué std::vector es mucho más popular que std::deque . Deque es casi tan eficiente en la búsqueda, más eficiente en insertar (sin vector :: reserva) y permite insertar / eliminar en el frente.

Herb Sutter una vez recomendó que si quieres usar el vector, simplemente prefiera el deque (estoy parafraseando). Sin embargo, en una charla reciente sobre Writing Modern C ++ , recomienda encarecidamente pensar en std::vector como un contenedor predeterminado. De acuerdo con el GOTW I vinculado anteriormente, incluso el estándar tiene una redacción similar.

¿Hay alguna razón para esta disparidad? ¿Es simplemente que el vector es más simple y más conocido, o hay una razón técnica? ¿O es que ese vector es solo un nombre más genial ...?

Además de que std::vector es la clase de contenedor más comúnmente conocida, también tiene varias ventajas sobre std::deque , a saber:

Un std::deque típico requiere una indirección adicional para acceder a los elementos a diferencia de std::vector .
Los iteradores en caso de std::deque deben ser punteros inteligentes y no punteros como en el caso de std::vector .
Se garantiza que los elementos de un std::vector sean contiguos y, por lo tanto, es compatible con las funciones de estilo c que toman las matrices como parámetros.
std::deque no proporciona soporte para controlar la capacidad y el momento de la reasignación.

Especialmente, el último punto es notable.

La estructura de std::deque es un poco más compleja, lo que hace que la iteración ingenua sea un poco más cara que std::vector . Las inserciones en std::vector con sus reasignaciones tienden a no ser un gran problema, especialmente cuando se usa reserve() y solo se agrega al final. Además, hay reglas de invalidación más fáciles de entender para std::vector aunque en realidad es una ventaja de std::deque que los objetos permanezcan al insertar / eliminar solo en cada extremo (tenga en cuenta que std::deque iterators se invalidan en cada inserción , independientemente de dónde suceda la inserción). Otra ventaja para std:vector es la garantía de que los valores son contiguos en la memoria y provocan menos asignaciones de memoria.

Supongo que recomendaría que el uso de los algoritmos std::deque se optimizaran consistentemente para usar secuencias segmentadas (no conozco ninguna biblioteca estándar de C ++ que haga esta optimización) y los usuarios accedían a las secuencias de forma consistente usando algoritmos (hasta donde sé , solo una pequeña fracción de usuarios considera la opción de usar algoritmos). De lo contrario, sospecharía que std::deque es la mejor opción con respecto al rendimiento solo si aprovechas sus propiedades específicas (por ejemplo, que los objetos se quedan y que puedes insertar / eliminar al final). Sin embargo, vale la pena perfilar las dos alternativas.

La gente usa std :: vector over std :: deque por una simple razón. Se conectan con una gran cantidad de bibliotecas C y tienen functions con parámetros que requieren un puntero a un almacenamiento contiguo, que std :: deque no garantiza (no puede).

Otra razón es cuando construyes código de acuerdo con std :: deque y tus requisitos cambian para que tengas que admitir acceso contiguo, tendrás que hacer un poco de refactorización.

Me veo obligado a mencionar que existen libraries cuyos autores afirman haber creado implementaciones vectoriales más eficientes para superar las ineficiencias cuando se aumenta la capacity .

No puedo hablar por nadie más, pero puedo hacerlo por mí mismo.

Cuando leí por primera vez sobre std::deque , pensé que era lo suficientemente bueno como para que por un tiempo lo tratara no solo como el contenedor predeterminado, sino como casi el único contenedor que utilicé.

Luego alguien preguntó por qué, y expuse largamente sobre sus virtudes y por qué era el mejor contenedor para prácticamente todo, y cómo era mucho más versátil que std::vector .

Afortunadamente, el tipo que cuestionó mi decisión fue lo suficientemente persuasivo como para hacer algunas pruebas. Las pruebas mostraron que en casi todos los casos, std::deque era más lento que std::vector , a menudo por un factor sustancial (por ejemplo, alrededor de 2). De hecho, del código que había escrito usando std::deque , el simple hecho de reemplazar std::deque con std::vector dio una aceleración en todos los casos excepto en un puñado.

He usado std::deque en algunos casos desde entonces, pero definitivamente ya no lo considero el predeterminado. El simple hecho es que en la implementación habitual es notablemente más lento que std::vector para la mayoría de los propósitos.

Debo agregar, sin embargo, que estoy razonablemente seguro de que con la implementación correcta, podría ser casi equivalente a std::vector en prácticamente todos los casos. La mayoría usa una representación que sin duda es genial desde un punto de vista asintótico, pero que no funciona tan maravillosamente (para muchos propósitos) en el mundo real.

std::vector se entiende muy bien, es simple y es compatible con C (tanto en términos de diseño de la memoria como en términos de utilizar punteros como iteradores).

Para algunas operaciones, también es más eficiente que std::deque . Acceder a los elementos por índice es un ejemplo.

Para una tarea dada, tiene sentido usar el contenedor más simple que hace bien el trabajo. En muchos casos, el contenedor más simple es std::vector .