c++ - resueltos - listas programacion

¿Lista enlazada eficiente en C++?

Question

Este document dice que std::list es ineficiente:

std :: list es una clase extremadamente ineficiente que rara vez es útil. Realiza una asignación de pila para cada elemento insertado en ella, por lo que tiene un factor constante extremadamente alto, particularmente para tipos de datos pequeños.

Comentario: eso es para mi sorpresa. std::list es una std::list doblemente enlazada, por lo que a pesar de su ineficiencia en la construcción del elemento, admite la inserción / eliminación en la complejidad de tiempo O (1), pero esta característica se ignora por completo en este párrafo citado.

Mi pregunta: supongo que necesito un contenedor secuencial para elementos homogéneos de pequeño tamaño, y este contenedor debe admitir la inserción / eliminación de elementos en la complejidad O (1) y no necesita acceso aleatorio (aunque el acceso aleatorio de soporte es bueno, no es obligatorio aquí). Tampoco quiero el factor de alta constante introducido por la asignación de montón para la construcción de cada elemento , al menos cuando el número de elemento es pequeño. Por último, los iteradores se deben invalidar solo cuando se elimina el elemento correspondiente . Aparentemente necesito una clase contenedora personalizada, que podría (o no) ser una variante de la lista con doble enlace. ¿Cómo debo diseñar este contenedor?

Si no se puede lograr la especificación mencionada, entonces quizás debería tener un asignador de memoria personalizado, por ejemplo, ¿asignador de puntero de golpe? Sé que std::list toma un asignador como su segundo argumento de plantilla.

Edición: Sé que no debería preocuparme demasiado por este problema, desde el punto de vista de la ingeniería: lo suficientemente rápido es lo suficientemente bueno. Es solo una pregunta hipotética, por lo que no tengo un caso de uso más detallado. ¡Siéntase libre de relajarse algunos de los requisitos!

Edit2: Entiendo que dos algoritmos de complejidad O (1) pueden tener un rendimiento completamente diferente debido a la diferencia en sus factores constantes.

Answer 1

std::list es una std::list doblemente enlazada, por lo que a pesar de su ineficiencia en la construcción del elemento, admite la inserción / eliminación en la complejidad de tiempo O (1) , pero esta característica se ignora por completo en este párrafo citado.

Se ignora porque es una mentira .

El problema de la complejidad algorítmica es que generalmente mide una cosa . Por ejemplo, cuando decimos que la inserción en un std::map es O (log N), queremos decir que realiza comparaciones con O (log N). Los costos de iteración , captura de líneas de caché de la memoria , etc ... no se tienen en cuenta.

Esto simplifica enormemente el análisis, por supuesto, pero desafortunadamente no necesariamente se asigna de manera clara a las complejidades de la implementación en el mundo real. En particular, una suposición atroz es que la asignación de memoria es de tiempo constante . Y eso, es una mentira descarada.

Los asignadores de memoria de propósito general (malloc y co), no tienen ninguna garantía sobre la complejidad de las asignaciones de memoria en el peor de los casos. El peor de los casos generalmente depende del sistema operativo, y en el caso de Linux puede involucrar al asesino OOM (cernir los procesos en curso y matar a uno para reclamar su memoria).

Los asignadores de memoria para propósitos especiales podrían tener un tiempo constante ... dentro de un rango particular de cantidad de asignaciones (o tamaño máximo de asignación). Dado que la notación Big-O es aproximadamente el límite en el infinito, no puede llamarse O (1).

Y, por lo tanto, donde el caucho se encuentra con el camino , la implementación de std::list NO en general incluye la inserción / eliminación O (1), porque la implementación se basa en un asignador de memoria real, no en uno ideal.

Esto es bastante deprimente, sin embargo, no es necesario perder todas las esperanzas.

Más notablemente, si puede calcular un límite superior al número de elementos y puede asignar esa cantidad de memoria por adelantado, entonces puede diseñar un asignador de memoria que realizará una asignación de memoria de tiempo constante, lo que le dará la ilusión de O ( 1).

Answer 2

Como alternativa, puede utilizar una matriz ampliable y manejar los enlaces explícitamente, como índices en la matriz.

Los elementos de la matriz no utilizados se colocan en una lista vinculada mediante uno de los enlaces. Cuando se elimina un elemento, se devuelve a la lista libre. Cuando se agote la lista libre, haga crecer la matriz y use el siguiente elemento.

Para los nuevos elementos libres, tienes dos opciones:

• adjuntarlos a la lista libre de una vez,
• adjúntelos a pedido, según el número de elementos en la lista libre frente al tamaño de la matriz.

Answer 3

El requisito de no invalidar los iteradores, excepto el de un nodo que se está eliminando, está prohibido para todos los contenedores que no asignan nodos individuales y es muy diferente de, por ejemplo, la list o el map .
Sin embargo, he descubierto que en casi todos los casos, cuando pensé que esto era necesario, resultó que con un poco de disciplina podría prescindir de él. Es posible que desee verificar si puede, se beneficiaría enormemente.

Si bien std::list es de hecho lo "correcto" si necesita algo como una lista (para la clase CS, en su mayoría), la afirmación de que casi siempre es la elección equivocada es, desafortunadamente, exactamente correcta. Si bien la afirmación O (1) es totalmente cierta, no obstante, es abismal en relación con cómo funciona el hardware real de la computadora, lo que le da un factor constante enorme. Tenga en cuenta que no solo los objetos que itera se colocan aleatoriamente, sino también los nodos que mantiene (sí, de alguna manera puede solucionarlo con un asignador, pero ese no es el punto). En promedio, tiene dos fallos de caché garantizados para cualquier cosa que haga, más hasta dos asignaciones dinámicas para operaciones de mutación (una para el objeto y otra para el nodo).

Edición: como se indica en @ratchetfreak a continuación, las implementaciones de std::list comúnmente colapsan la asignación de objetos y nodos en un bloque de memoria como una optimización (similar a lo que hace, por ejemplo, make_shared ), lo que hace que el caso promedio sea algo menos catastrófico ( una asignación por mutación y una falta de caché garantizada en lugar de dos).
Una consideración nueva y diferente en este caso podría ser que hacerlo tampoco puede ser totalmente libre de problemas. Fijar el objeto con dos punteros significa revertir la dirección mientras se elimina la referencia, lo que puede interferir con la búsqueda previa automática.
Por otro lado, el uso de un prefijo con los punteros significa que usted lo empuja hacia atrás por el tamaño de dos punteros, lo que significará hasta 16 bytes en un sistema de 64 bits (que podría dividir un objeto de tamaño medio en una línea de caché). límites cada vez). Además, hay que considerar que std::list no puede permitirse romper, por ejemplo, el código SSE solo porque agrega una compensación clandestina como una sorpresa especial (por lo que, por ejemplo, el xor-trick probablemente no sea aplicable para reducir la huella de dos punteros). Es probable que tenga que haber una cierta cantidad de relleno "seguro" para asegurarse de que los objetos agregados a una lista todavía funcionen como deberían.
No puedo decir si estos son problemas reales de rendimiento o simplemente desconfianza y temor por mi parte, pero creo que es justo decir que puede haber más serpientes escondidas en la hierba de lo que uno espera.

No es por ninguna razón que los expertos de C ++ de alto perfil (Stroustrup, especialmente) recomiendan el uso de std::vector menos que tenga una buena razón para no hacerlo.

Como muchas otras personas antes, he tratado de ser inteligente en cuanto a usar (o inventar) algo mejor que std::vector para uno u otro problema en particular especializado en el que parece que puedes hacerlo mejor, pero resulta que simplemente usando std::vector es casi siempre la mejor opción, o la segunda mejor opción (si std::vector no es la mejor, std::deque es lo que necesitas en su lugar).
Tiene muchas menos asignaciones que con cualquier otro enfoque, menos fragmentación de la memoria, menos conexiones indirectas y un patrón de acceso a la memoria mucho más favorable. Y adivina qué, está disponible y simplemente funciona.
El hecho de que de vez en cuando las inserciones requieran una copia de todos los elementos es (por lo general) un problema total. Crees que lo es, pero no lo es. Ocurre raramente y es una copia de un bloque de memoria lineal, que es exactamente en lo que son buenos los procesadores (a diferencia de muchas direcciones dobles y saltos aleatorios sobre la memoria).

Si el requisito de no invalidar los iteradores es realmente un deber absoluto, podría, por ejemplo, emparejar un std::vector de objetos con un conjunto de bits dinámico o, a falta de algo mejor, un std::vector<bool> . Luego use reserve() apropiadamente para que las reasignaciones no ocurran. Al eliminar un elemento, no lo elimine, solo márquelo como eliminado en el mapa de bits (llame el destructor manualmente). En los momentos apropiados, cuando sepa que está bien invalidar los iteradores, llame a una función de "aspiradora" que compacta tanto el vector de bits como el vector de objetos. Allí, todas las invalidaciones de iteradores imprevisibles desaparecieron.

