Programme C++ pour trier le dictionnaire par valeur

Il existe certaines structures de données appelées dictionnaires disponibles dans différents langages informatiques. Une forme spéciale de structure de données plus rapide qui stocke les données en fonction de clés et de valeurs est un dictionnaire. Il y conserve les paires clé-valeur afin que certains composants puissent être recherchés rapidement par clé, presque en temps réel. Les structures de données de type dictionnaire sont incluses dans la norme de langage C++ STL. Cette structure de données est appelée "map". map génère des paires clé et valeur de n'importe quel type (les types doivent être définis avant la compilation puisque nous utilisons C++). Dans cette section, nous verrons comment trier les entrées du dictionnaire en fonction de leurs valeurs en utilisant C++.

Voyons d'abord comment la structure des données cartographiques est définie. Deux de ces modèles internes sont requis. Les bibliothèques et la syntaxe requises sont indiquées ci-dessous -

Syntaxe pour définir la structure des données cartographiques

#include <map>
map<type1, type2> mapVariable;

Pour utiliser la structure des données cartographiques dans cet exemple, nous devons importer la bibliothèque "map". Cela nécessite des données de type 1 et 2. Type1 représente le type de données du paramètre clé, tandis que type2 représente le type de valeur. Les objets dérivés des classes de types de cartes sont appelés mapVariable. Examinons maintenant comment organiser votre carte en fonction de ces facteurs clés.

Utiliser un vecteur de paires

Dans cette idée, nous créons simplement un vecteur de paires clé-valeur (tableau dynamique, qui est un autre élément obtenu à partir de C++ STL). Triez ensuite en créant une fonction de comparaison. Le contenu est ensuite à nouveau stocké dans une carte sous un format trié.

Algorithme

• Prenez la carte M en entrée

• Définissez un tableau dynamique A pour stocker les paires clé-valeur

• Pour chaque paire clé-valeur p dans M, exécutez

  • insérer p dans A

• Fin

• Trier A par leurs clés

• Créer une carte vide newMap

• Pour chaque paire de p dans A -

  • insérera newMap

  dans p

• Fin

• Retour à la nouvelle carte

Exemple

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

// Create a comparator function to perform key-value pair comparison
bool compare ( pair <string, int> &a, pair <string, int> &b ){
   return a.second < b.second;
}
 
//Define sorting function to sort given dictionary or map
map <string, int> sorting( map <string, int> givenMap ){
   vector<pair <string, int> > pairVec;
   map<string, int> newMap;
   
   for ( auto& it : givenMap ) {
      pairVec.push_back( it );
   }
   
   sort( pairVec.begin(), pairVec.end(), compare);
   
   for ( auto& it : pairVec ) {
      cout << "Key: " << it.first << ", value: " << it.second << endl;
      newMap.insert( {it.first, it.second } );
   }
   return newMap;
}

void display( map <string, int>& givenMap ){
   for ( auto& it : givenMap ) {
      cout << "Key: " << it.first << ", value: " << it.second << endl;
   }
}
   
int main(){ 
   map<string, int> givenMap;
   
   givenMap = { { "Three", 3 },
        { "Two", 2 },
        { "Four", 4 },
        { "One", 1 },
        { "Five", 5 }
   };
   
   cout << "Before Sorting: " << endl;
   display( givenMap );
  
   cout << "After Sorting: " << endl;
   givenMap = sorting( givenMap ); 
}

Sortie

Before Sorting: 
Key: Five, value: 5
Key: Four, value: 4
Key: One, value: 1
Key: Three, value: 3
Key: Two, value: 2
After Sorting: 
Key: One, value: 1
Key: Two, value: 2
Key: Three, value: 3
Key: Four, value: 4
Key: Five, value: 5

Nous avons déjà trié, et si nous stockons le résultat final dans une carte, nous ne verrons aucune différence avant et après le tri, car la structure des données de la carte enregistre la plupart du temps les données sous une forme triée par clé. Ici, nous utilisons des vecteurs pour trier en fonction des valeurs. L'ordre peut être trouvé si nous les imprimons directement à partir du vecteur.

Utilisez un ensemble de paires

Vous pouvez utiliser un autre type de structure de données, un ensemble, pour trier les paires clé-valeur dans une structure de données mappée. Les données sont conservées ordonnées dans une structure de données de collection. Par conséquent, après avoir ajouté des éléments à la collection, il n’est pas nécessaire de trier à nouveau. Pour une meilleure compréhension, regardons l'algorithme.

Algorithme

• Prenez la carte M en entrée

• Définissez une collection S pour stocker les paires clé-valeur

• Pour chaque paire clé-valeur p dans M, exécutez

  • Insérez p dans S

• Fin

• Créer une carte vide newMap

• Pour chaque paire p -

  en S

  • insérera newMap

  dans p

• Fin

• Retour à la nouvelle carte

Exemple

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

// Create a comparator function to perform key-value pair comparison
struct compare {
   template <typename T>
   
   bool operator()(const T& a, const T& b) const
   {
      if (a.second != b.second) {
         return a.second < b.second;
      }
      return a.first < b.first;
   }
};

//Define sorting function to sort given dictionary or map
map <string, int> sorting( map <string, int> givenMap ){
   set<pair <string, int>, compare> pairSet( givenMap.begin(), givenMap.end() );
   map<string, int> newMap;
   
   for ( auto& it : givenMap ) {
      pairSet.insert( it );
   }
   
   for ( auto& it : pairSet ) {
      cout << "Key: " << it.first << ", value: " << it.second << endl;
      newMap.insert( {it.first, it.second } );
   }
   return newMap;
}

void display( map <string, int>& givenMap ){
   for ( auto& it : givenMap ) {
      cout << "Key: " << it.first << ", value: " << it.second << endl;
   }
}
   
int main(){ 
   map<string, int> givenMap;
   
   givenMap = { { "Three", 3 },
        { "Two", 2 },
        { "Four", 4 },
        { "One", 1 },
        { "Five", 5 }
   };
   
   cout << "Before Sorting: " << endl;
   display( givenMap );
  
   cout << "After Sorting: " << endl;
   givenMap = sorting( givenMap ); 
}

Sortie

Before Sorting: 
Key: Five, value: 5
Key: Four, value: 4
Key: One, value: 1
Key: Three, value: 3
Key: Two, value: 2
After Sorting: 
Key: One, value: 1
Key: Two, value: 2
Key: Three, value: 3
Key: Four, value: 4
Key: Five, value: 5

Conclusion

Dans cet article, nous avons vu deux manières différentes de trier une structure de données de dictionnaire (appelée map en C++) et de trier par valeur. Puisque map est une carte de hachage, les données de ses clés sont stockées à l'aide d'un algorithme de hachage. Bien que les clés soient différentes, les valeurs des différentes clés peuvent être les mêmes. Nous utilisons le tri par ensembles et par vecteurs, où les vecteurs et les ensembles transportent des informations d'appariement, et nous les trions. Chaque paire peut être triée de deux manières différentes. Le type valeur est le deuxième type et le type clé est le premier.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!