19 octobre 2023

Map et Set

Jusqu’à présent, nous avons découvert les structures de données complexes suivantes :

  • Les objets sont utilisés pour stocker des collections de clés.
  • Les tableaux sont utilisés pour stocker des collections ordonnées.

Mais ce n’est pas suffisant pour la vie réelle. C’est pourquoi Map et Set existent également.

Map

Une Map est une collection d’éléments de données saisis, tout comme un Object. Mais la principale différence est que Map autorise les clés de tout type.

Voici les méthodes et les propriétés d’une Map :

Par exemple :

let map = new Map();

map.set('1', 'str1');   // une clé de type chaîne de caractère
map.set(1, 'num1');     // une clé de type numérique
map.set(true, 'bool1'); // une clé de type booléenne

// souvenez-vous, dans un `Object`, les clés sont converties en chaîne de caractères
// alors que `Map` conserve le type d'origine de la clé,
// c'est pourquoi les deux appels suivants retournent des valeurs  :

alert( map.get(1)   ); // 'num1'
alert( map.get('1') ); // 'str1'

alert( map.size ); // 3

Au travers de cet exemple nous pouvons voir, qu’à la différence des Objects, les clés ne sont pas converties en chaîne de caractère. Il est donc possible d’utiliser n’importe quel type.

map[key] n’est pas la bonne façon d’utiliser un Map

Bien que map[key] fonctionne également, par exemple nous pouvons définir map[key] = 2, cela traite map comme un objet JavaScript simple, ce qui implique toutes les limitations correspondantes (uniquement des clés chaîne de caractères/symbol etc.).

Nous devons donc utiliser les méthodes de map : set, get et ainsi de suite.

Map peut également utiliser des objets comme clés.

Par exemple :

let john = { name: "John" };

// pour chaque utilisateur, nous stockons le nombre de visites
let visitsCountMap = new Map();

// john est utilisé comme clé dans la map
visitsCountMap.set(john, 123);

alert( visitsCountMap.get(john) ); // 123

Utiliser des objets comme clés est l’une des fonctionnalités les plus notables et les plus importantes de Map. La même chose ne compte pas pour Object. Une chaîne de caractères comme clé dans Object est très bien, mais nous ne pouvons pas utiliser un autre Object comme clé dans Object.

Essayons de faire comme l’exemple précédent directement avec un Object :

let john = { name: "John" };
let ben = { name: "Ben" };

let visitsCountObj = {}; // on créé notre object

visitsCountObj[ben] = 234; // essayez d'utiliser l'objet ben comme clé
visitsCountObj[john] = 123; // essayez d'utiliser l'objet john comme clé, l'objet ben sera remplacé

// C'est ce qui a été écrit!
alert( visitsCountObj["[object Object]"] ); // 123

Comme visitesCountObj est un objet, il convertit toutes les clés Object, telles que john et ben ci-dessus, en la même chaîne de caractères "[object Object]". Certainement pas ce que nous voulons.

Comment Map compare les clés

Pour tester l’égalité entre les clés, Map se base sur l’algorithme SameValueZero. C’est grosso modo la même chose que l’opérateur de stricte égalité ===, à la différence que NaN est considéré comme étant égal à NaN. NaN peut donc être utilisé comme clé.

Cet algorithme ne peut pas être modifié.

Chaînage

Chaque appel à map.set retourne la map elle-même, ce qui nous permet d’enchaîner les appels :

map.set('1', 'str1')
  .set(1, 'num1')
  .set(true, 'bool1');

Itération dans Map

Il existe 3 façons de parcourir les éléments d’une map :

  • map.keys() – renvoie un itérable pour les clés,
  • map.values() – renvoie un itérable pour les valeurs,
  • map.entries() – renvoie un itérable pour les entrées [key, value], il est utilisé par défaut dans for..of.

Par exemple :

let recipeMap = new Map([
  ['cucumber', 500],
  ['tomatoes', 350],
  ['onion',    50]
]);

