C ++ Fonctions SET non ordonnées
Une table de hachage est utilisée pour construire un ensemble non ordonné où les valeurs sont converties en index de table de hachage pour s'assurer que l'insertion d'une valeur est toujours attribuée au hasard. Le fait est qu'ils fonctionnent assez bien et donnent normalement une opération de recherche de temps constante. Toutes les fonctions de l'ensemble non ordonné nécessitent généralement un temps constant O (1). Bien que, dans la pire situation, ils puissent prendre le temps linéaire O (n) en fonction de l'algorithme de hachage opérationnel.
L'ensemble non ordonné peut inclure des clés de toute nature, qu'ils soient des données prédéfinies ou définies par l'utilisateur. Mais chaque fois que nous déclarons les clés des structures de données définies par l'utilisateur, nous devons donc indiquer la méthode de comparaison utilisée pour comparer les clés.
Différence entre l'ensemble et l'ensemble non ordonné
Un ensemble est une collection ordonnée de clés distinctes. Mais un ensemble non ordonné est une collection de clés qui pourraient être organisées dans n'importe quelle séquence. La mise en œuvre de Set en tant que structure d'arbre équilibrée permet de conserver l'ordre des composants. Les opérations de set ont une complexité de temps O (log n), mais un ensemble non ordonné a un O (1). De nombreuses méthodes sont définies pour l'ensemble non ordonné. Mais les plus populaires sont la taille et la méthode vide pour le stockage, la recherche de la valeur de la clé et l'insertion et la suppression de la configuration. Seules les clés distinctes sont soutenues par l'ensemble non ordonné; Pour les clés en double, un multiset non ordonné peut être utilisé.
Fonctions utilisées pour les ensembles non ordonnés
L'ensemble non ordonné a les méthodes suivantes:
- Insert (): cette fonction ajoute un nouvel élément au conteneur.
- Fonction end (): il renvoie un itérateur qui pointe vers l'élément après la fin.
- COUNT () Fonction: il compte le nombre de fois qu'un élément spécifique apparaît dans un ensemble non ordonné.
- Find () Méthode: il trouve un composant dans l'ensemble.
- Clear () Fonction: Il vide un ensemble non ordonné en supprimant tous ses composants.
- Fonction Cbegin (): il renvoie un itérateur constant correspondant au premier membre de l'ensemble non ordonné.
- Fonction Cend (): il renvoie un itérateur constant avec la dernière valeur de l'ensemble non ordonné.
- Bucket_Size (): Dans un ensemble non ordonné, cette fonction renvoie le nombre total d'éléments présents dans un certain seau.
- Fonction Erase (): il supprime du début à la fin, qu'il s'agisse d'un seul composant ou d'une collection d'articles.
- Fonction size (): il donne au nombre d'éléments de l'ensemble non ordonné.
- Fonction swap (): il vous permet d'échanger les données de deux ensembles non ordonnés.
- Fonction Emplace (): ajoute un élément utilisant cette fonction à un ensemble non ordonné.
- Max_size (): Cette fonction renvoie le plus d'éléments qu'un ensemble non ordonné est capable de maintenir.
- Méthode vide (): il vérifie si un ensemble non ordonné est vide.
- Plage égale: il renvoie une plage avec tous les éléments ayant la valeur prédéterminée comme valeur.
- Hash Method (): Il s'agit d'une méthode unaire qui n'accepte qu'un seul paramètre et construit sa valeur de retour sur une valeur size_t singulière.
- Fonction de réserve (): il est utilisé pour exiger la capacité d'un ensemble non ordonné à modifier.
- Fonction Bucket (): il renvoie le numéro de seau de l'élément.
- Bucket_Count () Fonction: le nombre global de seaux d'un ensemble non ordonné est renvoyé par cette méthode.
- Load_factor (): il renvoie le facteur de capacité qui est fréquemment utilisé pour l'ensemble non ordonné.
- Fonction rehash (): il augmente la gamme de seaux dans l'ensemble non ordonné sur le nombre défini ou plus.
- Max_load_factor (): il renvoie l'indice de capacité de charge ultime que l'ensemble non ordonné peut prendre en charge.
- EMPLAY_HINT () Fonction: Avec l'utilisation d'un indice, il n'ajoute qu'un nouvel élément à un ensemble non ordonné si la valeur ajoutée est distincte.
- Fonction key_eq (): il fournit une valeur booléenne basée sur la comparaison.
L'exécution de différentes fonctions non ordonnées dans le langage C ++ est couverte dans cet article.
Exemple 1:
Le temps de traitement moyen des fonctions find (), insert () et effacer () est constant. Si la clé n'est pas présente dans l'ensemble défini, la méthode find () fournit un itérateur à la fonction fin (); Sinon, il renvoie un itérateur à l'attribut clé. Pour acquérir la clé en faisant référence aux valeurs clés avec l'opérateur *, l'itérateur agit comme un pointeur vers les attributs clés. Ce qui suit est une instance d'une déclaration pour les fonctions find (), insert () et d'itération dans un ensemble non ordonné.
#inclureUtilisation de Namespace Std;
int main()
non ordonné_setstrings;
cordes.insérer ("i");
cordes.insérer ("amour");
cordes.insérer ("à");
cordes.insérer ("jouer");
cordes.insérer ("badminton");
String key = "like";
si (cordes.trouver (clé) == chaînes.fin())
couter<< key << " to explore " <
couter<< "explore " << key <
si (cordes.trouver (clé) == chaînes.fin())
couter<< key << " to explore\n" ;
autre
couter<< "explore " << key <
non commande_set :: iterator i;
pour (i = cordes.commencer(); je != cordes.fin(); i ++)
couter<< (*i) <
Nous incorporons le fichier d'en-tête dans le début de ce code. Ensuite, nous entrons dans l'espace de noms standard en tant que std. Ensuite, nous invoquons la fonction principale (). Dans cette fonction, nous déclarons l'ensemble non ordonné. Ici, nous utilisons un ensemble non ordonné pour organiser les éléments des ensembles. Nous passons la chaîne comme paramètre de la fonction de définition non ordonnée. Ensuite, nous insérons les différentes chaînes dans les ensembles. Nous passons les nombreuses chaînes comme arguments de la fonction insert (). Ensuite, nous spécifions la valeur de la clé en utilisant le mot-clé «clé». La méthode find () est utilisée à l'étape suivante. Cette fonction est appliquée pour trouver la chaîne requise de l'ensemble.
Nous utilisons la méthode fin () pour terminer les chaînes. Cette fonction renvoie l'itérateur chaque fois que la clé n'existe pas dans l'ensemble. La commande «cout» est appliquée pour imprimer l'instruction. Ensuite, nous initialisons à nouveau une valeur pour l'attribut «clé». Nous trouvons la valeur d'un attribut dans la chaîne en utilisant la fonction find () et terminons la chaîne à l'aide de la méthode fin (). Nous appliquons la déclaration «cout» pour afficher le résultat. Nous itérons sur l'ensemble de l'ensemble et imprimons le contenu de l'ensemble en utilisant l'instruction «cout». Nous utilisons la méthode d'ensemble non ordonnée et déclarons l'itérateur comme «I». La boucle «pour» est employée.
Tout d'abord, nous initialisons une variable, puis utilisons la fonction début () pour démarrer la chaîne spécifiée. De plus, nous définissons l'état de la boucle. La fonction fin () est appelée. La valeur de l'itérateur est incrémentée de 1. En fin de compte, l'instruction «cout» est utilisée pour montrer la valeur de l'itérateur.
Exemple 2:
Dans ce cas, nous exécuterons un code dans lequel nous déclarons une liste de valeurs différentes, puis nous trouvons toutes les doublons de cette liste par l'utilisation de la fonction définie non ordonnée.
#inclureUtilisation de Namespace Std;
void printDuplications (int a [], int b)
non ordonné_setIntset;
non commande_setduplicate;
pour (int j = 0; j < b; j++)
if (intset.trouver (a [j]) == intset.fin())
intset.insérer (a [j]);
autre
dupliquer.insérer (a [j]);
couter<< "The list of duplicated elements: ";
non commande_set :: iterator it;
pour (it = duplicate.commencer(); il != dupliquer.fin(); it ++)
couter<< *it << " ";
int main()
int a [] = 11, 30, 42, 21, 94, 35, 11, 77, 62, 89, 94, 35;
int b = sizeof (a) / sizeof (int);
printDuplicate (a, b);
retour 0;
Ici, nous incluons la bibliothèque. À l'étape suivante, nous utilisons l'espace de noms standard en tant que std. Nous utilisons la méthode print () pour afficher la réplique dans le tableau défini par l'utilisation d'un ensemble non ordonné. Nous fournissons un tableau et une variable pour attaquer l'entier comme les arguments de la méthode printduplicate ().
Maintenant, nous déclarons les ensembles non ordonnés pour acquérir et enregistrer les doublons. La fonction de jeu non ordonnée est utilisée. Nous passons l'entier comme son paramètre. Ensuite, nous utilisons une autre fonction SET non ordonnée pour trouver les éléments en double. Ici, nous appliquons la boucle «pour». Nous déclarons une variable de la boucle «pour». Ensuite, nous spécifions la condition. Ensuite, nous augmentons la valeur «J». Nous appelons la fonction find () pour trouver l'élément défini dans le tableau. Nous passons l'élément spécifique comme l'argument de cette fonction. Si l'élément requis est déjà présent dans le tableau, nous insérons cet élément dans l'ensemble en double.
Nous montrons les valeurs dupliquées du tableau en utilisant l'instruction «cout». Nous déclarons la variable «it» de l'itérateur pour l'ensemble non ordonné. La boucle «pour» est appliquée. Ensuite, les méthodes début () et end () sont utilisées dans la boucle «pour». Après cela, nous appelons la fonction principale (). Nous initialisons une variable «A». Ensuite, nous définissons les éléments du tableau et ce tableau est stocké dans une variable «A». Nous trouvons la taille du tableau requis en utilisant la méthode SIZEOF (). Nous passons le tableau comme le paramètre de cette fonction.
Nous divisons la valeur résultante par la taille des entiers. La valeur que nous obtenons après la division est stockée dans une variable «B». Nous affichons les valeurs en double du tableau à l'aide de la méthode printduplicate (). En fin de compte, nous utilisons la commande «return 0».
Exemple 3:
Un élément de données peut être ajouté au conteneur SET non ordonné à l'aide de la fonction de bibliothèque de modèle standard C ++ intégrée - la fonction insert (). Chaque élément d'un ensemble non ordonné a une valeur particulière et n'est ajouté que s'il n'est pas disponible dans l'ensemble. Étant donné que le conteneur utilise plusieurs méthodes de hachage, l'insertion est effectuée automatiquement au point qui remplit de manière optimale l'exigence. En conséquence, la taille du conteneur est considérablement améliorée par le nombre d'articles récupérés.
Paramètres de la méthode insert ():
- Valeur: il définit la valeur qui doit être ajoutée au conteneur.
- Premièrement, dernier: itérateurs qui fournissent une variété de composants. Notez que la plage englobe tous les composants entre le premier élément et le dernier élément, comme celui spécifié par le premier élément mais termine l'élément pointé par le dernier élément.
La méthode renvoie une paire, ayant la paire :: Configrée d'abord à un itérateur faisant référence au nouvel élément mis à jour ou au composant correspondant déjà présent dans l'ensemble. Si un nouvel élément de données est ajouté, la paire :: Le deuxième composant de la paire est ajusté à True; Sinon, il est spécifié comme faux si un élément identique est déjà présent.
Le programme suivant démontre la fonction susmentionnée:
#inclure#inclure
#inclure
Utilisation de Namespace Std;
int main()
non commande_set set = "lundi", "mardi";
String str = "mercredi";
Ensemble.insérer (str);
couter<< "The set of week days is:"
<
couter<< m
<< " ";
couter<
Tout d'abord, nous intégrons les fichiers d'en-tête requis. Le est responsable des fonctionnalités d'entrée et de sortie. Le fichier d'en-tête contient la déclaration des cordes. Le troisième contient tous les ensembles non ordonnés. Nous utilisons l'espace de noms standard comme std. Ensuite, nous commençons le codage à l'intérieur du corps de la fonction principale () après avoir appelé la fonction principale (). Nous utilisons l'ensemble de chaînes non ordonnées.
Ici, nous définissons les éléments de mon set. Nous spécifions les deux jours de la semaine. Maintenant, nous indiquons la valeur de la chaîne que nous voulons être insérée dans l'ensemble requis. Nous insérons cette chaîne en utilisant la méthode insert (). La déclaration «cout» est utilisée pour montrer le texte «L'ensemble des jours de semaine» est ». Nous utilisons à nouveau l'instruction «cout» avant d'entrer dans la commande «return 0». Cette déclaration «cout» imprime tous les noms des jours de la semaine.
Conclusion
L'utilisation des fonctions SET C ++ non ordonnées est couverte dans cet article. Nous avons implémenté les plusieurs codes sur le logiciel Devc ++ où nous avons utilisé de nombreuses fonctions liées aux ensembles non ordonnés. Les ensembles non ordonnés sont des structures de données qui peuvent contenir différents composants dans n'importe quel ordre et fournir un accès efficace à des éléments spécifiques en fonction de leur valeur. Dans le premier cas, nous avons utilisé les multiples fonctions SET non ordonnées pour examiner comment fonctionne le code. En utilisant la méthode find (), nous avons identifié un certain élément dans l'ensemble. À l'aide de la fonction fin (), nous avons terminé l'ensemble non ordonné. Dans la deuxième illustration, nous avons construit un tableau contenant divers entiers. Les valeurs répétées et non répétées sont incluses dans le tableau. Pour trouver les valeurs en double dans le tableau spécifié, nous avons appliqué la méthode find (). La méthode insert () a été utilisée dans le dernier exemple pour ajouter une valeur à l'ensemble non ordonné requis.