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):
[code language="cpp"]
std::map<std::pair<int,int>, double>; link_map;
[/code]
The first step then is to physically create the mappings:
[code language="cpp"]
// 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;
[/code]
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:
[code language="text"]
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
[/code]
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:
[code language="cpp"]
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;
}
[/code]
... As is data_t, an additional typedef used to define the mapping:
[code language="cpp"]
typedef std::pair<std::pair<int,int>, double> data_t;
[/code]
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:
[code language="text"]
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
[/code]
Full code listing
[code language="cpp"]
#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;
}
[/code]
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:
[code language="cpp"]
#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;
}
[/code]
Giving the following results, before and after we have sorted the std:map items:
[code language="txt"]
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
[/code]
Example 3: mapping between std::string and double
And one more example, this time using mappings between std::strings and doubles:
[code language="cpp"]
#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;
}
[/code]
Giving the following results:
[code language="txt"]
John 2.2
Luke 1.1
Mark 1.2
Matthew 2.1
Luke 1.1
Mark 1.2
Matthew 2.1
John 2.2
[/code]
Comments
Post a Comment