Suppression d'un élément de type entier dans un tableau

Version imprimable

30/05/2017, 18h08
free_01_binairy

Suppression d'un élément de type entier dans un tableau
Salut.
J'ai un tableau de type entier. J'aimerais supprimer un élément du tableau et ainsi réduire la taille de celui ci.
J'écris ceci:
Code:

1 2 3 4 int tab[3]= {3,7,3,1}; free(t+3); //ou free(t); //supprimer le premier élément
Je me dis que comme les éléments du tableau se suivent dans la mémoire, on ne peut donc que supprimer le début ou la fin du tableau. Mais cela ne marche pas correctement me semble-t-il selon résultats que j'ai pu avoir après compilation.
Une idée de votre part s'il vous plaît.
Merci
30/05/2017, 19h31
nnovic

Hello!
C'est quoi au juste, "t" ?
30/05/2017, 19h46
dalfab

Citation:

Envoyé par free_01_binairy

Je me dis que comme les éléments du tableau se suivent dans la mémoire, on ne peut donc que supprimer le début ou la fin du tableau.

J'ajoute à ton raisonnement qu'un tableau a une adresse fixe et une taille fixe, on ne peut donc pas non plus supprimer le début ou la fin.
31/05/2017, 03h43
free_01_binairy

Citation:

Envoyé par nnovic

C'est quoi au juste "t"?

C'est la variable tab que je voulais écrire. Juste une erreur de saisie.

Citation:

Envoyé par dalfab

J'ajoute à ton raisonnement qu'un tableau a une adresse fixe et une taille fixe.

Mais le premier élément du tableau est l'adresse du tableau.
Par exemple tab est l'adresse de tab[0] et tab+1 de tab[1] soit le deuxième élément du tableau.Si je n'ai pas tort dans ce raisonnement , il est donc par conséquent possible de modifier les valeurs qui s'y trouvent : ce qui est possible d'ailleurs. Pourquoi on ne peut donc pas les supprimer successivement du début à la fin ou inversement?
J'espère que je me fais comprendre.
Merci.

Un tableau est et reste avec ses caractéristiques de localisations initiales que sont son adresse et son nombre d'éléments. On peut que modifier les valeurs dans un tableau. On peut utiliser une variable supplémentaire qui représente la taille 'utile' d'un tableau, cette variable devra être impérativement plus petite que la taille réelle du tableau.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool ajouter( int tab[] , size_t* p_tailleUtile , size_t tailleMax ) {
   if ( *p_tailleUtile < tailleMax ) {
      tab[*p_tailleUtile] = 0x123456; // on ajoute à la 'fin'
      (*p_tailleUtile)++;
      return true;
   }
   return false; // plus de place!
}
bool enlever( int tab[] , size_t* p_tailleUtile ) {
   if ( *p_tailleUtile > 0 ) {
      (*p_tailleUtile)--;  // on ôte le 'dernier'
      return true;
   }
   return false; // est deja vide!
}
int main() {
    int table[12];
    int tailleUtile = 0;
    for ( int i = 0 ; i < 7 ; ++i )
       ajouter( tab , &tailleUtile , 12 );
    for ( int i = 0 ; i < 3 ; ++i )
       enlever( tab , &tailleUtile );
    // la nouvelle tailleUtile ici est de 7-3 = 4
}

31/05/2017, 09h49
nnovic

Les données d'un tableau sont comme des petits cailloux rangés dans des cases.
Si tu enlève un cailloux de sa case, ben la case est vide, les autres cailloux ne vont pas sauter tous seuls dans la case d'à-côté pour combler l'espace vide. C'est à toi de la faire avec ta main.
Ta main exécute un algorithme: on part de la case vide, on décale la main d'une case, on prend le caillou dans cette case, on le repose dans la case vide, et ainsi de suite...

Il y a une chose qui aurait du t'alerter que tu faisais fausse route: "free" ne peut libérer que la mémoire qui a été allouée par "malloc". Pas de "malloc" => pas de "free".
31/05/2017, 09h59
ternel

