Duda STL Vector

[pepon01]

Hola si tengo una lista que va a crecer conviene usar Vector, o que otro contenedor conviene?? Soy principiante en manejo de la STL y tengo entendido que primero se reserva cierto espacio, cuando se termina se copia en un espacio nuevo mayor y despues se borra el espacio original, pero en los deques y vector el espacio intermedio de reserva crece considerablemente, por lo que se recomienda usar en estos casos un List ...

estoy en lo cierto??
es un caso tipico de estructura de dato de tamaño variable, no es necesario eliminar datos intermedios solo al final
saludos

[vosk]

Se considera que el objeto vector es relativamente mas eficiente que los list para acceder a elementos intermedios y para añadir/quitar elementos finales, y se considera que es el contenedor menos eficiente para insertar/eliminar elementos que no sean finales.

Supongo que segun el caso será preferible la velocidad de acceso, o la optimizacion de memoria, o se requeriran metodos disponibles para determinado objeto.

En lo referente al espacio estas en lo cierto, los vectores guardan espacio para un numero concreto de elementos y cuando se sobrepasan se expande, lo que implica (a parte de reservar mas memoria) que deberá mover todos los elementos al nuevo bloque de memoria. Las list en cambio funcionan como una lista doblemente enlazada, reserva memoria para cada elemento y lo relaciona con sus elementos laterales. Otros tipos de listas se implementan como simples listas enlazadas.

No se si te habré ayudado con esto

Saludos
vosk

[pepon01]

hola gracias por la respuesta me quedo la duda de si cuando crecen mas de lo esprado, digamos que a un vector se le reservo espacio para 25 elementos y acaba teniendo mas de 200, en cada reacomodo la memoria inicial no se borra del todo, lei en otro post que cuando un vector o deque crecen mas de lo esperado el consumo de memoria es desmesurado consecuancia de que quedan espacios de memoria no borrados, ah y los elementos se añaden y borran solo al final

dependiendo del balance del consumo de memoria y velocidad de ejecucion tendre que elegir entre vector o list, de todos modos tendre que probar con ambos cual se acomoda mejor a mis necesidades

saludos

[ZeKi]

A un vector de STL no tienes porqué decirle un tamaño. Simplemente haz esto:

Código C++:

vector<int> v; // lo hacemos de enteros por ejemplo
 

Y luego cuando quieras añadir elementos llamas a push_back:

Código C++:

v.push_back(2);
 

Y eso lo que hará es meter el 2 al final del vector. También puedes jugar con los punteros:

Código C++:

vector<int*> v;
vector<int> *v;
 

[vosk]

pepon01: "...y los elementos se añaden y borran solo al final..."

No, los elementos se añaden y se borran al momento y en cualquier posicion pero solo tiene ventaja sobre los otros contenedores cuando añades o borras el elemento final.

El tamaño teorico de reserva de bloques por defecto es de 'vector::max_size()', aunqué no tiene por que ser exactamente ese valor. Puedes consultar el numero real de elementos que se han reservado para un vector con 'vector::capacity()'.

Si de todas formas quieres limitar el tamaño de elementos reservados puedes declarar el vector y aplicarle el metodo 'reserve()' antes de añadir ningun elemento (truncará el array del vector al nº de elementos que li indiques).

A parte está tambien la forma de definir tu propio modelo de reserva de memoria, pero no tengo ni idea de como funciona.

Saludos
vosk

[pepon01]

mmm mi pregunta esta mas que nada orientada al manejo de memoria para obtener un programa economico y eficaz, en la serie de tutoriales Zator se indica que si el tamaño de los datos varia constantemente es aconsejable un list por encima de un vector o deque :

http://www.zator.com/Cpp/E5_1_1.htm
http://www.zator.com/Cpp/E5_1_1a.htm

cuando dije se añaden al final me referia a mis necesidades osea solo añadire y borrare elementos al final, este mismo aspecto se discute en los enlaces adjuntos referidos tambien a las consideraciones de añadir elementos en posiciones intermedias

saludos

[vosk]

Hasta cierto limite y si solo vas a añadir/eliminar elementos al final aunqué la el numero de elementos esté creciendo continuamente es preferible usar el vector.

Acabo de probarlo y el vector me guarda un maximo teorico de 1073741823 elementos antes de una nueva relocalizacion de memoria. A partir de esto: si la aplicacion que estas creando está fuera de ese rango tal vez debas plantearte el uso de otro contenedor.

O tal vez quieras implementar dos aplicaciones test con cada uno de los contenedores, y con algun programa que encuentres por la red de monitorizacion de procesos podras ver cual puede servirte.

De todas formas echa un vistazo tambien a la pagina de cplusplus.com para complementar la informacion del manual de zator.

Saludos
vosk

[fightmx]

mmm mi pregunta esta mas que nada orientada al manejo de memoria para obtener un programa economico y eficaz

Es más eficiente asignar bloques grandes de memoria que bloques pequeños (la cantidad de solicitudes sería mayor para reservar la misma cantidad de memoria). Si tienes una idea aproximada de la cantidad límite de elementos que vas a manejar, entonces el vector es la mejor opción, siempre y cuando te quede claro como está reservando memoria. De forma muy simple el proceso del vector puede ser:

1. Vector sin elementos - No hay reserva de memoria
2. Inserto 1 nuevo elemento al final - Reserva memoria hasta para 1 elemento
3. Inserto 1 nuevo elemento al final - Reserva memoria hasta para 2 elementos - Copia elementos y remueve el bloque anterior de memoria
4. Inserto 1 nuevo elemento al final - Reserva memoria hasta para 4 elementos - Copia elementos y remueve el bloque anterior de memoria
5. Inserto 1 nuevo elemento al final - No es necesario reservar memoria
6. Inserto 1 nuevo elemento al final - Reserva memoria hasta para 8 elementos - Copia elementos y remueve el bloque anterior de memoria
7. Inserto 3 nuevos elementos al final - No es necesario reservar memoria
8. Inserto 1 nuevo elemento al final - Reserva memoria hasta para 16 elementos - Copia elementos y remueve el bloque anterior de memoria
9. Inserto 7 nuevos elementos al final - No es necesario reservar memoria
10. Inserto 1 nuevo elemento al final - Reserva memoria hasta para 32 elementos - Copia elementos y remueve el bloque anterior de memoria
...

Como ya te habían mencionado el vector trata de mantener una cantidad de elementos reservados en memoria (capacity) mayor que la cantidad de elementos que actualmente contiene (size), esto para amortizar el número de reservas y copias de elementos a nuevos bloques de memoria. En éste ejemplo supuse una implementación basada en potencias de 2, aunque el funcionamiento real depende de cada compilador.

Si conoces el número aproximado de elementos totales que vas a manejar entonces puedes ahorrarte todo el proceso, por ejemplo, si sabes que no vas a tener más de 30000 elementos, basta con:

Código C++:

myVector.reserve(30000);
 

La memoria se reserva en una sola vez y no habrá copia de elementos a nuevos bloques de memoria (siempre y cuando insertes al final, resulta eficiente y no malgastas memoria), si por algo el size del vector sobrepasa éste número el procedimiento es como antes (no quiere decir que no puedas almacenar más de 30000 elementos, simplemente que reservas memoria hasta para 30000 elementos antes de que una nueva reserva suceda). Por otro lado; si no tenemos ni idea de la cantidad total de elementos, lo que muy probablemente pasará, es que por la forma (que puede ser exponencial) en que se va reservando la memoria, terminemos con una cantidad reservada muy por encima de lo necesario (lo que afecta depende de cada situación).

Con un list la memoria se administra de manera constante, es decir, insertas un elemento y se reserva memoria para ese nuevo elemento (no importando el size), además no necesita mover bloques de memoria ya que mantiene referencias respecto a los elementos anterior y siguiente, resultando muy efectivo para la inserción intermedia; que por el contrario, en un vector insertar de manera intermedia implica forzosamente una nueva reserva y copia del bloque anterior de memoria (ya que debe mantener sus elementos continuos en memoria), esto último dándole ventaja del acceso aleatorio(indexado), algo de lo que carecen las listas.

Al final tienes que tomar en cuenta varios factores (tipo de inserción, forma de acceso, tipo de dato, constructores, etc.) y evaluar, muchas veces sacrificas memoria por rendimiento o viceversa, a veces puedes tener lo necesario para lograr un buen balance, en fin, depende de cada situación.

[sam90]

Hago una pequeña acotacion al tema... Hoy en dia la memoria no es un gran problema en la mayoria de las aplicaciones.
Por ejemplo si reservamos memoria para 30.000 enteros de 32 bits.

30.000 X 4B = 120.000B
120.000B / 1024 = 117KB

La verdad que hoy en dia 117KB no es nada. Asi que muchas veces es preferible tener esa gran reserva de una que de la otra forma.

Saludos

[dontexplain]

C++ es muy ineficiente para el manejo de todo lo que tenga que ver con arrays o vectores. El objeto vector es una mera basura que falla en cuanto más falta te hace, además de que consume muchos recursos y no tiene prevención de errores.

Como dicen el objeto vector en su inicialización no requiere de un tamaño o límite asignado inicialmente, sólo tener en cuenta que el tamaño máximo es el objeto de tipo size_type devuelto por vector::max_size.

Manejar vectores con char es un infierno, te aconsejo no hacerlo. Tendrás finalmente que usar string porque la recolocación de memoria es muy liosa y para hacer algo simple tienes que erigir montañas de código. Por supuesto, string ya son cientos de líneas de código adicionales.

[fightmx]

Hago una pequeña acotacion al tema... Hoy en dia la memoria no es un gran problema en la mayoria de las aplicaciones.

De acuerdo, sobre todo con tipos simples.

C++ es muy ineficiente para el manejo de todo lo que tenga que ver con arrays o vectores. El objeto vector es una mera basura que falla en cuanto más falta te hace, además de que consume muchos recursos y no tiene prevención de errores.

Creo que más bien depende del contexto y del tipo de datos, si estás manejando objetos definidos por ti, suele ser muy costoso, ya que se crean múltiples objetos temporales al estarse copiando elementos de manera interna(múltiples llamadas al constructor copia, aquí hay que tomar en cuenta que esto de las copias innecesarias cambia significativamente con las rvalue references en C++11). El rendimiento es muy superior si creas un contenedor de punteros por ejemplo, obviamente aquí tienes que encargarte de administrar la memoria a la que refieren tus punteros, nada nuevo a como se haría en C, que aún así puede seguir siendo la mejor opción, pero insisto, dependerá del contexto y de saber aprovechar las ventajas y evitar las desventajas en cada situación y con cualquier contenedor (no sólo del vector), ya que puedes obtener un rendimiento muy similar usando C o C++.

[vosk]

"...Es más eficiente asignar bloques grandes de memoria que bloques pequeños..."

Se conoce como memory pool y es bastante comun en aplicaciones 'grandes'; se diseña una libreria propia de manejo de memoria con varios tipos de acceso a las listas para que pueda ser reutilizada en proyectos futuros.

Si no se intenta hacer algo extremadamente complejo que lleve el sistema al maximo con los vectores tienes mas que suficiente, estan implementados en librerias estandar, estan documentados, testados para el uso comun y no suelen fallar.

Saludos
vosk