How to sort the multimap using comparator. It should be reflected in the multimap container
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort pairs
// according to second value
bool cmp(pair<string, int>& a,
pair<string, int>& b)
{
return a.second < b.second;
}
// Function to sort the map according
// to value in a (key-value) pairs
void sort(multimap<string, int>& M)
{
// Declare vector of pairs
vector<pair<string, int> > A;
// Copy key-value pair from Map
// to vector of pairs
for (auto& it : M) {
A.push_back(it);
}
// Sort using comparator function
sort(A.begin(), A.end(), cmp);
// Print the sorted value
for (auto& it : A) {
cout << it.first << ' '
<< it.second << endl;
}
}
// Driver Code
int main()
{
// Declare Map
multimap<string, int> M;
// Given Map
M = { { "GfG", 3 },
{ "To", 2 },
{ "Welcome", 1 } };
// Function Call
sort(M);
cout<<"\n";
for(auto i:M)
{
cout<<i.first<<" "<<i.second<<endl;
}
return 0;
}
This is code I got from Geekforgeeks! I totally understood the concept but I need to know how to sort the map itself if the map is multimap.?
OUTPUT
Welcome 1
To 2
GfG 3
GfG 3
To 2
Welcome 1
Basically the answer has been given in the comments already. I will summarize again and show an alternative.
The background is that we often want to use the properties of an associative container, but later sort it by its value and not by the key.
The unsorted associative containers, like std::unsorted_set, std::unordered_map , std::unordered_multiset and std::unordered_multimap cannot be ordered, as their names say. They are using a hash algorithm to store and retrieve their values.
Please read also in the CPP Reference about STL container.
And, if we look at the sorted associative container, we see that the std::set and the std::multiset do not work with key value pairs and the other two, the std::map and std::multimap have a key and value but are always sorted by their key.
But as said, we often want to have the advantages of an Associative container with a key - value pair and later some sorted-by-the-value data.
This can only be acieved by using 2 container having the needed property. In your above example the data is copied into a std::vector and then sorted. This mechanism can be used always, with any sortable container, by adding a std::pair of key and value to a container. So:
using Pair = std::pair<std::string, int>;
using Conatiner = std::vector<Pair>;
An often needed use case is counting something. For example, counting the letters in a string. This can be really easily achieved with a std::map or std::unordered_map and the sorted by the value using a 2nd container. Please see some example code below:
#include <iostream>
#include <string>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>
// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<char, unsigned int>;
// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;
// Sorted values will be stored in a multiset, because their may be double ranks
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------
// Function to get the rank of letters in a string
Rank getRank(const std::string& str) {
Counter counter;
for (const char c : str) counter[c]++;
return { counter.begin(), counter.end() };
}
// Test / Driver Code
int main() {
if (std::string userString{}; std::getline(std::cin, userString))
for (const auto& [letter, count] : getRank(userString))
std::cout << (int)letter << ' ' << count << ' ';
}
So, we use the property of the std::unordred map as a fast associative container, not sorted by the key, in combination with a std::multiset which will act as a "sorter".
Or, you can take a std::multiset from the beginning. Example:
#include <iostream>
#include <string>
#include <utility>
#include <set>
// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair <std::string, int> ;
// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second<p2.second; } };
using Sorted = std::multiset<Pair, Comp>;
// ------------------------------------------------------------
// Driver Code
int main()
{
Sorted data { { "GfG", 3 }, { "To", 2 }, { "Welcome", 1 } };
for (const auto& [key, value] : data)
std::cout << key << '\t' << value << '\n';
}
Depends of course all on what you want to achieve . . .