vectors example español ejemplo c++ list vector stl

español - vector c++ example



vector vs. lista en STL (12)

Básicamente, un vector es una matriz con administración automática de memoria. Los datos son contiguos en la memoria. Intentar insertar datos en el medio es una operación costosa.

En una lista, los datos se almacenan en ubicaciones de memoria no relacionadas. Insertar en el medio no implica copiar algunos de los datos para dejar espacio para el nuevo.

Para responder más específicamente a su pregunta, voy a citar esta página

los vectores generalmente son los más eficientes a tiempo para acceder a elementos y agregar o eliminar elementos del final de la secuencia. Para las operaciones que implican la inserción o eliminación de elementos en posiciones distintas al final, tienen un rendimiento peor que los deques y las listas, y tienen iteradores y referencias menos consistentes que las listas.

Noté en Effective STL que

vector es el tipo de secuencia que debe usarse por defecto.

¿Qué significa? Parece que ignorar el vector eficiencia puede hacer cualquier cosa.

¿Alguien podría ofrecerme un escenario donde el vector no sea una opción factible pero se debe usar una list ?

Bueno, los estudiantes de mi clase parecen ser incapaces de explicarme cuándo es más efectivo usar vectores, pero se ven bastante felices cuando me aconsejan usar listas.

Así es como lo entiendo

Listas : cada elemento contiene una dirección para el elemento siguiente o anterior, de modo que con esta función, puede aleatorizar los elementos, incluso si no están ordenados, el orden no cambiará: es eficiente si la memoria está fragmentada. Pero también tiene otra gran ventaja: puede insertar / eliminar elementos fácilmente, porque lo único que debe hacer es cambiar algunos punteros. Desventaja: para leer un solo artículo al azar, debe saltar de un elemento a otro hasta encontrar la dirección correcta.

Vectores : cuando se utilizan vectores, la memoria está mucho más organizada, como las matrices normales: cada n-ésimo elemento se almacena inmediatamente después (n-1) del elemento y antes (n + 1) del elemento. ¿Por qué es mejor que la lista? Porque permite un acceso aleatorio rápido. He aquí cómo: si conoce el tamaño de un elemento en un vector y si están contiguos en la memoria, puede predecir fácilmente dónde está el n-ésimo elemento; no tiene que buscar todo el elemento de una lista para leer el que desea, con vector, lo lee directamente, con una lista que no puede. Por otro lado, modificar la matriz vectorial o cambiar un valor es mucho más lento.

Las listas son más apropiadas para realizar un seguimiento de los objetos que se pueden agregar / eliminar en la memoria. Los vectores son más apropiados cuando desea acceder a un elemento a partir de una gran cantidad de elementos individuales.

No sé cómo se optimizan las listas, pero debe saber que si desea un acceso de lectura rápido, debe usar vectores, porque lo bueno que enumera AWL enumera, no será tan rápido en el acceso de lectura como en el vector.

Cuando desee mover objetos entre contenedores, puede usar list::splice .

Por ejemplo, un algoritmo de partición de gráfico puede tener un número constante de objetos divididos recursivamente entre un número creciente de contenedores. Los objetos deben inicializarse una vez y permanecer siempre en las mismas ubicaciones en la memoria. Es mucho más rápido reordenarlos reenlazando que reasignando.

Editar: a medida que las bibliotecas se preparan para implementar C ++ 0x, el caso general de empalmar una subsecuencia en una lista se está volviendo una complejidad lineal con la longitud de la secuencia. Esto se debe a que el splice (ahora) necesita iterar sobre la secuencia para contar la cantidad de elementos que contiene. (Porque la lista necesita registrar su tamaño.) Simplemente contar y volver a vincular la lista es aún más rápido que cualquier alternativa, y empalmar una lista completa o un solo elemento son casos especiales con complejidad constante. Pero, si tiene secuencias largas para empalmar, es posible que tenga que buscar un contenedor mejor, anticuado y no conforme.

Cuando tiene mucha inserción o eliminación en el medio de la secuencia. por ejemplo, un administrador de memoria.

En cualquier momento no puede tener iteradores invalidados.

La única regla list que se debe utilizar la list es cuando necesita distribuir punteros a los elementos del contenedor.

A diferencia del vector , sabes que la memoria de los elementos no se reasignará. Si fuera así, podría tener punteros a la memoria no utilizada, que es, en el mejor de los casos, un gran no-no y, en el peor, un SEGFAULT .

(Técnicamente, un vector de *_ptr también funcionaría, pero en ese caso estás emulando la list así que eso es solo semántica.)

Otras reglas suaves tienen que ver con los posibles problemas de rendimiento al insertar elementos en el medio de un contenedor, con lo cual sería preferible la list .