Précisons aussi que la notion de vide n'existe pas dans un tableau.
La seule chose qu'on puisse faire, c'est de ne pas utiliser certaines cases.
31/05/2017, 10h38
Médinoc
Pour rajouter sur ce qu'a dit dalfab, une fois qu'on a ça en tête on réalise que pour supprimer un élément, il faut d'abord le mettre en dernier.
Et pour faire ça, la facilité dépend de la réponse à la question "est-ce que l'ordre est important dans le tableau?"
- Si l'ordre n'est pas important, tu peux simplement échanger l’élément à supprimer avec le dernier.
- Mais si l'ordre est important, tu vas devoir décaler les éléments qui suivent vers la gauche (en gros, une permutation circulaire, surtout si on remet l'élément à la fin). Cela peut être fait de manière "naïve" avec des échanges successifs, ou d'une manière plus optimisée via un appel à memmove().
31/05/2017, 11h00
Jipété

Citation:

Envoyé par dalfab

Un tableau est et reste avec ses caractéristiques de localisations initiales que sont son adresse et son nombre d'éléments. On peut que modifier les valeurs dans un tableau. On peut utiliser une variable supplémentaire qui représente la taille 'utile' d'un tableau, cette variable devra être impérativement plus petite que la taille réelle du tableau.

Et pourquoi donc impérativement plus petite ?

Si j'ai un tableau de 7 cases prévu pour représenter les 7 jours de la semaine, la taille utile après remplissage sera de 7, non ? Donc identique à la taille du tableau.

Après, qu'on veuille enlever le dimanche pour ne représenter que les jours ouvrables, oui, ça ramènera la taille utile à 6, mais là on est déjà dans l'utilisation
31/05/2017, 11h48
ternel

"plus petite" fait sûrement référence au fait que pour un tableau de N cases, les indices valables vont de 0 à N-1.

Quand un tableau est alloué dans le tas, on peut désallouer des éléments à la fin avec realloc. Exemple :
Code:

