Topic: Shouldn't all std functions that require Swappable types indeed call swap?


Author: howard.hinnant@gmail.com (Howard Hinnant)
Date: Mon, 2 Oct 2006 17:01:56 GMT
Raw View
In article <45202EB9.934D4098@this.is.invalid>,
 unknown@this.is.invalid ("Niels Dekker (no reply address)") wrote:

> Whenever an std function needs to do some swapping, shouldn't this
> swapping have the effect of calling a swap function?
>
> According to the Draft (N2009), 17 std functions require some of their
> arguments to be iterators that point to a Swappable type:
>   iter_swap, swap_ranges, reverse, rotate, random_shuffle, partition,
> stable_partition, sort, stable_sort, partial_sort, partial_sort_copy,
> nth_element, inplace_merge, pop_heap, sort_heap, next_permutation, and
> prev_permutation.
>
> The Draft explicitly specifies the effect of iter_swap(a, b) as being
> equal to swap(*a, *b)  [following the resolution of issue 187, submitted
> by Andrew Koenig, C++ Standard Library Defect Report List, Revision
> R44].
>
> Also it specifies the effect of std::reverse in terms of applying
> iter_swap:
>   "Effects: For each non-negative integer i <= (last - first )/2,
> applies iter_swap to all pairs of iterators first + i, (last - i) - 1."
>
> Now it seems logical to me to specify the effect of the other functions
> in terms of applying iter_swap as well.  But instead, the effect of
> std::swap_ranges is specified in terms of calling swap directly:
>   "Effects: For each non-negative integer n < (last1 - first1 )
> performs: swap(*(first1 + n), *(first2 + n))."
>
> Isn't this an inconsistency?  Can't the effect of std::swap_ranges be
> described as well by applying iter_swap?
>
> More importantly, for the other 14 std functions it is not mentioned at
> all, whether or not either swap or iter_swap is used when sorting,
> shuffling, or placing the elements from one position to another.  It's
> unclear to me whether providing an efficient, non-throwing swap for my
> own class does have any effect on the behaviour of calls to these
> functions for my class.
>
> Actually, most of those 14 std functions do depend on iter_swap, when
> looking at the library implementations of MSVC++ 14.00.50727.42 and GNU
> g++ 3.4.4.  Only 4 of them don't seem to depend on iter_swap for both
> implementations: partial_sort, partial_sort_copy, pop_heap and
> sort_heap.  Two more of them don't seem to depend on iter_swap on
> MSVC++: rotate and stable_partition.  (These observations are based on
> providing an unimplemented specialization of std::iter_swap<int*, int*>
> and looking at the link errors when trying the call each of the 14
> functions with int pointers as arguments.)
>
> Shouldn't C++0x specify that whenever one of those 14 std function swaps
> some elements pointed to by the iterators passed as its arguments, it
> has the effect of applying iter_swap?

Imho, iter_swap(i, j) is nothing more than a convenience function for
swap(*i, *j).  Whether a std::algorithm uses iter_swap or swap should be
an implementation detail.  The important thing from the interface point
of view is that swap is a customization point in the algorithm.  Clients
can customize what swap is called by providing an implementation which
will be found via ADL.  iter_swap otoh, is not intended to be a
customization point.  I.e. if a std::algorithm calls it, it should call
it qualified:  std::iter_swap(i, j).

Any algorithm that requires Swappable, implies only that swap is a
customization point and not iter_swap.  If an algorithm (such as
reverse) mentions the use of iter_swap, it does not reflect any change
of semantics.  This is simply obsolete but harmless language since
iter_swap does nothing but call swap unqualified.

-Howard

---
[ 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.comeaucomputing.com/csc/faq.html                      ]





Author: howard.hinnant@gmail.com (Howard Hinnant)
Date: Wed, 4 Oct 2006 19:25:50 GMT
Raw View
In article <45224018.732CD2BF@this.is.invalid>,
 unknown@this.is.invalid ("Niels Dekker (no reply address)") wrote:

> Actually none of the two library implementaties I looked at use my Foo
> swap function, when I pass Foo pointers to partial_sort,
> partial_sort_copy, pop_heap, or sort_heap.  But I guess it just proves
> that they're not yet C++0x compliant  :-)

These 4 algorithms I believe also currently require Assignable and
CopyConstructible.  Implementations are free to "move" elements around
using these concepts in addition to, or completely instead of swapping
them.

I hope that move semantics will alter C++0X such that partial_sort,
pop_heap and sort_heap will only require MoveConstructible,
MoveAssignable and Swappable.  If this comes about, the implementation
may still not call swap function for your Foo, but it if Foo has a move
constructor and move assignment operator, then these algorithms will use
those instead of Foo's copy constructor and copy assignment (or just
call swap of course).

See the lengthy 3-part table in the middle of:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html

titled "Summary of algorithm requirements" for a summary of the proposed
requirements (in this area) for each algorithm.

In this table, only those algorithms with only a Swappable requirement
(and no other requirements) must call your Foo's swap if they are to
move any elements around.

For those algorithms with only the MoveConstructible and MoveAssignable
requirements, they are forbidden from calling your Foo's swap.  They
must use move construction and move assignment only (and Foo will
seamlessly translate those calls to copy construction and copy
assignment if it does not implement move construction and move
assignment).

For those algorithms with all of Swappable, MoveConstructible and
MoveAssignable, it is up to the implementation of which technique to use
to move elements around (and can use both).

-Howard

---
[ 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.comeaucomputing.com/csc/faq.html                      ]