Sí, eso requiere mantener un bit de "elemento eliminado" adicional, lo cual es molesto. Pero un std::list debe mantener dos punteros también, además del objeto real, y debe hacer asignaciones. Con el vector (o dos vectores), el acceso sigue siendo muy eficiente, ya que se realiza de manera amigable con el caché. La iteración, incluso cuando se comprueban los nodos eliminados, todavía significa que se mueve de forma lineal o casi lineal sobre la memoria.

Answer 4

La forma más sencilla que veo para cumplir todos tus requisitos:

1. Inserción / eliminación de tiempo constante (espero que el tiempo constante amortizado esté bien para la inserción).
2. No hay asignación / desasignación del montón por elemento.
3. No hay invalidación de iterador en la eliminación.

... sería algo como esto, simplemente haciendo uso de std::vector :

template <class T>
struct Node
{
// Stores the memory for an instance of ''T''.
// Use placement new to construct the object and
// manually invoke its dtor as necessary.
typename std::aligned_storage<sizeof(T), alignof(T)>::type element;
// Points to the next element or the next free
// element if this node has been removed.
int next;
// Points to the previous element.
int prev;
};
template <class T>
class NodeIterator
{
public:
...
private:
std::vector<Node<T>>* nodes;
int index;
};
template <class T>
class Nodes
{
public:
...
private:
// Stores all the nodes.
std::vector<Node> nodes;
// Points to the first free node or -1 if the free list
// is empty. Initially this starts out as -1.
int free_head;
};

... y ojalá con un nombre mejor que Nodes (estoy un poco mareado y no soy tan bueno para inventar nombres en este momento). Dejaré la implementación en tus manos, pero esa es la idea general. Cuando elimine un elemento, simplemente haga una eliminación de la lista con doble enlace utilizando los índices y empújela hacia la cabeza libre. El iterador no se invalida, ya que almacena un índice en un vector. Cuando inserte, verifique si la cabeza libre es -1. Si no, sobrescriba el nodo en esa posición y haga clic. De push_back contrario, push_back al vector.

Ilustración

Diagrama (los nodos se almacenan de forma contigua dentro de std::vector , simplemente usamos enlaces de índice para permitir el salto de elementos de una manera sin sucursales, junto con eliminaciones e inserciones de tiempo constante en cualquier lugar):

Digamos que queremos eliminar un nodo. Esta es su eliminación estándar de la lista con doble enlace, excepto que usamos índices en lugar de punteros y usted también empuja el nodo a la lista libre (que solo implica la manipulación de enteros):

Ajuste de eliminación de enlaces:

Empujando el nodo eliminado a la lista libre:

Ahora digamos que inserta en esta lista. En ese caso, quita la cabeza libre y sobrescribe el nodo en esa posición.

Después de la inserción:

La inserción en el medio en tiempo constante también debería ser fácil de entender. Básicamente, simplemente se inserta en el encabezado libre o en push_back al vector si la pila libre está vacía. Luego haces la inserción de tu lista estándar de doble enlace. Lógica para la lista gratuita (aunque hice este diagrama para otra persona e involucra una SLL, pero debería tener la idea):

Asegúrese de que construye y destruye correctamente los elementos mediante la colocación de llamadas nuevas y manuales al dtor en la inserción / eliminación. Si realmente desea generalizarlo, también tendrá que pensar en la seguridad de excepción y también necesitamos un constador de solo lectura.

Pros y contras

El beneficio de tal estructura es que permite inserciones / eliminaciones muy rápidas desde cualquier lugar de la lista (incluso para una lista gigantesca), el orden de inserción se conserva para el recorrido, y nunca invalida los iteradores al elemento que no se elimina directamente (aunque invalidará los punteros a ellos; use deque si no desea que se invaliden los punteros). Personalmente, le resultaría más útil que std::list (que prácticamente nunca uso).

Para listas lo suficientemente grandes (por ejemplo, más grande que su caché L3 completo como un caso en el que definitivamente debería esperar una gran ventaja), esto debería superar ampliamente a std::vector para eliminaciones e inserciones en / desde el centro y el frente. La eliminación de elementos del vector puede ser bastante rápida para los pequeños, pero intente eliminar un millón de elementos de un vector comenzando desde el frente y trabajando hacia atrás. Allí las cosas comenzarán a arrastrarse, mientras que esta terminará en un abrir y cerrar de ojos. std::vector está ligeramente sobrepuesto a la OMI cuando las personas comienzan a usar su método de erase para eliminar elementos de la mitad de un vector que abarca 10k o más elementos, aunque supongo que esto todavía es preferible a las personas que utilizan ingenuamente listas vinculadas en todas partes La forma en que cada nodo se asigna individualmente en contra de un asignador de propósito general, mientras que causa la memoria caché, se pierde.

