Structures de données

  • Raccourci de la révision : JavaScript/Structures_de_données
  • Titre de la révision : Structures de données
  • ID de la révision : 349747
  • Créé :
  • Créateur : bfn
  • Version actuelle ? Non
  • Commentaire

Contenu de la révision

Tous les langages de programmation ont des structures de données prédéfinies, mais celles-ci diffèrent de l’un à l’autre. Cet article essaye de lister toutes les structures de données prédéfinies en JavaScript ainsi que les propriété qu’ils ont; celles-ci peuvent être utilisées pour construire d’autres structures de données. Quand c’est possible, des comparaisons seront faites avec les autres langages de programmation

Le standard ECMAScript défini six types de données :

  • Number
  • String
  • Boolean
  • Null
  • Undefined
  • Object

Dans les sections suivantes, nous allons voir comment ces types peuvent être utilisés pour représenter des données et combinés pour implémenter des structures de données plus complexes.

Valeurs primitives

Tous les types sauf les objets ont des valeurs immutables. De façon spécifique, les chaînes de caractères sont immutables (c’est le contraire dans le langage C, par exemple). Nous nous référons aux valeurs de ces types comme des « valeurs primitives ». Ceci est expliqué plus en détail dans la section sur les {{ anch("Chaînes_de_caractères") }} ci-dessous.

Booleans, null et undefined

Parmis ces types, quatre constantes sont disponibles : true, false, null, and undefined. Puisque ce sont des constantes, il est impossible de représenter des données riches (ainsi que des structures de données) avec celles-ci.

Nombres

D’après le standard ECMAScript, il y a seulement un seul type de nombre, qui est le "double-precision 64-bit binary format IEEE 754 value", en particulier il n’y a pas de type spécifique pour les entiers. En plus de pouvoir représenter les nombres à virgule flottante, il a plusieurs valeurs symboliques : +Infinity (Infini positif), -Infinity (Infini négatif), and NaN (n’est pas un nombre).

Bien qu’un nombre ne représente souvent que sa valeur, JavaScript possède plusieurs opérateurs binaires. Ceux-ci peuvent être utilisés pour représenter plusieurs valeurs booléennes en utilisant le masquage de bits. Ceci est généralement considéré comme une mauvaise pratique, puisque JavaScript a d’autres moyens de représenter un ensemble de bookéens (comme un tableau de booléens ou un objet avec des valeurs booléennes associées à des propriétés nommées) et que le masquage de bits rend souvent le code plus difficile à lire, comprendre et maintenir. Il peut être nécessaire d’utiliser ce genre de technique peut s’avérer nécessaire dans des environnements critiques, comme lorsque l’on tente de minimiser l’espace de stockage local ou dans des cas extrêmes où chaque bit transmit sur le réseau compte. Cette technique ne devrait être utilisée qu’en dernier recours pour optimiser la taille.

Chaînes de caractères

Contrairement aux langages comme C, les chaînes de caractères sont immutables en JavaScript. Ce qui veut dire qu’une fois qu’une chaîne est créée, il est impossible de la modifier. Cependans, il est possible de créer une autre chaîne basée sur une opération effectuée sur la chaîne originale, par exemple une sous-chaîne de l’original (en prenant des lettres individuelles ou en utilisant String.substr()) ou une conaténation de deux chaînes en utilisant l’opérateur de concaténation (+) ou String.concat().

Attention au « chaîne-typage » !

Il peut être tentant d’utiliser des chaînes de caractères pour représenter des données complexes. Elles ont quelques propriétés intéressantes :

  • Il est facile de construire des chaînes complexes avec la concaténation.
  • Les chaînes de caractères sont faciles à débuger (Ce que l’on voit s’afficher est ce qu’il y a dans la chaîne).
  • Les chaînes de caractères sont les dénominateurs communs de beaucoup d’API (interfaces de programmation), comme les champs de formulaires, les valeurs du stockage local, ou encore les réponses de {{ domxref("XMLHttpRequest") }} quand on utilise responseText, et il peut être tentant de ne travailler qu’avec des chaînes de caractères.

