Does C++11 Change the Behavior of Explicitly Calling Std::Swap to Ensure Adl-Located Swap's Are Found, Like Boost::Swap

Does C++11 change the behavior of explicitly calling std::swap to ensure ADL-located swap's are found, like boost::swap?

I would have had to vote against your proof-of-concept implementation had it been proposed. I fear it would break the following code, which I'm pretty sure I've seen in the wild at least once or twice over the past dozen years.

namespace oops
{

    struct foo
    {
        foo() : i(0) {}
        int i;

        void swap(foo& x) {std::swap(*this, x);}
    };

    void swap(foo& lhs, foo& rhs)
    {
        lhs.swap(rhs);
    }

}

Whether you think the above is good code or bad, it works as the author intends in C++98/03 and so the bar for silently breaking it is pretty high. Telling users that in C++11 they would no longer have to write using std::swap; isn't a sufficiently high benefit to outweigh the disadvantage of silently turning the above code into infinite recursion.

Another way to get out of writing using std::swap; is to use std::iter_swap instead:

template <typename T>
void do_swap(T& lhs, T& rhs)
{
    std::iter_swap(&lhs, &rhs); // internally does what do_swap did above
}

Is std::swap guaranteed to find nonmember swap by ADL?

From C++14 (or more specifically N4140):

Requires: Type T shall be MoveConstructible (Table 20) and MoveAssignable (Table 22).
Effects: Exchanges values stored in two locations.

There is nothing here about calling non-member swap. So no, there are no guarantees that std::swap is implemented via non-member swap.

It's not entirely clear if an implementation would even be allowed to implement std::swap in terms of a user-defined, non-member ADL swap.

Question on boost::swap

This makes it less specialized than std::swap so you don't get overload ambiguity errors when both std::swap and boost::swap are in scope (std::swap will take precedence).
No, non-templates always have precedence over templates during overload resolution, so a namespace-scoped non-template swap will take precedence over both boost::swap and std::swap (as will a namespace-scoped template swap overloaded for a UDT – think partially-specialized, but not really..). Note that unlike std::swap, boost::swap is written explicitly to take advantage of ADL.

Here's what the C++03 standard has to say regarding both points – [over.match.best] (§13.3.3/1):

Define ICSi(F) as follows:

if F is a static member function, ICS1(F) is defined such that ICS1(F) is neither better nor worse than ICS1(G) for any function G, and, symmetrically, ICS1(G) is neither better nor worse than ICS1(F); otherwise,

let ICSi(F) denote the implicit conversion sequence that converts the i-th argument in the list to the type of the i-th parameter of viable function F. 13.3.3.1 defines the implicit conversion sequences and 13.3.3.2 defines what it means for one implicit conversion sequence to be a better conversion sequence or worse conversion sequence than another.

Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if for all arguments i, ICSi(F1) is not a worse conversion sequence than ICSi(F2), and then

for some argument j, ICSj(F1) is a better conversion sequence than ICSj(F2), or, if not that,

F1 is a non-template function and F2 is a function template specialization, or, if not that,

F1 and F2 are function template specializations, and the function template for F1 is more specialized than the template for F2 according to the partial ordering rules described in 14.5.5.2, or, if not that,

the context is an initialization by user-defined conversion (see 8.5, 13.3.1.5, and 13.3.1.6) and the standard conversion sequence from the return type of F1 to the destination type (i.e., the type of the entity being initialized) is a better conversion sequence than the standard conversion sequence from the return type of F2 to the destination type.

public friend swap member function

There are several ways to write swap, some better than others. Over time, though, it was found a single definition works best. Let's consider how we might think about writing a swap function.

We first see that containers like std::vector<> have a single-argument member function swap, such as:

struct vector
{
    void swap(vector&) { /* swap members */ }
};

Naturally, then, our class should too, right? Well, not really. The standard library has all sorts of unnecessary things, and a member swap is one of them. Why? Let's go on.

What we should do is identify what's canonical, and what our class needs to do to work with it. And the canonical method of swapping is with std::swap. This is why member functions aren't useful: they aren't how we should swap things, in general, and have no bearing on the behavior of std::swap.

Well then, to make std::swap work we should provide (and std::vector<> should have provided) a specialization of std::swap, right?

namespace std
{
    template <> // important! specialization in std is OK, overloading is UB
    void swap(myclass&, myclass&)
    {
        // swap
    }
}

Well that would certainly work in this case, but it has a glaring problem: function specializations cannot be partial. That is, we cannot specialize template classes with this, only particular instantiations:

