Boost logo

Boost :

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-05-05 14:56:14


On May 5, 2005, at 8:46 AM, Thorsten Ottosen wrote:

>
> Thorsten Ottosen ha escrito:
>
>>> What do you think of this? IMHO this can solve
>>> the problem of making std swapping algorithms
>>> work with ptr_containers, a problem for which
>>> (if I'm not wrong) no satisfying solution has been
>>> designed.
>>
>> you're right that no satisfiable solution has been reached.
>>
>> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1771.html
>>
>> explains a different way to fix standard algorithms by mandating
>> moving is
>> used if available.
>>
>> my understanding of this, based on discussion with Howard, is that we
>> can
>> actually
>> make an iterator with a proxy-reference for pointer containers that
>> works.
>
> Could you elaborate on this? I'm interested on how to apply this
> tecnhique
> for my own purposes. Thank you,
>>>>>>>>>>
>
> well, first of all, it requires the algorithm to move elements around
> if it
> can (so nothing will work until C++0x).
>
> secondly, your reference-type of the iterator is a proxy that can be
> moved
> where moving it actually moves the pointer underneith.
>
> maybe there is more to it, but Howard assured my that the algorithms in
> question would never do a lvalue to rvalue conversion
> (from the iterators reference to its value type)

Clarification: I'm not positive of the definition of "algorithms in
question", so I'll try to supply one. I believe you're referring to
algorithms only allowed to use Swappable, and not MoveConstructible or
MoveAssignable. N1771 lists those algorithms as:

swap_ranges
iter_swap
reverse
random_shuffle
partition
next_permutation
prev_permutation

Notably absent from this list is rotate, specifically mentioned in
Joaquín's proposal. This algorithm, along with several others,
requires Swappable, MoveConstructible and MoveAssignable. Such an
algorithm may call unqualified swap, but is also allowed to move
construct and move assign not only from one iterator reference to
another, but to and from the iterator's value_type (typically a local
temporary). For example from the insertion_sort example in N1771:

> value_type tmp(std::move(*j)); // move construct to temporary
> for (BidirectionalIterator k = i; k != first && tmp < *--k; --j)
> *j = std::move(*k); // move assign from reference to reference
> *j = std::move(tmp); // move assign from temporary to reference

Such capability is considered critical for the typical "gcd"
implementations of rotate.

If you would like to rig up a self contained test case for me to try
out on a full implementation of N1770/N1771 I would be happy to do so
and report back with the results.

-Howard


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk