¿El vector es un caso especial de listas vinculadas?

Question

Cuando hablo del STL, tengo varios compañeros diciéndome que "los vectores son listas vinculadas".

Tengo otro argumento que si llamas al método erase() con un iterador, rompe el vector, ya que es una lista vinculada.

También tienden a no entender por qué siempre estoy argumentando que los vectores son contiguos, como cualquier otra matriz, y no parecen entender lo que significa el acceso aleatorio. ¿El vector es estrictamente contiguo al igual que las matrices normales, o simplemente como máximo contiguo? (por ejemplo, asignará varios segmentos contiguos si la matriz completa no se ajusta).

Answer 1

Lamento decir que sus compañeros de clase están completamente equivocados. Si sus compañeros de clase pueden decir honestamente que "los vectores son listas vinculadas", debe decirles respetuosamente que deben recoger el a good C++ book (o cualquier libro de ciencias de la computación decente) y leerlo. O tal vez incluso los artículos de Wikipedia para vectors y lists. (Ver también los artículos para dynamic arrays y linked lists.)

---

vectores (como en std::vector) no son listas enlazadas. (Tenga en cuenta que std::vector no deriva de std::list). Si bien ambos pueden almacenar una colección de datos, la forma en que lo hace un vector es completamente diferente de cómo lo hace una lista vinculada. Por lo tanto, tienen diferentes características de rendimiento en diferentes situaciones.

Por ejemplo, las inserciones son una operación de tiempo constante en listas vinculadas, mientras que es una operación de tiempo lineal en vectores si se inserta en algún lugar que no sea el final. (Sin embargo, es amortizados de constante de tiempo si se inserta en el extremo de un vector.)

La clase std::vector en C++ son requiere que ser contiguos por el ++ estándar C:

23.2.4/1 Plantilla de clase vector

A vector es un tipo de secuencia que admite iteradores de acceso aleatorio. Además, admite operaciones de inserción y borrado de tiempo constante (amortizadas) al final; insertar y borrar en el medio toma tiempo lineal. La administración del almacenamiento se maneja automáticamente, aunque se pueden dar sugerencias para mejorar la eficiencia. Los elementos de un vector se almacenan de forma contigua, lo que significa que si v es una vector<T, Allocator> donde T es algún tipo que no sea bool, a continuación, que obedece a la identidad &v[n] == &v[0] + n para todos 0 <= n < v.size().

que para comparar std::list:

23.2.2/1 plantilla de clase list

A list es un tipo de secuencia que soporta iteradores bidireccionales y permite inserto constante de tiempo y borrar operaciones en cualquier lugar dentro de la secuencia, con administración de almacenamiento manejada automáticamente. A diferencia de los vectores (23.2.4) y deques (23.2.1), el acceso aleatorio rápido a los elementos de la lista no es compatible, pero muchos algoritmos solo necesitan acceso secuencial de todos modos.

Claramente, el estándar C++ estipula que un vector y una lista son dos contenedores diferentes que hacen las cosas de manera diferente.

No se puede "romper" un vector (al menos no intencionalmente) simplemente llamando al erase() con un iterador válido. ¡Eso haría que std::vector sea bastante inútil ya que el punto de su existencia es administrar la memoria para usted!

Answer 2

Por definición, vector s son bloques contiguos de memoria como matrices en C. Ver: http://en.wikipedia.org/wiki/Vector_(C%2B%2B)

Los vectores permiten el acceso aleatorio; es decir, un elemento de un vector puede ser al que se hace referencia de la misma manera que elementos de matrices (por índices de matriz). Las listas y conjuntos vinculados, en la otra mano , no son compatibles con el acceso aleatorio ni con la aritmética del puntero .

Answer 3

Los vectores no están vinculados a la lista de enlaces, brindan acceso aleatorio y son contiguos al igual que las matrices. Para lograr esto, reasignan la memoria debajo del capó.

La lista está diseñada para permitir inserciones y eliminaciones rápidas, sin invalidar referencias o iteradores excepto los que están en el elemento eliminado.

Answer 4

vector contendrá todo de su almacenamiento en un solo lugar. Un vector no es ni remotamente como una lista vinculada. De hecho, si tuviera que elegir dos estructuras de datos que eran muy diferentes entre sí, sería vector y list. "A lo más contiguo" es cómo funciona un deque.

vectorial:

1. garantizado almacenamiento contiguo para todos los elementos - será copiar o mover elementos.
2. O (1) tiempo de acceso.
3. O (n) para insertar o quitar.
4. Iteradores invalidados al insertar o quitar cualquier elemento.

lista:

1. Sin almacenamiento contiguo a todos - nunca copia o mueve elementos.
2. O (n) tiempo de acceso, además de todos los errores de caché desagradable que va a obtener.
3. O (1) inserte o elimine.
4. Iteradores válidos siempre que ese elemento específico no se elimine.

Como puede ver, se comportan de manera diferente en cada caso de uso de estructura de datos.