std :: forward_list y std :: :: forward_list push_back

Question

Me gustaría utilizar std::forward_list

Porque:

lista Forward es un contenedor que soporta la rápida inserción y extracción de elementos desde cualquier lugar desde el contenedor

Pero no hay implementación * std :: forward_list :: push_back *.

¿Existe alguna forma de alto rendimiento para agregar soporte por una o ninguna razón para hacerlo?

Answer 1

std::forward_list admite la inserción y eliminación rápida, pero no transversal al final. Para implementar .push_back, primero debe llegar al final de la lista, que es O (N) y no rápido en absoluto, que es probablemente la razón por la que no está implementado.

 

Se podía encontrar el iterador al último elemento incrementando .before_begin N veces

auto before_end = slist.before_begin(); 
for (auto& _ : slist) 
    ++ before_end; 

y luego usar .insert_after o .emplace_after para insertar el elemento:

slist.insert_after(before_end, 1234); 

Answer 2

Hay no push_back porque la lista no realiza un seguimiento de la parte posterior de la lista , solo el frente.

Se puede escribir una envoltura alrededor de la lista que mantiene un iterador al último elemento, e implementa push_back utilizando insert_after o push_front dependiendo de si la lista está vacía. Esto se volverá bastante complicado si desea admitir las operaciones más complejas (por ejemplo, sort y splice_after).

Alternativamente, si no necesita push_back para ser rápido, es sencillo hacerlo en tiempo lineal.

A menos que la memoria sea extremadamente estrecha, la mejor solución es usar list. Tiene las mismas características de rendimiento que forward_list, y es bidireccional, admite push_back y push_front; el costo es un puntero extra por elemento.

Answer 3

El punto de std :: forward_list es ser una versión ultra-stripped de std :: list, por lo que no almacena un iterador en el último elemento. Si necesita uno, usted tiene que mantener por sí mismo, así:

forward_list<int> a; 

auto it = a.before_begin(); 

for(int i = 0; i < 10; ++i) 
    it = a.insert_after(it, i); 

Answer 4

recomiendo contra std::forward_list al igual que yo recomiendo en contra std::list en casi todas las situaciones. Personalmente, nunca encontré una situación en mi código en la que una lista vinculada fuera la mejor estructura de datos.

En C++, su recopilación de datos predeterminada debe ser std::vector. Le da eficiente push_back, si eso es lo que realmente necesita. Desde el punto de vista técnico, no le ofrece una eliminación e inserción eficiente si solo observa las medidas abstractas de complejidad de gran O de esa operación.En el mundo real, sin embargo, std::vector todavía gana incluso para insertar y eliminar en el medio.

Como ejemplo, Bjarne Stroustrup creó una prueba de un elemento std::list de 100,000 frente a std::vector. Buscaría cada uno de un elemento y lo eliminaría. Luego, encontraría un punto de inserción e insertaría en el centro. Podría haber usado una búsqueda binaria en el std::vector, pero no hizo la comparación "más justa".

Los resultados muestran una victoria fuerte para std::vector, incluso en esta situación donde se supone que std::list es fuerte. Simplemente atravesando el std::list toma mucho más tiempo debido a cuán separados están en la memoria todos los objetos. std::list no es compatible con caché, que posiblemente sea lo más importante para los procesadores modernos.

The complete talk by Bjarne Stroustrup

Thorough explanation of the effects, with benchmarks at multiple sizes

Tenga en cuenta que este segundo enlace aquí da algunas situaciones de donde posiblemente puede que desee utilizar un std::list, por ejemplo, cuando el tamaño de los elementos es grande. Sin embargo, he estado en una situación en la que tengo muchos elementos en un orden particular y necesito eliminar algunos.

Estos elementos eran más grandes que cualquier tipo incorporado, pero no grandes, quizás 20-30 bytes cada uno en una computadora de 32 bits). La cantidad de elementos era lo suficientemente grande para que toda mi estructura de datos tuviera unos cientos de MiB. La recopilación de datos fue un conjunto de valores que teóricamente podrían ser válidos según la información actualmente conocida. El algoritmo iteraba sobre todos los elementos y eliminaba los elementos que ya no podían ser válidos en función de la información nueva, con cada pase probablemente eliminando alrededor del 80% de los elementos restantes.

Mi primera implementación fue un enfoque directo std::vector donde eliminé elementos no válidos a medida que atravesaba. Esto funcionó para pequeños conjuntos de datos de prueba, pero cuando traté de hacer algo real, fue demasiado lento para ser útil. Cambié a std::list como contenedor, pero usé el mismo algoritmo y vi mejoras significativas en el rendimiento. Sin embargo, todavía era demasiado lento para ser útil. El cambio ganador fue volver a cambiar a std::vector, pero en lugar de eliminar elementos que estaban mal, creé un nuevo std::vector, y todos los elementos que encontré que eran buenos se pusieron en ese std::vector, y luego al final de la función Simplemente descartaría el viejo std::vector y usaría el nuevo, y esto me dio una aceleración tan grande como la std::list como la me dio sobre la implementación original de std::vector, y esto fue lo suficientemente rápido como para ser útil.

Answer 5

Desafortunadamente no puedo agregar un comentario (baja reputación) pero solo quería mencionar que una de las ventajas de la lista forward_list & es que las operaciones de inserción-eliminación no invalidan los iteradores. Tenía una aplicación donde la colección de elementos crecía mientras iteraba y procesaba elementos individuales. La ausencia de invalidación de iterador me permitió implementar escaneo de segmento (comienzo de la lista como inicio del segmento y comienzo del último segmento como final).