Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 500
Maximilian Mordig Avatar asked Aug 13 '14 12:08

Maximilian Mordig


People also ask

How does STD swap work?

The std::swap() function is a built-in function in the C++ STL (Standard Template Library). Where a is the first variable which stores some value and b also a variable that stores some value, both a and b values are to swap. The function does not return anything it only swaps the values of a and b variables.

Is swap a standard library?

swap() in C++ The function std::swap() is a built-in function in the C++ Standard Template Library (STL) which swaps the value of two variables.

Which header file contains swap in C++?

valarray swap() function in c++ The swap() function is defined in valarray header file. This function is used to swap the content of one valarray with another valarray.

How do you swap objects in C++?

Create a class Swap, declare three variables in it, i.e., a, b, and temp and create a constructor for inputs. Declare a friend function in it. Define the friend function outside the class scope by taking arguments as call by reference to pass the copy of Swap Object. Perform the swap operation with Swap variables.


2 Answers

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.

like image 135
Niall Avatar answered Oct 11 '22 01:10

Niall


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.

like image 20
Useless Avatar answered Oct 11 '22 00:10

Useless