How to sort items contained in STL maps

By definition you cannot sort a std::map by value, since a std::map sorts its elements by key.

This posting documents a way to get around this by dumping std::map key-value pairs into a std::vector first, then sorting that std::vector with a less-than functor afterwards

Example 1: mapping between std::pair and double

I use the STL map to create a one-to-one mapping between a pair of link node IDs (using a std::pair) and the weight value connecting these nodes (using a double):

std::map<std::pair<int,int>, double>; link_map;

The first step then is to physically create the mappings:

// Create mapping between node pairs and weights 
link_map[ std::pair<int,int>(0,1) ] = 1.1;
link_map[ std::pair<int,int>(1,2) ] = 0.1;
link_map[ std::pair<int,int>(2,3) ] = 6.2;
link_map[ std::pair<int,int>(3,4) ] = 3.4;
link_map[ std::pair<int,int>(4,5) ] = 5.7;
link_map[ std::pair<int,int>(5,6) ] = 2.2;
link_map[ std::pair<int,int>(0,8) ] = 1.8;  

So that the std::pair node IDs and their respective weights are printed as follows. Notice that since the std::pair is used as the map key, the map items are automatically sorted according to this, not the weight values:

0 1 1.1
0 8 1.8
1 2 0.1
2 3 6.2
3 4 3.4
4 5 5.7
5 6 2.2

Given that for the specfic problem I was working on, I needed some means of obtaining the mappings so that they were sorted according to their weights, not their std::pair key values. One way to do this is not so much try to sort the std::map itself (which you can’t), but to use a function to insert these mappings into a std::vector and sort the std::vector items. An an additional functor which which to define how the items are sorted is also defined:

template<class T>
struct less_second : std::binary_function<T,T,bool>
{
    inline bool operator()( const T& lhs, const T& rhs )
    {
        return lhs.second < rhs.second;
    }
};

// Initialize and sort vector with data_t items from link_map
std::vector<data_t> sorted_edges()
{    
    std::vector< data_t > vec(link_map.begin(), link_map.end());       
    std::sort(vec.begin(), vec.end(), less_second<data_t>());   
    return vec;
}

… As is data_t, an additional typedef used to define the mapping:

typedef std::pair<std::pair<int,int>, double> data_t;

So that when we print out the vector of data_t items, we can see that they are sorted according to the second map parameter (double), and not the std::pair representing node IDs:

1 2 0.1
0 1 1.1
0 8 1.8
5 6 2.2
3 4 3.4
4 5 5.7
2 3 6.2

Full code listing

#include <map>
#include <vector>
#include <iostream>
#include <algorithm>

typedef std::pair<std::pair<int,int>, double> data_t;
std::map<std::pair<int,int>, double> link_map;
std::map<std::pair>int,int>, double>::iterator link_it;

template<class T>
struct less_second : std::binary_function<T,T,bool>
{
    inline bool operator()( const T& lhs, const T& rhs )
    {
        return lhs.second < rhs.second;
    }
};

// Initialize and sort vector with data_t items from link_map
std::vector<data_t> sorted_edges()
{    
    std::vector< data_t > vec(link_map.begin(), link_map.end());       
    std::sort(vec.begin(), vec.end(), less_second<data_t>());   
    return vec;
}

void PrintLinkMap()
{
    std::cout << std::endl;
    for ( link_it  = link_map.begin();
          link_it != link_map.end();
          link_it++ )
    {      
        std::pair<int,int> p = (*link_it).first;
        double weight = (*link_it).second;
        
	std::cout << p.first  << " " << p.second << " "
              << weight   << std::endl;      
    }
}

void PrintSortedEdges( const std::vector<data_t>& vec )
{
    std::vector<data_t>::const_iterator vec_it = vec.begin();
    std::cout << std::endl;
    for ( ; vec_it != vec.end(); vec_it++ )
    {
        std::pair<int,int> p = (*vec_it).first;
        double weight = (*vec_it).second;
        std::cout << p.first  << " " 
                  << p.second << " " 
		  << weight   << std::endl;
    }
}

int main()
{
    // Create mapping between node pairs and weights 
    link_map[ std::pair<int,int>(0,1) ] = 1.1;
    link_map[ std::pair<int,int>(1,2) ] = 0.1;
    link_map[ std::pair<int,int>(2,3) ] = 6.2;
    link_map[ std::pair<int,int>(3,4) ] = 3.4;
    link_map[ std::pair<int,int>(4,5) ] = 5.7;
    link_map[ std::pair<int,int>(5,6) ] = 2.2;
    link_map[ std::pair<int,int>(0,8) ] = 1.8;  

    PrintLinkMap();

    // Sort the mapping according to link weight
    // and return in the form of a vector
    std::vector<data_t> vec = sorted_edges();   

    PrintSortedEdges( vec );

    return 0;
}

