Las listas consumen la mayor parte de su tiempo en la asignación de memoria cuando push_back. Por otro lado, los vectores tienen que copiar sus elementos cuando se necesita un cambio de tamaño. ¿Qué contenedor es, por lo tanto, el más eficiente para almacenar una lista de adyacencia?Vector STL vs list: ¿Más eficiente para listas de adyacencia de gráficos?
No creo que se pueda responder con absoluta certeza. No obstante, calculo que hay al menos un 90% de posibilidades de que un vector lo haga mejor. Una lista de adyacencia en realidad tiende a favorecer un vector más que muchas aplicaciones, porque el orden de los elementos en la lista de adyacencia no importa (normalmente). Esto significa que cuando agrega elementos, normalmente está al final del contenedor, y cuando elimina un elemento, puede cambiarlo al final del contenedor primero, de modo que solo lo agregue o elimine al final.
Sí, un vector tiene que copiar elementos cuando se expande, pero en realidad esto casi nunca es una preocupación sustancial. En particular, la tasa de expansión exponencial de un vector significa que el número promedio de veces que los elementos se copian tiende hacia una constante, y en una implementación típica, esa constante es aproximadamente 3.
Si se encuentra en una situación donde la copia honesta es un problema real (por ejemplo, copiar elementos es extremadamente caro), mi siguiente elección después del vector todavía no sería la lista. En cambio, probablemente consideraría usar std :: deque en su lugar. Básicamente es un vector de punteros a bloques de objetos. Rara vez tiene que copiar algo para hacer una expansión, y en la rara ocasión en que lo hace, todo lo que tiene que copiar son los punteros, no los objetos. A menos que necesite las otras capacidades únicas de un deque (insertar/eliminar en tiempo constante en cualquier extremo), un vector suele ser una mejor opción, pero aun así un deque es casi siempre una mejor opción que una lista (es decir, el vector es generalmente la primera opción, deque es un segundo bastante cercano, y lista una última distante).
La respuesta depende del uso-caso. P.S. @quasiverse - vectores llaman a realloc cuando la memoria "reserva", implícita o explícitamente, se agota
Si tiene una lista de adyacencias en constante cambio (inserta y elimina), una lista sería lo mejor. Si tiene una lista de adyacencia más o menos estática y la mayoría de las veces realiza recorridos/búsquedas, entonces un vector le proporcionará el mejor rendimiento.
Los contenedores STL no están rígidamente definidos, por lo que las implementaciones varían. Si tiene cuidado, puede escribir su código para que no le importe si se trata de un vector o una lista que se está utilizando, y puede intentarlo para ver cuál es más rápido. Dada la complejidad de los efectos de caché, etc., es casi imposible predecir las velocidades relativas con precisión.
Puede agregar una tercera opción a esta comparación: una lista con un asignador especializado.
Uso de asignadores para pequeños objetos de tamaño fijo puede aumentar considerablemente la velocidad de la asignación/desasignación ...
¿Quién dijo que los vectores de hacer una copia? – quasiverse
@quasiverse: los requisitos en 'vector' requieren esencialmente una copia a medida que crece. 'vector's son necesarios para almacenar sus elementos contiguamente. A medida que agrega elementos, eventualmente utilizará el espacio asignado, y en la próxima adición obtendrá una nueva asignación de memoria seguida de una copia de los elementos actuales al nuevo espacio, seguido de una desasignación del espacio antiguo. . –