.. _prog-e3-references: ********** Références ********** Les références sont un concept fondamental en informatique. Elles permettent de manipuler des données de manière indirecte, de partager des données entre différentes parties d'un programme, et de construire des structures de données complexes. Comprendre les références est essentiel pour tout programmeur, car elles sont omniprésentes les langages de programmation modernes. L'abstraction fondamentale ========================== Un pointeur est une référence vers une donnée. Il permet d'accéder à une valeur située ailleurs en mémoire. L'idée essentielle est que **une variable peut contenir soit une valeur, soit un moyen d'accéder à une autre valeur**. Par exemple ``x = 42`` signifie que la variable ``x`` contient la valeur 42, tandis que ``p → x`` signifie que la variable ``p`` contient une référence (adresse) vers la variable ``x``. .. quiz:: quizz-prog-e3-11-abstraction :title: L'abstraction fondamentale - :quiz:`{"type":"TF","answer":"T"}` Un pointeur est une référence vers une donnée - :quiz:`{"type":"TF","answer":"F"}` Un pointeur contient directement la valeur de la variable qu'il désigne - La notation ``p → x`` signifie que ``p`` contient l':quiz:`{"type":"SC","values":"adresse,valeur,type,taille","answer":"adresse"}` de la variable ``x`` Le modèle des boîtes et des flèches =================================== On peut représenter la mémoire par des boîtes et les références par des flèches. .. figure:: images/prog-e3-11-boites-fleches.drawio.png :alt: SSH keys :align: center .. quiz:: quizz-prog-e3-11-boites :title: Le modèle des boîtes et des flèches - :quiz:`{"type":"TF","answer":"T"}` Dans ce modèle, les références sont représentées par des flèches - Dans ce modèle, les cases mémoire contenant des valeurs sont représentées par des :quiz:`{"type":"SC","values":"boîtes,flèches,graphes,arbres","answer":"boîtes"}` L'opération fondamentale ======================== Un pointeur permet deux opérations : - la lecture c'est à dire accéder à la valeur pointée, souvent exprimée de façon abstraite par ``obtenir(p)`` ; - l'écriture c'est à dire modifier la valeur pointée, souvent exprimée de façon abstraite par ``modifier(p, nouvelle_valeur)``. Un graphe d'objets ================== Une vision moderne consiste à voir la mémoire comme un graphe. .. mermaid:: graph TD A((A)) B((B)) C((C)) A --> B A --> C Les pointeurs sont alors simplement des arêtes du graphe. Cette abstraction permet de décrire des structures de données complexes comme : * listes chaînées ; * arbres ; * graphes ; * objets ; * références Python ; * pointeurs C. .. quiz:: quizz-prog-e3-11-graphe :title: Un graphe d'objets - :quiz:`{"type":"TF","answer":"T"}` Dans la vision graphe, les pointeurs représentent des arêtes - :quiz:`{"type":"TF","answer":"T"}` Les références Python peuvent être représentées comme des arêtes dans un graphe - Parmi les structures de données citées, les listes :quiz:`{"type":"FB","answer":"chaînées","flags":"fuzzy"}` sont un exemple de structure décrite par un graphe d'objets - :quiz:`{"type":"TF","answer":"T"}` Les arbres peuvent également être représentés comme des graphes d'objets L'abstraction "Référence" ========================= Sans jamais parler d'adresse mémoire, on peut définir une abstraction de la notion de référence comme suit : - créer(objet) : crée une référence vers l'objet donné ; - obtenir(ref) : retourne l'objet référencé par la référence donnée ; - modifier(ref, objet) : modifie l'objet référencé par la référence donnée. Cette abstraction fonctionne pour C (pointeurs) et pour Python (références d'objets). .. figure:: images/prog-e3-11-abstraction-reference.drawio.png :alt: L'abstraction référence :align: center .. quiz:: quizz-prog-e3-11-adt :title: L'abstraction référence - :quiz:`{"type":"TF","answer":"T"}` L'abstraction référence fonctionne à la fois pour les pointeurs C et les références Python - :quiz:`{"type":"TF","answer":"F"}` L'abstraction référence nécessite de manipuler des adresses mémoire explicitement - Les 3 opérations de l'abstraction référence sont créer, obtenir et :quiz:`{"type":"FB","answer":"modifier","flags":"fuzzy"}` Les pointeurs C =============== Le rôle majeur des pointeurs est de permettre le partage de données. Ils permettent à plusieurs variables de faire référence à la même donnée, ce qui est essentiel pour construire des structures de données complexes et pour optimiser l'utilisation de la mémoire. Sans référence, ``A possède une copie`` et ``B possède une copie`` seraient les seules options, ce qui rendrait impossible le partage de données. Avec les références, on peut dire que ``A et B font référence à la même donnée``, ce qui permet de construire des structures de données plus complexes et de partager des données entre différentes parties d'un programme. Un des fondements du langage C est la manipulation directe de la mémoire. C'est une vraie particularité du C, car tous les langages de haut niveau comme Java ou Python mettent en oeuvre des mécanismes automatiques de réservation, protection et libération de la mémoire utilisée. La manipulation de la mémoire va nécessiter d'accéder à l'adresse des variables. On se servira pour cela d'un pointeur, une variable particulière qui ne contient pas de valeur mais **l'adresse mémoire** d'une autre variable. L'utilisation des pointeurs est incontournable, elle facilite la programmation dans certains cas, voire est indispensable dans d'autres. .. quiz:: quizz-prog-e3-11-ptrc :title: Les pointeurs C - :quiz:`{"type":"TF","answer":"F"}` En C, la gestion de la mémoire est automatique comme en Java ou Python - :quiz:`{"type":"TF","answer":"T"}` Les pointeurs permettent à plusieurs variables de partager la même donnée - Un pointeur C est une variable qui contient l':quiz:`{"type":"SC","values":"adresse mémoire,valeur entière,type,taille","answer":"adresse mémoire"}` d'une autre variable - :quiz:`{"type":"TF","answer":"T"}` L'utilisation des pointeurs est incontournable en C Le principe ----------- L'idée générale est de ne plus manipuler seulement les valeurs des variables, mais également leur adresse mémoire. On considère le code source suivant, dans lequel deux variables sont déclarées en mémoire : .. code-block:: c :linenos: // pointers.c #include int main() { int b = 4; int* a = &b; return 0; } Dans ce programme : - ``b`` est une variable de type ``int`` (entier) dont la valeur est initialisée à ``4`` ; - ``a`` est une variable de type ``int*`` (pointeur vers un entier) et dont la valeur est initialisée à l'adresse de ``b``. La variable ``a`` contient une valeur particulière qui n'est ni un ``int``, ni un ``double``, ni un ``char``. Il s'agit de l'adresse d'une autre variable. Modifions un peu le code pour afficher les valeurs et les adresses de chacune des deux variables ``a`` et ``b`` : .. code-block:: c :linenos: // pointers.c #include int main() { int b = 4; int* a = &b; printf("b = %d\n", b); // valeur de b printf("&b = %p\n", &b); // adresse de b printf("a = %p\n", a); // valeur de a printf("*a = %d\n", *a); // valeur pointée par a printf("&a = %p\n", &a); // adresse de a return 0; } Observer attentivement ce code, et en particulier - l'emplacement réservé ``%p`` utilisé pour afficher un pointeur (l'adresse d'une variable) (ligne 11) ; - l'opérateur ``&`` permettant d'accéder à l'adresse d'une variable (ligne 11) ; - l'opérateur d'indirection ``*`` utilisé pour accéder au contenu d'un pointeur (ligne 13). .. note:: - l'opérateur ``&`` s'applique à toute variable ; - l'opérateur d'indirection ``*`` n'est valide que si la variable à laquelle il s'applique est un pointeur ; - lorsqu'ils sont chainés, les opérateurs ``&`` et ``*`` s'évaluent de droite à gauche. Ce code produit l'affichage suivant (les adresses mémoires seront différentes sur votre machine) :: b = 4 &b = 0x7ffd1191ca00 a = 0x7ffd1191ca00 *a = 4 &a = 0x7ffd1191c7ac ce qui correspond à la figure ci dessous. .. image:: images/c-06-pointers-fig-01.svg En résumé : - ``b`` est une variable de type ``int`` (entier) située à l'adresse ``0x7ffd1191ca00`` et dont la valeur est ``4`` ; - ``a`` est une variable de type ``int*`` (pointeur vers un entier) située à l'adresse ``0x7ffd1191c7ac`` et dont la valeur est ``0x7ffd1191ca00`` (l'adresse de ``b``). Le contenu de la variable pointée par ``a`` est ``4``. Dans ce qui suit, ``b`` est un ``int`` et ``a`` un pointeur vers ``b``. .. quiz:: quizz-01 :title: Syntaxe des pointeurs Dans ce qui suit, ``b`` est un ``int`` et ``a`` un pointeur vers ``b``. - 01 - L'opérateur d'indirection, utilisé pour récupérer la valeur d'une variable dont on connait le pointeur est :quiz:`{"type":"FB","answer":"*", "size":5}` - 02 - L'opérateur permettant d'obtenir l'adresse d'une variable est :quiz:`{"type":"FB","answer":"&", "size":5}` - 03 - l'expression ``&a`` est valide :quiz:`{"type":"TF","answer":"T"}` - 04 - l'expression ``&b`` est valide :quiz:`{"type":"TF","answer":"T"}` - 05 - l'expression ``*a`` est valide :quiz:`{"type":"TF","answer":"T"}` - 06 - l'expression ``*b`` est valide :quiz:`{"type":"TF","answer":"F"}` - 07 - l'expression ``&*a`` est valide :quiz:`{"type":"TF","answer":"T"}` - 08 - l'expression ``&*a`` fournit l'adresse de ``a`` :quiz:`{"type":"TF","answer":"F"}` - 09 - l'expression ``&*a`` fournit l'adresse de ``b`` :quiz:`{"type":"TF","answer":"T"}` - 10 - l'expression ``&*a`` fournit la valeur de ``a`` :quiz:`{"type":"TF","answer":"T"}` - 11 - l'expression ``&*a`` fournit la valeur de ``b`` :quiz:`{"type":"TF","answer":"F"}` - 12 - l'expression ``&*b`` est valide :quiz:`{"type":"TF","answer":"F"}` - 13 - l'expression ``&*b`` fournit l'adresse de ``a`` :quiz:`{"type":"TF","answer":"F"}` - 14 - l'expression ``&*b`` fournit l'adresse de ``b`` :quiz:`{"type":"TF","answer":"F"}` - 15 - l'expression ``&*b`` fournit la valeur de ``a`` :quiz:`{"type":"TF","answer":"F"}` - 16 - l'expression ``&*b`` fournit la valeur de ``b`` :quiz:`{"type":"TF","answer":"F"}` - 17 - l'expression ``*&a`` est valide :quiz:`{"type":"TF","answer":"T"}` - 18 - l'expression ``*&a`` fournit l'adresse de ``a`` :quiz:`{"type":"TF","answer":"F"}` - 19 - l'expression ``*&a`` fournit l'adresse de ``b`` :quiz:`{"type":"TF","answer":"T"}` - 20 - l'expression ``*&a`` fournit la valeur de ``a`` :quiz:`{"type":"TF","answer":"T"}` - 21 - l'expression ``*&a`` fournit la valeur de ``b`` :quiz:`{"type":"TF","answer":"F"}` - 22 - l'expression ``*&b`` est valide :quiz:`{"type":"TF","answer":"T"}` - 23 - l'expression ``*&b`` fournit l'adresse de ``a`` :quiz:`{"type":"TF","answer":"F"}` - 24 - l'expression ``*&b`` fournit l'adresse de ``b`` :quiz:`{"type":"TF","answer":"F"}` - 25 - l'expression ``*&b`` fournit la valeur de ``a`` :quiz:`{"type":"TF","answer":"F"}` - 26 - l'expression ``*&b`` fournit la valeur de ``b`` :quiz:`{"type":"TF","answer":"T"}` La déclaration -------------- Un pointeur est une variable dont la valeur est l'adresse mémoire d'une autre variable. Comme toute variable dans un programme C elle doit être déclarée avant utilisation. Pour illustrer ça, commentons la ligne 7 du code ci dessus, ce qui a pour effet de ne pas déclarer la variable ``b``. Le compilateur produit un message du type:: pointers.c: In function 'main': pointers.c:7:15: error: 'b' undeclared (first use in this function) 7 | int* a = &b; | ^ pointers.c:7:15: note: each undeclared identifier is reported only once for each function it appears in Analyser toutes les informations fournies par ce message d'erreur. .. quiz:: quizz-02 :title: Message d'erreur - L'erreur de compilation concerne le fichier :quiz:`{"type":"FB","answer":"pointers.c", "size":10}` - L'erreur de compilation concerne la fonction :quiz:`{"type":"FB","answer":"main", "size":5}` - L'erreur de compilation se situe à la ligne :quiz:`{"type":"FB","answer":"7", "size":2}` - On peut localiser la position de l'erreur de compilation sur la ligne :quiz:`{"type":"TF","answer":"T"}` - L'erreur de compilation est due à l'absence d'initialisation :quiz:`{"type":"TF","answer":"F"}` - L'erreur de compilation est due à l'absence de déclaration :quiz:`{"type":"TF","answer":"T"}` La forme générale de déclaration des pointeurs est la suivante:: type *varname; L'astéristique identifie ``varname`` comme un pointeur vers une variable de type ``type``. Pour les types courants : .. code-block:: c int *i; /* pointeur vers un int */ double *d; /* pointeur vers un double */ char *c /* pointeur vers un character */ .. note:: Il y a deux écritures possibles pour la déclaration d'un pointeur. Les deux sont valides, équivalentes et expriment deux façons de voir les choses. Selon le cas, il sera plus signifiant de considérer l'une ou l'autre : - ``int *i;`` exprime le fait que le contenu de ``i`` est un ``int`` ; - ``int* i;`` exprime le fait que ``i`` est un pointeur vers un ``int``. .. quiz:: quizz-prog-e3-11-decl :title: Déclaration d'un pointeur - Dans la déclaration ``int *i``, le symbole ``*`` indique que ``i`` est un :quiz:`{"type":"SC","values":"pointeur,entier,tableau,caractère","answer":"pointeur"}` - :quiz:`{"type":"TF","answer":"T"}` ``int *i`` et ``int* i`` sont deux déclarations équivalentes en C - Le type C pour un pointeur vers un ``double`` s'écrit :quiz:`{"type":"FB","answer":"double[ ]?\*", "flags":"regex","size":8}` Les références en Python ======================== En Python, les variables sont **toujours** des références à des objets. Par exemple : .. code-block:: python a = [1, 2, 3] # 1. la liste [1, 2, 3] est créée en mémoire, 2. la variable a fait référence à cette liste b = a # la variable b fait référence à la même liste que a .. figure:: images/prog-e3-11-espace-variables-objets.drawio.png :alt: Un objet et deux références :align: center Ici, ``a`` et ``b`` font référence au même objet liste. Si on modifie la liste à travers ``a``, la modification est visible à travers ``b`` : .. code-block:: python >>> a = [1, 2, 3] >>> b = a >>> id(a) == id(b) True >>> a.append(4) >>> print(b) [1, 2, 3, 4] Si on veut créer deux structures de données indépendantes, il faut explicitement copier l'objet, ce qui crée deux références vers deux objets distincts. Il y a création d'un nouvel objet, et la variable ``b`` fait référence à ce nouvel objet. Par exemple : .. code-block:: python >>> a = [1, 2, 3] >>> b = a.copy() >>> id(a) == id(b) False >>> a.append(4) >>> print(b) [1, 2, 3] .. figure:: images/prog-e3-11-espace-variables-objets-2.drawio.png :alt: Deux objets et deux références :align: center .. important:: En Python le programmeur n'a accès qu'à l'espace des références. En C, le programmeur a accès à l'espace des références (pointeurs) et à l'espace des objets, ce qui crée une complexité supplémentaire, mais permet de manipuler la mémoire de manière plus fine. .. note:: Il existe du sucre syntaxique pour les références en Python. Ainsi ``b = list(a)`` réalise la même opération que ``a.copy()``. .. note:: La méthode ``copy()`` crée une copie superficielle de la liste. Si la liste contient des objets mutables, les références à ces objets sont copiées, pas les objets eux-mêmes. Pour créer une copie indépendante de tous les objets imbriqués, il faut utiliser ``copy.deepcopy()``. .. note:: Une référence Python a un comportement très proche d'un pointeur C (copie de l'adresse lors de l'affectation, partage du même objet), mais elle ne permet pas l'arithmétique des pointeurs, ne peut pas être déréférencée explicitement (`*`), et sa gestion mémoire est assurée automatiquement par l'interpréteur (comptage de références et ramasse-miettes). .. quiz:: quizz-prog-e3-11-python :title: Les références en Python - :quiz:`{"type":"TF","answer":"F"}` En Python, ``b = a`` crée une copie de l'objet référencé par ``a`` - :quiz:`{"type":"TF","answer":"T"}` Après ``b = a``, l'expression ``id(a) == id(b)`` est vraie - Pour créer une copie indépendante d'une liste, on utilise la méthode :quiz:`{"type":"FB","answer":"copy()","flags":"fuzzy"}` - :quiz:`{"type":"TF","answer":"F"}` La méthode ``copy()`` crée une copie profonde de tous les objets imbriqués - Pour une copie profonde, on utilise :quiz:`{"type":"SC","values":"copy.deepcopy(),copy.copy(),list.deepcopy(),a.deepcopy()","answer":"copy.deepcopy()"}` - :quiz:`{"type":"TF","answer":"F"}` Une référence Python permet l'arithmétique des pointeurs comme en C