El inconveniente es que solo admite el acceso secuencial, requiere la sobrecarga de dos enteros por elemento, y como puede ver en el diagrama anterior, su localidad espacial se degrada si constantemente elimina cosas de forma esporádica.

Degradación de la localidad espacial

La pérdida de la localidad espacial a medida que comience a eliminar e insertar una gran cantidad desde / hacia el centro conducirá a zig-zagear los patrones de acceso a la memoria, lo que podría desalojar los datos de una línea de caché solo para regresar y recargarlos durante un solo ciclo secuencial. Esto es generalmente inevitable con cualquier estructura de datos que permita retiros desde el medio en tiempo constante, al mismo tiempo que permite recuperar ese espacio y preservar el orden de inserción. Sin embargo, puede restaurar la localidad espacial ofreciendo algún método o puede copiar / intercambiar la lista. El constructor de copias puede copiar la lista de manera que itere a través de la lista de origen e inserte todos los elementos, lo que le devuelve un vector perfectamente contiguo y compatible con caché sin agujeros (aunque hacerlo invalidará los iteradores).

Alternativa: Asignador de lista libre

Una alternativa que cumple con sus requisitos es implementar una lista gratuita conforme a std::allocator y usarla con std::list . Sin embargo, nunca me gustó tratar con las estructuras de datos y jugar con los asignadores personalizados, ya que se duplicaría el uso de memoria de los enlaces en 64 bits mediante el uso de punteros en lugar de índices de 32 bits, así que prefiero la solución anterior personalmente utilizando std::vector como básicamente su asignador de memoria analógico e índices en lugar de punteros (que reducen el tamaño y se convierten en un requisito si utilizamos std::vector ya que los punteros se invalidarán cuando el vector reserva una nueva capacidad).

Listas enlazadas indexadas

Llamo a este tipo de cosas una "lista enlazada indexada", ya que la lista enlazada no es realmente un contenedor sino una forma de vincular cosas que ya están almacenadas en una matriz. Y encuentro que estas listas enlazadas indexadas son exponencialmente más útiles ya que no es necesario que se sumerja en las agrupaciones de memoria para evitar las asignaciones / desasignaciones de almacenamiento dinámico por nodo y todavía puede mantener una localidad de referencia razonable (gran LOR si puede permitirse el lujo de publicar procesar las cosas aquí y allá para restaurar la localidad espacial).

También puede hacer esto individualmente si agrega un entero más al iterador de nodo para almacenar el índice de nodo anterior (no tiene carga de memoria en 64 bits, suponiendo requisitos de alineación de 32 bits para int y de 64 bits para punteros). Sin embargo, luego pierde la capacidad de agregar un iterador inverso y hacer que todos los iteradores sean bidireccionales.

Punto de referencia

Preparé una versión rápida de lo anterior ya que parece que estás interesado en ellos: versión de lanzamiento, MSVC 2012, sin iteradores comprobados ni nada de eso:

--------------------------------------------
- test_vector_linked
--------------------------------------------
Inserting 200000 elements...
time passed for ''inserting'': {0.000015 secs}
Erasing half the list...
time passed for ''erasing'': {0.000021 secs}
time passed for ''iterating'': {0.000002 secs}
time passed for ''copying'': {0.000003 secs}
Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]
finished test_vector_linked: {0.062000 secs}
--------------------------------------------
- test_vector
--------------------------------------------
Inserting 200000 elements...
time passed for ''inserting'': {0.000012 secs}
Erasing half the vector...
time passed for ''erasing'': {5.320000 secs}
time passed for ''iterating'': {0.000000 secs}
time passed for ''copying'': {0.000000 secs}
Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]
finished test_vector: {5.320000 secs}

