Currently, std algorithms are classified into
nonmodifying, modifying and sorting. It turns out that
the two latter categories can be further refined so
that, with some stricter specifications in the std,
some of their algorithms are applicable to a wider
spectrum of situations:

Consider a special container with bidir iterators
which are nonmutable (i.e. they dereference to
const T&). Further suppose that the container
allows for rearranging of the elements in the
sequence, so that, while swapping elements is
not allowed, the following overload is provided

  iter_swap(it1,it2)

with the property that the order of the sequence
elements pointed to by it1 and it2 is reversed.
FWIW, this type of situation is not entirely
unrealistic (I'm working on a lib where this
comes out.) Most likely, this implies that
iterators have an inner extra level of indirection.
As these iterators are nonmutable, none of
the modifying algorithms are applicable to the
sequence, even though some of them (vg reverse,
rotate, sort) are conceptually compatible with
the restrictions imposed: in the end, their typical
implementation does nothing but swapping elements
around.

Take for instance rotate: an implementation
could be made to work with this special type of
sequence if only it called unqualified iter_swap
for doing the swapping work. Same for rotate
and the various sorting algorithms.

So, I propose the following:

* Define the concept element-swappable for
iterators along this (sort of):

"An iterator is element-swappable if their pointed-to
values are swappable (as defined in
[lib.swappable.requirements] in N1523) or if
a namespace scope function named iter_swap exists in
the same namespace as the definition of the iterator,
such that the expression iter_swap(it1,it2) has the
effect that all iterators equivalent to it1 now point
to the value originally pointed to by it2, and
viceversa."

* Specify that std::iter_swap is implemented by
unqualifyingly calling swap.
* For those algorithms where it makes sense,
classify them as "swapping algorithms" instead
of the cruder "modifying", and require that
the iterators be element-swappable.

Note that my proposal is actually an extension
of N1523:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm

And that's it. Comments/suggestions? Does this make
any sense?

Joaqu   n M L   pez Mu   oz
Telef   nica, Investigaci   n y Desarrollo


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]