Set vs Hashset en C++

1. Set vs Hashset en C++
2. Définir en C++
3. Jeu de hachage en C++
4. Principales différences entre un ensemble et un hachage en C++
5. Conclusion

Un set en C++ fonctionne comme un conteneur pour stocker des éléments de données et les récupérer chaque fois que nécessaire. De même, un hashset, plus précisément, unordered_set en C++, sert un objectif similaire en tant qu’ensembles d’éléments de données de stockage.

Dans cet article, nous discuterons en détail d’un set et d’un unordered_set.

Set vs Hashset en C++

Un set est un conteneur associatif utilisé pour stocker des éléments de données, alors qu’un unordered_set est également un conteneur associatif utilisé pour stocker des éléments de données pour nos besoins futurs. Alors, en quoi ces deux structures de données sont-elles différentes des vecteurs, cartes et autres objets conteneurs ?

La réponse est simple. Le set et un unordered_set stockent des éléments de données uniques.

Par conséquent, ils n’autorisent pas les éléments en double. Cependant, d’autres structures de données comme les vecteurs et les cartes permettent également le stockage d’éléments en double.

Ces deux structures de données sont présentes dans la bibliothèque de modèles standard C++.

Maintenant, puisque nous expliquons brièvement quand utiliser le set et le unordered_set en C++, comprenons-les maintenant en détail.

Définir en C++

Comme indiqué précédemment, un set est un conteneur associatif qui stocke des éléments de données uniques de manière triée. Cependant, vous pouvez les stocker dans n’importe quel ordre aléatoire, mais dès que vous les récupérez du set, il renverra les éléments de manière triée uniquement.

Par conséquent, un set contient des définitions pour trier les éléments de données cachés de l’utilisateur.

Les sets en C++ sont implémentés sous forme d’arbres de recherche binaire ; par conséquent, ils sont commandés. De plus, la recherche d’un élément prend un temps O(log n).

Voyons comment implémenter un set en C++.

#include <iostream>
#include <set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Production:

1 3 4 6 8 9

Par conséquent, comme vous pouvez le voir dans l’exemple de code ci-dessus, les éléments stockés dans le tableau sont dans un ordre aléatoire et contiennent des éléments en double. Cependant, dès qu’ils sont stockés dans un ensemble s, ils sont triés en interne, et les éléments en double sont également supprimés.

Par conséquent, la sortie est un groupe trié d’éléments sans aucun doublon.

Jeu de hachage en C++

Le unordered_set ou le hashset en C++ signifient tous deux la même chose. Ce unordered_set est également utilisé pour stocker des éléments de données uniques, mais la seule différence entre un set et un unordered_set est qu’un unordered_set n’a pas d’ordre dans lequel les éléments sont stockés tandis que le set stocke les éléments dans l’ordre trié.

Ce unordered_set ne stocke pas non plus les éléments en double. Cependant, ils sont implémentés à l’aide de tables de hachage.

L’élément, également appelé clé, à insérer est haché dans un index de la table de hachage et est stocké à cet index particulier.

Comme les éléments sont stockés dans n’importe quel ordre aléatoire, leur récupération prend un temps O(1), ce qui rend son opération de recherche plus rapide à mettre en œuvre.

Prenons un exemple d’utilisation d’un unordered_set en C++.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  unordered_set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  unordered_set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Production:

1 9 6 3 8 4

Par conséquent, comme vous pouvez le voir dans l’exemple de code ci-dessus, les éléments sont stockés dans n’importe quel ordre aléatoire dans l’ensemble ; cependant, les éléments renvoyés par l’ensemble sont également dans n’importe quel ordre aléatoire, mais il supprime tous les éléments en double et ne renvoie que les éléments uniques à l’utilisateur.

Principales différences entre un ensemble et un hachage en C++

1. Les sets sont utilisés pour stocker les éléments dans l’ordre croissant, alors qu’un unordered_set stocke les éléments sans ordre.
2. Les sets sont implémentés à l’aide des arbres de recherche binaires, tandis qu’un unordered_set est implémenté à l’aide des tables de hachage.
3. L’opération de recherche dans un set prend un temps O(log n) pour rechercher un élément, alors qu’elle prend un temps O(1) pour rechercher un élément dans un unordered_set.
4. Les sets sont inclus dans le fichier d’en-tête #include<set> alors qu’un unordered_set est inclus à l’aide du fichier d’en-tête #include<unordered_set>.

Conclusion

Dans cet article, nous avons abordé un set et un hashset en C++. Ces deux structures de données sont présentes dans la STL C++ et sont utilisées pour stocker des éléments de données uniques.

Cependant, la principale différence entre les deux est qu’un set renvoie un ensemble trié d’éléments, tandis qu’un unordered_set renvoie les éléments de données sans ordre.

Vous pouvez utiliser n’importe lequel des deux, mais l’opération de recherche est plus rapide dans un unordered_set, prenant un temps presque constant pour rechercher un élément ; par conséquent, il est préféré.