C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Whence swap?
Goto page 1, 2  Next
 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ language, library and standards
View previous topic :: View next topic  
Author Message
Scott Meyers
Guest
PostPosted: Sat Jul 17, 2004 4:55 am    Post subject: Whence swap? Reply with quote


As far as I know, the STL marked the introduction of a nonthrowing "swap"
into C++, and since then swap has become the cornerstone of idioms such as
copy-and-swap for achieving the strong exception safety guarantee. Does
anybody know why swap was introduced into the STL in the first place? My
understanding is that it's not mandated as part of the implementation of
any algorithm (e.g., sort need not call swap), so why was swap designed in?
Was it put there specifically as a mechanism for writing strongly exception
safe functions, or was that just something peole later figured out it could
be used for?

All insights appreciated,

Scott

---
[ 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 ]

Back to top
Pete Becker
Guest
PostPosted: Sat Jul 17, 2004 3:15 pm    Post subject: Re: Whence swap? Reply with quote


Scott Meyers wrote:
Quote:

As far as I know, the STL marked the introduction of a nonthrowing "swap"
into C++, and since then swap has become the cornerstone of idioms such as
copy-and-swap for achieving the strong exception safety guarantee. Does
anybody know why swap was introduced into the STL in the first place? My
understanding is that it's not mandated as part of the implementation of
any algorithm (e.g., sort need not call swap), so why was swap designed in?
Was it put there specifically as a mechanism for writing strongly exception
safe functions, or was that just something peole later figured out it could
be used for?


It can be more efficient than doing multiple copies of an entire object.
Especially for large containers, where swap can exchange a bit of
bookkeeping information and a couple of pointers rather than copy all of
the stored objects.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

---
[ 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 ]


Back to top
David Abrahams
Guest
PostPosted: Sat Jul 17, 2004 3:15 pm    Post subject: Re: Whence swap? Reply with quote


[email]Usenet (AT) aristeia (DOT) com[/email] (Scott Meyers) writes:

Quote:
As far as I know, the STL marked the introduction of a nonthrowing "swap"
into C++

std::swap is not nonthrowing.

Quote:
and since then swap has become the cornerstone of
...oversold, often inefficient Wink...
idioms such as copy-and-swap for achieving the strong exception
safety guarantee.

and which others?

Quote:
Does anybody know why swap was introduced into the STL in the first
place?

I'm guessing, here: for efficient sorting.

Quote:
My understanding is that it's not mandated as part of the
implementation of any algorithm (e.g., sort need not call swap), so
why was swap designed in?

Because if sort *does* call swap, and if for something like
std::string there's an efficient overload, you can efficiently sort
collections of strings. Otherwise the sort still calls swap and its
default implementation just does the copy construction and assignments
that would have happened if sort was swapping "manually" anyway.

IOW, swap provides a customization point for sorting.

Quote:
Was it put there specifically as a
mechanism for writing strongly exception safe functions

Definitely not. I just pointed out that we could easily give some
functions the strong guarantee via copy/swap (now sometimes I wish I
hadn't) -- swap had already been there for a long time.

Quote:
or was that just something peole later figured out it could be used
for?

The latter.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ 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 ]


Back to top
Andrew Koenig
Guest
PostPosted: Sat Jul 17, 2004 4:43 pm    Post subject: Re: Whence swap? Reply with quote

"Scott Meyers" <Usenet (AT) aristeia (DOT) com> wrote


Quote:
As far as I know, the STL marked the introduction of a nonthrowing "swap"
into C++, and since then swap has become the cornerstone of idioms such as
copy-and-swap for achieving the strong exception safety guarantee. Does
anybody know why swap was introduced into the STL in the first place? My
understanding is that it's not mandated as part of the implementation of
any algorithm (e.g., sort need not call swap), so why was swap designed
in?


Because it is usually possible to swap the contents of two n-element
containers in O(1) time, but swapping the elements would require O(n). This
difference is significant for algorithms such as sort and reverse that
depend on swapping to do their work.

---
[ 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 ]


Back to top
Scott Meyers
Guest
PostPosted: Sun Jul 18, 2004 12:13 am    Post subject: Re: Whence swap? Reply with quote
On Sat, 17 Jul 2004 16:43:27 +0000 (UTC), Andrew Koenig wrote:
Quote:
Because it is usually possible to swap the contents of two n-element
containers in O(1) time, but swapping the elements would require O(n). This
difference is significant for algorithms such as sort and reverse that
depend on swapping to do their work.

But the sorting algorithms are not required to call swap. Reverse is
required to call iter_swap, but iter_swap is not required to call swap, and
neither Comeau 4.3.3 nor g++ 3.2 (mingw) do.

