How Does the Standard Library Implement Std::Swap

How does the standard library implement std::swap?

How is std::swap implemented?

Yes, the implementation presented in the question is the classic C++03 one.

A more modern (C++11) implementation of std::swap looks like this:

template<typename T> void swap(T& t1, T& t2) {
    T temp = std::move(t1); // or T temp(std::move(t1));
    t1 = std::move(t2);
    t2 = std::move(temp);
}

This is an improvement over the classic C++03 implementation in terms of resource management because it prevents unneeded copies, etc. It, the C++11 std::swap, requires the type T to be MoveConstructible and MoveAssignable, thus allowing for the implementation and the improvements.

Why would I need to provide a custom implementation?

A custom implementation of swap, for a specific type, is usually advised when your implementation is more efficient or specific than the standard version.

A classic (pre-C++11) example of this is when your class manages a large amount of resources that would be expensive to copy and then delete. Instead, your custom implementation could simply exchange the handles or pointers required to effect the swap.

With the advent of std::move and movable types (and implemented your type as such), circa C++11 and onwards, a lot of the original rationale here is starting to fall away; but nevertheless, if a custom swap would be better than the standard one, implement it.

Generic code will generally be able to use your custom swap if it uses the ADL mechanism appropriately.

How is std::swap() implemented?

That is entirely up to the compiler for the target processor. How it compiles on one machine may not be the same as the other. Some, if not most, CPUs have a XCHG instruction to swap using registers without needing a third temporary register; however, it’s up to the compiler to decide to optimize accordingly. I imagine even if not used, the compiler would still try to use registers for simple numerical or Boolean swaps when built in release mode (optimizations enabled). Even if you could coerce the compiler to use registers on one platform, there’s no reason it will obey the same on all of them. Unless you want to detect architectures and write your own assembly (a neat, but bad idea for best compatibility and support, trust me lol) I’d suggest not to micro-optimize this and just let the compiler do its thing

utility not necessarily included when swap() is performed - How can this become a problem?

Let's try to understand the note you quoted from cppreference.

It is unspecified whether <utility> is actually included when the standard library functions perform the swap, so the user-provided swap() should not expect it to be included.

E.g., std::sort may perform the swap. To use std::sort, you need to include <algorithm>. The statement basically says, despite this, <algorithm> may not have <utility> included. It follows that below code may be problematic.

#include <algorithm>

int main() {
  int arr[] = { 4, 1, 7 };
  std::sort(arr, arr + 3);
  std::swap(arr[0], arr[1]); // may error out here
}

This is counter-intuitive, for std::sort performs std::swap internally itself. To stay on the safe side, always explicitly include <utility> if you need std::swap. Don't assume that some other standard library headers that use std::swap themselves have <utility> included for you. Following code should always work, while #include <utility> seems unnecessary at first sight.

#include <algorithm>
#include <utility>

int main() {
  int arr[] = { 4, 1, 7 };
  std::sort(arr, arr + 3);
  std::swap(arr[0], arr[1]);
}

what does `using std::swap` inside the body of a class method implementation mean?

This mechanism is normally used in templated code, i.e. template <typename Value> class Foo.

Now the question is which swap to use. std::swap<Value> will work, but it might not be ideal. There's a good chance that there's a better overload of swap for type Value, but in which namespace would that be? It's almost certainly not in std:: (since that's illegal), but quite likely in the namespace of Value. Likely, but far from certain.

In that case, swap(myValue, anotherValue) will get you the "best" swap possible. Argument Dependent Lookup will find any swap in the namespace where Value came from. Otherwise the using directive kicks in, and std::swap<Value> will be instantiated and used.

In your code, mSize is likely an integral type, and mArray a pointer. Neither has an associated namespace, and std::swap is with 99.9% certainty optimal for them anyway. Therefore, the using std::swap; declaration seems useless here.

Why are there so many specializations of std::swap?

So what it is gained from specializing std::pair?

Performance. The generic swap is usually good enough (since C++11), but rarely optimal (for std::pair, and for most other data structures).

I'm also left wondering if I should be writing my own specializations for custom classes, or simply relying on the template version.

I suggest relying on the template by default, but if profiling shows it to be a bottleneck, know that there is probably room for improvement. Premature optimization and all that...

how to provide a swap function for my class?

1. 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 ...
}

2. 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);
}

...

3. 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 {
    // ...
}

}

4. 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.

Is there a built-in way to swap two variables in C?

There is no equivalent in C - in fact there can't be, as C doesn't have template functions. You will have to write separate functions for all the types you want to swap.

---

Related Topics