namespace std
{
    template <typename T>
    void swap<T>(myclass<T>&, myclass<T>&) // error! no partial specialization
    {
        // swap
    }
}

This method works some of the time, but not all of the time. There must be a better way.

There is! We can use a friend function, and find it through ADL:

namespace xyz
{
    struct myclass
    {
        friend void swap(myclass&, myclass&);
    };
}

When we want to swap something, we associate^† std::swap and then make an unqualified call:

using std::swap; // allow use of std::swap...
swap(x, y); // ...but select overloads, first

// that is, if swap(x, y) finds a better match, via ADL, it
// will use that instead; otherwise it falls back to std::swap

What is a friend function? There is confusion around this area.

Before C++ was standardized, friend functions did something called "friend name injection", where the code behaved as if if the function had been written in the surrounding namespace. For example, these were equivalent pre-standard:

struct foo
{
    friend void bar()
    {
        // baz
    }
};

// turned into, pre-standard:    

struct foo
{
    friend void bar();
};

void bar()
{
    // baz
}

However, when ADL was invented this was removed. The friend function could then only be found via ADL; if you wanted it as a free function, it needed to be declared as so (see this, for example). But lo! There was a problem.

If you just use std::swap(x, y), your overload will never be found, because you've explicitly said "look in std, and nowhere else"! This is why some people suggested writing two functions: one as a function to be found via ADL, and the other to handle explicit std:: qualifications.

But like we saw, this can't work in all cases, and we end up with an ugly mess. Instead, idiomatic swapping went the other route: instead of making it the classes' job to provide std::swap, it's the swappers' job to make sure they don't use qualified swap, like above. And this tends to work pretty well, as long as people know about it. But therein lies the problem: it's unintuitive to need to use an unqualified call!

To make this easier, some libraries like Boost provided the function boost::swap, which just does an unqualified call to swap, with std::swap as an associated namespace. This helps make things succinct again, but it's still a bummer.

Note that there is no change in C++11 to the behavior of std::swap, which I and others mistakenly thought would be the case. If you were bit by this, read here.

In short: the member function is just noise, the specialization is ugly and incomplete, but the friend function is complete and works. And when you swap, either use boost::swap or an unqualified swap with std::swap associated.

†Informally, a name is associated if it will be considered during a function call. For the details, read §3.4.2. In this case, std::swap normally isn't considered; but we can associate it (add it to the set of overloads considered by unqualified swap), allowing it to be found.

Why std::swap does not work with std::bitsetn content?

This:

std::swap( bitset[pos], bitset[_Count-pos-1] );

should actual fail to compile. operator[] for a std::bitset doesn't return a reference, it returns a proxy object. That proxy object isn't an lvalue, so it cannot bind to the T& in std::swap. I'm assuming the fact that it compiles at all means that you're using MSVC which has an extension that allows binding temporaries to non-const references - at which point you're probably just swapping the proxies and not what the proxies are actually referring to.

Side-note: The name _Count is reserved by the standard, as is any other name which begins with an _ followed by a capital letter.

What is the copy-and-swap idiom?

Overview

Why do we need the copy-and-swap idiom?

Any class that manages a resource (a wrapper, like a smart pointer) needs to implement The Big Three. While the goals and implementation of the copy-constructor and destructor are straightforward, the copy-assignment operator is arguably the most nuanced and difficult. How should it be done? What pitfalls need to be avoided?

The copy-and-swap idiom is the solution, and elegantly assists the assignment operator in achieving two things: avoiding code duplication, and providing a strong exception guarantee.

How does it work?

Conceptually, it works by using the copy-constructor's functionality to create a local copy of the data, then takes the copied data with a swap function, swapping the old data with the new data. The temporary copy then destructs, taking the old data with it. We are left with a copy of the new data.

In order to use the copy-and-swap idiom, we need three things: a working copy-constructor, a working destructor (both are the basis of any wrapper, so should be complete anyway), and a swap function.

A swap function is a non-throwing function that swaps two objects of a class, member for member. We might be tempted to use std::swap instead of providing our own, but this would be impossible; std::swap uses the copy-constructor and copy-assignment operator within its implementation, and we'd ultimately be trying to define the assignment operator in terms of itself!

(Not only that, but unqualified calls to swap will use our custom swap operator, skipping over the unnecessary construction and destruction of our class that std::swap would entail.)

An in-depth explanation

The goal

Let's consider a concrete case. We want to manage, in an otherwise useless class, a dynamic array. We start with a working constructor, copy-constructor, and destructor:

