std::swap question 
Author Message
 std::swap question

I read an interesting article in the March 2001 issue of CUJ about exception
safety in c++.
The article was named 'Here Be Dragons'.

From what I understood the author (forgot the name) claimed that std::swap
made a no-throw
guarantee for standard types. That's cool but when I checked out the source
for std::swap in
VC++ standard library I can't really see how it can make that guarantee as
it allocates a local
variable which should put it on the stack. But the stack might overflow,
right? So that should
generate an exception or unpredictable result.

All in all I liked the article alot and I got some good ideas to use in the
future.

Ps. I would love to cut-n-paste the code for std::swap for you guys to
analyze it. It's not long
     but I'm unsure if that's legal. OTOH you guys knows all the std::*
functions by heart
     anyway.

Marten



Thu, 02 Oct 2003 00:56:53 GMT  
 std::swap question

Quote:

> From what I understood the author (forgot the name) claimed that std::swap
> made a no-throw
> guarantee for standard types. That's cool but when I checked out the
source
> for std::swap in
> VC++ standard library I can't really see how it can make that guarantee as
> it allocates a local
> variable which should put it on the stack. But the stack might overflow,
> right?

Now there's an exercise.  Create a swap function that doesn't allocate a
local variable to use as a temporary value.

Quote:
> So that should generate an exception or unpredictable result.

That's an interesting problem.  How can you throw an exception when the
stack is full?

Remember, the C++ Standard has no concept of stacks or heaps -- those are
OS-specific things.  All the std knows about is what will produce undefined
behavior or when it should throw an exception within its own specifications.
If I pull the plug on my computer, any program that's running will have
undefined behavior but that doesn't mean it has to be mentioned in the
standard.

Quote:
> Ps. I would love to cut-n-paste the code for std::swap for you guys to
> analyze it.

I imagine it's something like:

template<class T> void swap<T>( T& a, T& b )
{
    T temp = a;
    a = b;
    b = temp;

Quote:
}

Sean


Thu, 02 Oct 2003 01:48:35 GMT  
 std::swap question

Quote:
> I read an interesting article in the March 2001 issue of CUJ about
exception
> safety in c++.
> The article was named 'Here Be Dragons'.

> From what I understood the author (forgot the name) claimed that std::swap
> made a no-throw
> guarantee for standard types. That's cool but when I checked out the
source
> for std::swap in
> VC++ standard library I can't really see how it can make that guarantee as
> it allocates a local
> variable which should put it on the stack. But the stack might overflow,
> right? So that should
> generate an exception or unpredictable result.

There is no such thing in Standard C++ as a "stack overflow exception", so
std::swap can guarantee not to throw one!.

NeilB



Thu, 02 Oct 2003 00:58:49 GMT  
 std::swap question

Quote:

> From what I understood the author (forgot the name) claimed that
> std::swap made a no-throw guarantee for standard types. That's cool
> but when I checked out the source for std::swap in VC++ standard
> library I can't really see how it can make that guarantee as it
> allocates a local variable which should put it on the stack. But the
> stack might overflow, right? So that should generate an exception or
> unpredictable result.

In terms of the standard, the only exceptions it covers are C++
language exceptions, not hardware/OS exceptions.  A stack overflow
will not cause a C++ exception (but it may cause an OS or hardware
exception.)

The guarantee of std::swap is that for built-in types it will not
throw a C++ exception.  If, whild calling std::swap, the stack DOES
overflow, no C++ exception is thrown.  Thus, even with unpredicatable
behavior, the guarantee is met.

But if your stack is going to overflow with an additional 4 bytes,
then your program is already seriously flawed (for an unrelated
reason) and std::swap should be the least of your concerns.  :)

--
Chris



Thu, 02 Oct 2003 13:59:44 GMT  
 std::swap question

Quote:

>Now there's an exercise.  Create a swap function that doesn't allocate a
>local variable to use as a temporary value.

I think this will do it:

template < class T > void swap( T& a, T& b )
{
    char* pa = reinterpret_cast<char*>( & a );
    char* pb = reinterpret_cast<char*>( & b );

    for( int i = 0; i < sizeof(a); ++i, ++pa, ++pb )
    {
        *pb = *pa ^ *pb;
        *pa = *pa ^ *pb;
        *pb = *pa ^ *pb;
    }

Quote:
}



Fri, 03 Oct 2003 22:15:35 GMT  
 std::swap question

Quote:

> I think this will do it:

> template < class T > void swap( T& a, T& b )
> {
>     char* pa = reinterpret_cast<char*>( & a );
>     char* pb = reinterpret_cast<char*>( & b );

>     for( int i = 0; i < sizeof(a); ++i, ++pa, ++pb )
>     {
>         *pb = *pa ^ *pb;
>         *pa = *pa ^ *pb;
>         *pb = *pa ^ *pb;
>     }
> }

int a = 3;
swap(a, a);     // surprise!

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



Fri, 03 Oct 2003 22:23:28 GMT  
 std::swap question
First: aren't pa, pb and i local variables in your example? Where exactly is
the advantage?

Second: this is good for POD types only (not even for them as Pete Becker
shows - it can't handle overlapping memory regions). The requirement on
std::swap template is that it works with any Assignable type, including
classes with nontrivial assignment operators. No template trick (like
partial specialization) can separate POD and non-POD types, though one can
provide optimized specializations for fundamental types.
--
With best wishes,
    Igor Tandetnik


Quote:

> >Now there's an exercise.  Create a swap function that doesn't allocate a
> >local variable to use as a temporary value.

> I think this will do it:

> template < class T > void swap( T& a, T& b )
> {
>     char* pa = reinterpret_cast<char*>( & a );
>     char* pb = reinterpret_cast<char*>( & b );

>     for( int i = 0; i < sizeof(a); ++i, ++pa, ++pb )
>     {
>         *pb = *pa ^ *pb;
>         *pa = *pa ^ *pb;
>         *pb = *pa ^ *pb;
>     }
> }



Fri, 03 Oct 2003 22:45:02 GMT  
 std::swap question


Fri, 19 Jun 1992 00:00:00 GMT  
 std::swap question
  Actually, a template/ partial specialization trick can be used for POD and
non-POD types; just like iterator_traits<> & numeric_limits; and I await the
day I can use this with VC. Unfortunately, the C++ standard doesn't define
something like this yet, as it is useful and pertains to all types (not just
numeric types as numeric_limits<> does):

EITHER (Plan A)

template< class T >
struct value_traits
{
  inline static bool is_POD() throw() { return T::is_POD(); }

Quote:
};

OR (Plan B)

template< class T >
struct value_traits
{
  inline static bool is_POD() throw() { return false; }

Quote:
};

BASIC TYPES:
template< class T >
struct value_traits< T* >
{
  inline static bool is_POD() throw() { return true; }

Quote:
}

template< class T >
struct value_traits< char >
{
  inline static bool is_POD() throw() { return true; }
Quote:
}

...

THEN each new type needs EITHER (Plan A) a static method is_POD() indicating
if the type is POD or not OR (Plan B) a complete specialization of
value_traits is needed to specify the type as POD. Plan B is definitely the
more backward compatable.

Right now, I use a const bool template parameter on each of my custom
containers which defaults to false, which indicates POD; but I'd love to
switch to Plan B when VC supports partial specialization. POD awareness is
something that definitely speeds my apps up (and probabaly is preventing
generic programming in C++ with STL from reaching speeds typically
associated with hand-writen C speeds). POD awareness means I can use raw
memory techniques for moving and copying data, and I don't have to call
destructors. I can also use exception un-safe techniques, because I can
assure assignment, and construction can't throw.


Quote:
> First: aren't pa, pb and i local variables in your example? Where exactly
is
> the advantage?

> Second: this is good for POD types only (not even for them as Pete Becker
> shows - it can't handle overlapping memory regions). The requirement on
> std::swap template is that it works with any Assignable type, including
> classes with nontrivial assignment operators. No template trick (like
> partial specialization) can separate POD and non-POD types, though one can
> provide optimized specializations for fundamental types.
> --
> With best wishes,
>     Igor Tandetnik



Sat, 04 Oct 2003 02:50:42 GMT  
 std::swap question
Plan A is awful in that it requires the programmer to remember to add a
method to every single class he writes, and explicit specialization of
value_traits for every third-party class or struct he happens to use,
including ones from STL or windows.h. Imagine for a second how many structs
there are in Windows headers. I don't think it is really feasible.

Plan B is good at distinguishing fundamental types from all other types (and
actually I said it was possible in my previous post), but what about POD
structs? You are back to providing explicit specialization for every single
one.

Or maybe you are thinking fundamental (aka basic) types and POD types are
the same? POD type is any fundamental type, plus arrays, structures and
unions of POD types. In addition, structures and unions must be really
plain - no funny business like vurtual functions, user-defined constructors
or assignment operators and so on. See complete description in C++ standard
chapter 9 "Classes" paragraph 4.
--
With best wishes,
    Igor Tandetnik



Quote:
>   Actually, a template/ partial specialization trick can be used for POD
and
> non-POD types; just like iterator_traits<> & numeric_limits; and I await
the
> day I can use this with VC. Unfortunately, the C++ standard doesn't define
> something like this yet, as it is useful and pertains to all types (not
just
> numeric types as numeric_limits<> does):

> EITHER (Plan A)

> template< class T >
> struct value_traits
> {
>   inline static bool is_POD() throw() { return T::is_POD(); }
> };

> OR (Plan B)

> template< class T >
> struct value_traits
> {
>   inline static bool is_POD() throw() { return false; }
> };

> BASIC TYPES:
> template< class T >
> struct value_traits< T* >
> {
>   inline static bool is_POD() throw() { return true; }
> }

> template< class T >
> struct value_traits< char >
> {
>   inline static bool is_POD() throw() { return true; }
> }
> ...

> THEN each new type needs EITHER (Plan A) a static method is_POD()
indicating
> if the type is POD or not OR (Plan B) a complete specialization of
> value_traits is needed to specify the type as POD. Plan B is definitely
the
> more backward compatable.

> Right now, I use a const bool template parameter on each of my custom
> containers which defaults to false, which indicates POD; but I'd love to
> switch to Plan B when VC supports partial specialization. POD awareness is
> something that definitely speeds my apps up (and probabaly is preventing
> generic programming in C++ with STL from reaching speeds typically
> associated with hand-writen C speeds). POD awareness means I can use raw
> memory techniques for moving and copying data, and I don't have to call
> destructors. I can also use exception un-safe techniques, because I can
> assure assignment, and construction can't throw.



> > First: aren't pa, pb and i local variables in your example? Where
exactly
> is
> > the advantage?

> > Second: this is good for POD types only (not even for them as Pete
Becker
> > shows - it can't handle overlapping memory regions). The requirement on
> > std::swap template is that it works with any Assignable type, including
> > classes with nontrivial assignment operators. No template trick (like
> > partial specialization) can separate POD and non-POD types, though one
can
> > provide optimized specializations for fundamental types.
> > --
> > With best wishes,
> >     Igor Tandetnik



Sat, 04 Oct 2003 04:31:03 GMT  
 std::swap question


Fri, 19 Jun 1992 00:00:00 GMT  
 std::swap question
My goodness, what a vicious attack on what I thought was just a simple solution.
I hadn't considered overlapping memory swaps (easily handled, though) nor objects
that are not bitwise assignable (not so easily handled, I think).

But in the spirit of my "solution", the fact that pa, pb and i are local is of no
consequence - they end up in registers so do not affect the stack.

Quote:
-----Original Message-----

First: aren't pa, pb and i local variables in your example? Where exactly is
the advantage?

Second: this is good for POD types only (not even for them as Pete Becker
shows - it can't handle overlapping memory regions). The requirement on
std::swap template is that it works with any Assignable type, including
classes with nontrivial assignment operators. No template trick (like
partial specialization) can separate POD and non-POD types, though one can
provide optimized specializations for fundamental types.
--
With best wishes,
    Igor Tandetnik



> >Now there's an exercise.  Create a swap function that doesn't allocate a
> >local variable to use as a temporary value.

> I think this will do it:

> template < class T > void swap( T& a, T& b )
> {
>     char* pa = reinterpret_cast<char*>( & a );
>     char* pb = reinterpret_cast<char*>( & b );

>     for( int i = 0; i < sizeof(a); ++i, ++pa, ++pb )
>     {
>         *pb = *pa ^ *pb;
>         *pa = *pa ^ *pb;
>         *pb = *pa ^ *pb;
>     }
> }

.



Sat, 04 Oct 2003 05:17:35 GMT  
 std::swap question


Fri, 19 Jun 1992 00:00:00 GMT  
 std::swap question
I know that POD is more than just basic types. Without an automatic
detection factility such as is_POD() operator from the C++ compiler, there's
no way to get automatic/ always correct behavior, right? However, I thought
I'd suggest a pretty elegant way to let containers be optimized for POD and
use memcpy, etc. for library implementations. The primary container
optimization, I thought, would be some kind of POD vs non-POD detection,
which could be a custom extension into an STL implementation. Just my
thoughts on why I find STL implementations lacking sometimes.

BTW, I thought structures are the same as classes. For ex: "struct s { ..."
is shorthand for "class s { public: ...", meaning structures can have al the
funny business that classes have (like virtual functions, etc.). I know
unions must be plain... I wonder if there's a way to take advantage of the
compiler's detection of POD by trying to build a union of a type...


Quote:
> Plan A is awful in that it requires the programmer to remember to add a
> method to every single class he writes, and explicit specialization of
> value_traits for every third-party class or struct he happens to use,
> including ones from STL or windows.h. Imagine for a second how many
structs
> there are in Windows headers. I don't think it is really feasible.

> Plan B is good at distinguishing fundamental types from all other types
(and
> actually I said it was possible in my previous post), but what about POD
> structs? You are back to providing explicit specialization for every
single
> one.

> Or maybe you are thinking fundamental (aka basic) types and POD types are
> the same? POD type is any fundamental type, plus arrays, structures and
> unions of POD types. In addition, structures and unions must be really
> plain - no funny business like vurtual functions, user-defined
constructors
> or assignment operators and so on. See complete description in C++
standard
> chapter 9 "Classes" paragraph 4.
> --
> With best wishes,
>     Igor Tandetnik



> >   Actually, a template/ partial specialization trick can be used for POD
> and
> > non-POD types; just like iterator_traits<> & numeric_limits; and I await
> the
> > day I can use this with VC. Unfortunately, the C++ standard doesn't
define
> > something like this yet, as it is useful and pertains to all types (not
> just
> > numeric types as numeric_limits<> does):

> > EITHER (Plan A)

> > template< class T >
> > struct value_traits
> > {
> >   inline static bool is_POD() throw() { return T::is_POD(); }
> > };

> > OR (Plan B)

> > template< class T >
> > struct value_traits
> > {
> >   inline static bool is_POD() throw() { return false; }
> > };

> > BASIC TYPES:
> > template< class T >
> > struct value_traits< T* >
> > {
> >   inline static bool is_POD() throw() { return true; }
> > }

> > template< class T >
> > struct value_traits< char >
> > {
> >   inline static bool is_POD() throw() { return true; }
> > }
> > ...

> > THEN each new type needs EITHER (Plan A) a static method is_POD()
> indicating
> > if the type is POD or not OR (Plan B) a complete specialization of
> > value_traits is needed to specify the type as POD. Plan B is definitely
> the
> > more backward compatable.

> > Right now, I use a const bool template parameter on each of my custom
> > containers which defaults to false, which indicates POD; but I'd love to
> > switch to Plan B when VC supports partial specialization. POD awareness
is
> > something that definitely speeds my apps up (and probabaly is preventing
> > generic programming in C++ with STL from reaching speeds typically
> > associated with hand-writen C speeds). POD awareness means I can use raw
> > memory techniques for moving and copying data, and I don't have to call
> > destructors. I can also use exception un-safe techniques, because I can
> > assure assignment, and construction can't throw.



> > > First: aren't pa, pb and i local variables in your example? Where
> exactly
> > is
> > > the advantage?

> > > Second: this is good for POD types only (not even for them as Pete
> Becker
> > > shows - it can't handle overlapping memory regions). The requirement
on
> > > std::swap template is that it works with any Assignable type,
including
> > > classes with nontrivial assignment operators. No template trick (like
> > > partial specialization) can separate POD and non-POD types, though one
> can
> > > provide optimized specializations for fundamental types.
> > > --
> > > With best wishes,
> > >     Igor Tandetnik



Sat, 04 Oct 2003 05:26:40 GMT  
 std::swap question
Structures and unions can have all the funny business that classes have. But
if they do have the funny business, they are not called POD. That's why it
is so hard to distinguish between POD and non-POD structs. I too see where
it may be of benefit, but, unfortunately, I don't see any reasonable way to
make the compiler divulge the information.
--
With best wishes,
    Igor Tandetnik



Quote:
> I know that POD is more than just basic types. Without an automatic
> detection factility such as is_POD() operator from the C++ compiler,
there's
> no way to get automatic/ always correct behavior, right? However, I
thought
> I'd suggest a pretty elegant way to let containers be optimized for POD
and
> use memcpy, etc. for library implementations. The primary container
> optimization, I thought, would be some kind of POD vs non-POD detection,
> which could be a custom extension into an STL implementation. Just my
> thoughts on why I find STL implementations lacking sometimes.

> BTW, I thought structures are the same as classes. For ex: "struct s
 ..."
> is shorthand for "class s { public: ...", meaning structures can have al
the
> funny business that classes have (like virtual functions, etc.). I know
> unions must be plain... I wonder if there's a way to take advantage of the
> compiler's detection of POD by trying to build a union of a type...



> > Plan A is awful in that it requires the programmer to remember to add a
> > method to every single class he writes, and explicit specialization of
> > value_traits for every third-party class or struct he happens to use,
> > including ones from STL or windows.h. Imagine for a second how many
> structs
> > there are in Windows headers. I don't think it is really feasible.

> > Plan B is good at distinguishing fundamental types from all other types
> (and
> > actually I said it was possible in my previous post), but what about POD
> > structs? You are back to providing explicit specialization for every
> single
> > one.

> > Or maybe you are thinking fundamental (aka basic) types and POD types
are
> > the same? POD type is any fundamental type, plus arrays, structures and
> > unions of POD types. In addition, structures and unions must be really
> > plain - no funny business like vurtual functions, user-defined
> constructors
> > or assignment operators and so on. See complete description in C++
> standard
> > chapter 9 "Classes" paragraph 4.
> > --
> > With best wishes,
> >     Igor Tandetnik



> > >   Actually, a template/ partial specialization trick can be used for
POD
> > and
> > > non-POD types; just like iterator_traits<> & numeric_limits; and I
await
> > the
> > > day I can use this with VC. Unfortunately, the C++ standard doesn't
> define
> > > something like this yet, as it is useful and pertains to all types
(not
> > just
> > > numeric types as numeric_limits<> does):

> > > EITHER (Plan A)

> > > template< class T >
> > > struct value_traits
> > > {
> > >   inline static bool is_POD() throw() { return T::is_POD(); }
> > > };

> > > OR (Plan B)

> > > template< class T >
> > > struct value_traits
> > > {
> > >   inline static bool is_POD() throw() { return false; }
> > > };

> > > BASIC TYPES:
> > > template< class T >
> > > struct value_traits< T* >
> > > {
> > >   inline static bool is_POD() throw() { return true; }
> > > }

> > > template< class T >
> > > struct value_traits< char >
> > > {
> > >   inline static bool is_POD() throw() { return true; }
> > > }
> > > ...

> > > THEN each new type needs EITHER (Plan A) a static method is_POD()
> > indicating
> > > if the type is POD or not OR (Plan B) a complete specialization of
> > > value_traits is needed to specify the type as POD. Plan B is
definitely
> > the
> > > more backward compatable.

> > > Right now, I use a const bool template parameter on each of my custom
> > > containers which defaults to false, which indicates POD; but I'd love
to
> > > switch to Plan B when VC supports partial specialization. POD
awareness
> is
> > > something that definitely speeds my apps up (and probabaly is
preventing
> > > generic programming in C++ with STL from reaching speeds typically
> > > associated with hand-writen C speeds). POD awareness means I can use
raw
> > > memory techniques for moving and copying data, and I don't have to
call
> > > destructors. I can also use exception un-safe techniques, because I
can
> > > assure assignment, and construction can't throw.



> > > > First: aren't pa, pb and i local variables in your example? Where
> > exactly
> > > is
> > > > the advantage?

> > > > Second: this is good for POD types only (not even for them as Pete
> > Becker
> > > > shows - it can't handle overlapping memory regions). The requirement
> on
> > > > std::swap template is that it works with any Assignable type,
> including
> > > > classes with nontrivial assignment operators. No template trick
(like
> > > > partial specialization) can separate POD and non-POD types, though
one
> > can
> > > > provide optimized specializations for fundamental types.
> > > > --
> > > > With best wishes,
> > > >     Igor Tandetnik



Sat, 04 Oct 2003 06:30:52 GMT  
 
 [ 21 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Bug in overlaoding std::swap?

2. basic std::stringstream and std::string questions

3. Swap pointers to swap data and how?

4. Question about swap function in Quicksort?

5. Question: Correct process to byte-swap floats?

6. question about FAQ, swapping values

7. Question about swapping nodes in a doubly linked list

8. Generic swap - comments and questions

9. question about SWAP

10. No std::min or std::max?

11. bug: VS7.0 (6.0) C++ std::auto_ptr conflict with std::vector

12. convert between std::string and std::wstring

 

 
Powered by phpBB® Forum Software