Avec des conventions, il est possible de représenter n’importe quelle structure de données dans une chaîne de catractères. Cela n’en fait pas une bonne idée. Par exemple, avec un séparateur, on peut émuler une liste (même si un tableau serait plus approprié). Malheureusement, quand ce séparateur est utilisé dans un des éléments de la « liste », celle-ci est cassée. Un caractère d’échappement peut être choisi, etc. Tout ceci demande des conventions et devient un cauchemard à maintenir qui n’existe pas quand on choisi le bon outil pour la bonne tâche.

Il est recommandé d’utiliser les chaînes de caractères pour les données textuelles et symboliques, mais de convertir les chaînes et d’utiliser la bonne abstraction pour représenter ces données.

Objets

En JavaScript, les objets peuvent être vus comme des sacs de propriétés. Avec la syntaxe litérales des objets, un ensemble limité de propriétés sont initialisées; ensuite de nouvelles propriétés peuvent être ajoutées et d’autres supprimées. Les valeurs des propriétés peuvent être de n’importe quel type, y compris d’autres objets, ce qui permet de construire des structures de données complexes.

Objets « normaux » et fonctions

Un objet, en JavaScript, est une correspondance entre des clefs et des valeurs. Les clefs sont des chaînes de caractères et les valeurs peuvent être n’importe quoi. Ceci rend l’objet un bon choix pour les tables de hashage. Cependant, il faut faire attention à propos de la pseudo-propriété non-standard __proto__. Dans un environnement qui la supporte, '__proto__' ne permet pas de manipuler une propriété qui porte ce nom, mais le prototype de l’objet. Dans un contexte où on ne sait pas forcément d’ou viens la chaîne de caractères (comme dans un champ de formulaire), il faut faire attention : d’autres ont eu des problèmes avec ça. Dans ce cas, une alternative est d’utiliser une abstraction StringMap.

Les fonction sont des objets réguliers avec la capacité additionnelle de pouvoir être appelées.

Tableaux

Les tableaux sont des objets réguliers pour lesquels il y a  une relation particulière entre les propriétés qui représentent des nombres entiers et la propriété 'length'. De plus, les tableaux héritent de Array.prototype qui permet d’utiliser un certain nombre de fonctions pratiques pour manipuler des tableaux, comme indexOf (chercher une valeur dans un tableau) ou push (ajouter un élément à la fin d’un tableau), etc. Cela fait des tableaux un choix parfait pour représenter des listes ou ensembles d’éléments.

Dates

Pour représenter des dates, le mieux est d’utiliser le type Date prédéfini.

WeakMaps, Maps, Sets

Non standards. Seront très probablement standardisés comme parties du standard ECMAScript 6.

Ces structures de données utilisent des références d’objets comme clefs. Un Set représente un ensemble d’objets, tandis que les WeakMaps et Maps (tables de correspondance) associent une valeur à un objet. La différence entre les deux est que les objets formant les clefs peuvent être énumérés dans le premier cas. Cela permet d’optimiser le ramasse-miettes dans le dernier cas.

On peut implémenter les Maps et Sets en pure ECMAScript 5. Cependant, puisque les objets ne peuvent être comparés (dans le sens de « moins que », par exemple), les performances pour accéder à une clef seront forcément linéaires. Les implémentations natives (dont les WeakMaps) peuvent avoir des performances approximativement linéaires en temps constant.

De manière générale, pour associer des données avec un nœud DOM, on peut ajouter des propriétés directement sur l’objet, ou utiliser les attributes data-*. L’inconvénient est que ces données sont accessibles à n’importe quel script tournant dans le même contexte. Les Maps et WeakMaps permettent d’associer des données à un objet de façon privée.

TypedArrays

Non standard. Sera très probablement standardisé comme partie du standard ECMAScript 6.

Voir aussi

Source de la révision

<p>Tous les langages de programmation ont des structures de données prédéfinies, mais celles-ci diffèrent de l’un à l’autre. Cet article essaye de lister toutes les structures de données prédéfinies en JavaScript ainsi que les propriété qu’ils ont; celles-ci peuvent être utilisées pour construire d’autres structures de données. Quand c’est possible, des comparaisons seront faites avec les autres langages de programmation</p>
<p>Le standard ECMAScript défini six types de données :</p>
<ul>
  <li><span style="background-color:#ffff00;">Number</span></li>
  <li><span style="background-color:#ffff00;">String</span></li>
  <li><span style="background-color:#ffff00;">Boolean</span></li>
  <li><span style="background-color:#ffff00;">Null</span></li>
  <li><span style="background-color:#ffff00;">Undefined</span></li>
  <li><span style="background-color:#ffff00;">Object</span></li>