1 2 3 4 5 6 7 8 void bidouillerLeTas() { char* tab = malloc(100); char* tabRaccourci = realloc(tab, 7); // désalloue 93 bytes à la fin printf("Adresse du tableau avant raccourcissement : %p.\n", tab); printf("Adresse du tableau apres raccourcissement : %p.\n", tabRaccourci); free(tabRaccourci); }
Normalement, les deux adresses affichées doivent être égales.
Mais il n'existe pas d'instruction standard qui permet de désallouer des éléments au début d'un tableau alloué dans le tas.

Quand une variable (tableau ou non) est allouée dans la pile, on ne peut pas libérer la mémoire qu'elle occupe tant qu'on n'est pas sorti du bloc. Et, quand on sort du bloc, il n'y a pas d'instruction à appeler pour libérer de la mémoire occupée dans la pile. Le compilateur se débrouille tout seul. Exemple :
Code:

1 2 3 4 5 6 void bidouillerLaPile() { char unByte = 'p'; char tab[3] = {'l', 'u', 'm'}; char encoreUnByte = 'e'; }
Chez moi, si je compile avec GCC 6.3.0 sans optimisation, GCC va stocker dans la pile les variables unByte, tab et encoreUnByte. Pour les allouer, il décale de 16 octets le registre de sommet de pile %rsp. Ensuite, dans 5 octets parmi les 16, il écrit des valeurs qui correspondent à 'p', 'l', 'u', 'm' et 'e'. Enfin, pour désallouer ces variables, le compilateur ne fait que redécaler le registre de sommet de pile de 16 octets dans l'autre sens. Extrait du code assembleur :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 subq $16, %rsp #, .seh_stackalloc 16 .seh_endprologue .loc 1 7 0 movb $112, -1(%rbp) #, unByte .loc 1 8 0 movb $108, -16(%rbp) #, tab movb $117, -15(%rbp) #, tab movb $109, -14(%rbp) #, tab .loc 1 9 0 movb $101, -2(%rbp) #, encoreUnByte .loc 1 11 0 nop addq $16, %rsp #,
Citation:

Envoyé par Jipété

Et pourquoi donc impérativement plus petite ?

Sûrement une petite étourderie de formulation. La taille utile doit être inférieure ou égale à la taille réelle du tableau.

31/05/2017, 13h54
free_01_binairy

Merci
Je voudrais mettre Résolu à discussion. Mais dans le smartphone pas possible. Quelqu'un a une idée de commet le faire pour moi ?

Citation:
Envoyé par Pyramidev
Quand un tableau est alloué dans le tas, on peut désallouer des éléments à la fin avec realloc. Exemple :
Code:

1 2 3 4 5 6 7 8 void bidouillerLeTas() { char* tab = malloc(100); char* tabRaccourci = realloc(tab, 7); // désalloue 93 bytes à la fin printf("Adresse du tableau avant raccourcissement : %p.\n", tab); printf("Adresse du tableau apres raccourcissement : %p.\n", tabRaccourci); free(tabRaccourci); }
Normalement, les deux adresses affichées doivent être égales.
Mais il n'existe pas d'instruction standard qui permet de désallouer des éléments au début d'un tableau alloué dans le tas.
Je conteste cette partie de ton message : aucune garantie n'est offerte à l'utilisateur en ce qui concerne les adresses retournées. C'est entièrement à la discrétion de l'implémentation, en l'occurrence celle du gestionnaire de mémoire. On peut très bien imaginer que celui-ci décide de relocaliser le nouveau, plus petit buffer pour prévenir une potentielle fragmentation, par exemple.

De plus ce morceau de code entraîne un comportement indéfini dû à la consultation du contenu d'un pointeur invalidé ligne 5, si realloc réussit.

31/05/2017, 15h13
Pyramidev

Citation:

Envoyé par Matt_Houston

Je conteste cette partie de ton message : aucune garantie n'est offerte à l'utilisateur en ce qui concerne les adresses retournées. C'est entièrement à la discrétion de l'implémentation, en l'occurrence celle du gestionnaire de mémoire. On peut très bien imaginer que celui-ci décide de relocaliser le nouveau, plus petit buffer pour prévenir une potentielle fragmentation, par exemple.

Au temps pour moi. Je viens de vérifier ce que dit la norme du C11 pour realloc et, en effet, il n'y a pas de garantie, même quand la nouvelle taille du tableau n'est pas plus grande que l'ancienne.

Citation:

Envoyé par Matt_Houston

De plus ce morceau de code entraîne un comportement indéfini dû à la consultation du contenu d'un pointeur invalidé ligne 5, si realloc réussit.

Non. Ma ligne 5 ne fait que consulter la valeur du pointeur tab qui est la valeur retournée par malloc(100). Je ne consulte pas ce vers quoi tab pointe. L'expression realloc(tab, 7) peut invalider ce vers quoi tab pointe, mais ne modifie pas la valeur du pointeur tab.
31/05/2017, 16h23
Matt_Houston

C'est faux dans le cas général : tu n'as pas cette garantie. Dès lors que le pointeur est passé à realloc (si l'appel réussit) ou free, il est invalidé et tu ne peux plus t'en servir autrement qu'en lui affectant une nouvelle valeur. Je ne parle même pas de déréférencement ici !

Le paragraphe 6.2.4.2 de la norme ISO précise :

Citation:

The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.

La durée de vie du bloc alloué ligne 3 se termine ligne 4 (encore une fois si realloc réussit). En remontant chercher la définition d'une « valeur indéterminée », on trouve en 3.19.2.1 :

Citation:

indeterminate value
either an unspecified value or a trap representation

Je ne sais pas s'il existe des couples architecture-implémentation où un pointeur peut contenir une trap representation mais on ne peut de toute manière rien déduire de la consultation d'une valeur par définition indéterminée.

On doit trouver sensiblement la même chose dans la norme C++.
31/05/2017, 19h08
Pyramidev

Tu as encore raison. :cry:

Après avoir fouillé N4296 (draft de C++14), j'ai trouvé un passage similaire dans §3.7.4.2 Deallocation functions :

« If the argument given to a deallocation function in the standard library is a pointer that is not the null pointer value (4.10), the deallocation function shall deallocate the storage referenced by the pointer, rendering invalid all pointers referring to any part of the deallocated storage. Indirection through an invalid pointer value and passing an invalid pointer value to a deallocation function have undefined behavior. Any other use of an invalid pointer value has implementation-defined behavior.³⁸ »

Note 38 : « Some implementations might define that copying an invalid pointer value causes a system-generated runtime fault. »