// on parcourt les clés (les légumes)
for (let vegetable of recipeMap.keys()) {
  alert(vegetable); // cucumber, tomatoes, onion
}

// on parcourt les valeurs (les montants)
for (let amount of recipeMap.values()) {
  alert(amount); // 500, 350, 50
}

// on parcourt les entries (couple [clé, valeur])
for (let entry of recipeMap) { // équivalent à : recipeMap.entries()
  alert(entry); // cucumber,500 (etc.)
}
L’ordre d’insertion est conservé

Contraitement aux Object, Map conserve l’ordre d’insertion des valeurs.

Il est aussi possible d’utiliser forEach avec Map comme on pourrait le faire avec un tableau :

// exécute la fonction pour chaque couple (key, value)
recipeMap.forEach( (value, key, map) => {
  alert(`${key}: ${value}`); // cucumber: 500 etc.
});

Object.entries: Créer une Map à partir d’un objet

Lorsqu’une Map est créée, nous pouvons passer un tableau (ou un autre itérable) contenant des paires clé/valeur pour l’initialisation, comme ceci :

// tableau de paires [clé, valeur]
let map = new Map([
  ['1',  'str1'],
  [1,    'num1'],
  [true, 'bool1']
]);

alert( map.get('1') ); // str1

Si nous avons un objet simple et que nous souhaitons en créer une Map, nous pouvons utiliser la méthode intégrée Object.entries(obj) qui renvoie un tableau de paires clé/valeur pour un objet exactement dans ce format.

Nous pouvons donc créer une Map à partir d’un objet de la manière suivante :

let obj = {
  name: "John",
  age: 30
};

let map = new Map(Object.entries(obj));

alert( map.get('name') ); // John

Ici, Object.entries renvoie le tableau de paires clé/valeur : [ ["name", "John"], ["age", 30] ]. C’est ce dont a besoin la Map.

Object.fromEntries: Objet à partir d’une Map

Nous venons de voir comment créer une Map à partir d’un objet simple avec Object.entries(obj).

Il existe une méthode Object.fromEntries qui fait l’inverse : étant donné un tableau de paires [clé, valeur], elle crée un objet à partir de ces paires :

let prices = Object.fromEntries([
  ['banana', 1],
  ['orange', 2],
  ['meat', 4]
]);

// maintenant, prices = { banana: 1, orange: 2, meat: 4 }

alert(prices.orange); // 2

Nous pouvons utiliser Object.fromEntries pour obtenir un objet simple à partir d’une Map.

Par exemple, nous stockons les données dans une Map, mais nous devons les transmettre à un code tiers qui attend un objet simple.

Voici comment procéder :

let map = new Map();
map.set('banana', 1);
map.set('orange', 2);
map.set('meat', 4);

let obj = Object.fromEntries(map.entries()); // créer un objet simple (*)

// terminé!
// obj = { banana: 1, orange: 2, meat: 4 }

alert(obj.orange); // 2

Un appel à map.entries() renvoie un itérable de paires clé/valeur, exactement dans le bon format pour Object.fromEntries.

Nous pourrions également raccourcir la ligne (*) :

let obj = Object.fromEntries(map); // .entries() omis

C’est la même chose, car Object.fromEntries attend un objet itérable en argument. Pas nécessairement un tableau. Et l’itération standard pour une map renvoie les mêmes paires clé/valeur que map.entries(). Ainsi, nous obtenons un objet simple avec les mêmes clés/valeurs que la map.

Set

Un Set est une collection de types spéciaux – “ensemble de valeurs” (sans clés), où chaque valeur ne peut apparaître qu’une seule fois.

Ses principales méthodes sont :

  • new Set([iterable]) – crée le set et si un objet iterable est fourni (généralement un tableau), en copie les valeurs dans le set.
  • set.add(value) – ajoute une valeur, renvoie le set lui-même.
  • set.delete(value) – supprime la valeur, renvoie true si value existait au moment de l’appel, sinon false.
  • set.has(value) – renvoie true si la valeur existe dans le set sinon false.
  • set.clear() – supprime tout du set.
  • set.size – c’est le nombre d’éléments.

