Pregunta Lista C ++ STL vs conjunto


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

¡Gracias!


20
2018-02-20 15:40


origen


Respuestas:


Lista

  1. Buscando (tiempo lineal).
  2. Insertar, eliminar, mover (toma tiempo constante).
  3. Los elementos pueden ser ordenados.
  4. Los elementos pueden ser ordenados.
  5. Los elementos pueden ser duplicados.

Conjunto

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

34
2018-02-20 16:33



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, por lo general se implementa como un árbol rojo-negro.

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


19
2018-02-20 15:44



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.


11
2018-02-20 15:45



En std :: list, la inserción y la eliminación se toman un tiempo en O (1), lo que significa muy rapido, y sobre todo significa a una velocidad que no depende de la cantidad 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 una gran cantidad de elementos están contenidos en el conjunto. El N en la expresión O (log (N)) significa la cantidad de elementos. Grosso modo, significa que el tiempo empleado 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 que lleva encontrar el elemento para eliminar. Si debe buscar en el contenedor para eliminar el elemento, que probablemente sea el caso, entonces std :: list tomará un tiempo bastante largo para esta búsqueda, que estará en O (N) (lo que significa no rapido, 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 (log 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 de multiplicación que ocultan se vuelven más importantes que la familia de funciones de tiempo en la que se enfoca.

Para hacerlo breve:    std :: list => Más lento para buscar el elemento para eliminar; más rápido para eliminarlo.    std :: set => Más rápido para buscar el elemento para eliminar; menos rápido para eliminarlo.

Pero para toda la operación, y para una gran cantidad de elementos, el std :: set es mejor.

También deberías considerar usar tablas hash. Buenas implementaciones de esas están disponibles en Boost, Qt o C ++ 0x. Hacen todas estas operaciones en el tiempo tendiendo hacia O (1) (que significa muy muy rápido)


3
2018-02-20 17:13



Debe medir el rendimiento usted mismo con un uso realista en datos realistas. Compruebe el rendimiento típico y 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 funciona mejor en muchos casos. Solo si el rendimiento no es lo suficientemente importante como para perder tiempo de medición, vaya por la complejidad de la gran O.

"Si no estás midiendo no eres ingeniero" (Rico Mariani)


2
2018-02-20 16:28



Si te preocupa la velocidad, 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 tienes muchos 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á perfilar su aplicación para decidir entre los dos.

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


2
2018-02-20 16:00