</ul>
<p>Dans les sections suivantes, nous allons voir comment ces types peuvent être utilisés pour représenter des données et combinés pour implémenter des structures de données plus complexes.</p>
<h2 id="Primitive_values">Valeurs primitives</h2>
<p>Tous les types sauf les objets ont des valeurs immutables. De façon spécifique, les chaînes de caractères sont immutables (c’est le contraire dans le langage C, par exemple). Nous nous référons aux valeurs de ces types comme des « valeurs primitives ». Ceci est expliqué plus en détail dans la section sur les&nbsp;{{ anch("Chaînes_de_caractères") }}&nbsp;<span style="line-height: inherit;">ci-dessous.</span></p>
<h3 id="Booleans.2C_null_and.2C_undefined">Booleans, null et undefined</h3>
<p>Parmis ces types, quatre constantes sont disponibles :&nbsp;<code><span style="background-color:#ffff00;">true</span></code><span style="background-color:#ffff00;">, </span><code><span style="background-color:#ffff00;">false</span></code><span style="background-color:#ffff00;">, </span><code><span style="background-color:#ffff00;">null</span></code><span style="background-color:#ffff00;">, and </span><code><span style="background-color:#ffff00;">undefined</span></code>. Puisque ce sont des constantes, il est impossible de représenter des données riches (ainsi que des structures de données) avec celles-ci.</p>
<h3 id="Numbers">Nombres</h3>
<p>D’après le standard ECMAScript, il y a seulement un seul type de nombre, qui est le "<span style="background-color:#ffff00;">double-precision 64-bit binary format IEEE 754 value"</span>, en particulier il n’y a pas de type spécifique pour les entiers. En plus de pouvoir représenter les nombres à virgule flottante, il a plusieurs valeurs symboliques :&nbsp;<code>+Infinity</code> (Infini positif), <code>-Infinity </code>(Infini négatif), and <code>NaN</code> (n’est pas un nombre).</p>
<p>Bien qu’un nombre ne représente souvent que sa valeur, JavaScript possède plusieurs&nbsp;<a href="/JavaScript/Reference/Operators/Bitwise_Operators" title="en/JavaScript/Reference/Operators/Bitwise_Operators">opérateurs binaires</a>. Ceux-ci peuvent être utilisés pour représenter plusieurs valeurs booléennes en utilisant le&nbsp;<a class="external" href="http://fr.wikipedia.org/wiki/Masque_(informatique)">masquage de bits</a>. Ceci est généralement considéré comme une mauvaise pratique, puisque JavaScript a d’autres moyens de représenter un ensemble de bookéens (comme un tableau de booléens ou un objet avec des valeurs booléennes associées à des propriétés nommées) et que le masquage de bits rend souvent le code plus difficile à lire, comprendre et maintenir. Il peut être nécessaire d’utiliser ce genre de technique peut s’avérer nécessaire dans des environnements critiques, comme lorsque l’on tente de minimiser l’espace de stockage local ou dans des cas extrêmes où chaque bit transmit sur le réseau compte. Cette technique ne devrait être utilisée qu’en dernier recours pour optimiser la taille.</p>
<h3 id="Strings">Chaînes de caractères</h3>
<p>Contrairement aux langages comme C,<span style="background-color:#ffff00;">&nbsp;les chaînes de caractères sont immutables en JavaScript.</span>&nbsp;Ce qui veut dire qu’une fois qu’une chaîne est créée, il est impossible de la modifier. Cependans, il est possible de créer une autre chaîne basée sur une opération effectuée sur la chaîne originale, par exemple une sous-chaîne de l’original (en prenant des lettres individuelles ou en utilisant<span style="line-height: inherit;">&nbsp;</span><a href="/en/JavaScript/Reference/Global_Objects/String/substr" style="line-height: inherit;" title="substr"><code>String.substr()</code></a><span style="line-height: inherit;">) ou une conaténation de deux chaînes en utilisant l’opérateur de concaténation (</span><code style="font-size: 14px; line-height: inherit;">+</code><span style="line-height: inherit;">) ou </span><a href="/en/JavaScript/Reference/Global_Objects/String/concat" style="line-height: inherit;" title="concat"><code>String.concat()</code></a><span style="line-height: inherit;">.</span></p>
<h4 id="Beware_of_.22stringly-typing.22_your_code!">Attention au « chaîne-typage » !</h4>
<p>Il peut être tentant d’utiliser des chaînes de caractères pour représenter des données complexes. Elles ont quelques propriétés intéressantes :</p>
<ul>
  <li>Il est facile de construire des chaînes complexes avec la concaténation.</li>
  <li>Les chaînes de caractères sont faciles à débuger (Ce que l’on voit s’afficher est ce qu’il y a dans la chaîne).</li>
  <li>Les chaînes de caractères sont les dénominateurs communs de beaucoup d’API (interfaces de programmation), comme&nbsp;<a href="/DOM/HTMLInputElement" title="HTMLInputElement">les champs de formulaires</a>, les valeurs du&nbsp;<a href="/Storage" title="Storage">stockage local</a>, ou encore les réponses de {{ domxref("XMLHttpRequest") }} quand on utilise&nbsp;<code>responseText</code>, et il peut être tentant de ne travailler qu’avec des chaînes de caractères.</li>