#include <algorithm> // std::copy
#include <cstddef> // std::size_t

class dumb_array
{
public:
    // (default) constructor
    dumb_array(std::size_t size = 0)
        : mSize(size),
          mArray(mSize ? new int[mSize]() : nullptr)
    {
    }

    // copy-constructor
    dumb_array(const dumb_array& other)
        : mSize(other.mSize),
          mArray(mSize ? new int[mSize] : nullptr)
    {
        // note that this is non-throwing, because of the data
        // types being used; more attention to detail with regards
        // to exceptions must be given in a more general case, however
        std::copy(other.mArray, other.mArray + mSize, mArray);
    }

    // destructor
    ~dumb_array()
    {
        delete [] mArray;
    }

private:
    std::size_t mSize;
    int* mArray;
};

This class almost manages the array successfully, but it needs operator= to work correctly.

A failed solution

Here's how a naive implementation might look:

// the hard part
dumb_array& operator=(const dumb_array& other)
{
    if (this != &other) // (1)
    {
        // get rid of the old data...
        delete [] mArray; // (2)
        mArray = nullptr; // (2) *(see footnote for rationale)

        // ...and put in the new
        mSize = other.mSize; // (3)
        mArray = mSize ? new int[mSize] : nullptr; // (3)
        std::copy(other.mArray, other.mArray + mSize, mArray); // (3)
    }

    return *this;
}

And we say we're finished; this now manages an array, without leaks. However, it suffers from three problems, marked sequentially in the code as (n).

The first is the self-assignment test.

This check serves two purposes: it's an easy way to prevent us from running needless code on self-assignment, and it protects us from subtle bugs (such as deleting the array only to try and copy it). But in all other cases it merely serves to slow the program down, and act as noise in the code; self-assignment rarely occurs, so most of the time this check is a waste.

It would be better if the operator could work properly without it.

The second is that it only provides a basic exception guarantee. If new int[mSize] fails, *this will have been modified. (Namely, the size is wrong and the data is gone!)

For a strong exception guarantee, it would need to be something akin to:

 dumb_array& operator=(const dumb_array& other)
 {
     if (this != &other) // (1)
     {
         // get the new data ready before we replace the old
         std::size_t newSize = other.mSize;
         int* newArray = newSize ? new int[newSize]() : nullptr; // (3)
         std::copy(other.mArray, other.mArray + newSize, newArray); // (3)

         // replace the old data (all are non-throwing)
         delete [] mArray;
         mSize = newSize;
         mArray = newArray;
     }

     return *this;
 }

The code has expanded! Which leads us to the third problem: code duplication.

Our assignment operator effectively duplicates all the code we've already written elsewhere, and that's a terrible thing.

In our case, the core of it is only two lines (the allocation and the copy), but with more complex resources this code bloat can be quite a hassle. We should strive to never repeat ourselves.