Example 2: mapping between object pointer and double

Here is another example, except this time we use a mapping between a pointer to an object and a double value. We use the same generic functor for sorting the vector:

#include <map>  
#include <vector>  
#include <iostream>  
#include <algorithm>  

class A
{
private:
    int data;
public:
    A(const int& d) : data(d) {} 
    int val() const { return data; }
};

typedef std::pair<A*, double> data_a;  
std::map<A*, double> a_map;  
std::map<*, double>::iterator a_it;        
      
template<class T>  
struct less_second : std::binary_function<T,T,bool>  
{  
    inline bool operator()( const T& lhs, const T& rhs )  
    {  
        return lhs.second < rhs.second;  
    }  
};  
      
// Initialize and sort vector with data_t items from link_map  
std::vector<data_a> sort_by_weight()  
{      
    std::vector< data_a > vec(a_map.begin(), a_map.end());         
    std::sort(vec.begin(), vec.end(), less_second<data_a>());     
    return vec;  
}  
      
void Print()  
{  
    std::cout << std::endl;  
    for ( a_it  = a_map.begin();  
          a_it != a_map.end();  
          a_it++ )  
    {        
        A* a = (*a_it).first;  
        double weight = (*a_it).second;                
        std::cout << a->val() << " " << weight << std::endl;        
    }  
}  
      
void PrintSorted( const std::vector<data_a>& vec )  
{  
    std::vector<data_a>::const_iterator vec_it = vec.begin();  
    std::cout << std::endl;  
    for ( ; vec_it != vec.end(); vec_it++ )  
    {  
        A* a = (*vec_it).first;  
        double weight = (*vec_it).second;  
        std::cout << a->val() << " "   
                  << weight   << std::endl;  
    }  
}  
      
int main()  
{  
    // Create mapping between class A objects and doubles
    a_map[ new A(23) ] = 2.1;  
    a_map[ new A(44) ] = 1.2;        
    a_map[ new A(55) ] = 1.1;        
    a_map[ new A(25) ] = 2.2; 
    a_map[ new A(71) ] = 0.2;   

    Print();
      
    // Sort the mapping according to link weight  
    // and return in the form of a vector  
    std::vector<data_a> vec = sort_by_weight();     
      
    PrintSorted( vec );  
      
    return 0;  
} 

Giving the following results, before and after we have sorted the std:map items:

23 2.1
44 1.2
55 1.1
25 2.2
71 0.2

71 0.2
55 1.1
44 1.2
23 2.1
25 2.2

Example 3: mapping between std::string and double

And one more example, this time using mappings between std::strings and doubles:

#include <map>  
#include <vector>  
#include <iostream>  
#include <algorithm>  

typedef std::pair<std::string, double> data_s;  
std::map<std::string, double> s_map;  
std::map<std::string, double>::iterator s_it;  
       
template<class T>  
struct less_second : std::binary_function<T,T,bool>  
{  
    inline bool operator()( const T& lhs, const T& rhs )  
    {  
        return lhs.second < rhs.second;  
    }  
};  
      
// Initialize and sort vector with data_t items from link_map  
std::vector<data_s> sort_by_weight()  
{      
    std::vector< data_s > vec(s_map.begin(), s_map.end());         
    std::sort(vec.begin(), vec.end(), less_second<data_s>());     
    return vec;  
}  
      
void Print()  
{  
    std::cout << std::endl;  
    for ( s_it  = s_map.begin();  
          s_it != s_map.end();  
          s_it++ )  
    {        
        std::string s = (*s_it).first;  
        double weight = (*s_it).second;  
              
        std::cout << s << " " << weight << std::endl;        
    }  
}  
      
void PrintSorted( const std::vector<data_s>& vec )  
{  
    std::vector<data_s>::const_iterator vec_it = vec.begin();  
    std::cout << std::endl;  
    for ( ; vec_it != vec.end(); vec_it++ )  
    {  
        std::string s = (*vec_it).first;  
        double weight = (*vec_it).second;  
        std::cout << s << " "   
                  << weight   << std::endl;  
    }  
}  
      
int main()  
{  
    // Create mapping between classstd::string and doubles
    s_map[ "Matthew" ] = 2.1;  
    s_map[ "Mark" ]    = 1.2;        
    s_map[ "Luke" ]    = 1.1;        
    s_map[ "John" ]    = 2.2; 

    Print();
      
    // Sort the mapping according to link weight  
    // and return in the form of a vector  
    std::vector<data_s> vec = sort_by_weight();     
      
    PrintSorted( vec );  
      
    return 0;  
} 

Giving the following results:

John 2.2
Luke 1.1
Mark 1.2
Matthew 2.1

Luke 1.1
Mark 1.2
Matthew 2.1
John 2.2

Leave a Reply