</ul>
<p>Avec des conventions, il est possible de représenter n’importe quelle structure de données dans une chaîne de catractères. Cela n’en fait pas une bonne idée. Par exemple, avec un séparateur, on peut émuler une liste (même si un tableau serait plus approprié). Malheureusement, quand ce séparateur est utilisé dans un des éléments de la « liste », celle-ci est cassée. Un caractère d’échappement peut être choisi, etc. Tout ceci demande des conventions et devient un cauchemard à maintenir qui n’existe pas quand on choisi le bon outil pour la bonne tâche.</p>
<p>Il est recommandé d’utiliser les chaînes de caractères pour les&nbsp;<span style="background-color:#ffff00;">données textuelles et symboliques</span>, mais de convertir les chaînes et d’utiliser la bonne abstraction pour représenter ces données.</p>
<h2 id="Objects">Objets</h2>
<p>En JavaScript, <span style="background-color:#ffff00;">les objets peuvent être vus comme des sacs de propriétés</span>. Avec la&nbsp;<a href="/en/JavaScript/Guide/Values,_variables,_and_literals#Object_literals" title="en/JavaScript/Guide/Values,_variables,_and_literals#Object_literals">syntaxe litérales des objets</a>, un ensemble limité de propriétés sont initialisées; ensuite de nouvelles propriétés peuvent être ajoutées et d’autres supprimées. Les valeurs des propriétés peuvent être de n’importe quel type, y compris d’autres objets, ce qui permet de construire des structures de données complexes.</p>
<h3 id=".22Normal.22_objects.2C_and_functions">Objets « normaux » et fonctions</h3>
<p>Un objet, en JavaScript, est une&nbsp;<span style="line-height: inherit; background-color: rgb(255, 255, 0);">correspondance entre des clefs et des valeurs</span><span style="line-height: inherit;">. </span><span style="line-height: inherit; background-color: rgb(255, 215, 0);">Les clefs sont des chaînes de caractères</span><span style="line-height: inherit;">&nbsp;et&nbsp;</span><span style="line-height: inherit; background-color: rgb(255, 255, 0);">les valeurs peuvent être n’importe quoi.</span><span style="line-height: inherit;">&nbsp;Ceci rend l’objet un bon choix pour les </span><a class="external" href="http://fr.wikipedia.org/wiki/Table_de_hachage" style="line-height: inherit;">tables de hashage</a><span style="line-height: inherit;">. Cependant, il faut faire attention à propos de la pseudo-propriété non-standard&nbsp;</span><a href="/JavaScript/Reference/Global_Objects/Object/proto" style="line-height: inherit;" title="__proto__">__proto__</a><span style="line-height: inherit;">. Dans un environnement qui la supporte,</span><span style="line-height: inherit; background-color: rgb(255, 255, 0);"> </span><code style="font-size: 14px; line-height: inherit;"><span style="background-color:#ffff00;">'__proto__'</span></code><span style="line-height: inherit; background-color: rgb(255, 255, 0);">&nbsp;ne permet pas de manipuler une propriété qui porte ce nom, mais le prototype de l’objet</span><span style="line-height: inherit;">. Dans un contexte où on ne sait pas forcément d’ou viens la chaîne de caractères (comme dans un champ de formulaire), il faut faire attention : </span><a class="external" href="http://productforums.google.com/forum/#!category-topic/docs/documents/0hQWeOvCcHU" style="line-height: inherit;">d’autres ont eu des problèmes avec ça</a><span style="line-height: inherit;">. Dans ce cas, une alternative est d’utiliser une </span><a class="external" href="http://code.google.com/p/google-caja/source/browse/trunk/src/com/google/caja/ses/StringMap.js?r=4779" style="line-height: inherit;"><span style="background-color:#ffff00;">abstraction StringMap</span></a><span style="line-height: inherit; background-color: rgb(255, 255, 0);">.</span></p>
<p>Les fonction sont des objets réguliers avec la capacité additionnelle de pouvoir être appelées.</p>
<h3 id="Arrays">Tableaux</h3>
<p>Les&nbsp;<a href="/JavaScript/Reference/Global_Objects/Array" title="Array">tableaux</a>&nbsp;sont des <span style="background-color:#ffff00;">objets réguliers</span>&nbsp;pour lesquels il y a &nbsp;<span style="background-color:#ffff00;">une relation particulière entre les propriétés qui représentent des nombres entiers et la propriété 'length'.</span>&nbsp;De plus, les tableaux héritent de <code>Array.prototype</code> qui permet d’utiliser un certain nombre de fonctions pratiques pour manipuler des tableaux, comme&nbsp;<a href="/JavaScript/Reference/Global_Objects/Array/indexOf" title="en/JavaScript/Reference/Global_Objects/Array/indexOf">indexOf</a> (chercher une valeur dans un tableau) ou <a href="/JavaScript/Reference/Global_Objects/Array/push" title="en/JavaScript/Reference/Global_Objects/Array/push">push</a> (ajouter un élément à la fin d’un tableau), etc. Cela fait des tableaux un choix parfait pour représenter des listes ou ensembles d’éléments.</p>
<h3 id="Dates">Dates</h3>
<p>Pour représenter des dates, le mieux est d’utiliser le type <a href="/JavaScript/Reference/Global_Objects/Date" title="en/JavaScript/Reference/Global_Objects/Date">Date</a>&nbsp;prédéfini.</p>
<h3 id="WeakMaps.2C_Maps.2C_Sets">WeakMaps, Maps, Sets</h3>
<p>Non standards. Seront très probablement standardisés comme parties du standard ECMAScript 6.</p>
<p>Ces structures de données utilisent des références d’objets comme clefs. Un <code>Set</code> représente un ensemble d’objets, tandis que les WeakMaps et Maps (tables de correspondance) associent une valeur à un objet. La différence entre les deux est que les objets formant les clefs peuvent être énumérés dans le premier cas. Cela permet d’optimiser le ramasse-miettes dans le dernier cas.</p>
<p>On peut implémenter les Maps et Sets en pure ECMAScript 5. Cependant, puisque les objets ne peuvent être comparés (dans le sens de « moins que », par exemple), les performances pour accéder à une clef seront forcément linéaires. Les implémentations natives (dont les WeakMaps) peuvent avoir des performances approximativement linéaires en temps constant.</p>
<p>De manière générale, pour associer des données avec un nœud DOM, on peut ajouter des propriétés directement sur l’objet, ou utiliser les attributes <code>data-*</code>. L’inconvénient est que ces données sont accessibles à n’importe quel script tournant dans le même contexte. Les Maps et WeakMaps permettent d’associer des données à un objet de façon privée.</p>
<h3 id="TypedArrays">TypedArrays</h3>
<p>Non standard. Sera très probablement standardisé comme partie du standard ECMAScript 6.</p>
<h2 id="See_also">Voir aussi</h2>
<ul>
  <li><a class="link-https" href="https://github.com/nzakas/computer-science-in-javascript/">la collection des structures de données et algorithmes communs en JavaScript de Nicholas Zakas</a></li>
</ul>
Revenir à cette révision