Ce qu’il faut surtout savoir c’est que lorsque l’on appelle plusieurs fois set.add(value) avec la même valeur, la méthode ne fait rien. C’est pourquoi chaque valeur est unique dans un Set.

Par exemple, nous souhaitons nous souvenir de tous nos visiteurs. Mais chaque visiteurs doit être unique.

Set est exactement ce qu’il nous faut :

let set = new Set();

let john = { name: "John" };
let pete = { name: "Pete" };
let mary = { name: "Mary" };

// visites, certains utilisateurs viennent plusieurs fois
set.add(john);
set.add(pete);
set.add(mary);
set.add(john);
set.add(mary);

// set conserve une fois chaque visiteurs
alert( set.size ); // 3

for (let user of set) {
  alert(user.name); // John (puis Pete et Mary)
}

L’alternative à Set aurait pu être un tableau d’utilisateurs en vérifiant avant chaque insertion que l’élément n’existe pas en utilisant arr.find. Cependant les performances auraient été moins bonnes car cette méthode parcours chaque élément du tableau. Set est beaucoup plus efficace car il est optimisé en interne pour vérifier l’unicité des valeurs.

Parcourir un Set

Nous pouvons parcourir les éléments d’un Set avec for..of ou en utilisant forEach :

let set = new Set(["oranges", "apples", "bananas"]);

for (let value of set) alert(value);

// même chose en utilisant forEach:
set.forEach((value, valueAgain, set) => {
  alert(value);
});

A noter que la fonction de callback utilisée par forEach prend 3 arguments en paramètres : une value, puis la même valeur valueAgain, et enfin le set lui-même.

C’est pour la compatibilité avec Map où le callback forEach passé possède trois arguments. Ça a l’air un peu étrange, c’est sûr. Mais cela peut aider à remplacer facilement Map par Set dans certains cas, et vice versa.

Les méthodes pour parcourir les éléments d’une Map peuvent être utilisées :

  • set.keys() – renvoie un objet itérable pour les valeurs,
  • set.values() – identique à set.keys(), pour compatibilité avec Map,
  • set.entries() – renvoie un objet itérable pour les entrées [value, value], existe pour la compatibilité avec Map.

Résumé

Map – est une collection de valeurs-clés.

Méthodes et propriétés :

  • new Map([iterable]) – crée la map, avec un iterable facultatif (par exemple un tableau) de paires [key, value] pour l’initialisation.
  • map.set(key, value) – stocke la valeur par la clé, renvoie la map elle-même.
  • map.get(key) – renvoie la valeur par la clé, undefined si key n’existe pas dans la map.
  • map.has(key) – retourne true si la key existe, false sinon.
  • map.delete(key) – supprime l’élément par la clé, renvoie true si key existait au moment de l’appel, sinon false.
  • map.clear() – supprime tout de la map.
  • map.size – renvoie le nombre d’éléments actuel.

La différence entre Map avec un objet traditionel :

  • N’importe quel type peut être utilisé comme clé.
  • Accès à des méthodes tels que size.

Set – est une collection de valeurs uniques.

Méthodes et propriétés :

  • new Set([iterable]) – crée le set avec un iterable facultatif (par exemple un tableau) de valeurs pour l’initialisation.
  • set.add(value) – ajoute une valeur (ne fait rien si value existe), renvoie l’ensemble lui-même.
  • set.delete(value) – supprime la valeur, renvoie true si value existait au moment de l’appel, sinon false.
  • set.has(value) – renvoie true si la valeur existe dans l’ensemble, sinon false.
  • set.clear() – supprime tout du set.
  • set.size – c’est le nombre d’éléments.

On ne peut pas dire que les éléments dans une Map ou un Set sont désordonnés car ils sont toujours parcourut par ordre d’insertion. Il est cependant impossible de réorganiser les éléments ou bien de les retrouver par leur index.

Exercices

importance: 5

Disons que arr est un tableau.

