sorting vector on 2 parameters

Question

struct bvp{
    unsigned b;
    unsigned v;
    unsigned p;
};

vector bvpVec;

Now I want to sort the vector bvpVec first by b and then by v. I am able to sort using std::sort() using b only. But I am not getting how can I use bvpVec to sort first by b and then by p. E.g. if my vectors are:

(b,v,p)
(1,4,2)
(0,82,0)
(55,1,0)
(0,81,0)
(2,30,0)

Then I want to sort as follows:

(b,v,p)
(0,81,0)
(0,82,0)
(1,4,2)
(2,30,0)
(55,1,0)

Also my vector bvpVec is large, so it will be add on if anyone can suggest any sorting procedure which is faster than std::sort() for my case.

std::sort is pretty much as fast as it gets for most use cases — RedAgito, May 23 '15 at 23:02

Xiaotian Pei · Answer 1 · 2015-05-23T23:07:31.917

you can provide a custom comparison, and pass it to std::sort as the third argument.

bool comp(const bvp& lhs, const bvp& rhs) {
    return lhs.b < rhs.b || (lhs.b == rhs.b && lhs.p < rhs.p);
}

std::sort(bvpVec.begin(), bvpVec.end(), comp);

or you can provide operator< for bvp.

bool operator<(const bvp& lhs, const bvp& rhs) {
    return lhs.b < rhs.b || (lhs.b == rhs.b && lhs.p < rhs.p);
}

std::sort(bvpVec.begin(), bvpVec.end());

if you use C++11, you can even try lambda

std::sort(bvpVec.being(), bvpVec.end(), 
          [](const bvp& lhs, const bvp& rhs) { 
              return lhs.b < rhs.b || (lhs.b == rhs.b && lhs.p < rhs.p);
          });

score 1 · Answer 2 · answered May 23 '15 at 23:04

Use a custom comparator like

bool comp(const bvp& lhs, const bvp& rhs)
{
    return std::tie(lhs.b, lhs.v, lhs.p) < std::tie(rhs.b, rhs.v, rhs.p);
}

std::tie creates a tuple of references, and the operator< sorts tuples in lexicographic order, so the net effect is to sort by b first, then by v, then by p.

score 1 · Accepted Answer · answered May 23 '15 at 23:04

std::sort can do this just fine. You just have to write the comparison function appropriately.

struct bvp{
    unsigned b;
    unsigned v;
    unsigned p;

    bool operator<(bvp const &other) const  { 
        if (b < other.b)
            return true;
        if (b > other.b)
            return false;
        return v < other.v;
    }
};

With that, you just do:

std::vector<bvp> bvpvec;

// ...
std::sort(bvpvec.begin(), bvpvec.end());

As far as optimizing goes, one possibility is to implement the comparison in a separate class:

struct comp { 
    bool operator()(bvp const &a, bvp const &b) const { 
        if (a.b < b.b)
            return true;
        if (a.b > b.b)
            return false;
        return a.v < b.v; 
    }
};

This often assists the compiler in being able to generate inline code for the comparison, eliminating a function call in the inner-most loop of the sort.

std::sort(bvpvec.begin(), bvpvec.end(), comp());

sorting vector on 2 parameters

3 Answers3