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
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
