Using std::sort on vector of pointers to objects

[Joanna_]

Hello again,

I would like to sort an std::vector containing pointers to SampleInCache objects, using the std::sort algorithm. But since the vector contains no objects, but pointers, I can not do that by simply overloading the <-operator of my SampleInCache class.

I tried this :

//adding this to SampleInCache.h

template <>
struct std::greater
{

bool operator()(const SampleInCache* leftVal, const SampleInCache* rightVal) const
{
//The sorting is actually more complex,
//but I first tried sorting only based on the last_time_used member of SampleInCache class
return leftVal->last_time_used < rightVal->last_time_used;
}

};

But then I get this error :
"error C2913: explicit specialization; 'std::greater' is not a specialization of a class template"

Does anyone see what I did wrong ?

Greetings,

Joanna

[matthias_k]

Maybe you wanted to do that:

template<>
struct std::greater<const SampleInCache*>
: public std::binary_function<bool, const SampleInCache*, const SampleInCache*>
{
   ...
};

However, there is a better solution IMHO: Use boost lambda and you will never have to write your own functors again which do the dereferencing:

using boost::lambda;
std::sort( begin, end, *_1 > *_2 );

This will automagically create a functor for you which does the dereferencing and comparison. Look it up on http://www.boost.org/doc/html/lambda.html

[Yves M]

I don't think that you're meant to specialise std::greater. A simple way would be to overload operator < in your class and then use the following template:

template <typename T>
struct pointer_less_than
{
  const bool operator()(const T *a, const T * b) const {
    // check for 0
    if (a == 0) {
      return b != 0; // if b is also 0, then they are equal, hence a is not < than b
    } else if (b == 0) {
      return false;
    } else {
      return *a < *b;
    }
  }
};

// later

std::vector<sometype *> v;

std::sort(v.begin(), v.end(), pointer_less_than<sometype>());

[matthias_k]

Joanna,

if the comparison you do in operator() is more complex, as you stated, it might be better to write a new functor afterall, specialized for your purpose.

struct sample_in_cache_less
: std::binary_function<const SampleInCache&, const SampleInCache&, bool>
{
      bool operator() (const SampleInCache& lhs, const SampleInCache& rhs ) const
      {
               // do your comparison
      }
};

Note that you can still use pointers and boost::lambda, this has the advantage that your functor now works on objects AND pointers to those.

#include <boost/lambda/lambda.hpp>
using namespace boost::lambda;

std::vector<SampleInCache> v1;
// populate v1 ...
std::sort( v1.begin(), v1.end(), sample_in_cache_less() );

// create vector of pointers to objects in v1
std::vector<SampleInCache*> v2( v1.size() );
std::transform( v1.begin(), v1.end(), v2.begin(), &_1 );

// now sort it with your predicate applying to the pointees!
std::sort( v2.begin(), v2.end(), bind( sample_in_cache_less(), *_1, *_2 ) );

The _1 and _2 are placeholders for the arguments passed to your operator(). boost::lambda::bind then creates an adaptor for your functor which will work on pointers. This adaptor (which itself is a functor) is then passed as the predicate function to std::sort.

Hope that helps!

[Joanna_]

Thanks for the reactions.

A simple way would be to overload operator < in your class and then use the following template: ...

I tried out your solution, because of its simplicity. Since I already had overloaded the <-operator in my SampleInCache class, I only had to add this :

//In SampleInCache.cpp
template <SampleInCache>
struct pointer_less_than
{
  const bool operator()(const SampleInCache *a, const SampleInCache * b) const {
    // check for 0
    if (a == 0)
	{
      return b != 0; // if b is also 0, then they are equal, hence a is not < than b
    }
	else if (b == 0) 
	{
      return false;
    }
	else
	{
      return *a < *b;
    }
  }
};


SampleInCache::TestMethod(){
...
//testlist is declared as list<SampleInCache*> testlist;
std::sort(testlist.begin(),testlist.end(),pointer_less_than<SampleInCache>());
...
}

But I get these compile errors (all on the last line "std::sort(....);":

error C2780: 'void std::sort(_RanIt,_RanIt)' : expects 2 arguments - 3 provided
error C2955: 'pointer_less_than' : use of class template requires template argument list
error C2975: 'pointer_less_than' : invalid template argument for 'function-parameter', compile-time evaluatable constant expression expected

Kind regards,

Joanna

[matthias_k]

//In SampleInCache.cpp
template <SampleInCache>
struct pointer_less_than
{
     // <snip>
};

That doesn't make sense. Either you want it to be a normal class, or a template. If it ought to be a template, you have to parametrize its type:

//In SampleInCache.cpp
template <typename T>
struct pointer_less_than
: std::binary_function(bool, const T*, const T*>
{
  const bool operator()(const T *a, const T * b) const {
    // check for 0
    if (a == 0)
	{
      return b != 0; // if b is also 0, then they are equal, hence a is not < than b
    }
	else if (b == 0) 
	{
      return false;
    }
	else
	{
      return *a < *b;
    }
  }
};

However, this approach is bad for several reasons. It you're not proficient with templates, I'm gonna skip this though. One reason is, that the type T provided might be a reference type, and the argument list in your operator() would evaluate to "const Type& *a " and this is illegal. You can only solve this issue using template meta programming, and I doubt you want to deal with that.

So just do as in my example, make your functor a normal class and declare the arguments to be pointers:

struct sample_in_cache_less
: std::binary_function<const SampleInCache*, const SampleInCache*, bool>
{
      bool operator() (const SampleInCache* lhs, const SampleInCache* rhs ) const
      {
               // do your comparison
      }
};

This is always legal, and it's easy.

One note: Don't forget to derive your functor classes from std::binary_function if they take two arguments and from std::unary_function is they take one argument. Those base classes simply provide some necessary typedefs to make your functor what is called an "adaptable binary/unary function", as defined by the C++ standard. This makes sure they will work flawlessly together with STL algorithms.

[matthias_k]

However, this approach is bad for several reasons. It you're not proficient with templates, I'm gonna skip this though. One reason is, that the type T provided might be a reference type, and the argument list in your operator() would evaluate to "const Type& *a " and this is illegal.

If anyone is interested in a solution which avoids these issues, check out this generic adaptor I have written using boost template metaprogramming facilities. It is completely generic, in that it abstracts from e.g. whether a function pointer or a functor is passed, and solves issues arising from type incompatibilities such as the one mentioned above and of course the reference-to-reference problem.
Thanks to the guys from boost, this wasn't such a big deal afterall (god bless them).

It hasn't been tested a lot, so if anyone should stumble over inconsistencies of any kind, please report them to me.

EDIT: Note that this template can do nothing what lambda can't. It's probably only useful if you don't have access to boost::lambda (while on the other hand, this template also uses boost headers, so that's probably a rare case, ah well).