(One might wonder: if this much code is needed to manage one resource correctly, what if my class manages more than one?

While this may seem to be a valid concern, and indeed it requires non-trivial try/catch clauses, this is a non-issue.

That's because a class should manage one resource only!)

A successful solution

As mentioned, the copy-and-swap idiom will fix all these issues. But right now, we have all the requirements except one: a swap function. While The Rule of Three successfully entails the existence of our copy-constructor, assignment operator, and destructor, it should really be called "The Big Three and A Half": any time your class manages a resource it also makes sense to provide a swap function.

We need to add swap functionality to our class, and we do that as follows†:

class dumb_array
{
public:
    // ...

    friend void swap(dumb_array& first, dumb_array& second) // nothrow
    {
        // enable ADL (not necessary in our case, but good practice)
        using std::swap;

        // by swapping the members of two objects,
        // the two objects are effectively swapped
        swap(first.mSize, second.mSize);
        swap(first.mArray, second.mArray);
    }

    // ...
};

(Here is the explanation why public friend swap.) Now not only can we swap our dumb_array's, but swaps in general can be more efficient; it merely swaps pointers and sizes, rather than allocating and copying entire arrays. Aside from this bonus in functionality and efficiency, we are now ready to implement the copy-and-swap idiom.

Without further ado, our assignment operator is:

dumb_array& operator=(dumb_array other) // (1)
{
    swap(*this, other); // (2)

    return *this;
}

And that's it! With one fell swoop, all three problems are elegantly tackled at once.

Why does it work?

We first notice an important choice: the parameter argument is taken by-value. While one could just as easily do the following (and indeed, many naive implementations of the idiom do):

dumb_array& operator=(const dumb_array& other)
{
    dumb_array temp(other);
    swap(*this, temp);

    return *this;
}

We lose an important optimization opportunity. Not only that, but this choice is critical in C++11, which is discussed later. (On a general note, a remarkably useful guideline is as follows: if you're going to make a copy of something in a function, let the compiler do it in the parameter list.‡)

Either way, this method of obtaining our resource is the key to eliminating code duplication: we get to use the code from the copy-constructor to make the copy, and never need to repeat any bit of it. Now that the copy is made, we are ready to swap.

Observe that upon entering the function that all the new data is already allocated, copied, and ready to be used. This is what gives us a strong exception guarantee for free: we won't even enter the function if construction of the copy fails, and it's therefore not possible to alter the state of *this. (What we did manually before for a strong exception guarantee, the compiler is doing for us now; how kind.)

At this point we are home-free, because swap is non-throwing. We swap our current data with the copied data, safely altering our state, and the old data gets put into the temporary. The old data is then released when the function returns. (Where upon the parameter's scope ends and its destructor is called.)

Because the idiom repeats no code, we cannot introduce bugs within the operator. Note that this means we are rid of the need for a self-assignment check, allowing a single uniform implementation of operator=. (Additionally, we no longer have a performance penalty on non-self-assignments.)

And that is the copy-and-swap idiom.

What about C++11?

The next version of C++, C++11, makes one very important change to how we manage resources: the Rule of Three is now The Rule of Four (and a half). Why? Because not only do we need to be able to copy-construct our resource, we need to move-construct it as well.

Luckily for us, this is easy:

class dumb_array
{
public:
    // ...

    // move constructor
    dumb_array(dumb_array&& other) noexcept ††
        : dumb_array() // initialize via default constructor, C++11 only
    {
        swap(*this, other);
    }

    // ...
};

What's going on here? Recall the goal of move-construction: to take the resources from another instance of the class, leaving it in a state guaranteed to be assignable and destructible.

So what we've done is simple: initialize via the default constructor (a C++11 feature), then swap with other; we know a default constructed instance of our class can safely be assigned and destructed, so we know other will be able to do the same, after swapping.

(Note that some compilers do not support constructor delegation; in this case, we have to manually default construct the class. This is an unfortunate but luckily trivial task.)

Why does that work?

That is the only change we need to make to our class, so why does it work? Remember the ever-important decision we made to make the parameter a value and not a reference:

dumb_array& operator=(dumb_array other); // (1)

Now, if other is being initialized with an rvalue, it will be move-constructed. Perfect. In the same way C++03 let us re-use our copy-constructor functionality by taking the argument by-value, C++11 will automatically pick the move-constructor when appropriate as well. (And, of course, as mentioned in previously linked article, the copying/moving of the value may simply be elided altogether.)

And so concludes the copy-and-swap idiom.

Footnotes

*Why do we set mArray to null? Because if any further code in the operator throws, the destructor of dumb_array might be called; and if that happens without setting it to null, we attempt to delete memory that's already been deleted! We avoid this by setting it to null, as deleting null is a no-operation.

†There are other claims that we should specialize std::swap for our type, provide an in-class swap along-side a free-function swap, etc. But this is all unnecessary: any proper use of swap will be through an unqualified call, and our function will be found through ADL. One function will do.

‡The reason is simple: once you have the resource to yourself, you may swap and/or move it (C++11) anywhere it needs to be. And by making the copy in the parameter list, you maximize optimization.

††The move constructor should generally be noexcept, otherwise some code (e.g. std::vector resizing logic) will use the copy constructor even when a move would make sense. Of course, only mark it noexcept if the code inside doesn't throw exceptions.

Making swap faster, easier to use and exception-safe

So why not simply write a swap template that does exactly that: swap the object representations*?

There's many ways in which an object, once being constructed, can break when you copy the bytes it resides in. In fact, one could come up with a seemingly endless number of cases where this would not do the right thing - even though in practice it might work in 98% of all cases.

That's because the underlying problem to all this is that, other than in C, in C++ we must not treat objects as if they are mere raw bytes. That's why we have construction and destruction, after all: to turn raw storage into objects and objects back into raw storage. Once a constructor has run, the memory where the object resides is more than only raw storage. If you treat it as if it weren't, you will break some types.

However, essentially, moving objects shouldn't perform that much worse than your idea, because, once you start to recursively inline the calls to std::move(), you usually ultimately arrive at where built-ins are moved. (And if there's more to moving for some types, you'd better not fiddle with the memory of those yourself!) Granted, moving memory en bloc is usually faster than single moves (and it's unlikely that a compiler might find out that it could optimize the individual moves to one all-encompassing std::memcpy()), but that's the price we pay for the abstraction opaque objects offer us. And it's quite small, especially when you compare it to the copying we used to do.

You could, however, have an optimized swap() using std::memcpy() for aggregate types.

how to provide a swap function for my class?

is the proper use of swap. Write it this way when you write "library" code and want to enable ADL (argument-dependent lookup) on swap. Also, this has nothing to do with SFINAE.

// some algorithm in your code
template<class T>
void foo(T& lhs, T& rhs) {
    using std::swap; // enable 'std::swap' to be found
                    // if no other 'swap' is found through ADL
    // some code ...
    swap(lhs, rhs); // unqualified call, uses ADL and finds a fitting 'swap'
                    // or falls back on 'std::swap'
    // more code ...
}

Here is the proper way to provide a swap function for your class:

namespace Foo {

class Bar{}; // dummy

void swap(Bar& lhs, Bar& rhs) {
    // ...
}

}

If swap is now used as shown in 1), your function will be found. Also, you may make that function a friend if you absolutely need to, or provide a member swap that is called by the free function:

// version 1
class Bar{
public:
    friend void swap(Bar& lhs, Bar& rhs) {
    // ....
    }
};

// version 2
class Bar{
public:
    void swap(Bar& other) {
    // ...
    }
};

void swap(Bar& lhs, Bar& rhs) {
    lhs.swap(rhs);
}

...

You mean an explicit specialization. Partial is still something else and also not possible for functions, only structs / classes. As such, since you can't specialize std::swap for template classes, you have to provide a free function in your namespace. Not a bad thing, if I may say so. Now, an explicit specialization is also possible, but generally you do not want to specialize a function template:

namespace std
{  // only allowed to extend namespace std with specializations

template<> // specialization
void swap<Bar>(Bar& lhs, Bar& rhs) noexcept {
    // ...
}

}

No, as 1) is distinct from 2) and 3). Also, having both 2) and 3) will lead to always having 2) picked, because it fits better.

