C++ Memoria dinámica

[rafaelfinacut10]

Hola a todos...Necesito ayuda para terminar un código, pero no encuentro la manera de hacerlo...es un programa que opera en la colección dinámica de datos. La idea es usar una estructura que contenga dos campos: la primera almacena el número de elementos en las colecciones, y la segunda es la colección real (un vector de ints dinámicamente asignado). Como puede ver, la colección está llena con la cantidad requerida de datos pseudoaleatorios. La función principal no esta terminada.. Esto es lo que se espera
1.Si la colección está vacía, debe asignar un vector de un elemento y almacenar un nuevo valor en él
2. Si la colección no está vacía, debe asignar un nuevo vector con una longitud mayor en uno que el vector actual, luego copiar todos los elementos del antiguo vector al nuevo, agregar un nuevo valor al nuevo vector y finalmente liberar el vector viejo.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Collection {
int  elno; int *elements;
};

void AddToCollection(Collection &col, int element) {
// la primera parte de la funcion
if (col.elno==0){
   col.elements= new int[1];
   col.elements[0]= element;
}
//lo que no esta terminado
   else {
   int *temporal;
   temporal = new[];
}

}
void PrintCollection(Collection col) {
cout << "[ "; for(int i = 0; i < col.elno; i++) 
cout << col.elements[i] << " "; cout << "]" << endl; }

int main(void) {
Collection collection = { 0, NULL };
int elems; cout << "How many elements? ";
cin >> elems;
srand(time(NULL));
for(int i = 0; i < elems; i++) 
AddToCollection(collection, rand() % 100 + 1); PrintCollection(collection); delete[] collection.elements;
return 0;
}

[MAFUS]

Deberías dar un poco de formato a tu código: cada sentencia en una línea, controlar las sangrías, dejar las llaves de cierre solas en su propia línea. Consideraciones estéticas. El código se ve mucho mejor y a simple vista se puede seguir de forma más intuitiva.

A lo que voy. Te dejo la función inacabada rellena con el código comentado más una recomendación: cuanto menos código escribas mejor (sin llegar a hacer críptica la solución, hay que sacrificar muchas veces la simplicidad por la claridad). La lógica muchas veces se puede simplificar, y no digo solo operaciones lógicas sino las líneas de código. Muchas veces el código se repite y no nos damos cuenta. Vale la pena perder un poco de tiempo en revisarlo y dejar todo lo que se repita fuera de las estructuras condicionales y reorganizar éstas para que solo toquen los pequeños cambios que se suceden.

Tu solución, supongo que esto te lo ha dado el profesor

Código (cpp) [Seleccionar] Expandir

void AddToCollection(Collection &col, int element) {
   // la primera parte de la funcion
   if (col.elno==0) {
       col.elements = new int[1];
       col.elements[0] = element;
   }
   //lo que no esta terminado
   else {
       int *temporal;
       int i;

       temporal = new int[col.elno + 1]; // Hago que temporal sea un elemento más grande que el actual número de elementos.
       for(i = 0; i < col.elno; ++i)
           temporal[i] = col.elements[i]; // Copio todos los elementos del array antiguo al nuevo.
       temporal[i] = element; // i está actualizada al nuevo último elemento por la forma en que trabaja for,
                              // así que guardo el elemento pasado a la función.
       delete[] col.elements; // Ahora puedo borrar el arrar antiguo
       col.elements = temporal; // y hacer que el puntero elements apunte al nuevo array.
   }
   col.elno++; // Actualizo elno para indicar que hay un elemento más.
}

Ahora la mía:
Se basa en que todo el trabajo es el mismo, menos en una cosa, tanto si no había elementos guardados o si los había.
Obviamente faltan las comprobaciones de seguridad, por si acaso hubiera algún fallo pero no están incluidas por simplicidad y claridad.

Código (cpp) [Seleccionar] Expandir

void AddToCollection(Collection &col, int element) {
   int *temporal;
   int i;

   temporal = new int[col.elno + 1];
   for(i = 0; i < col.elno; ++i)
       temporal[i] = col.elements[i];
   temporal[i] = element;
   if(col.elno) // Esta es la excepeción que he nombrado. Que es lo mismo a: if(col.elno > 0)
       delete[] col.elements;
   col.elements = temporal;
   col.elno++;
}

[dijsktra]

Comentando un poco el problema original

[...] es un programa que opera en la colección dinámica de datos.
[...]
Esto es lo que se espera
1.Si la colección está vacía, debe asignar un vector de un elemento y almacenar un nuevo valor en él
2. Si la colección no está vacía, debe asignar un nuevo vector con una longitud mayor en uno que el vector actual, luego copiar todos los elementos del antiguo vector al nuevo, agregar un nuevo valor al nuevo vector y finalmente liberar el vector viejo.