Era demasiado perezoso para usar un temporizador de alta precisión, pero con suerte eso da una idea de por qué uno no debería usar vector''s método de erase tiempo lineal vector''s en rutas críticas para tamaños de entrada no triviales con un vector encima de allí que toma ~ 86 veces más tiempo (y exponencialmente) peor, cuanto mayor sea el tamaño de la entrada, lo intenté con 2 millones de elementos originalmente, pero me di por vencido después de esperar casi 10 minutos y por eso creo que el vector está demasiado sobrevalorado para este tipo de uso. Dicho esto, podemos convertir la eliminación del medio en una operación de tiempo constante muy rápida sin barajar el orden de los elementos, sin invalidar los índices e iteradores que los almacenan, y mientras seguimos utilizando vector ... Todo lo que tenemos que hacer es simplemente hacer almacena un nodo vinculado con índices prev/next para permitir saltar sobre los elementos eliminados.

Para su eliminación, utilicé un vector fuente aleatorio aleatorio de índices pares para determinar qué elementos eliminar y en qué orden. Eso imita en cierto modo un caso de uso en el mundo real en el que está eliminando la mitad de estos contenedores a través de los índices / iteradores que obtuvo anteriormente, como eliminar los elementos que el usuario seleccionó anteriormente con una herramienta de marquesina después de presionar el botón de eliminar (y nuevamente, realmente no debería usar scalar vector::erase para esto con tamaños no triviales, incluso sería mejor crear un conjunto de índices para eliminar y usar remove_if , aún mejor que vector::erase que remove_if un iterador en un hora).

Tenga en cuenta que la iteración se vuelve ligeramente más lenta con los nodos vinculados, y eso no tiene que ver con la lógica de iteración, sino que el hecho de que cada entrada en el vector sea más grande con los enlaces agregados (más memoria para procesar secuencialmente equivale a más caché). fallos y faltas de página). Sin embargo, si está haciendo cosas como eliminar elementos de entradas muy grandes, el sesgo de rendimiento es tan épico para los contenedores grandes entre el tiempo lineal y la eliminación de tiempo constante que esto suele ser un intercambio que vale la pena.

Answer 5

La nueva propuesta de slot_map reclama O (1) para insertar y eliminar.

También hay un enlace a un video con una implementación propuesta y algunos trabajos anteriores.

Si supiéramos más sobre la estructura real de los elementos, podría haber algunos contenedores asociativos especializados que sean mucho mejores.

Answer 6

Segundo, la respuesta de @Useless, particularmente el punto 2 de la PS sobre la revisión de requisitos. Si se relaja la restricción de invalidación del iterador, entonces usar std::vector<> es la sugerencia estándar de Stroustrup para un contenedor con un número pequeño de elementos (por razones ya mencionadas en los comentarios). questions Related sobre SO.

A partir de C ++ 11 también hay std::forward_list .

Además, si la asignación de almacenamiento dinámico estándar para los elementos agregados al contenedor no es lo suficientemente buena, entonces diría que debe observar sus requisitos exactos y afinarlos.

Answer 7

Solo quería hacer un pequeño comentario sobre tu elección. Soy un gran fan de vector debido a sus velocidades de lectura, y puedes acceder directamente a cualquier elemento, y hacer la clasificación si es necesario. (vector de clase / estructura por ejemplo).

Pero de todos modos estoy divagando, hay dos consejos ingeniosos que quería revelar. Con inserciones vectoriales puede ser costoso, por lo que un buen truco, no inserte si puede salirse con la suya de no hacerlo. hacer un push_back normal (poner al final) luego intercambiar el elemento con uno que desee.

Lo mismo con las eliminaciones. Son caros. Así que permítelo con el último elemento, bórralo.

Answer 8

Sugeriría hacer exactamente lo que dice @Yves Daoust, excepto que en lugar de usar una lista vinculada para la lista gratuita, use un vector. Empuje y haga estallar los índices libres en la parte posterior del vector. Esto es amortizado O (1) insertar, buscar y eliminar, y no implica ninguna búsqueda de puntero. Tampoco requiere ningún negocio repartidor molesto.

Answer 9

Sus requisitos son exactamente los de std::list , excepto que ha decidido que no le gusta la sobrecarga de la asignación basada en nodos.

El enfoque sano es comenzar en la parte superior y solo hacer todo lo que realmente necesite:

1. Solo usa std::list .

   Haga una evaluación comparativa: ¿es el asignador predeterminado realmente demasiado lento para sus propósitos?

   • No: has terminado.

   • Sí: goto 2

2. Utilice std::list con un asignador personalizado existente, como el asignador de grupo de Boost

   Como referencia: ¿es el asignador de grupo Boost realmente demasiado lento para tus propósitos?

   • No: has terminado.

   • Sí: goto 3