If swap was introduced to facilitate swapping-based algorithms, why is swap
not mentioned wrt those algorithms in the standard?

Thanks,

Scott

---
[ 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 ]


Back to top
James Kuyper
Guest
PostPosted: Sun Jul 18, 2004 5:33 am    Post subject: Re: Whence swap? Reply with quote
[email]Usenet (AT) aristeia (DOT) com[/email] (Scott Meyers) wrote in message news:<MPG.1b61fd662d3812a2989779 (AT) news (DOT) hevanet.com>...
Quote:
As far as I know, the STL marked the introduction of a nonthrowing "swap"
into C++, and since then swap has become the cornerstone of idioms such as
copy-and-swap for achieving the strong exception safety guarantee. Does
anybody know why swap was introduced into the STL in the first place? My
understanding is that it's not mandated as part of the implementation of
any algorithm (e.g., sort need not call swap), so why was swap designed in?

For containers, the effects of a.swap(b) are given as swap(a,b).

Quote:
Was it put there specifically as a mechanism for writing strongly exception
safe functions, or was that just something peole later figured out it could
be used for?

I can't claim any historical knowledge of this issue. However, I
understand that there's a naive implementation of swap<T>() that will
work for any Assignable type. On the other hand, for many particular
types, such as handle types, swap<T>() can be specialized to use a
much more efficient approach. The swap<T>() template allows you to
write code that uses the naive implementation for most types, and the
more efficient implementation that is provided by the specializations,
if there are any, without you having to even be aware of the
distinction.

I don't know if that's the main purpose, but I think it's at least
part of the purpose.

---
[ 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 ]


Back to top
David Abrahams
Guest
PostPosted: Sun Jul 18, 2004 5:33 am    Post subject: Re: Whence swap? Reply with quote
[email]Usenet (AT) aristeia (DOT) com[/email] (Scott Meyers) writes:

Quote:
On Sat, 17 Jul 2004 16:43:27 +0000 (UTC), Andrew Koenig wrote:
Because it is usually possible to swap the contents of two n-element
containers in O(1) time, but swapping the elements would require O(n). This
difference is significant for algorithms such as sort and reverse that
depend on swapping to do their work.

But the sorting algorithms are not required to call swap.

No, but they're allowed to. They were not allowed to call it without
qualification before
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#226 was
resolved by
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm but
that doesn't change anything for sorting sequences of standard
containers. Those will still be swapped by std::swap.

Quote:
Reverse is required to call iter_swap, but iter_swap is not required
to call swap

It is since
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#187 ;-)

Quote:
and neither Comeau 4.3.3 nor g++ 3.2 (mingw) do.

If swap was introduced to facilitate swapping-based algorithms, why
is swap not mentioned wrt those algorithms in the standard?

Because the standard is generally designed to *allow* optimizations
but not *mandate* implementation details, so as not to prevent
implementors from finding new, innovative optimizations.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ 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 ]


Back to top
Scott Meyers
Guest
PostPosted: Sun Jul 18, 2004 9:20 am    Post subject: Re: Whence swap? Reply with quote
On Sun, 18 Jul 2004 05:33:57 +0000 (UTC), David Abrahams wrote:
Quote:
No, but they're allowed to. They were not allowed to call it without
qualification before
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#226 was
resolved by
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm but
that doesn't change anything for sorting sequences of standard
containers. Those will still be swapped by std::swap.

Thanks for the URLs. I'm now confused. Suppose I'm the author of a class
Widget, and I want to optimize Widget swapping. What do I do?

1 Define the member functions Widget::swap?
2 Define the non-member function swap(Widget&, Widget&)?
3 Define the specialization std::swap<Widget>(Widget&, Widget&)?

Until your post, I would have guessed that I should definitely do 3, and it
would probably be a nice idea to do 1, too. Now I'm beginning to think
that I'm supposed to do 2 instead of 3...

Now suppose that Widget is a template. I can still do 1, and I can do 2 by
defining swap as a template. But I'm not allowed to do 3 at all, because I
can't add partial specializations to std. At least I don't think I can.
So what do I do?

In summary, what is a class or class template author supposed to do to
offer optimized swapping that will be automatically taken advantage of by
the standard and other libraries?

Thanks,

Scott

---
[ 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 ]


Back to top
John Nagle
Guest
PostPosted: Sun Jul 18, 2004 9:21 am    Post subject: Re: Whence swap? Reply with quote

===================================== MODERATOR'S COMMENT:
A. Yes.
Q. Is top-posting discouraged in this newsgroup?


===================================== END OF MODERATOR'S COMMENT
In some ways, "swap" is more primitive than assignment.
Objects with backpointers, for example, can be swapped
but not copied. All objects which can be copied can
be swapped, but the reverse is not always true.

