Re: [boost][std][ptr_container][multi_index] proposalaboutstdalgorithms based on iter_swap

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