Comparison function for sorting std::set>>

Question

I have these structures:

typedef std::pair<unsigned int, std::pair<int, int> > myPair;
typedef std::set< myPair> Graph;

Graph g;

What is the right comparison function for sorting the graph like?

std::sort(g.begin(), g.end(), Cmp());

I tried doing something like this:

struct Cmp{
    bool operator()(const myPair& l, const myPair& r)const{
        return l.second.second < r.second.second;
    }
};

I want the set to be ordered according to the second element of the most inner pair. Is it possible?

a = (std::make_pair(0,std::make_pair(1,1)));
b = (std::make_pair(0,std::make_pair(1,2)));
c = (std::make_pair(0,std::make_pair(1,0)));
d = (std::make_pair(1,std::make_pair(2,0)));

The result would be:

Before the ordering

c = (0,(1,0)), a = (0,(1,1)), b = (0,(1,2)), d = (1,(2,0)

After the ordering

c = (0,(1,0)), d = (1,(2,0), a = (0,(1,1)), b = (0,(1,2))

Question: Is it possible to create the set in this ordering manner?

score 0 · Answer 1 · answered Jan 13 '15 at 14:07

0

You cannot call std::sort on std::set, but you can construct set with predicate.

typedef std::set<myPair, Cmp> Graph;

answered Jan 13 '15 at 14:07

ForEveR

55,233
2
119
133

score 0 · Answer 2 · answered Jan 13 '15 at 14:10

0

You'd need another set with a different predicate. You can't change the sorting algorithm of an existing set.

answered Jan 13 '15 at 14:10

Bartek Banachewicz

38,596
7
91
135

score 0 · Accepted Answer · edited May 23 '17 at 12:27

Your comparison function is a good start. What is missing is "tie resolution". You need to specify what happens when l.second.second == r.second.second, and also what happens when l.second.first == r.second.first:

bool operator()(const myPair& l, const myPair& r)const{
    return (l.second.second < r.second.second) ||
           ((l.second.second == r.second.second) && (l.second.first < r.second.first)) ||
           ((l.second.second == r.second.second) && (l.second.first == r.second.first) && (l.first < r.first)).
}

The first condition comes from your implementation.
The second condition tells what to do when the first-priority items are equal to each other
The third condition tells what to do when both the first-priority and the second-priority items are equal to each other.

In order to use this function for ordering your set, you need to pass it as the second template parameter to std::set. Here is a Q&A explaining how to do it.

Comparison function for sorting std::set>>

3 Answers3