how to sort a std::set using more than one key

Question

I need to copy a set to another one based on more than one key. the keys are used to -collectively- maintain the uniqueness as well as the order of elements in the set.

My class:

class LaneConnector {
public:

    const Lane* getLaneFrom() const {
        return From;
    }
    const Lane* getLaneTo() const {
        return To;
    }

private:

    Lane* From;
    Lane* To;
}

my functor:

struct MyLaneConectorSorter {
  bool operator() (const LaneConnector* rhs, const LaneConnector* lhs) const
  {

    const Lane* a = lhs->getLaneFrom();
    const Lane* b = rhs->getLaneFrom();

    bool key1 = a->getLaneID() < b->getLaneID();
    bool key2 = a->getLaneParent->ID() < b->getLaneParent->ID();
    bool key2 = a->getLaneParent->getParent->ID() < b->getLaneParent->getParent->ID(); 
    //remind you that I NEED the elements to be in ascending order of 
    //getLaneParent->getParent->ID() ,a->getLaneParent->ID() and then a->getLaneID()
    //duplicate elements are the ones which have all three keys same and need to be discarded 
    return (key1 && key2 && key3); //which dont seem to be working
  }
};

and my source and origin sets:

const std::set<LaneConnector*> src = ..... ; //the getter give me a const version
std::set<sim_mob::LaneConnector *, MyLaneConectorSorter> dest;

and how I fill it up:

for(std::set<sim_mob::LaneConnector*>::iterator it = tempLC.begin(); it != tempLC.end(); it++)
{
    dest.insert(*it);//I know I can insert it right at the time of declaration, but keep it like this for now...please 
}

your kind help would be highly appreciated.

It looks like you aren't entirely clear about your ordering. By your definition you could have `A` and `B` where none of `A — BoBTFish, Sep 25 '12 at 08:42
Instead of posting [questions](http://stackoverflow.com/questions/12577571/sort-stdset-using-operator-to-order-the-insertions) after [questions](http://stackoverflow.com/questions/12576763/how-to-sort-a-stdset-with-const-getters), why don't you do a bit of research yourself? I think what you are looking for is [std::multiset](http://www.cplusplus.com/reference/stl/multiset/). — Hindol, Sep 25 '12 at 08:45

Tony Delroy · Answer 1 · 2012-09-25T09:05:12.040

3

You need to prioritorise your key field comparisons... only if the most important field is equal, then you compare the second most important - if that's equal then you compare the third most important etc.. As soon as there's an inequality, you return true or false as appropriate. So, it's not a && operation, it should be ? : or an if-else chain, as in:

return lhs.key1 < rhs.key1 ? true :
       rhs.key1 < lhs.key1 ? false :
       lhs.key2 < rhs.key2 ? true :
       rhs.key2 < lhs.key2 ? false :
       ...
       false;

For the set to operate correctly, you must ensure the keys are never equal - so that last false is never actually used.

edited Sep 25 '12 at 09:05

answered Sep 25 '12 at 08:41

Tony Delroy

102,968
15
177
252

2

If all are equal, you **must** return false as per the contract of `operator<`. – fredoverflow Sep 25 '12 at 08:45
@FredOverflow: interesting - thanks for that and answer updated; regardless, from memory it won't be sufficient to make the `set` work - doesn't the order absolutely need to be deterministic...? – Tony Delroy Sep 25 '12 at 08:54
@TonyDelroy: indeed: `set` needs a binary predicate conforming a 'strict weak ordering', just like `sort` and so on... – xtofl Sep 25 '12 at 08:59
Well, `a < a` is false, that's all there is to it, really. – fredoverflow Sep 25 '12 at 09:07

score 3 · Answer 2 · edited May 23 '17 at 10:24

3

Since getting operator< for multiple tests right is rather hard, I advocate my way of doing this with tuple (in this case with make_tuple instead of tie since we're dealing with temporaries returned from functions):

#include <tuple>

struct MyLaneConectorSorter {
  bool operator() (const LaneConnector* lhs, const LaneConnector* rhs) const
  {
    const Lane* a = lhs->getLaneFrom();
    const Lane* b = rhs->getLaneFrom();
    auto const* pa = a->getLaneParent();
    auto const* pb = b->getLaneParent();

    return std::make_tuple(a->getLaneID(), pa->ID(), pa->getParent()->ID()) < 
           std::make_tuple(b->getLaneID(), pb->ID(), pb->getParent()->ID())
}

This should work and you can get tuple and make_tuple from Boost too, if your compiler doesn't offer them yet.

edited May 23 '17 at 10:24

Community

1
1

answered Sep 25 '12 at 08:52

Xeo

129,499
52
291
397

Yes! and following the DRY motto and the SRP principle, you could make a method to convert the `lhs` to a `tuple`. – xtofl Sep 25 '12 at 11:06
@xtofl: Not necessarily convert, but `get_comparision_tuple` out of the `LaneConnector`. :) – Xeo Sep 25 '12 at 11:09
@Xeo very cool Xeo, anyway, my compiler doesn't support tuple and I have to use boost. When I build the program, it says: error: no match for ‘operator<’ in ‘boost::tuples::make_tuple . any solution to that? – rahman Sep 26 '12 at 08:47
@rahman: For Boost.Tuple, you need to `#include ` for the relational operators to be available. – Xeo Sep 26 '12 at 09:22

score 2 · Answer 3 · answered Sep 25 '12 at 08:49

2

If you have three member foo, bar and baz to compare on, this is a common way to compare them:

return lhs.foo < rhs.foo
    || lhs.foo == rhs.foo && (lhs.bar < rhs.bar
                           || lhs.bar == rhs.bar && lhs.baz < rhs.baz);

Do you see the pattern? ;)

answered Sep 25 '12 at 08:49

fredoverflow

256,549
94
388
662

+1: that's actually the way I usually do it, but thought the more verbose approach in my answer easier for a beginner to follow.... – Tony Delroy Sep 25 '12 at 08:58

score 1 · Answer 4 · answered Sep 25 '12 at 08:42

I have problem understanding your sorting rules, but if the relation is a simple sub-sort than the code should look like this:

if (a->getLaneID() < b->getLaneID())
  return true;
else if (a->getLaneID() == b->getLaneID())
{
  if (a->getLaneParent->ID() < b->getLaneParent->ID())
    return true;
  // etc...
}
return false;

score 1 · Answer 5 · answered Sep 25 '12 at 08:52

Your class MyLaneConnectionSorter has a flaw.

std::set expects a comparison class that can order elements. So your comparison function must provide behaviour similar to less functor or operator<, i.e. either a < b or a > b (which is b < a) or a == b (which is !(a < b) && !(a > b))

If we take your comparison function, it will consider Lanes (6, 5, 4) and (7, 3, 4) (in format (PPID, PID, ID)) to be equal, because neither one is less than another. So you need to compare like this:

if (a->getLaneParent->getParent->ID() < b->getLaneParent->getParent->ID()) return true;
else if (a->getLaneParent->getParent->ID() > b->getLaneParent->getParent->ID()) return false;
else {
    if (a->getLaneParent->ID() < b->getLaneParent->ID()) return true;
    else if (a->getLaneParent->ID() > b->getLaneParent->ID()) return false;
    else {
        return (a->getLaneID() < b->getLaneID());
    }
}

how to sort a std::set using more than one key

5 Answers5