que - Lista de C++ STL vs conjunto

c++ que es (6)

¿Cuál de esos dos es más rápido para inserciones y eliminaciones aleatorias? Supongo que la lista, teniendo los valores como las claves como con los conjuntos parece ser atractivo también. ¿Es el rendimiento similar para iterar sobre todo el contenedor?

¡Gracias!

Debe medir el rendimiento usted mismo con un uso realista en datos realistas. Verifique tanto el desempeño típico como el peor de los casos.

Aunque std :: vector tiene una complejidad de tiempo O (N) para la inserción aleatoria, std :: set O (log (N)) y std :: list O (1), std :: vector se desempeña mejor en muchos casos. Solo si el rendimiento no es lo suficientemente importante como para pasar la medición del tiempo, vaya por la complejidad de la gran O.

"Si no estás midiendo no estás haciendo ingeniería" (Rico Mariani)

En std :: list, la inserción y eliminación propiamente dicha toman un tiempo en O (1), lo que significa muy rápido , y sobre todo significa a una velocidad que no depende del número de elementos en la lista.

En un std :: set, la inserción y la eliminación toman tiempo en O (log (N)), lo que significa un poco más lento si hay muchos elementos en el set . La N en la expresión O (log (N)) significa el número de elementos. Grosso modo, significa que el tiempo tomado por la operación es proporcional al logaritmo (la base no importa aquí, ya que es equivalente a multiplicar por una constante, que se ignora en el análisis de algoritmos teóricos) del número de elementos en el set

Pero es vital tener en cuenta el tiempo necesario para encontrar el elemento a eliminar. Si debe buscar en el contenedor el elemento que desea eliminar, que es lo más probable, entonces std :: list tardará bastante tiempo en realizar esta búsqueda, que estará en O (N) (lo que significa que no es rápido , porque el tiempo es directamente proporcional al número de elementos, no al logaritmo del mismo, mientras que std :: set tomará un tiempo en O (registro N) para la búsqueda.

También tenga en cuenta que esos análisis teóricos se vuelven absolutamente inválidos para contenedores con muy pocos elementos, en cuyo caso las constantes multiplicadoras que ocultan se vuelven más importantes que la familia de funciones de tiempo en las que se enfoca.

Para hacerlo más corto: std :: list => Más lento para buscar el elemento a eliminar; Más rápido para eliminarlo. std :: set => Más rápido para buscar el elemento a eliminar; Menos rápido para borrarlo.

Pero para toda la operación, y para un gran número de elementos, std :: set es mejor.

También debe considerar el uso de tablas hash . Las buenas implementaciones de estos están disponibles en Boost, Qt o C ++ 0x. Hacen todas estas operaciones en el tiempo que tienden hacia O (1) (lo que significa muy, muy rápido ).

Primero piense en la semántica, luego en el rendimiento.

Si tiene un conjunto de enteros y le inserta los enteros 6, 8, 13, 8, 20, 6 y 50, terminará con un conjunto que contiene los siguientes cinco elementos: { 6, 8, 13, 20, 50 }.

Si haces eso con una lista, terminarás con una lista que contiene los siguientes siete elementos: { 6, 8, 13, 8, 20, 6, 50 } .

¿Entonces qué quieres? No tiene sentido comparar la velocidad de los contenedores con una semántica tan diferente.

Si te importa la velocidad, entonces probablemente deberías usar std::vector . std::list realiza una asignación de montón cada vez que se inserta un elemento y eso suele ser un cuello de botella.

Una excepción es cuando los artículos individuales son muy caros de copiar, o cuando tiene una gran cantidad de ellos. En esos casos, es probable que una lista tenga un mejor rendimiento, ya que no tiene que mover elementos cuando se redimensiona. Un std::deque también es una buena opción aquí, pero necesitará un perfil de su aplicación para poder decidir entre los dos.

Finalmente, use std::set solo si necesita mantener sus artículos ordenados (o si no quiere artículos repetidos). De lo contrario, será significativamente más lento que una lista o un vector.

std :: list es O (1) para inserciones y eliminaciones. Pero es posible que necesite O (n) para encontrar el punto de inserción o eliminación. std :: set es O (log (n)) para inserciones y eliminaciones, generalmente se implementa como un árbol rojo-negro.

Considere el esfuerzo de encontrar el punto de inserción / eliminación para hacer su elección.

Lista

Búsqueda (tiempo lineal).
Insertar, borrar, mover (lleva tiempo constante).
Los elementos pueden ser ordenados.
Los elementos pueden ser ordenados.
Los elementos pueden estar duplicados.

Conjunto

Búsqueda (logarítmica en tamaño).
Insertar y eliminar (logarítmico en general).
Los elementos no están ordenados.
Los elementos siempre se ordenan de menor a mayor.
Los elementos son únicos.