1,105,406 Community Members

Sorting a vector of shared_ptr

Member Avatar
daviddoria
Posting Virtuoso
1,968 posts since Feb 2008
Reputation Points: 334 [?]
Q&As Helped to Solve: 204 [?]
Skill Endorsements: 8 [?]
Featured
 
0
 

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

Member Avatar
pseudorandom21
Practically a Posting Shark
888 posts since Jan 2011
Reputation Points: 166 [?]
Q&As Helped to Solve: 115 [?]
Skill Endorsements: 0 [?]
 
0
 

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)

Member Avatar
Rashakil Fol
Super Senior Demiposter
2,596 posts since Jun 2005
Reputation Points: 982 [?]
Q&As Helped to Solve: 209 [?]
Skill Endorsements: 42 [?]
Team Colleague
 
2
 

> 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.

Member Avatar
daviddoria
Posting Virtuoso
1,968 posts since Feb 2008
Reputation Points: 334 [?]
Q&As Helped to Solve: 204 [?]
Skill Endorsements: 8 [?]
Featured
 
0
 

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?

Member Avatar
mike_2000_17
21st Century Viking
4,084 posts since Jul 2010
Reputation Points: 2,253 [?]
Q&As Helped to Solve: 800 [?]
Skill Endorsements: 73 [?]
Moderator
Featured
Sponsor
 
1
 

>>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.

Member Avatar
Rashakil Fol
Super Senior Demiposter
2,596 posts since Jun 2005
Reputation Points: 982 [?]
Q&As Helped to Solve: 209 [?]
Skill Endorsements: 42 [?]
Team Colleague
 
0
 

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.

Member Avatar
vijayan121
Posting Virtuoso
1,769 posts since Dec 2006
Reputation Points: 1,097 [?]
Q&As Helped to Solve: 329 [?]
Skill Endorsements: 16 [?]
 
0
 

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' ;
}
You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article