Créez une fonction unique(arr) qui devrait renvoyer un tableau avec les éléments uniques d’arr.

Par exemple :

function unique(arr) {
  /* your code */
}

let values = ["Hare", "Krishna", "Hare", "Krishna",
  "Krishna", "Krishna", "Hare", "Hare", ":-O"
];

alert( unique(values) ); // Hare, Krishna, :-O

P.S. Ici, les chaînes de caractères sont utilisées, mais elles peuvent être des valeurs de n’importe quel type.

P.P.S. Utilisez Set pour stocker des valeurs uniques.

Open a sandbox with tests.

function unique(arr) {
  return Array.from(new Set(arr));
}

Ouvrez la solution avec des tests dans une sandbox.

importance: 4

Anagrams sont des mots qui ont le même nombre de mêmes lettres, mais dans un ordre différent.

Par exemple :

nap - pan
ear - are - era
cheaters - hectares - teachers

Ecrivez une fonction aclean(arr) qui retourne un tableau nettoyé des anagrammes.

Par exemple :

let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];

alert( aclean(arr) ); // "nap,teachers,ear" ou "PAN,cheaters,era"

De chaque groupe d’anagrammes ne devrait rester qu’un mot, peu importe lequel.

Open a sandbox with tests.

Pour trouver tous les anagrammes, divisons chaque mot en lettres et trions-les. Lorsque ils sont triés par lettres, tous les anagrammes sont identiques.

Par exemple :

nap, pan -> anp
ear, era, are -> aer
cheaters, hectares, teachers -> aceehrst
...

Nous allons utiliser les variantes triées par lettre comme clés de map pour stocker une seule valeur pour chaque clé :

function aclean(arr) {
  let map = new Map();

  for (let word of arr) {
    // diviser le mot en lettres, les trier et les rejoindre
    let sorted = word.toLowerCase().split('').sort().join(''); // (*)
    map.set(sorted, word);
  }

  return Array.from(map.values());
}

let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];

alert( aclean(arr) );

Le tri des lettres se fait par la chaîne d’appels en ligne (*).

Pour plus de commodité, divisons-le en plusieurs lignes :

let sorted = word // PAN
  .toLowerCase() // pan
  .split('') // ['p','a','n']
  .sort() // ['a','n','p']
  .join(''); // anp

Deux mots différents, 'PAN' et 'nap', reçoivent la même forme de lettre triée 'anp'.

La ligne suivante place le mot dans le map :

map.set(sorted, word);

Si nous rencontrons à nouveau un mot trié de la même manière, il écrasera la valeur précédente avec la même clé dans le map. Nous aurons donc toujours au maximum un mot par lettre.

À la fin Array.from(map.values()) prends un itérable sur les valeurs du Map (nous n’avons pas besoin des clés dans le résultat) et renvoi un tableau avec celles-ci.

Ici, nous pourrions également utiliser un objet simple au lieu du Map, car les clés sont des chaînes de caractères.

Voilà à quoi la solution peut ressembler :

function aclean(arr) {
  let obj = {};

  for (let i = 0; i < arr.length; i++) {
    let sorted = arr[i].toLowerCase().split("").sort().join("");
    obj[sorted] = arr[i];
  }

  return Object.values(obj);
}

let arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];

alert( aclean(arr) );

Ouvrez la solution avec des tests dans une sandbox.

importance: 5

Nous voulons obtenir un tableau de map.keys() dans une variable puis lui appliquer des méthodes spécifiques aux tableaux, par ex: .push.

Mais cela ne fonctionne pas :

let map = new Map();

map.set("name", "John");

let keys = map.keys();

// Error: keys.push is not a function
keys.push("more");

Pourquoi ? Comment pouvons-nous corriger le code pour que keys.push fonctionne ?

C’est parce que map.keys() retourne un itérable, mais pas un tableau.

Nous pouvons le convertir en tableau en utilisant Array.from :

let map = new Map();

map.set("name", "John");

let keys = Array.from(map.keys());

keys.push("more");

alert(keys); // name, more
Carte du tutoriel