Re: [boost] why no strict ownership smart pointer in boost

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2003-07-03 11:22:54

On Thursday, July 3, 2003, at 11:05  AM, Schoenborn, Oliver wrote:

> I could sure use some feedback about how the technique stands to 
> generic
> algorithms.

I'm not sure how this will work with your library, but the below 
example is meant to illustrate the kind of accidental ownership 
transfer I am concerned about.  With your statement:

> No, transient shared ownership.

I suspect that everything will be just fine.

my_partition3 is meant to be a "typical" 3rd party generic algorithm 
taking a range of iterators, and a generic compare functor.  It looks 
at the first, middle and last elements in the range, selects the median 
of those elements, and then partitions the range using the afore 
selected median.

#include <iterator>
#include <algorithm>

template <class It, class Comp>
It
my_partition3(It first, It last, Comp comp)
{
        typedef typename std::iterator_traits<It>::difference_type 
difference_type;
        typedef typename std::iterator_traits<It>::value_type      value_type;
        difference_type len = std::distance(first, last);
        switch (len)
        {
        case 0:
        case 1:
                return first;
        case 2:
                --last;
                if (comp(*last, *first))
                        std::iter_swap(first, last);
                return last;
        }
        It middle = first;
        std::advance(middle, len/2);
        --last;
        if (comp(*middle, *first))
                std::iter_swap(first, middle);
        if (comp(*last, *first))
        {
                std::iter_swap(first, last);
                std::iter_swap(middle, last);
        }
        else if (comp(*last, *middle))
                std::iter_swap(middle, last);
        ++last;
        value_type partition = *middle;
        while (true)
        {
                while (true)
                {
                        if (first == last)
                                return first;
                        if (!comp(*first, partition))
                                break;
                        ++first;
                }
                --last;
                while (true)
                {
                        if (first == last)
                                return first;
                        if (comp(*last, partition))
                                break;
                        --last;
                }
                std::iter_swap(first, last);
                ++first;
        }
}

The "catch" in this otherwise reasonable example is the statement:

        value_type partition = *middle;

This statement assumes copy semantics.  That is, *middle is assumed to 
be left unchanged.  If you create a range of shared_ptr, with an 
indirect less-than comparator for example, then things work just great:

#include <iostream>
#include <memory>

struct indirect_less
{
        template <class T>
        bool operator()(const T& x, const T& y) const
                { return *x < *y; }
};

int main()
{
        typedef std::tr1::shared_ptr<int> Ptr;

        Ptr ia[9];
        Ptr* begin = ia;
        unsigned size = sizeof(ia)/sizeof(ia[0]);
        Ptr* end = ia + size;
        for (unsigned k = 0; k < size; ++k)
                ia[k].reset(new int(k));
        std::random_shuffle(begin, end);
        for (Ptr* k = begin; k < end; ++k)
                std::cout << **k << ' ';
        std::cout << '\n';
        Ptr* i = my_partition3(begin, end, indirect_less());
        for (Ptr* k = begin; k < i; ++k)
                std::cout << **k << ' ';
        std::cout << "- ";
        for (Ptr* k = i; k < end; ++k)
                std::cout << **k << ' ';
}

But if you:

        typedef std::auto_ptr<int> Ptr;

instead, then you get trouble.  It compiles, but the "partition 
assignment" now transfers ownership out of the container.  This results 
in a runtime crash.

It is examples such as this one, that have made me come to believe:

        It is not safe to move with copy syntax from lvalues.

I.e. publicly accessible "copy" constructors that look like A(A&) are 
accidents waiting to happen.

It sounds to me like this isn't a problem with the NoPtr lib, even when 
vector<DynObj> is used in place of a raw array in the above example.  
Either it will compile and work, or won't compile (both of which I 
consider acceptable behavior).  It is compiling and not working that I 
dislike so much.

-Howard