Class with member swap and std::swap specialization still not Swappable?
Niels Dekker (no reply address)
C++0x? It has a public swap member function and a specialization of
std::swap.
#include <algorithm>
class Uncopyable
{
public:
Uncopyable() {}
void swap(Uncopyable &) {}
private:
Uncopyable(const Uncopyable &);
Uncopyable& operator=(const Uncopyable&);
};
namespace std
{
template <>
void swap<Uncopyable>(Uncopyable& lhs, Uncopyable & rhs)
{
lhs.swap(rhs);
}
}
If I understand the Draft well, this class is not Swappable. Which
sounds rather counter-intuitive to me!
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf
Wouldn't it better to include any T as being Swappable for which the
following lines are valid, and have the right semantics?
using std::swap;
swap(t, u); // t and u are values of type T
This corresponds to the way Scott Meyers recommands calling a swap
function, in Effective C++, 3rd Edition, item 25.
Kind regards,
Niels Dekker
www.xs4all.nl/~nd/dekkerware
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Greg Herlihy
> Does the following class meet the Swappable requirement, according to
> C++0x? It has a public swap member function and a specialization of
> std::swap.
>
> #include <algorithm>
>
> class Uncopyable
> {
> public:
> Uncopyable() {}
> void swap(Uncopyable &) {}
> private:
> Uncopyable(const Uncopyable &);
> Uncopyable& operator=(const Uncopyable&);
> };
>
> namespace std
> {
> template <>
> void swap<Uncopyable>(Uncopyable& lhs, Uncopyable & rhs)
> {
> lhs.swap(rhs);
> }
> }
>
> If I understand the Draft well, this class is not Swappable. Which
> sounds rather counter-intuitive to me!
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf
>
> Wouldn't it better to include any T as being Swappable for which the
> following lines are valid, and have the right semantics?
> using std::swap;
> swap(t, u); // t and u are values of type T
No, the second line all by itself should be valid:
swap( t, u );
which is not the case in the above program. Because swap() has been
defined in the std namespace, it will not be found when passed
arguments of a class (Uncopyable) that has been declared in the global
namespace.
The fix therefore is to declare swap() in the same namespace as the one
in which Uncopyable is declared - whether that namespace is, as in this
case, the global namespace, or whether it is some other namespace that
the program has declared:
void swap(Uncopyable& lhs, Uncopyable & rhs)
{
lhs.swap(rhs);
}
Greg
Jens Theisen
> > Wouldn't it better to include any T as being Swappable for which the
> > following lines are valid, and have the right semantics?
> > using std::swap;
> > swap(t, u); // t and u are values of type T
This recommendation is there in case you can't be sure that t and u
are not defined in the global namespace - there nothing will be found
by ADL. Stuff in you namespaces and namespace std are fine.
Jens
Niels Dekker (no reply address)
> following lines are valid, and have the right semantics?
> using std::swap;
> swap(t, u); // t and u are values of type T
Greg Herlihy replied:
>
> No, the second line all by itself should be valid:
>
> swap( t, u );
>
> which is not the case in the above program. Because swap() has been
> defined in the std namespace, it will not be found when passed
> arguments of a class (Uncopyable) that has been declared in the global
> namespace.
Thank you. So will std functions that have those Swappable requirements
(e.g., std::iter_swap) give compile errors when I try to use them for
objects of my Uncopyable class, even if it has a specialization for
std::swap?
In other words, will the following program be rejected by C++0x?
------------------------------------------------------------------------
#include <algorithm>
class Uncopyable
{
public:
Uncopyable() {}
void swap(Uncopyable &) {}
private:
Uncopyable(const Uncopyable &);
Uncopyable& operator=(const Uncopyable&);
};
namespace std
{
template <>
void swap<Uncopyable>(Uncopyable& lhs, Uncopyable & rhs)
{
lhs.swap(rhs);
}
}
int main()
{
Uncopyable t, u;
std::iter_swap(&t, &u); // Rejected by C++0x?
}
------------------------------------------------------------------------
Kind regards,
Niels Dekker
Howard Hinnant
Thanks Niels. I think you make a good point. I've opened LWG issue 594.
-Howard
Greg Herlihy
> > Wouldn't it better to include any T as being Swappable for which the
> > following lines are valid, and have the right semantics?
> > using std::swap;
> > swap(t, u); // t and u are values of type T
>
> Greg Herlihy replied:
> >
> > No, the second line all by itself should be valid:
> >
> > swap( t, u );
> >
> > which is not the case in the above program. Because swap() has been
> > defined in the std namespace, it will not be found when passed
> > arguments of a class (Uncopyable) that has been declared in the global
> > namespace.
>
> Thank you. So will std functions that have those Swappable requirements
> (e.g., std::iter_swap) give compile errors when I try to use them for
> objects of my Uncopyable class, even if it has a specialization for
> std::swap?
Even when a program fails to meet the Swappable requirement for a given
operation, it may still compile and even run as expected. There is just
no assurance - the code could compile but not work as expected. And it
is this kind of "silent failure" that is the real risk for not meeting
the requirements (see below).
> In other words, will the following program be rejected by C++0x?
> ------------------------------------------------------------------------
> #include <algorithm>
>
> class Uncopyable
> {
> public:
> Uncopyable() {}
> void swap(Uncopyable &) {}
> private:
> Uncopyable(const Uncopyable &);
> Uncopyable& operator=(const Uncopyable&);
> };
>
> namespace std
> {
> template <>
> void swap<Uncopyable>(Uncopyable& lhs, Uncopyable & rhs)
> {
> lhs.swap(rhs);
> }
> }
>
> int main()
> {
> Uncopyable t, u;
>
> std::iter_swap(&t, &u); // Rejected by C++0x?
> }
No, the code will compile and run as expected even though Uncopyable
has not met the Swappable requirements. However the results could well
be different if an (otherwise unrelated) swap() routine is declared in
the global namespace.
void swap(Uncopyable& lhs, Uncopyable& rhs)
{
// do nothing interesting
}
Now all calls to swap() that used to call the Uncopyable specialization
in the std namespace are now dispatched to this global swap() routine -
even though this routine does not meet the Swappable requirements. So
although the program will still compile and run - the addition of this
new routine means that it will no longer produce the expected results.
Whereas if the program had declared the required swap() routine in the
appropriate (that is, global) namespace to begin with - then this
unfortunate situation would have been avoided.
Greg
Niels Dekker (no reply address)
> Thanks Niels. I think you make a good point. I've opened LWG issue 594.
Thank you, Howard! Hopefully providing an appropriate specialization of
std::swap will be sufficient to make a class Swappable in C++0x...
Yet another Swappable question, though. Is it allowed for a Swappable
class to throw an exception, while swapping?
For example, my BadCopier class (see below) throws a bad_alloc in its
copy constructor, as well as in its assignment operator, but still it is
both CopyConstructible and Assignable, or not? So is it Swappable?
My BadSwapper class (further below) throws a bad_alloc whenever its swap
function is called. Still... is it Swappable as well? I doubt it, as
it doesn't meet the post-condition for swap(t, u), as described in the
Draft, Table 32, Swappable requirements:
"t has the value originally held by u, and u has the value originally
held by t."
(Draft: www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf)
Here are my "bad" classes:
------------------------------------------------------------------------
class BadCopier
{
int m_data;
public:
explicit BadCopier(int arg = 0): m_data(arg) {}
BadCopier(const BadCopier& rhs): m_data(rhs.m_data)
{
throw std::bad_alloc();
}
BadCopier & operator=(const BadCopier& rhs)
{
m_data = rhs.m_data;
throw std::bad_alloc();
}
};
class BadSwapper
{
int m_data;
public:
explicit BadSwapper(int arg = 0): m_data(arg) {}
friend void swap(BadSwapper& lhs, BadSwapper& rhs)
{
std::swap(lhs.m_data, rhs.m_data);
throw std::bad_alloc();
}
};
------------------------------------------------------------------------
Please let me know if both classes satisfy the Swappable requirements!
Kind regards,
Niels Dekker
Howard Hinnant
unk...@this.is.invalid ("Niels Dekker (no reply address)") wrote:
> Yet another Swappable question, though. Is it allowed for a Swappable
> class to throw an exception, while swapping?
You raise good points. I believe the current WD says that you can throw
while swapping. The current CopyConstructible requirement has similar
wording to the Swappable requirement, and clearly a copy constructor can
throw.
That being said, a personal coding guideline of mine is that none of
swap, move constructor or move assignment should throw. Bad things
happen. But at this point that's more of a coding guideline than a
standards requirement, and should probably stay that way. Caveat: I have
proposed a corner or two that do require a nothrow move constructor,
e.g.:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1858.html
23.2.4.2 - vector capacity
It amazes me how often a throwing swap or move actually turns out ok
(for a sufficiently lax definition of ok). But on some primeval level,
such things scare me, much like rattle snakes do. Yes, they can be
handled safely. I'm glad other people do that so I don't have to. :-)
-Howard
Pete Becker
>
> That being said, a personal coding guideline of mine is that none of
> swap, move constructor or move assignment should throw.
On the other hand, this precludes a small-object optimization for
std::tr1::function. If its swap member function is allowed to throw
exceptions then it can hold small function objects internally rather
than putting them on the free store.
--
-- Pete
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Howard Hinnant
peteb...@acm.org (Pete Becker) wrote:
> > That being said, a personal coding guideline of mine is that none of
> > swap, move constructor or move assignment should throw.
>
> On the other hand, this precludes a small-object optimization for
> std::tr1::function. If its swap member function is allowed to throw
> exceptions then it can hold small function objects internally rather
> than putting them on the free store.
<nod> std::tr1::function is a subject I've been worrying a lot about
lately for a variety of reasons.
In the sso optimizations I've done to date for std::function I restrict
the sso to function pointers and empty function objects. Admittedly
that doesn't restrict empty function objects from throwing on swap, but
it does make it "6-nines" unlikely. And it also allows the sso
optimization for a vast majority of use cases.
But this is a very interesting standards question: How much of this
should be QOI, and how much should be standard?
Fwiw the other area that std::function concerns me is: Does
std::function(F) require F to be CopyConstructible?
I believe it does today. And I'm not happy with that answer. I haven't
come up with a good way to say no to requiring CopyConstructible of F
yet. Perhaps concepts will lend a hand...
-Howard
Pete Becker
>
> In the sso optimizations I've done to date for std::function I restrict
> the sso to function pointers and empty function objects. Admittedly
> that doesn't restrict empty function objects from throwing on swap, but
> it does make it "6-nines" unlikely. And it also allows the sso
> optimization for a vast majority of use cases.
>
Doug Gregor mentioned to me a few months ago that he was re-implementing
function, and decided to ignore the possibility that copying a callable
object (note switch to TR1 terminology <g>) might throw an exception. In
my opinion that's exactly right: you don't impose constraints for fringe
cases at the expense of making the mainline harder, bigger, or slower. I
wouldn't call this 6-nines, because that implies statistical data that
almost certainly doesn't exist. Besides, that's too extreme. The best
rule is that almost everything works as advertised, and the cases that
don't are easy to recognize. The more sophisticated the implementation
gets, the harder it is to describe the cases it can't handle.
My analogy is the old through-the-lens metering systems on cameras. They
looked at the overall brightness of the image, and set the exposure to
get a mid-tone. That got 90% of most people's pictures right. If the
subject was backlit (background brighter than subject) that would
produce a picture that was underexposed, and you had to override the
automatic setting to give more exposure. If the background was dark, the
picture would be overexposed, and you had to override the other way.
Then they (Nikon, I think) came out with fancier exposure systems that
looked at five different areas of the image, to get better exposures in
some cases. They got 95% right, but you could no longer just look at the
scene to figure out what whether the exposure would be right or whether
you had to override the automatic setting. Of course, today you get
instant feedback, so you can adjust after you take the first shot. But
that's hacking.
--
-- Pete
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
---
Niels Dekker (no reply address)
> On the other hand, this precludes a small-object optimization for
> std::tr1::function. If its swap member function is allowed to throw
> exceptions then it can hold small function objects internally rather
> than putting them on the free store.
I'm sorry I'm not yet familiar with either std::tr1::function, or
small-object optimization. Can you please explain in more detail why
std::tr1::function or any class with small-object optimization would
need to have a throwing swap?
Kind regards,
Niels Dekker
Niels Dekker (no reply address)
the swap function to throw an exception, according to the Draft
(N1905). This was confirmed by both Howard Hinnant and Pete Becker, in
a previous discussion, "Is a Swappable class allowed to throw an
exception?". Thanks for your replies, sofar! My next question, though:
how will std functions that impose Swappable requirements onto their
arguments cope with a throwing swap?
For example, suppose the swap function called by swap_ranges might throw
an exception. Typically this would result in having the two ranges only
partially swapped. (Which might mean user data getting corrupted!)
Does the caller have a way to tell how much of its ranges has been
swapped successfully, after calling swap_ranges? Is swap_ranges allowed
to catch the exception thrown by the swap function, and return the value
of the iterator, pointing at where it went wrong?
In other words, is the following implementation of std::swap_ranges
conforming to the Draft?
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2)
{
while (first1 != last1)
{
try
{
swap(*first1, *first2);
}
catch(...)
{
return first2;
}
++first1;
++first2;
}
return first2;
}
Kind regards,
Niels Dekker
David Abrahams
> When objects of a Swappable class are being swapped, it is allowed for
> the swap function to throw an exception, according to the Draft
> (N1905). This was confirmed by both Howard Hinnant and Pete Becker, in
> a previous discussion, "Is a Swappable class allowed to throw an
> exception?". Thanks for your replies, sofar! My next question, though:
> how will std functions that impose Swappable requirements onto their
> arguments cope with a throwing swap?
The same way they deal today with element copies throwing during sort,
swap_ranges, etc.
> For example, suppose the swap function called by swap_ranges might throw
> an exception. Typically this would result in having the two ranges only
> partially swapped. (Which might mean user data getting corrupted!)
The standard library only maintains (and can only maintain) the
invariants that are visible to it. Users are responsible for
maintaining their own invariants. If being "uncorrupted" according to
some higher-level user invariant depends on the ranges either being
fully swapped or fully unswapped, it's the user's job to ensure that.
> Does the caller have a way to tell how much of its ranges has been
> swapped successfully, after calling swap_ranges?
No. And what would the caller do with that information anyway? Any
attempt to unswap the swapped parts could throw, too.
> Is swap_ranges allowed to catch the exception thrown by the swap
> function, and return the value of the iterator, pointing at where it
> went wrong?
No. I don't think it's explicitly stated anywhere, but standard
library algorithms are intended to be exception-neutral.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
Niels Dekker (no reply address)
previous posting, "What if an exception is thrown while swapping
Swappable objects?"
Now suppose a base class is Swappable (according to the Draft), because
it has a swap function. Does this automatically make a class that is
publicly derived from this base class Swappable as well?
Example:
#include <algorithm>
class Base // This class is surely Swappable
{
friend void swap(Base& lhs, Base& rhs)
{
std::swap(lhs.m_data, rhs.m_data);
}
public:
explicit Base(int arg=0): m_data(arg)
{
}
protected:
int m_data;
};
class Derived: public Base // Is Derived Swappable as well?
{
public:
explicit Derived(int arg1=0, int arg2=0): Base(arg1), m_const(arg2)
{
}
protected:
const int m_const;
};
My feeling is that the Derived class is not Swappable. Because although
the call swap(t, u) is valid for Derived objects t and u, it
certainly does not fulfill the postcondition described in Table 33 of
the Draft (N2009):
"t has the value originally held by u, and u has the value originally
held by t"
So it's not allowed to call std functions that impose Swappable
requirements onto their arguments, for this Derived class. E.g., the
following call to iter_swap is incorrect:
int main()
{
Derived t(22, 44), u(66, 88);
std::iter_swap(&t, &u); // Violating the Swappable requirement!?!
}
Is this little program well defined in C++0x? Should the compiler issue
an error? Is the compiler allowed to do so? Or does it result in
undefined behaviour?
Kind regards,
Niels Dekker
Greg Herlihy
> it has a swap function. Does this automatically make a class that is
> publicly derived from this base class Swappable as well?
The derived class automatically meets the technical requirements of a
Swappable type. But it's up to the programmer to decide whether
Swappable's semantic requirements have been met as well.
> Example:
> #include <algorithm>
>
> class Base // This class is surely Swappable
> {
> friend void swap(Base& lhs, Base& rhs)
> {
> std::swap(lhs.m_data, rhs.m_data);
> }
> public:
> explicit Base(int arg=0): m_data(arg)
> {
> }
> protected:
> int m_data;
> };
>
> class Derived: public Base // Is Derived Swappable as well?
> {
> public:
> explicit Derived(int arg1=0, int arg2=0): Base(arg1), m_const(arg2)
> {
> }
> protected:
> const int m_const;
> };
> My feeling is that the Derived class is not Swappable. Because although
> the call swap(t, u) is valid for Derived objects t and u, it
> certainly does not fulfill the postcondition described in Table 33 of
> the Draft (N2009):
> "t has the value originally held by u, and u has the value originally
> held by t"
Since you wrote both the Base and Derived classes, only you know the
answer to that question. To decide whether the Swap routine has swapped
the values of the Derived objects, requires knowing where the value of
a Derived object is to be found in the first place. Specifically, does
Derived m_const's data member participate in the value representation
of the object? Often the answer can be found in the class's
implementation of an equality test. Those class members that constitute
value will be involved in the test.
Basically, there are two possible evaluations:
If Derived's author does not consider its m_const member to be part of
the object's stored value, then swapping two Derived class instances by
swapping only their Base class subobjects would meet all the
requirements of Swappable.
On the other hand, if Derived::m_const (or some other Derived data
member) stores a portion of the object's value - then leaving those
members behind when swapping two Derived objects would clearly not be
exchanging their values, it would be scrambling them. (Ignoring for the
moment that m_const being const could not be swapped)
The Standard allows either answer to be the "right" one. After all,
evaluating a program against what the Standard says can only do so
much. At a certain point, the programmer must decide whether the
program is correct according to the terms that the program has defined
for itself.
Greg
David Abrahams
> "Niels Dekker no reply address wrote:
>> Now suppose a base class is Swappable (according to the Draft), because
>> it has a swap function. Does this automatically make a class that is
>> publicly derived from this base class Swappable as well?
>
> The derived class automatically meets the technical requirements of a
> Swappable type. But it's up to the programmer to decide whether
> Swappable's semantic requirements have been met as well.
Semantic requirements are a part of the "technical requirements."
Maybe you meant to say it meets the syntactic, or structural,
requirements?
Everything else you wrote, I agree with.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
---
Greg Herlihy
> "Greg Herlihy" <gre...@pacbell.net> writes:
>
> > "Niels Dekker no reply address wrote:
> >> Now suppose a base class is Swappable (according to the Draft), because
> >> it has a swap function. Does this automatically make a class that is
> >> publicly derived from this base class Swappable as well?
> >
> > The derived class automatically meets the technical requirements of a
> > Swappable type. But it's up to the programmer to decide whether
> > Swappable's semantic requirements have been met as well.
>
> Semantic requirements are a part of the "technical requirements."
> Maybe you meant to say it meets the syntactic, or structural,
> requirements?
Yes, I should have written that the sample program has met Swappable's
"syntactical requirements". In other words, the program has provided a
function with the right name and the right signature - but whether the
function provided also does the right thing when called (that is,
whether it fulfills Swappable's "operational" or "functional"
requirements) by correctly exchanging the values of its two arguments -
that question cannot be answered without an understanding of how the
type of object being swapped, represents its value.
A good example of value data members and non-value data members is a
shared pointer that maintains a raw pointer and int reference count. To
swap two of these shared pointers would necessitate swapping their raw
pointer members - whereas also swapping their reference count data
members would be disasterous. So we can conclude that the raw pointer
data member represents value, while the reference count data member
does not.
Greg
David Abrahams
> A good example of value data members and non-value data members is a
> shared pointer that maintains a raw pointer and int reference count. To
> swap two of these shared pointers would necessitate swapping their raw
> pointer members - whereas also swapping their reference count data
> members would be disasterous.
I'm having a hard time imagining such a smart pointer, frankly.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
---
Greg Herlihy
> "Greg Herlihy" <gre...@pacbell.net> writes:
>
> > A good example of value data members and non-value data members is a
> > shared pointer that maintains a raw pointer and int reference count. To
> > swap two of these shared pointers would necessitate swapping their raw
> > pointer members - whereas also swapping their reference count data
> > members would be disasterous.
>
> I'm having a hard time imagining such a smart pointer, frankly.
Consider this code that uses a hypothetical smart_pointer class for an
unidentified type T:
smart_pointer<T> a1(new T);
smart_pointer<T> a2 = a1;
smart_pointer<T> a3 = a1;
smart_pointer<T> a4 = a1;
smart_pointer<T> b1(new T);
smart_pointer<T> b2 = b1;
swap(a1, b1);
Now say that I want to swap a1 and b1 such that a1 will reference b1's
shared object (and vice versa) and I want all smart_pointers variables
sharing either object (that is, all smart_pointer variables equal to a1
or b1) to have their values be exchanged as well. So the values of a2,
a3, a4 and b2 should all change. Clearly if the program swaps the
reference count along with the shared value, the program will end up
with four instances of a shared object with a reference count of 2, and
two instances of a shared object with a reference count of 4. So the
values must be exchanged and not their reference counts.
Now in order to implement the smart_pointer class and have it even be
able to exchange the values of all four "a" variables with the values
of the two "b" variables as described, smart_pointer's shared type, T,
have to be itself some kind of pointer. In fact T is likely a smart
pointer itself. Because a shared pointer pointer (or a shared shared
pointer) would have the interesting quality described above - in which
updating the value of any one copy updates the value in all of its
copies - in other words, smart_pointer behaves like a smart reference.
A smart reference class would combine the automated memory management
of smart pointers, with with the non-nil guarantee and global value
visibility of references (but not inherit any of references'
syntactical restraints).
Greg
Niels Dekker (no reply address)
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?
Howard Hinnant
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
Niels Dekker (no reply address)
> 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).
Thanks for clarifying this for me. Hope it's clear to other programmers
as well! So a programmer is free to add a function named "iter_swap" to
one of the programmer's namespaces, but this won't have an effect on any
std::algorithm. On the other hand, a programmer should never specialize
std::iter_swap, because it's unspecified whether such specialization
would effect the behaviour of any std::algorithm.
> Any algorithm that requires Swappable, implies only that swap is a
> customization point [and not iter_swap]
So the answer to the question put in the subject line is yes! All std
functions that require Swappable types should indeed have the effect of
calling an appropriate swap function, whenever they're swapping objects
of that type. Which allows the programmer (the client) to customize
each of those std functions. Please correct me if I'm wrong.
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 :-)
Kind regards,
Niels Dekker
Howard Hinnant
unk...@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