How does the standard library implement std::swap?

问题:

How is the swap function implemented in the STL? Is it as simple as this:

template<typename T> void swap(T& t1, T& t2) {
    T tmp(t1);
    t1=t2;
    t2=tmp;
}

In other posts, they talk about specializing this function for your own class. Why would I need to do this? Why can't I use the std::swap function?

回答1:

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

回答2:

How is the swap function implemented in the STL?

Which implementation? It's a specification, not a single concrete library. If you mean how does my compiler's standard library do it, either tell us which compiler that is, or read the code yourself.

Is it as simple as this:

That's essentially the naive version pre-C++11.

This un-specialized implementation forces a copy: for T = std::vector<SomethingExpensive> in your example, the code translates as:

template<typename T> void swap(T& t1, T& t2) {
  T tmp(t1); // duplicate t1, making an expensive copy of each element
  t1=t2;     // discard the original contents of t1,
             // and replace them with an expensive duplicate of t2
  t2=tmp;    // discard the original contents of t2,
             // and replace them with an expensive duplicate of tmp
}            // implicitly destroy the expensive temporary copy of t1

so to exchange two vectors we essentially created three. There were three dynamic allocations and a lot of expensive objects copied, and any of those operations could throw, possibly leaving the arguments in an indeterminate state.

Since this was obviously awful, overloads were provided for expensive containers, and you were encouraged to write overloads for your own expensive types: eg. the std::vector specialization had access to the vector's internals, and could swap two vectors without all the copying:

template <typename T> void swap(vector<T> &v1, vector<T> &v2) { v1.swap(v2); }
template <typename T> void vector<T>::swap(vector<T>& other) {
  swap(this->size_, other.size_); // cheap integer swap of allocated count
  swap(this->used_, other.used_); // cheap integer swap of used count
  swap(this->data__, other.data_); // cheap pointer swap of data ptr
}

Note that this involves no copies at all of anything expensive, no dynamic (de)allocation, and is guaranteed not to throw.

Now, the reason for this specialization is that vector::swap has access to vector's internals, and can safely and efficiently move them around without copying.

Why would I need to do this [specializing ... for your own class] ?

Pre-C++11, for the same reason as std::vector - to make swapping efficient and exception-safe.

Since C++11, you really don't - if you either provide move construction and assignment, or the compiler can generate sane defaults for you.

The new generic swap:

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

can use move construction/assignment to get essentially the same behaviour as the custom vector implementation above, without needing to write a custom implementation at all.