Arguably, objects going into collections should be
swapped in, rather than copied in. Then you could
have collections of objects with backpointers.
Collections of auto_ptr would work, too.

John Nagle
Animats


Scott Meyers wrote:

Quote:
As far as I know, the STL marked the introduction of a nonthrowing "swap"
into C++, and since then swap has become the cornerstone of idioms such as
copy-and-swap for achieving the strong exception safety guarantee. Does
anybody know why swap was introduced into the STL in the first place?

---
[ 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 ]


Back to top
Howard Hinnant
Guest
PostPosted: Mon Jul 19, 2004 12:11 am    Post subject: Re: Whence swap? Reply with quote
In article <MPG.1b63b85dd21c460698977f (AT) news (DOT) hevanet.com>,
[email]Usenet (AT) aristeia (DOT) com[/email] (Scott Meyers) wrote:

Quote:
On Sun, 18 Jul 2004 05:33:57 +0000 (UTC), David Abrahams wrote:
No, but they're allowed to. They were not allowed to call it without
qualification before
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#226 was
resolved by
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm but
that doesn't change anything for sorting sequences of standard
containers. Those will still be swapped by std::swap.

Thanks for the URLs. I'm now confused. Suppose I'm the author of a class
Widget, and I want to optimize Widget swapping. What do I do?

1 Define the member functions Widget::swap?
2 Define the non-member function swap(Widget&, Widget&)?
3 Define the specialization std::swap<Widget>(Widget&, Widget&)?

Until your post, I would have guessed that I should definitely do 3, and it
would probably be a nice idea to do 1, too. Now I'm beginning to think
that I'm supposed to do 2 instead of 3...

Now suppose that Widget is a template. I can still do 1, and I can do 2 by
defining swap as a template. But I'm not allowed to do 3 at all, because I
can't add partial specializations to std. At least I don't think I can.
So what do I do?

In summary, what is a class or class template author supposed to do to
offer optimized swapping that will be automatically taken advantage of by
the standard and other libraries?

Do 2. If you want to additionally do 1 to help you implement 2, no
problem.

If you're an author of non-std generic code that wants to use swap, do
so like:

template <class T>
void foo(T& t1, T& t2)
{
using std::swap;
swap(t1, t2);
}

swap is a fundamental operation on a type, like copy. It belongs in the
type's interface.

Coming soon (I hope): Move is a fundamental operation on a type, like
copy and swap. It belongs in the type's interface.

-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.jamesd.demon.co.uk/csc/faq.html ]


Back to top
David Abrahams
Guest
PostPosted: Mon Jul 19, 2004 12:11 am    Post subject: Re: Whence swap? Reply with quote
[email]Usenet (AT) aristeia (DOT) com[/email] (Scott Meyers) writes:

Quote:
On Sun, 18 Jul 2004 05:33:57 +0000 (UTC), David Abrahams wrote:
No, but they're allowed to. They were not allowed to call it without
qualification before
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#226 was
resolved by
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm but
that doesn't change anything for sorting sequences of standard
containers. Those will still be swapped by std::swap.

Thanks for the URLs. I'm now confused. Suppose I'm the author of a class
Widget, and I want to optimize Widget swapping. What do I do?

1 Define the member functions Widget::swap?

#1 is irrelevant to generic code, since builtins don't have member
functions.

Quote:
2 Define the non-member function swap(Widget&, Widget&)?
3 Define the specialization std::swap<Widget>(Widget&, Widget&)?

If you want your swap to be used in as many contexts as possible, you
should do #2 (in Widget's namespace) _and_ #3. You can of course
dispatch one to the other.

#3 will pick up std:: qualified calls to swap, and #2 will pick up
unqualified calls to swap. Doing #2 means you have to hope that the
author of those other libraries was cognizant of ADL and really
expects the "usual semantics" for swap(x,y).

Quote:
Until your post, I would have guessed that I should definitely do 3, and it
would probably be a nice idea to do 1, too. Now I'm beginning to think
that I'm supposed to do 2 instead of 3...

#2 is your best option once all libraries agree that swap means what
std:: says and it should be called without qualification. Until
then, it's #2 and #3.

Quote:
Now suppose that Widget is a template. I can still do 1, and I can do 2 by
defining swap as a template. But I'm not allowed to do 3 at all

Right.

Quote:
because I can't add partial specializations to std.

Yes you can. But there's no partial specialization of function
templates.

Quote:
At least I don't think I can. So what do I do?

You do #2.

Quote:
In summary, what is a class or class template author supposed to do to
offer optimized swapping that will be automatically taken advantage of by
the standard and other libraries?

With the caveat that there are no guarantees that a (standard) library
implementation not written with the resolution to LWG#226 in mind will
ever use swap, you do #2/#3 for non-templates and #2 for templates.
In practice many people will probably just do #2 and call it "good
enough".