Destroy and then construct new object using the same variable

I think the only way to make this really safe to use is to require the called constructor to be noexcept, for example by adding a static_assert:

static_assert(noexcept(T(22, Brown, true)), "The constructor must be noexcept for inplace reconstruction");
T x(31, Blue, false);
x.~T();
::new (&x) T(22, Brown, true);

Of course this will only work for C++11.

Swapping two variable value without using third variable

Using the xor swap algorithm

void xorSwap (int* x, int* y) {
    if (x != y) { //ensure that memory locations are different
       *x ^= *y;
       *y ^= *x;
       *x ^= *y;
    }
}

Why the test?

The test is to ensure that x and y have different memory locations (rather than different values). This is because (p xor p) = 0 and if both x and y share the same memory location, when one is set to 0, both are set to 0.
When both *x and *y are 0, all other xor operations on *x and *y will equal 0 (as they are the same), which means that the function will set both *x and *y set to 0.

If they have the same values but not the same memory location, everything works as expected

*x = 0011
*y = 0011
//Note, x and y do not share an address. x != y

*x = *x xor *y  //*x = 0011 xor 0011
//So *x is 0000

*y = *x xor *y  //*y = 0000 xor 0011
//So *y is 0011

*x = *x xor *y  //*x = 0000 xor 0011
//So *x is 0011

Should this be used?

In general cases, no. The compiler will optimize away the temporary variable and given that swapping is a common procedure it should output the optimum machine code for your platform.

Take for example this quick test program written in C.

#include <stdlib.h>
#include <math.h>

#define USE_XOR 

void xorSwap(int* x, int *y){
    if ( x != y ){
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

void tempSwap(int* x, int* y){
    int t;
    t = *y;
    *y = *x;
    *x = t;
}

int main(int argc, char* argv[]){
    int x = 4;
    int y = 5;
    int z = pow(2,28); 
    while ( z-- ){
#       ifdef USE_XOR
            xorSwap(&x,&y);
#       else
            tempSwap(&x, &y);
#       endif
    }
    return x + y;    
}

Compiled using:

gcc -Os main.c -o swap

The xor version takes

real    0m2.068s
user    0m2.048s
sys  0m0.000s

Where as the version with the temporary variable takes:

real    0m0.543s
user    0m0.540s
sys  0m0.000s

Does C++11 Change the Behavior of Explicitly Calling Std::Swap to Ensure Adl-Located Swap's Are Found, Like Boost::Swap