3. Utilice std::list con un asignador personalizado enrollado a mano que se ajusta a sus necesidades únicas, en función de todos los perfiles que realizó en los pasos 1 y 2

   Punto de referencia como antes, etc., etc.

4. Considera hacer algo más exótico como último recurso.

   Si llegas a esta etapa, deberías tener una pregunta SO muy bien especificada, con muchos detalles sobre lo que necesitas exactamente (por ejemplo, "Necesito meter n nodos en una línea de caché" en lugar de "este documento dice que esto es lento y eso suena mal ").

PD. Lo anterior hace dos suposiciones, pero vale la pena investigar ambas:

1. Como señala Baum mit Augen, no es suficiente hacer una sincronización simple de extremo a extremo, porque necesita estar seguro de a dónde va el tiempo. Podría ser el asignador en sí mismo, o el caché se pierde debido al diseño de la memoria, o algo más. Si algo es lento, todavía necesita estar seguro de por qué antes de saber qué debe cambiar.

2. sus requisitos se toman como un hecho, pero encontrar formas de debilitarlos es a menudo la forma más fácil de hacer algo más rápido.

   • ¿Realmente necesita una inserción y eliminación constante en todas partes, o solo en la parte delantera o trasera, o en ambas, pero no en el medio?
   • ¿Realmente necesita esas restricciones de invalidación de iterador, o pueden ser relajadas?
   • ¿Hay patrones de acceso que puedas explotar? Si con frecuencia quita un elemento del frente y luego lo reemplaza por uno nuevo, ¿podría actualizarlo en el lugar?

Answer 10

Utilice dos std::list s: una "lista libre" que se preasigna con un gran alijo de nodos al inicio, y la otra lista "activa" en la que se splice nodos de la lista libre. Este es un tiempo constante y no requiere asignar un nodo.

Answer 11

Gracias por todas las respuestas. Este es un punto de referencia simple, aunque no riguroso.

// list.cc
#include <list>
using namespace std;
int main() {
for (size_t k = 0; k < 1e5; k++) {
list<size_t> ln;
for (size_t i = 0; i < 200; i++) {
ln.insert(ln.begin(), i);
if (i != 0 && i % 20 == 0) {
ln.erase(++++++++++ln.begin());
}
}
}
}

y

// vector.cc
#include <vector>
using namespace std;
int main() {
for (size_t k = 0; k < 1e5; k++) {
vector<size_t> vn;
for (size_t i = 0; i < 200; i++) {
vn.insert(vn.begin(), i);
if (i != 0 && i % 20 == 0) {
vn.erase(++++++++++vn.begin());
}
}
}
}

Esta prueba tiene como objetivo probar qué std::listafirmaciones sobresalen en - O (1) insertando y borrando. Y, debido a las posiciones que pido para insertar / eliminar, esta carrera está fuertemente sesgada std::vector, ya que tiene que cambiar todos los elementos siguientes (por lo tanto, O (n)), mientras que std::listno es necesario hacerlo.

Ahora los compilo.

clang++ list.cc -o list
clang++ vector.cc -o vector

Y prueba el tiempo de ejecución. El resultado es:

 time ./list
./list 4.01s user 0.05s system 91% cpu 4.455 total
time ./vector
./vector 1.93s user 0.04s system 78% cpu 2.506 total

std::vector ha ganado.

Compilado con optimización O3, std::vectortodavía gana.

 time ./list
./list 2.36s user 0.01s system 91% cpu 2.598 total
time ./vector
./vector 0.58s user 0.00s system 50% cpu 1.168 total

std::listtiene que llamar a la asignación de pila para cada elemento, mientras que std::vectorpuede asignar memoria de pila en lotes (aunque podría ser dependiente de la implementación), por lo tanto std::list, la inserción / eliminación tiene un factor constante más alto, aunque es O (1).

No es de extrañar que this documento diga

std::vector Es bien amado y respetado.

EDIT : lo std::dequehace aún mejor en algunos casos, al menos para esta tarea .

// deque.cc
#include <deque>
using namespace std;
int main() {
for (size_t k = 0; k < 1e5; k++) {
deque<size_t> dn;
for (size_t i = 0; i < 200; i++) {
dn.insert(dn.begin(), i);
if (i != 0 && i % 20 == 0) {
dn.erase(++++++++++dn.begin());
}
}
}
}

Sin optimización:

./deque 2.13s user 0.01s system 86% cpu 2.470 total

Optimizado con O3:

./deque 0.27s user 0.00s system 50% cpu 0.551 total