Cheers,
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ 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 ]


Back to top
David Abrahams
Guest
PostPosted: Mon Jul 19, 2004 3:26 am    Post subject: Re: Whence swap? Reply with quote
[email]nagle (AT) animats (DOT) com[/email] (John Nagle) writes:

Quote:
===================================== MODERATOR'S COMMENT: A. Yes.
Q. Is top-posting discouraged in this newsgroup?


===================================== END OF MODERATOR'S COMMENT
In some ways, "swap" is more primitive than assignment.

The real primitive is "move".

Quote:
Objects with backpointers, for example, can be swapped
but not copied. All objects which can be copied can
be swapped,

I don't think so. A non-assignable but copyable object can't be
swapped.

Quote:
but the reverse is not always true.

Arguably, objects going into collections should be
swapped in, rather than copied in.

I think it'd be better not to try to swap const objects, don't you?
That seems like a pretty common case. Also, when inserting a new
object, there's nothing to swap with!

I'm pretty sure what you're looking for is "move construction". I'm
sure you've seen
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm,
though...?

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ 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 ]


Back to top
Andrei Alexandrescu
Guest
PostPosted: Mon Jul 19, 2004 5:03 pm    Post subject: Re: Whence swap? Reply with quote
"Howard Hinnant" <hinnant (AT) metrowerks (DOT) com> wrote

Quote:
If you're an author of non-std generic code that wants to use swap, do
so like:

template void foo(T& t1, T& t2)
{
using std::swap;
swap(t1, t2);
}

Does your implementation of the standard library use that idiom when
swapping stuff internally? Would that be a standard-compliant way of doing
things?

Andrei


---
[ 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 ]


Back to top
John Nagle
Guest
PostPosted: Mon Jul 19, 2004 5:03 pm    Post subject: Re: Whence swap? Reply with quote
David Abrahams wrote:
Quote:
nagle (AT) animats (DOT) com (John Nagle) writes:

The real primitive is "move".

I'd intended to say something about move semantics, but
the topic discussed "swap".
Quote:

Objects with backpointers, for example, can be swapped
but not copied.

This is the real case when you need "swap".

Quote:
Also, when inserting a new
object, there's nothing to swap with!

Arguably, you're swapping with an object constructed with the
default constructor.

Quote:
I'm pretty sure what you're looking for is "move construction". I'm
sure you've seen
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm,
though...?

That seems overly complicated. A simpler approach is that
these definitions should be available:

template <class T> T stl::swap(T& a, T& b)
{ T temp = a; a = b; b = temp; } // default, overrideable

template <class T> T stl::move(T& a, const T& b)
{ a = b; } // default implementation, overrideable

Insertion into collections should use "move", and some other operations
should use "swap" when appropriate. (Should resizing a vector
use "swap"?) Classes that don't define "swap" or "move" get the
existing assignment semantics, but classes that need it can
define either or both.

John Nagle

---
[ 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 ]


Back to top
Daniel Frey
Guest
PostPosted: Mon Jul 19, 2004 6:02 pm    Post subject: Re: Whence swap? Reply with quote
Andrei Alexandrescu (See Website for Email) wrote:
Quote:
"Howard Hinnant" <hinnant (AT) metrowerks (DOT) com> wrote in message
news:hinnant-B42471.11413118072004 (AT) syrcnyrdrs-02-ge0 (DOT) nyroc.rr.com...

If you're an author of non-std generic code that wants to use swap, do
so like:

template <class T
void foo(T& t1, T& t2)
{
using std::swap;
swap(t1, t2);
}


Does your implementation of the standard library use that idiom when
swapping stuff internally? Would that be a standard-compliant way of doing
things?

The standard doesn't put any requirements on functions called swap()
outside of namespace std, thus such an STL implementation cannot be
standard compliant. The user defined swap() could do anything it likes
(even nothing), although it's quite unlikely.

But if you consider the above to be the right direction, that is
mandating user defined swap() functions to be implemented with the right
semantics, I suggest you think about making std::swap an ADL-function in
general:

namespace std
{
namespace detail
{
template< typename T > void swap( T& lhs, T& rhs )
{
// Old implementation of std::swap() goes here...
}
}

template< typename T > void swap( T& lhs, T& rhs )
{
using detail::swap;
swap( lhs, rhs );
}
}

No need for the above mentioned idiom [using std::swap; swap(...);]
anymore. :)

Regards, Daniel

--
Daniel Frey

aixigo AG - financial solutions & technology
Schloß-Rahe-Straße 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: [email]daniel.frey (AT) aixigo (DOT) de[/email], web: http://www.aixigo.de


---
[ 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 ]


Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ language, library and standards All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.