[boost] Re: smarter auto_ptr

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2004-01-18 14:03:31

On Jan 17, 2004, at 11:21 AM, Bronek Kozicki wrote:

> I want to ask you to take a look at file ext_auto_ptr_07.zip (size 3KB)
> , which is available in files section of boost YahooGroup . If you are
> not happy downloading file from Yahoo, you may get it from my own WWW :
> http://b.kozicki.pl/cpp/ext_auto_ptr_07.zip .
>
> Actually ext_auto_ptr_07.zip contains two files: T191.hpp and T191.cpp
> (both files are available standalone under http://b.kozicki.pl/cpp/ ) .
> File T191.hpp contains improved auto_ptr (placed in namespace
> boost::ext), file T191.cpp is simple application using its new features
> (tested under MSVC71 and MINGW - GCC 3.3.1).
>
> This auto_ptr is based on Rani Sharoni proposal to improve standard
> std::auto_ptr. Rani's idea is to use SFINAE in smart way and remove
> auto_ptr_ref from standard (as there is no longer need for it). Whole
> story can be found here:
> http://groups.google.com/groups?threadm=3fc75686%40news.microsoft.com

I agree that a smart pointer with auto_ptr-like semantics is an  
important tool.  The important semantics are:

     This pointer maintains unique ownership of this resource (memory).

  And I like the idea of a policy deleter class, though I do not want to  
pay any overhead for the policy when it is stateless (i.e.  
sizeof(smart_pointer) == sizeof(void*) for common cases).

My biggest problem with auto_ptr is:

    One should never move from lvalues with copy syntax.

That is, given a smart pointer S (or any type for that matter), and  
given a code snippet that looks like:

S s1;
...
S s2(s1);

or

s2 = s1;  // not ok to move here

s1's value should not change during the copy (as does auto_ptr).

The reasoning for this is that sooner or later S is going to wind up in  
generic code which will be written with the assumption that copy syntax  
means copy, not move:

template <class T>
T
foo(T t)
{
     ...
     T temp = t;  // assumes copy (t isn't supposed to change here)
     ...
     return t;
}

If the semantics of S are such that it is not capable of a copy (like  
auto_ptr), then it is far better to cause a compile time error, than to  
move from an lvalue with copy syntax.

Note though it is ok (even desirable) to move from an rvalue with copy  
syntax.  For example:

S source() {return S();}
...
S s1;
...
s1 = source();  // ok to move here

If the temporary (rvalue) return value from source() is altered during  
the assignment to s1, there is no way for the rest of the program to  
know, since no part of the program can have a reference to the  
temporary, except for S::operator=.

Below is a brief, realistic demo of the dangers of moving with copy  
syntax from an lvalue:

#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;
     }
}

Jane Coder has written a useful generic algorithm called my_partition3.  
  It takes a range of values, examines the first, middle and last of  
these values, and then partitions the range based on the median of  
[*first, *middle, *last].  For example, given:

4 2 0 6 8 5 1 7 3

The algorithm looks at 4, 8, and 3, then chooses 4 (the median of  
[*first, *middle, *last]) as the value to partition the range with:

3 2 0 1 - 4 5 6 7 8

Jane Coder tests my_partition3 carefully and it looks good.  The code  
is then successfully used throughout the project.

Joe Coder comes along a year later and wants to reuse Jane's  
my_partition3.  Only Joe needs to work on a range of smart pointers.   
He quickly creates indirect_less for the comparison object, and passes  
a range of auto_ptr into my_partition3.

#include <iostream>
#include <memory>
#include <ctime>

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

int main()
{
     typedef std::auto_ptr<int> Ptr;   // fails at run time
//    typedef std::tr1::shared_ptr<int> Ptr;  // works
//    typedef Metrowerks::move_ptr<int> Ptr;  // fails at compile time

     Ptr ia[9];
     Ptr* begin = ia;
     unsigned size = sizeof(ia)/sizeof(ia[0]);
     Ptr* end = ia + size;
     for (int 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 << ' ';
}

It compiles fine.  But there is a hidden run-time error.  If Joe is  
lucky the run-time error will show up quickly.  But it could go  
undetected until after shipping.  The problem is this line in  
my_partition3:

     value_type partition = *middle;

It looks like a copy.  Jane intended it to be a copy.  But if it turns  
out to be a move (as it did in Joe's code), then the algorithm fails at  
run time (the worst time to fail).

If Joe has used shared_ptr instead of auto_ptr, his code would have  
worked.  If Joe had used some pointer that failed to compile if asked  
to "copy" from an lvalue, then he would have been alerted to the bug at  
compile time and had the opportunity to fix it.

The moral of this story is not that one should always use shared_ptr.   
Sometimes one really does need the semantics of unique ownership.  The  
moral of this story is that auto_ptr is dangerous because it moves from  
lvalues with copy syntax.  So if you want to improve auto_ptr, that is  
a behavior you do not want in your improved design.

It is safe to move from lvalues with some syntax other than copy.  So  
the functionality of auto_ptr can still be had, just not with the same  
syntax.  You might consider something like:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/ 
n1377.htm#move_ptr%20Example

This example relies on a language feature not available to you.   
However, I believe you can emulate this behavior in today's C++ using  
the same techniques you have demonstrated.

In summary, I think an "improved auto_ptr" must "pass" the above test  
by failing to compile.  I also believe the name "auto_ptr" should not  
be used for such a smart pointer because of backwards compatibility  
issues.

Just my .02.

-Howard