C++23 : quatre nouveaux conteneurs associatifs

Les quatre conteneurs associatifs std::flat_map, std::flat_multimap, std::flat_set et std::flat_multiset en C++23 sont un simple remplacement des conteneurs associatifs ordonnés std::map, std::multimap, std::set et std::multiset. En C++23, nous les avons pour deux raisons : l’utilisation de la mémoire et les performances.

Publicité

Avec C++23, nous disposons de 12 conteneurs associatifs. Douze? Correct!

• C++98: std::map, std::set, std::multimap et std::multiset
• C++11: std::unordered_map, std::unordered_set, std::unordered_multimap et std::unordered_multiset
• C++23: std::flat_map, std::flat_set, std::flat_multimap et std::flat_multiset

Il est urgent d’adopter une approche systématique. Je vais commencer par les conteneurs associatifs C++98 et C++11.

Conteneurs associatifs

Tous les conteneurs associatifs ont en commun d’associer une clé à une valeur. Par conséquent, on peut obtenir la valeur en utilisant la clé. Les conteneurs associatifs C++98 sont des conteneurs associatifs ordonnés, tandis que les conteneurs associatifs C++11 sont des conteneurs associatifs non ordonnés.

Publicité

Pour classer les conteneurs associatifs, il faut répondre à trois questions simples :

• Les clés sont-elles triées ?
• La clé a-t-elle une valeur associée ?
• Une clé peut-elle apparaître plusieurs fois ?

Le tableau suivant avec 2³ = 8 lignes répond aux trois questions. Je réponds à une quatrième question du tableau. Quelle est la rapidité du temps d’accès dans un cas moyen ?

Je voudrais donner plus d’informations sur les conteneurs associatifs pour comprendre leurs caractéristiques de performances.

Conteneurs associatifs commandés

Les clés des conteneurs associatifs commandés sont ordonnées. Par défaut, la relation la plus petite (<) est utilisée et les conteneurs sont triés par ordre croissant.

Cet ordre a des conséquences intéressantes.

• La clé doit prendre en charge une relation d’ordre.
• Les conteneurs associatifs sont généralement appelés Arbres rouge-noir mis en œuvre. Ce sont des arbres de recherche binaires équilibrés.
• Le temps d’accès à la clé et donc aussi à la valeur est logarithmique.

Le conteneur associatif ordonné le plus couramment utilisé est std::map:

std::map int2String{ 
  {3, "three"}, {2, "two"}, {1, "one"},
  {5, "five"}, {6, "six"}, {4, "four"}, 
  {7, "seven"} };

L’arbre de recherche binaire équilibré peut avoir la structure suivante :

Conteneurs associatifs non ordonnés

L’idée principale des conteneurs associatifs non ordonnés est que la clé est mappée au compartiment à l’aide de la fonction de hachage. La valeur est simplement ajoutée à la clé.

Les conteneurs associatifs non ordonnés stockent leurs clés dans des compartiments. Le compartiment dans lequel la clé va va dépend de la fonction de hachage, qui mappe la clé à un numéro unique. Ce nombre est divisé par le nombre de buckets modulo. Lorsque différentes clés sont mappées sur le même compartiment, cela s’appelle une collision. Une bonne fonction de hachage répartit les clés uniformément. La valeur est simplement liée à la clé.

L’utilisation de la fonction de hachage a des conséquences importantes pour le conteneur associatif non ordonné.

• La fonction de hachage de la clé doit être disponible.
• Les clés doivent prendre en charge la comparaison d’égalité pour gérer les collisions.
• Le temps d’exécution de la fonction de hachage étant constant, le temps d’accès aux clés d’un conteneur associatif non ordonné est constant lorsque les clés sont uniformément réparties.

Selon std::map est std::unordered_map le conteneur associatif non ordonné le plus couramment utilisé.

std::unordered_map str2Int{ 
  {"Grimm",491634333356}, 
  {"Grimm-Jaud", 49160123335}, 
  {"Schmidt",4913333318},
  {"Huber",490001326} };

Le graphique montre comment les clés sont attribuées à leur compartiment à l’aide de la fonction de hachage.

Les quatre conteneurs associatifs std::flat_map, std::flat_multimap, std::flat_set et std::flat_multiset en C++23 sont un simple remplacement des conteneurs associatifs ordonnés std::map, std::multimap, std::set et std::multiset.

Adaptateurs pour conteneurs

Les conteneurs associatifs ordonnés à plat en C++23 partagent la même interface que leurs homologues C++98.

Les conteneurs associatifs ordonnés à plat sont appelés adaptateurs de conteneur car ils nécessitent des conteneurs séquentiels distincts pour leurs clés et leurs valeurs. Ce conteneur séquentiel doit prendre en charge un itérateur à accès aléatoire. Par défaut, un std::vector utilisé, mais aussi un std::array ou un std::deque est possible.

L’extrait de code suivant montre la déclaration de std::flat_map et std::flat_set:

template,
        class KeyContainer = vector, 
        class MappedContainer = vector>
class flat_map;

template, 
         class KeyContainer = vector>
class flat_set;

La raison des conteneurs associatifs ordonnés à plat est la performance.

Comparaison des conteneurs plats commandés et de leurs homologues non plats

Mourir conteneur associatif ordonné plat offrent une durée et une complexité de stockage différentes de celles des conteneurs commandés. Ils occupent moins d’espace de stockage et sont plus rapides à lire que leurs homologues non commandés à plat. Ils fournissent un itérateur avec un accès aléatoire.

Mourir conteneur associatif ordonné non plat améliorer les performances lors de l’insertion ou de la suppression d’un élément. Ils garantissent également que les itérateurs restent valides après l’insertion ou la suppression d’un élément. Ils prennent en charge un itérateur bidirectionnel.

Jusqu’à présent, je ne peux afficher aucun chiffre car aucun compilateur ne prend en charge les conteneurs associatifs ordonnés à plat. Je mettrai à jour mon test de performances “Plus d’amis spéciaux avec std :: map et std :: unordered_map” si std::flat_map est disponible.

Et après?

UN std::mdspan est une vue multidimensionnelle non propriétaire d’une séquence contiguë d’objets. Cette séquence contiguë d’objets peut être un simple tableau C, un pointeur avec une taille, un std::arrayun std::vector ou un std::string être.

(moi)