CODEWITHSUNDEEP
c++algorithmsortingstl
user8147810
user8147810

Reputation:

Sorting a vector of structs twice

Let's say I have a vector of structs, 

struct foo {
 int num;
 char s;
};

vector<foo> vec;

s can be one of the three values: a, b or c while num can be any positive or negative integer.

What I want is to

first, sort the vector according to num, and then, for each set of repeating values of num, sort them according to s where (a < b < c).

I understand the first step is fairly easy and can be achieved by predicate function, 

bool compare (foo &a, foo &b) {
 if(a.num < b.num) return true;
 else return false;
}

and std::sort(vec.begin(), vec.end(), compare)

What I am stuck at is the second part. To sort repeating values in the vector according to s. I've tried adding another condition in this predicate and creating a separate predicate for another sort step, but I seem to be missing something.

Any help is much appreciated. Thank you!

Upvotes: 1

Views: 113

Answers (3)

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153820

I’m not recommending the approach but you could use two invocations of sort: one sort on the inner elements followed by a stable sort on the outer elements (it is bound to be slower, though):

std::sort(vec.begin(), vec.end(),
          [](foo const& f0, foo const& f1){ return f0.s < f1.s; });
std::stable_sort(vec.begin(), vec.end(),
          [](foo const& f0, foo const& f1){ return f0.num < f1.num; });

Another approach would first sort the elements according to the outer condition and then sort the equal ranges (i.e., equal according to the outer condition) according to the inner condition: 

auto outer_cond = [](foo const& f0, foo const& f1) {
    return f0.num < f1.num;
};

// sort elements according to the outer condition
std::sort(vec.begin(), vec.end(), outer_cond);

for (auto first = vec.begin(); first != vec.end();) {
    // find equal range
    first = std::adjacent_find(first, vec.end(),
                 [](foo const& f0, foo const& f1) { return f0.num == f1.num; });
    auto last = first;
    std::tie(first, last) = std::equal_range(first, vec.end(), *first, outer_cond);

    // sort equal range according to the inner condition
    std::sort(first, last,
              [](foo const& f0, foo const& f1) { return f0.s < f1.s; });

    first = last;
}

However, sorting the entire range with a suitable predicate is probably most efficient.

Upvotes: 1

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

If you want to sort based on num, and if both num values are equal in the predicate, then sort by s, this can be accomplished by using std::tie

#include <tuple>
bool compare (foo &a, foo &b) 
{
   return std::tie(a.num, a.s) < std::tie(b.num, b.s);
}

If you are using a C++ 98 standard compiler and not C++ 11, then the same thing can be accomplished using make_pair

#include <utility>
bool compare (foo &a, foo &b) 
{
   return std::make_pair(a.num, a.s) < std::make_pair(b.num, b.s);
}

My preference, if available, is std::tie over using std::make_pair. The reason is that if you add a third member to your struct, and you want to sort on this new member if both num and s are equal, the code using std::tie is easier to update, as make_pair only works for two values:

#include <tuple>
bool compare (foo &a, foo &b) 
{
   return std::tie(a.num, a.s, a.something_else) < std::tie(b.num, b.s, b.something_else);
}

Upvotes: 2

Rahul Gurnani
Rahul Gurnani

Reputation: 194

You can modify your sort function to something like :

    bool compare (foo &a, foo &b) {
       if(a.num < b.num) return true;
       else if(a.num == b.num) return a.s < b.s;

       return false;
    }

Upvotes: 3

Related Questions