CODEWITHSUNDEEP
c++
abeln
abeln

Reputation: 3759

Sorting a class member with a custom predicate

I have a scenario that looks like this:

#include <algorithm>
using namespace std;

// a "heavy" struct with lots of members
struct B {
  int key;
  // other members  
} 

class A {
  vector<B> bs;
}

I want to sort the bs by their keys. Now, a way I've done this in the past to avoid swapping Bs (since they're rather heavy), is to define a vector of indices and sort the indices instead. This works if bs is not a class member.

e.g.

vector<B> bs;
vector<size_t> indices;

bool pred(size_t i, size_t j) { return bs[i] < bs[j]; }

indices.resize(bs.size());
for (size_t i = 0; i < bs.size(); i++) indices[i] = i;
std::sort(indices.begin(), indices.end(), pred);

However, when bs is a class member, this "technique" fails because the predicate can only take two parameters. In particular, there's no way of passing "this".

I can see three different ways to solve this problem:

Is there any other way of doing this? Thanks!

Upvotes: 0

Views: 1284

Answers (2)

Naveen
Naveen

Reputation: 73443

Assuming that b is in class A and is accessible through a member function called get, you can write a functor like this:

struct Comparator
{
  Compartor(A& a): m_a(a){}
  bool operator()(int i, int j) const
  {
    return m_a.get(i) < m_a.get(j);
  }

 A& m_a;
};

And use it like this:

A a;
std::sort(indices.begin(), indices.end(), Comparator(a));

Upvotes: 1

Mark B
Mark B

Reputation: 96251

If you can write a lightweight swap for B then the problem doesn't really exist: sort will use your lightweight swap.

If that's not an option you could store (smart) pointers to your class in the vector and sort the pointers.

Or make your class use the pimpl idiom and then swap because almost free.

Definitely don't use a global pointer, because sometime someone will want to make this code threadsafe and that global container used for sorting will be a giant thorn in any attempt to multi-thread sorting of these objects.

Upvotes: 1

Related Questions