Sorting a vector of shared_ptr

[daviddoria]

Can anyone explain why I can't sort this vector:

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>
 
struct Test
{
public:
  Test(const unsigned int input) : a(input){}
  int a;
};
 
struct SortFunctor
{
  bool operator()(std::shared_ptr<Test>& object1, std::shared_ptr<Test>& object2)
  {
    return(object1->a < object2->a);
  }
};
 
//////////////////////////
int main (int argc, char *argv[])
{
  srand(time(NULL));
 
  std::vector<std::shared_ptr<Test> > objects;
  std::shared_ptr<Test> object1(new Test(rand()%50));
  objects.push_back(object1);
 
  std::shared_ptr<Test> object2(new Test(rand()%50));
  objects.push_back(object2);
 
  std::sort(objects.begin(), objects.end(), SortFunctor());
 
  return 0;
}

http://ideone.com/LoNoC - it complains "no known conversion for argument 1 from ‘const std::shared_ptr<Test>’ to ‘std::shared_ptr<Test>&’

It works if I changie the functor operator() to be const std::shared_ptr<Test>, but can't you always pass a mutable object to a function expecting a const object?

Thanks,

David

[pseudorandom21]

What version of boost are you using?
It compiles fine for me (the exact code you posted, with some additional include files).

Here, try this (same code):

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <memory>
#include <boost/shared_ptr.hpp>

struct Test
{
public:
  Test(const unsigned int input) : a(input){}
  int a;
};
 
struct SortFunctor
{
  bool operator()(std::shared_ptr<Test>& object1, std::shared_ptr<Test>& object2)
  {
    return(object1->a < object2->a);
  }
};
 
//////////////////////////
int main (int argc, char *argv[])
{
  srand(time(NULL));
 
  std::vector<std::shared_ptr<Test> > objects;
  std::shared_ptr<Test> object1(new Test(rand()%50));
  objects.push_back(object1);
 
  std::shared_ptr<Test> object2(new Test(rand()%50));
  objects.push_back(object2);
 
  std::sort(objects.begin(), objects.end(), SortFunctor());
 
  return 0;
}

Compiled with VS2010 using boost 1.47 (installer on boostpro.com)

[Rashakil Fol]

> It works if I changie the functor operator() to be const std::shared_ptr<Test>, but can't you always pass a mutable object to a function expecting a const object?

Uh, yeah. And your error was that you were trying to pass a const object to a function expecting a non-const reference.

[daviddoria]

pseudorandom21 - I am not using Boost at all, but rather compiling with the gnu-c++0x flag. Also, your compiler must not be very strict if it allows this :).

Rashakil Fol - Oh right, I forgot it was expecting non-const reference, which of course means the object being passed must not be const. However, I guess I don't understand why the object that was getting passed was const?

[mike_2000_17]

>>However, I guess I don't understand why the object that was getting passed was const?

My guess is that the STL implementation of std::sort wraps the "compare" object inside another functor that takes either const-references or const-iterators. So, the only viable options when defining a comparison functor is to use either const-reference or value parameters, which makes sense from a const-correctness point-of-view, a comparison function should not modify its operands. STL uses const-ness pro-actively in these situations, I suggest you do the same.

[Rashakil Fol]

This question could have been answered by just looking at the header file and line numbers of the error.

/// This is a helper function...
  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
			  _RandomAccessIterator __last,
			  const _Tp& __pivot, _Compare __comp)
    {
      while (true)
	{
	  while (__comp(*__first, __pivot))
	    ++__first;
	  --__last;
	  while (__comp(__pivot, *__last))
	    --__last;
	  if (!(__first < __last))
	    return __first;
	  std::iter_swap(__first, __last);
	  ++__first;
	}
    }

You can see that __pivot is const.

[vijayan121]

The IS specifies that a predicate should not assume that the dereferenced iterator yields a non-const object. Arguments should therefore be taken by reference-to-const or by value.

The IS also specifies that algorithms that take function objects as arguments are permitted to copy those function objects. So in most cases, the overloaded function call operator would be a const member function.

struct S { int v ; } ;

struct binary_predicate
{
  bool operator() ( const S& a, const S& b ) const
  { return a.v < b.v ; }
};

If the predicate holds mutable state, it should be suitably wrapped (so that object identity is maintained). For example:

struct S { int v ; } ;

struct predicate_with_state
{
  explicit predicate_with_state() : num_compares(0) {}

  bool operator() ( const S& a, const S& b ) // not const
  { ++num_compares ; return a.v < b.v ; }

  int num_compares ;
};

int main()
{
   std::vector<S> seq = { {6}, {4}, {9}, {1}, {4} } ;
   predicate_with_state predicate ;

   // wrap the predicate in a std::reference_wrapper<>
   std::sort( seq.begin(), seq.end(), std::ref(predicate) ) ;
   std::cout << predicate.num_compares << '\n' ;
}