Redimensionnement des tableaux - Différence entre deux blocs d'exécution?

Question

J'ai une fonction qui développe un tableau lorsque j'essaie d'ajouter un élément s'il est plein. Lequel des blocs d'exécution est meilleur ou plus rapide?

Je pense que mon deuxième bloc (commenté) peut être faux, car après avoir doublé mon tableau, je reviens vers l'original.

Lors de la création de tableaux, le compilateur recherche-t-il un bloc contigu en mémoire dans lequel il s'insère entièrement? (Sur la pile/tas, je ne comprends pas vraiment lequel, bien qu'il soit important pour moi d'apprendre qu'il est sans importance pour la question réelle.)

Si oui, cela signifie-t-il que l'utilisation du second bloc pourrait potentiellement écraser d'autres informations en écrasant la mémoire adjacente? (Puisque l'original utiliserait 20 blocs de mémoire adjacents, et le dernier 40.)

Ou est-ce que cela signifierait simplement que l'emplacement des éléments dans ma matrice serait divisé, causant de mauvaises performances?

void Grow() 
{ 
    length *= 2; // double the size of our stack 

    // create temp pointer to this double sized array 
    int* tempStack = new int[length]; 

    // loop the same number of times as original size 
    for(int i = 0; i < (length/2); i++) 
    { 
    // copy the elements from the original array to the temp one 
    tempStack[i] = myStack[i]; 
    } 

    delete[] myStack; //delete the original pointer and free the memory 
    myStack = tempStack; //make the original point to the new stack 

    //Could do the following - but may not get contiguous memory block, causing 
    // overwritten >data 
#if 0 
    int* tempStack = myStack; //create temp pointer to our current stack 
    delete[] myStack; //delete the original pointer and free memory 
    myStack = new int[length *= 2]; //delete not required due to new? 
    myStack = tempStack; 
#endif 
} 

Answer 1

Le deuxième bloc ne serait pas accomplir ce que vous voulez du tout.

Lorsque vous faites

myStack = new int[length *= 2]; 

le système renvoie un pointeur à l'endroit où il arrive d'affecter le nouveau tableau plus large. Puis, vous réaffectez myStack à l'ancien emplacement (que vous avez déjà désaffecté!), Ce qui signifie que vous pointez sur une mémoire non allouée (mauvaise!) Et que vous avez perdu le pointeur vers la nouvelle mémoire vous venez d'attribuer (aussi mauvais!).

Modifier: Pour clarifier, votre tableau sera alloué sur le tas . De plus, le (nouveau) pointeur retourné par votre plus grande allocation de tableau (new int[foo]) sera un bloc de mémoire contigu, comme l'ancien, probablement dans un emplacement différent. À moins d'être hors limites, ne vous inquiétez pas de l'écrasement de la mémoire.

Answer 2

Votre deuxième bloc est incorrect en raison de cette séquence:

int* tempStack = myStack; //create temp pointer to our current stack 
delete[] myStack; //delete the original pointer and free memory 

tempStack et MyStack et les deux pointeurs simplement le même bloc de mémoire. Lorsque vous supprimez [] le pointeur sur la deuxième ligne, vous n'avez plus accès à cette mémoire via aucun pointeur. En utilisant la gestion de la mémoire C++, si vous souhaitez agrandir un tableau, vous devez créer un nouveau tableau avant de supprimer l'ancien et de copier les valeurs vous-même. Cela dit, puisque vous travaillez avec POD, vous pouvez utiliser la gestion de la mémoire de style C qui supporte directement la croissance d'un tableau via realloc. Cela peut être un peu plus efficace si le gestionnaire de mémoire se rend compte qu'il peut développer le tampon sans le déplacer (bien que s'il ne peut pas développer le tampon, il se repliera sur la façon dont vous développez votre tableau dans votre premier bloc).

La gestion de la mémoire de style C n'est acceptable que pour les tableaux de POD. Pour les non-POD, vous devez faire la nouvelle technique de tableau/copier/supprimer l'ancien tableau.

Answer 3

Ceci ne répond pas exactement à votre question, mais vous ne devriez pas faire l'un ou l'autre. Généralement new[] ou delete[] devrait être évité en faveur de l'utilisation de std::vector. new[] est difficile à utiliser car il nécessite une gestion de la mémoire explicite (si une exception est levée lors de la copie des éléments, vous devrez intercepter l'exception et supprimer le tableau pour éviter une fuite de mémoire). std::vector prend soin de cela pour vous, augmente automatiquement lui-même, et est susceptible d'avoir une mise en œuvre efficace accordée par le vendeur. Un argument pour utiliser des tableaux explicites est d'avoir un bloc contigu de mémoire qui peut être passé aux fonctions C, mais cela peut également être fait avec std::vector pour toute implémentation non pathologique (et la prochaine version de la norme C++ exiger que toutes les implémentations conformes supportent cela). (Pour référence, voir http://www.gotw.ca/publications/mill10.htm par Herb Sutter, ancien président de la commission des normes ISO C.)

Un autre argument contre std::vector est la bizarrerie avec std::vector<bool>, mais si vous avez besoin que vous pouvez simplement utiliser std::vector<char> ou std::vector<int> à la place. (Voir: http://www.gotw.ca/publications/mill09.htm)