[boost] Re: Sorting list < shared_ptr < foo > > using std::list::sort()

From: Heath Davis (1heathdavis_at_[hidden])
Date: 2003-04-24 10:32:33

Bravo!!! This is a truly novel approach!  I agree that the 
shared_ptr::operator< is meaningless.  If boost wishes to claim STL 
compatibility, container functions should be allowed to operate directly 
on the base level objects, rendering smart pointers completely 
transparent.  Proper functionality would then be defined as:

The order of any given STL container will be predictable and definite 
following any given STL container operation. The resulting order of an 
operation against any "std::some_container < object >" would then be 
identical to the resulting order of the same operation against 
"std::some_container < boost::some_smart_pointer < object > >".  No 
special preparation will be required on behalf of object beyond that of 
being directly containable by STL.  Otherwise stated, if object works 
correctly in STL containers, nothing intrusive must be done to object to 
make it compatible with boost, nor will any exteral "helper" functions 
be required to make "boost::some_smart_pointer" transparent.

If your sortable_ptr class brings boost in that direction, then I thank 
you for addressing this issue.

>> I have experienced some difficulty with sorting lists of type:
>>
>> list < shared_ptr < foo > >
>>
> 
> For a while I have been toying with the idea of a smart pointer called 
> sortable_ptr, which would behave in the way that [I believe that] the 
> original poster erroneously presumed that boost::shared_ptr already did. 
>  I was originally planning to do some more practical testing of the 
> concept before possibly submitting it as a proposal to Boost, but since 
> the topic has now been raised, I will take the opportunity to get some 
> feedback as to whether the idea is sound, or if I have missed something 
> crucial.
> 
> The following is an extract from the draft documentation I have been 
> writing.
> 
> - - - -
> 
> The class sortable_ptr is publicly derived from boost::shared_ptr, but 
> defines the comparison operator < (and its siblings >, <=, and >= ) to 
> make a comparison of the actual objects.  This means that if the class 
> myclass has operator< defined, we can write
> 
> sortable_ptr<myclass> aptr(new myclass(/* Something */));
> sortable_ptr<myclass> bptr(new myclass(/* Something else*/));
> assert((aptr < bptr) == (*aptr < *bptr));
> 
> This is different from boost::shared_ptr, which does only define the < 
> operator to do a direct comparison of the pointers themselves (or 
> something to that effect).
> 
> The == and != operators retain the semantics that they inherited from 
> boost::shared_ptr, which is to test the pointers themselves for 
> identity.  This means that even if neither aptr < bptr nor aptr > bptr 
> is true for two sortable_ptr pointers, the expression aptr == bptr may 
> or may not be true.  If it is true this will mean that both aptr and 
> bptr refer to the same myclass object, which of course is neither less 
> than or greater than itself.  If the expression aptr == bptr is false, 
> it will mean that aptr and bptr point at different objects that are 
> equivalent as to their sort order.
> 
> What is the advantage of this?
> 
> Before answering that question, we note that we have at leas not done 
> anything illegal by introducing these definitions.  Neither 
> boost::shared_ptr nor sortable_ptr support the notion of pointer 
> arithmetic, so we do not need the < operator to be defined in any 
> particular way for that purpose.
> 
> We can still store sortable_ptr pointers in any of the sequence 
> containers in the Standard Template Library, since these only demand 
> that the == operator tests for proper identity between the objects that 
> are being stored in the list or deque or vector, which it does.
> The sort algorithms in STL use the < operator of the objects in the 
> container by default, so if we sort a container of sortable_ptr 
> pointers, they will appear in the same order as the objects themselves 
> would have been sorted.  For vectors and deques it can be considerably 
> faster to sort pointers rather than the objects themselves, since the 
> generic sort algorithms work by swapping the items in the container, and 
> it can be much faster to swap two small pointers than to swap two big 
> and complex objects.
> 
> For the associative containers set, multiset, map, and multimap, the 
> default is to use the < operator of the objects that are stored in the 
> container to define equivalence and sort order, which is exactly what we 
> want.  When we store sortable_ptr pointers in an associative container, 
> the pointers will be sorted in the same order as the actual objects 
> would have been if we had stored them directly in a corresponding 
> associative container for objects.  The definition of operator< ensures 
> that any two sortable_ptr pointers are equivalent if, and only if, the 
> two underlying objects are equivalent, so for sets and maps, which 
> cannot hold more than one object with equivalent keys, it will be the 
> same objects that are represented in the container whether the objects 
> are stored directly or via sortable_ptr pointers.
> 
> - - - -
> 
> The draft implementation looks like this at the moment:
> 
> //======================================
> //  'sortable_ptr'
> //--------------------------------------
> template <class T, class Compare = std::less<T> >
> class sortable_ptr : public boost::shared_ptr<T>
> {
> private:
>   typedef sortable_ptr self;
>   typedef boost::shared_ptr<T> base;
> 
> public:
>   // From 'boost::shared_ptr'
>   //   typedef T element_type;
>   //   typedef T value_type;
>   //   typedef T * pointer;
>   //   typedef typename detail::shared_ptr_traits<T>::reference reference;
>   //
>   typedef Compare element_compare;
> 
>   element_compare element_comp() const {return element_compare();}
> 
>   bool operator<  (const self& other) const {return 
> element_compare()(**this, *other);}
>   bool operator>  (const self& other) const {return other < *this;}
>   bool operator<= (const self& other) const {return !(other < *this);}
>   bool operator>= (const self& other) const {return !(other > *this);}
> 
> 
> // Constructors
>   sortable_ptr() {}
> 
>   template<class Y>
>   sortable_ptr(const sortable_ptr<Y>& other) : base(other) {}
> 
>   template<class Y>
>   explicit sortable_ptr(const boost::shared_ptr<Y>& other) : base(other) {}
> 
>   template<class Y>
>   explicit sortable_ptr(const boost::weak_ptr<Y>& other) : base(other) {}
> 
>   template<class Y>
>   explicit sortable_ptr(std::auto_ptr<Y>& other) : base(other) {}
> 
>   template<class Y>
>   explicit sortable_ptr(Y* other) : base(other) {}
> 
> // Assignment
> 
> };
> 
> - - - -
> 
> Does this represent a sensible idea, or am I barking up a totally 
> pointless tree?
> 
> Christian Engström
> 
> 
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
> 
>