Tableau dynamique alloué en C++

Question

Je suis en train de faire un devoir et j'ai été bloqué à un moment donné ici. J'essaie d'écrire une fonction list_add(). La première fonctionnalité de cette fonction est d'ajouter des valeurs au tableau. Sa deuxième fonction est d'augmenter la taille du tableau. Cela fonctionne donc un peu comme un vecteur. Je ne sais pas si j'ai bien compris. Ce que j'ai essayé de faire, c'est de créer un nouveau tableau dynamique alloué qui est plus grand que l'ancien, puis de copier toutes les valeurs dans le nouveau tableau.

Est-ce la bonne approche ?

Voici le corps principal

int main()
{
    const int N = 7;

    //declaring dynamic array allocation
    int* list = new int[N];

    int used = 0, a_val;
    for(int i=0;i<11;i++)
    {
        list_add(list, used, N, i);
    }

    cout << endl << "Storlek: " << N << endl << endl;
    cout << "Printar listan " << endl;
    for(int i=0;i<used;i++)
    {
        cout << list[i] << ". ";
    }

}

Voici la fonction

bool list_add(int *list, int& space_used, int max_size, int value)
{

    if(max_size-space_used > 0)
    {
        *(list+(max_size-space_used-1)) = value;
        space_used++;
        return true;
    }
    else
    {
        cout << "Increasing size of array!" << endl;
        int new_max_size = space_used+1;
        delete [] list;
        int *list_new = new int[new_max_size];

        for(int i=0; i<new_max_size; i++)
        {
            list_new[i] = i;
            cout << list_new[i] << ". ";
        }
        cout << endl;
        space_used++;
        list = list_new;
        return false;
    }
}

Answer 1

Vous avez la bonne idée, mais la mise en œuvre pourrait avoir besoin d'un peu d'"huile de coude".

Essayez ceci :

garder 2 int

capacité - longueur à laquelle vous allouez
size - fin actuelle du tableau

if capacity <= size:
   make new list( size = capacity x 2 )
   memcopy old list into new list -> if you can't memcopy, copy over the data one-by-one
   delete old list
if capacity > size:
   list[size] = value
   size++

http://www.cplusplus.com/reference/clibrary/cstring/memcpy/

Answer 2

Un problème qui me saute aux yeux est que vous ne modifiez pas la valeur de votre pointeur de liste en dehors de la portée de votre fonction list_add. Vous devriez faire des changements comme...

bool list_add(int *list, int& space_used, int max_size, int value)

devient

bool list_add(int **list, int& space_used, int max_size, int value)

et

list = list_new

devient

*list = list_new

Sinon, je pense que vous constaterez que lorsque vous réallouerez votre liste, après le retour de list_add, le pointeur de votre liste pointera toujours vers l'ancien emplacement.

Answer 3

Il y a quatre problèmes avec l'implémentation de votre code :

1. Il ne copie pas les éléments de la liste.
2. Il n'assigne pas la valeur de new_list a la list variable dans main
3. Il insère les valeurs de l'arrière vers l'avant, au lieu de les insérer après la dernière valeur.
4. max_size n'est pas mis à jour. Il est facile de manquer cela, car vous n'augmentez la taille du tableau que d'une unité à chaque fois. De cette façon, le tableau devrait être alloué à chaque fois qu'une valeur est ajoutée. Si vous augmentez la nouvelle taille de plus d'une unité, elle sera toujours réallouée à chaque fois.

Le premier problème peut être résolu en changeant la boucle for dans list_add pour qu'il en fasse une copie :

for (int i = 0; i < space_used; i++) {   // this also changed.
    list_new[i] = list[i];
    cout ...
}
// insert the new value (in the front?)
list_new[max_size-space_used-1] = value;     
delete [] list;         // Delete the list afterwards instead of earlier.

Le second problème peut être résolu en renvoyant un pointeur sur la liste. Changez le main à cette fonction :

for (int i = 0; i < 11; i++) {
    list = list_add(list, used, N, i); 
}

Le troisième problème peut être résolu en modifiant cette ligne

list_new[max_size-space_used-1] = value;

à

list_new[space_used++] = value;

Vous devez également supprimer le space_used++ après ça.

Pour voir le quatrième problème, vous devez changer cette ligne

int new_max_size = space_used+1;

à

int new_max_size = space_used+3;

Il réallouera toujours à chaque fois. Il ne devrait cependant le faire que deux fois.

---

Voici le code complet :

#include <iostream>
using std::cout;
using std::endl;

int* list_add(int *list, int& space_used, int& max_size, int value) {
    if (max_size - space_used > 0) {
        list[space_used++] = value;
        return list;
    }
    else {
        cout << "Increasing size of array!" << endl;
        int new_max_size = space_used+1;

        int *list_new = new int[new_max_size];

        for (int i = 0; i < space_used; i++) {
            list_new[i] = list[i];
            cout << list_new[i] << ". ";
        }
        cout << endl;

        list_new[space_used++] = value;
        max_size=new_max_size;

        delete [] list;
        return list_new;
    }
}

int main() {
    int N = 7;

    //declaring dynamic array allocation
    int* list = new int[N];

    int used = 0, a_val;

    for (int i = 0; i < 11; i++) {
        list=list_add(list, used, N, i);
    }

    cout << endl << "Storlek: " << N << endl << endl;
    cout << "Printar listan " << endl;

    for (int i = 0; i < used; i++) {
        cout << list[i] << ". ";
    }
}

Answer 4

Je m'inquiéterais de cette ligne :

*(list+(max_size-space_used-1)) = value;

et celui-ci :

list_new[i] = i;

Answer 5

Il y a beaucoup de choses à dire sur la façon de résoudre les problèmes, mais ce n'est pas le cas ici.

#include <vector>
#include <iostream>

int main() 
{
    std::vector<int> numbers;

    for (int i = 0; i < 11; i++) {
        numbers.push_back(i);
    }

    for (int i = 0; i < numbers.size(); i++) {
        std::cout << numbers[i] << ". ";
    }

    std::cout << "\n";
}

UPDATE : Comme indiqué ci-dessus dans mon autre réponse Cette fonction contient au moins quatre bogues en 16 lignes. C'est-à-dire un bug pour quatre lignes de code. Et puis il y a les problèmes de conception du code. Par exemple, la taille du tableau et le tableau lui-même devraient être associés. Vous ne pouvez pas garantir autrement que la fonction fonctionne.

Deux des problèmes dans le code (2,4) pourraient être résolus en utilisant un struct contenant le pointeur du tableau et la taille maximale de la structure de données. De cette façon, vous devez passer les deux variables ensemble.