c++ - library - lista stl

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

Question

Me gustaría usar std :: forward_list

Porque:

La lista de reenvío es un contenedor que admite la inserción y eliminación rápida de elementos desde cualquier lugar del contenedor

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

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

Answer 1

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

Puede escribir un contenedor alrededor de la lista que mantiene un iterador en el ú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 la list . Tiene las mismas características de rendimiento que forward_list , y es bidireccional, compatible con push_back y push_front ; el costo es un puntero extra por elemento.

Answer 2

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, tendrá que mantenerlo usted 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 3

Recomiendo contra std::forward_list como recomiendo 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 ofrece push_back eficiente, 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 aún gana incluso para insertar y eliminar en el medio .

Como ejemplo, Bjarne Stroustrup creó una prueba de 100,000 elementos std::list vs. 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 fuerte victoria para std::vector , incluso en esta situación donde std::list se supone que es fuerte. Simplemente atravesar std::list lleva 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.

La charla completa de Bjarne Stroustrup

Explicación detallada de los efectos, con puntos de referencia en múltiples tamaños

Tenga en cuenta que este segundo enlace aquí proporciona algunas situaciones en las que posiblemente desee utilizar una std::list , como 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 sencillo std::vector donde eliminé elementos invá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 un 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 sobre la std::list como la std::list me dio sobre mi implementación std::vector original, y esto fue lo suficientemente rápido como para ser útil.

Answer 4

std::forward_list compatible con la inserción y eliminación rápida, pero no transversal hasta el final . Para implementar .push_back , primero tendrá que 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.

Puede encontrar el iterador en el último elemento incrementando .before_begin N veces

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

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

slist.insert_after(before_end, 1234);

Answer 5

Desafortunadamente, no puedo agregar un comentario (baja reputación), pero solo quería mencionar que una de las ventajas de la lista de enlaces y listas 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).