C++ program to sort dictionary by value

There are some data structures called dictionaries available in various computer languages. A special form of faster data structure that stores data according to keys and values ​​is a dictionary. It keeps key-value pairs there so that certain components can be searched quickly by key, almost in real time. Dictionary-like data structures are included in the C STL language standard. This data structure is called "map". map generates key and value pairs of any type (types must be defined before compilation since we are using C). In this section, we will look at how to sort dictionary entries based on their values ​​using C.

Let’s first take a look at how the map data structure is defined. Two of these internal templates are required. The required libraries and syntax are shown below -

Syntax for defining map data structure

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

To use the map data structure in this example, we must import the "map" library. This requires data of type 1 and 2. Type1 represents the data type of the key parameter, while type2 represents the value type. Objects derived from map type classes are called mapVariable. Now let's examine how to organize your map based on these key factors.

Use Vector of Pairs

In this idea, we just create a vector of key-value pairs (a dynamic array, which is another element obtained from the C STL). Then sort by creating a comparison function. The contents are then stored in a map again in sorted format.

algorithm

• Take map M as input

• Define a dynamic array A to store key-value pairs

• For each key-value pair p in M, execute

  • Insert p into A

• Finish

• Sort A by their keys

• Create an empty map newMap

• For each pair of p in A -

  • Insert newMap into p

• Finish

• Return to new map

Example

#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 ); 
}

Output

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

We have already sorted, and if we store the final result in a map, we will not see any difference before and after sorting, because the map data structure saves data in the sorted form of keys most of the time. Here we use vectors to sort based on values. The order can be found if we print them directly from the vector.

Use a set of pairs

You can use another type of data structure, a collection, to sort the key-value pairs in the mapping data structure. Data is kept ordered in a collection data structure. Therefore, after adding elements to the collection, there is no need to sort again. For better understanding, let's look at the algorithm.

algorithm

• Take map M as input

• Define a collection S to store key-value pairs

• For each key-value pair p in M, execute

  • Insert p into S

• Finish

• Create an empty map newMap

• For each pair of p -

  in S

  • Insert newMap into p

• Finish

• Return to new map

Example

#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 ); 
}

Output

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

in conclusion

In this article, we saw two different ways to sort a dictionary data structure (called a map in C) and sort by value. Since map is a hash map, the data of its keys are stored using a hash algorithm. Although the keys are different, the values ​​for different keys may be the same. We use set and vector sorting, where both vectors and sets carry pairing information, and we sort them. Each pairing can be sorted in two different ways. The value type is the second type and the key type is the first.

The above is the detailed content of C++ program to sort dictionary by value. For more information, please follow other related articles on the PHP Chinese website!