La mayoría de las respuestas aquí pierden un detalle importante: ¿para qué?

¿Qué quieres guardar en el containter?

Si se trata de una colección de int s, std::list perderá en cada escenario, independientemente de si puede reasignar, solo eliminar desde el frente, etc. Las listas son más lentas, cada inserción le cuesta una interacción con el asignador ... Sería extremadamente difícil preparar un ejemplo, donde list<int> beats vector<int> . E incluso entonces, deque<int> puede ser mejor o más cercano, lo que no justifica el uso de listas, que tendrán una mayor sobrecarga de memoria.

Sin embargo, si está lidiando con grandes y feos borrones de datos, y pocos de ellos, si no desea sobreasignarlos al insertarlos, y copiarlos debido a la reasignación sería un desastre, entonces, tal vez, esté mejor con una list<UglyBlob> que vector<UglyBlob> .

Aún así, si cambia al vector<UglyBlob*> o incluso al vector<shared_ptr<UglyBlob> > , de nuevo, la lista se retrasará.

Entonces, el patrón de acceso, el conteo de elementos objetivo, etc. aún afecta la comparación, pero en mi opinión, el tamaño de los elementos, el costo de copiar, etc.

Preservar la validez de los iteradores es una de las razones para usar una lista. Otro es cuando no quieres que un vector se reasigne al empujar elementos. Esto puede ser manejado por un uso inteligente de reserva (), pero en algunos casos puede ser más fácil o más factible simplemente usar una lista.

Si no necesita insertar elementos con frecuencia, entonces un vector será más eficiente. Tiene una localidad de caché de CPU mucho mejor que una lista. En otras palabras, el acceso a un elemento hace que sea muy probable que el siguiente elemento esté presente en la memoria caché y pueda recuperarse sin tener que leer la RAM lenta.

Una de las capacidades especiales de std :: list es el empalme (vincular o mover parte de una lista completa a una lista diferente).

O tal vez si sus contenidos son muy caros de copiar. En tal caso, podría ser más económico, por ejemplo, ordenar la colección con una lista.

También tenga en cuenta que si la colección es pequeña (y los contenidos no son particularmente caros de copiar), un vector aún puede superar a una lista, incluso si inserta y borra en cualquier lugar. Una lista asigna cada nodo individualmente, y eso puede ser mucho más costoso que mover algunos objetos simples.

No creo que haya reglas muy duras. Depende de lo que más quieras hacer con el contenedor, así como de la cantidad que esperas que tenga el contenedor y el tipo contenido. Un vector generalmente supera una lista, porque asigna su contenido como un único bloque contiguo (básicamente es una matriz asignada dinámicamente y, en la mayoría de los casos, una matriz es la forma más eficiente de contener muchas cosas).

vector:

  • Memoria contigua
  • Pre-asigna espacio para los elementos futuros, por lo que se requiere espacio adicional más allá de lo necesario para los elementos mismos.
  • Cada elemento solo requiere el espacio para el tipo de elemento en sí (sin punteros adicionales).
  • Puede reasignar memoria para todo el vector cada vez que agrega un elemento.
  • Las inserciones al final son constantes, tiempo amortizado, pero las inserciones en otros lugares son O (n) costosas.
  • Los borrados al final del vector son tiempo constante, pero para el resto es O (n).
  • Puedes acceder aleatoriamente a sus elementos.
  • Los iteradores se invalidan si agrega o quita elementos del vector o desde él.
  • Puede acceder fácilmente a la matriz subyacente si necesita una matriz de elementos.

lista:

  • Memoria no contigua
  • Sin memoria preasignada La sobrecarga de memoria para la lista en sí es constante.
  • Cada elemento requiere espacio adicional para el nodo que contiene el elemento, incluidos los punteros a los elementos siguientes y anteriores de la lista.
  • Nunca tiene que reasignar memoria para toda la lista solo porque agrega un elemento.
  • Las inserciones y borraduras son baratas, sin importar en qué parte de la lista se encuentren.
  • Es barato combinar listas con empalmes.
  • No se puede acceder aleatoriamente a los elementos, por lo que llegar a un elemento particular de la lista puede ser costoso.
  • Los iteradores siguen siendo válidos incluso cuando agrega o elimina elementos de la lista.
  • Si necesita una matriz de elementos, deberá crear una nueva y agregarlos a ella, ya que no hay una matriz subyacente.

En general, use el vector cuando no le importe qué tipo de contenedor secuencial está utilizando, pero si está haciendo muchas inserciones o borrones hacia y desde cualquier lugar del contenedor que no sea el final, va a querer para usar la lista. O si necesita acceso aleatorio, querrá vector, no lista. Aparte de eso, existen instancias naturales en las que necesitará una u otra según su aplicación, pero en general, esas son buenas pautas.