Le veo un fallo a este planteamiento. Está claro que la mayor ventaja de emplear dinámica es que se ajusta más la memoria seǵun la necesidad en tiempo de ejecución... Pero se incurre en gran ineficiencia en cuanto a tiempo...
Me explico:

Añadir el primer elemento cuesta 1, el segundo 2, el tercero 3, el cuarto 4... debido a que tienes que hacer una copia del array aumentado a cada momento... De esta manera incurres en coste cuadratico O(n^2), cuando, con memoria estatica, aunque ineficaz en espacio,  tenias un coste  O(n) en tiempo

Código [Seleccionar] Expandir

1+2+3 + ... + n = n(n+1)/2  \in O(n^2)

lo que hace muy costoso e ineficiente...

Este es un viejo problema de coste amortizado...

Básicamente consiste en, cada vez que se incremente en la memoria, hacerlo multiplicando por un factor - que depende de una heurística o de la aplicación particular...

En nuestro caso, elegimos FACTOR=2, por lo que cada vez que se "llene la memoria" la duplicamos, y solo en ese momento, hacemos copia del vector original . Es cierto que se pierde precisión con respecto  a la idea dinamica original de tu planteamiento llegando a gastar N*2 cuando sólo se tiene N+1 en el caso peor, pero en términos de coste amortizado en tiempo es de coste constante O(1)...  (es algo complejo de explicar en un solo post)


Primero vamos con la entrada (1 renglon) y salida (2 y 3 renglon) de los programas. El programa almacena la colección de entrada en un array estatico de como mucho 1000 elementos y despues lo convierte a colección dinámica. Se puede ver el ratio de memoria empleada/reservada

Código [Seleccionar] Expandir


1
1
N/MAX=1/10000 vs. N/NN=1/1

Código [Seleccionar] Expandir

1 2
1 2
N/MAX=2/10000 vs. N/NN=2/2

Código [Seleccionar] Expandir

1 2 3 4
1 2 3 4
N/MAX=4/10000 vs. N/NN=4/4

Código [Seleccionar] Expandir


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N/MAX=16/10000 vs. N/NN=16/16

Código [Seleccionar] Expandir


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
N/MAX=32/10000 vs. N/NN=32/32

Ahora el codigo del programa.
Yo voy a lo sustancial, no manejo "structs" , pero es posible que a tí te interese para simular un TAD, y lo podrás adoptar a tu manera con "structs". Tampco programo la reservar memoria, porque viene con

Código (c) [Seleccionar] Expandir


#include <stdlib.h>
void *realloc(void *ptr, size_t size);


pero a ti te puede interesar programarla "por razones didácticas"

Este es el programa

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>

#define MAX 10000

#define FACTOR 2

/* Pre : *NN = 1  */
void static2Dynamic(const int V[],const int N,int **D, int *NN)
{
 int nn,n;

  /* I : nn <= *NN  */
 for ( nn=n=0; n<N; n++)
   {
     if (nn == *NN)
      {
         (*NN) *= FACTOR;
 if  (!(*D=(int *)realloc(*D,sizeof(int)*(*NN))))
         {
           perror("realloc");
           exit(EXIT_FAILURE);
         }
      }
     (*D)[nn++]= V[n];
   }
}

int main (int argc, char **args)
{
 int *D ;
 int N,n,NN;
 int V[MAX];
 if  (!(D=(int *)malloc(sizeof(int))))
   {
     perror("malloc");
     exit(EXIT_FAILURE);
   }
 NN=1;
 for(N=0; (scanf("%d",&V[N])!=EOF); N++);
 static2Dynamic(V,N,&D,&NN);
 for( n=0; n<N; n++) printf("%d ",D[n]);
 printf("\nN/MAX=%d/%d vs. N/NN=%d/%d\n",N,MAX,N,NN);
 return 0;
}




Ahora bien, fijate lo que psa si metemos, digamos 33 elementos...

Código [Seleccionar] Expandir


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
N/MAX=33/10000 vs. N/NN=33/64

Se despercia casi la mitad, pero aún así, no tanto como 33/10000...

Por ultimo, si quieres progrmaarte tu realloc, puede ser algo así

Código (c) [Seleccionar] Expandir


void *myrealloc(const int *ptr, const size_t old_size,const size_t new_size )
{
 int *p;
 if (!(p = malloc(new_size)))
   {
     perror("malloc");
     exit(EXIT_FAILURE);      
   }
 int i;
 for (i=0; (i < old_size) && (i < new_size);i++) *(p+i) = *(ptr+i);
 free((void *)ptr);
 return p;
}


Cambiando lo que haya que cambiar en el fuente del main