More efficient algorithms with swap

Some algorithms need to swap

One of the benefits of regular types is, that they can easily be used with STL’s containers and algorithms. A group of STL algorithms does only move around the elements in it’s input ranges; they do neither remove nor add elements there; they only change the ordering of the elements – they only permute them (Jonathan Boccara calls them permutationers for exactly this reason. They include popular algorithms like

• std::sort,
• std::stable_sort,
• std::partial_sort,
• std::nth_element,
• std::partition,
• std::stable_partition,
• std::rotate,
• std::reverse,
• std::next_permutation or
• std::random_shuffle.

All of them need to move around elements in the input range. This “moving around” usually comes up in the form of swapping. Let’s have a look at a rather simple example: std::random_shuffle. This is a very simple (and somewhat flawed becasue of std::rand) implementation taken from cppreference.com:

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last) {
  typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
  typedef typename std::iterator_traits<RandomIt>::value_type value_type;
 
  for (diff_t i = last - first - 1; i > 0; --i) {
    value_type& a = first[i];
    value_type& b = first[std::rand() % (i + 1)];
    value_type tmp = a;
    a = b;
    b = tmp;
  }
}

This implementation of random_shuffle exchanges every element in the range with another randomly chosen other element in the range – it swaps them. This swapping is commonly used in permutating algorithms, so STL offers a function template for that: std::swap. A possible generic implementation could look like this:

template<typename T>
void swap(T& a, T& b  {
  T tmp = a;
  a = b;
  b = tmp;
}

Please note that this implementation need to make a copy of one of those values. This is unfortunate for objects which are expensive to copy such as large std::vectors. This is unfortunate especially since swap can be implemented for std::vector in particular quite efficiently.

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last) {
  typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
 
  for (diff_t i = last - first - 1; i > 0; --i) {
    std::swap(first[i], first[std::rand() % (i + 1)])
  }
}

Using std::swap not only simplifies this implementation massively. If also has performance benefits.

The image above show what needs to be happen in order top assign a std::vector to another (for more details have look at this article): each value of the source vector needs to be copied to the target vector. Note that in the show case the capacity of the target vector is already large enough to fit all elements; in the general case an allocation may be necessary. In the generic implementation of swap two assignments and one copy is happening. Depending on circumstances, these might require quite a lot allocations and copying of elements!

In contrast to that swapping two vectors is really cheap as we only need to swap the pointer to the beginning, the end and end of capacity to the vector. This is an obvious win over two assignments and a copy of entire (potentially large) vectors!

For this reason and because this is true for many other STL containers/types, there are overloads of std::swap for each of them. std::vector actually has a member function called swap for this reason.

As having a specific implementation of swap may be beneficial in many case, we really should provide an overload for our optional as well. The C++ Core Guidelines recommend to do so as well.

Swapping optionasls

Following the example of std::vector we will have a member function swap and a free function swap. The free function is beneficial to have in the general case; the member function is arguably easier to use – at least if you are using and IDE with autocompletion. For a discussion about this topic please have a look at Klaus Iglberger’s talk on Free Function. As people like to use member functions and it doesn’t hurt to much to provide them, we’ll just do it. And std::optional has a swap member function, too.

The swap member functions.

As a quick preliminary remark I would to emphasis that we should use the swap operation of optional’s value type. Form the discussion above this should be quite obvious that this makes quite some sense.

As we should start with writing test cases for our new swap function first, we need to provide a first dummy implementation of optional::swap.

template <typename T>
class optional {
 public:
 //...
  void swap(optional& other) {}
 //...
};

After thinking a bit about the problem at hand we will quickly see, that there are four cases to distinguish here:

1. both optionals store a value.
2. both optionals store no value.
3. optional a stores a value but optional b doesn’t.
4. optional a stores no value but optional b doesn’t.

Based on these distinction of cases, we can derive these test cases.

TEST_CASE(
    "If two optionals with values are swapped, their values are swapped.") {
  unsigned int anyValueX = 10;
  unsigned int anyValueY = 2;
  optional_unsigned_int x(anyValueX);
  optional_unsigned_int y(anyValueY);

  x.swap(y);

  REQUIRE(*x == anyValueY);
  REQUIRE(*y == anyValueX);
}

TEST_CASE("If two optionals with no values are swapped, they stay empty.") {
  optional_unsigned_int x;
  optional_unsigned_int y;

  x.swap(y);

  REQUIRE(not x.has_value());
  REQUIRE(not y.has_value());
}

TEST_CASE(
    "If an optional with a value and an optional without a value are swapped, "
    "the value is transferred.") {
  unsigned int anyValueX = 10;
  optional_unsigned_int x(anyValueX);
  optional_unsigned_int y;

  SECTION("this has value") {
    x.swap(y);
  }
  SECTION("other has value") {
    y.swap(x);
  }

  REQUIRE(not x.has_value());
  REQUIRE(y.has_value());
  REQUIRE(*y == anyValueX);
}

We now need to address these these cases in out implementation.

1. For case 1 we can just use std::swap on the values of the optionals.
2. For case 2 there is basically nothing to do: there are no values to care about and swapping to booleans with the same value doesn’t make that much sense.
3. In case 3 and 4 we can just copy the value of the optional with the value to the optional without a value and destroy the old value.

template <typename T>
class optional {
 public:
 //...
  void swap(optional& other) {
    if (this->has_value() and other.has_value()) {
      std::swap(*(*this), *other);
    } else if (this->has_value()) {
      other.constructValue(*(*this));
      other.mHasValue = true;
      this->destructValue();
      this->mHasValue = false;
    } else if (other.has_value()) {
      this->constructValue(*other);
      this->mHasValue = true;
      other.destructValue();
      other.mHasValue = false;
    }
  }
 //...
};

This implementation will make the tests pass but it is a bit cumbersome as we need to quite a log of manual work here in case 3 and 4. We should revisit constructValue and destructValue. If any of them is called it is always accompanied with an assignment to mHasValue: if constructValue is called mHasValue is set to true and if destructValue is called mHasValue is set to false. This makes a lot of sense since mHasValue denotes whether there is a constructed object stored in the optional. We might as well always set mHaveValue accordingly in both of these function calls and save us some code even in other places of our implementation.

template <typename T>
class optional {
 public:
 //...
  optional& operator=(const optional& other) {
    if (mHasValue && other.mHasValue) {
      *(*this) = *other;
    } else if (other.mHasValue) {
      constructValue(*other);
    } else if (mHasValue) {
      destructValue();
    }
    return *this;
  }
 //...
  void swap(optional& other) {
    if (this->has_value() and other.has_value()) {
      std::swap(*(*this), *other);
    } else if (this->has_value()) {
      other.constructValue(*(*this));
      this->destructValue();
    } else if (other.has_value()) {
      this->constructValue(*other);
      other.destructValue();
    }
  }
 //...
 private:
 //...
  void constructValue(const T& other) {
    new (&mBuffer.mStorage) T(other);
    mHasValue = true;
  }

  void destructValue() {
    reinterpret_cast<T*>(&mBuffer.mStorage)->~T();
    mHasValue = false;
  }
};

Free function swap

Implementing the free function swap is now actually quite easy, but we should still add a test for it.

TEST_CASE("Free Function swap called on options swaps the optionals") {
  unsigned int anyValueX = 10;
  optional_unsigned_int x(anyValueX);
  optional_unsigned_int y;

  swap(x, y);

  REQUIRE(not x.has_value());
  REQUIRE(y.has_value());
  REQUIRE(*y == anyValueX);
}

Given that, we can not add our implementation, which just forwards to the member function swap.

template< class T >
void swap(optional<T>& a, optional<T>& b ) {
  a.swap(b);
}

But where to put it? We could just put it in the global namespace, but in general it is considered bad practice (yes, we do it all the time here, but we did it only for the sake of simplicity!). As it is intended as an overload of std::swap we could add it to the std namespace, right? No we can’t! Because in general it is undefined behavior to add declarations to the std namespace. There are exceptions, but std::swap isn’t one of them.

We could add swap as a friend function though. We did it with the comparison operators before.

template <typename T>
class optional {
 public:
 //...
  friend void swap(optional& a, optional& b ) {
    a.swap(b);
  }
 //...
};

Doing this has some nice properties:

1. swap will now always be in the same namespace. The C++ Core Guidelines recommend that as well – we’ll get back to that.
2. We save quite some boilerplate code as we can spare the template line we otherwise would have to add.
3. swap is now consistently implemented like the comparison operators. If you think about, swap can be considered to be a binary operator like + or - but with prefix instead of infix notation.

On the usage of swap

Consider the following code:

optional<int> a, b;
std::swap(a, b);

Will this code call our swap implementation? No, it won’t! It will call the default implementation of swap. This implies, that the example implementation of `std::random_shuffle’ we used above won’t use it either. The reason for that is that I ruthlessly simplified the implementation above. An actual implementation would look more like this:

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last) {
  typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
 
  for (diff_t i = last - first - 1; i > 0; --i) {
    using std::swap;
    swap(first[i], first[std::rand() % (i + 1)])
  }
}

With such an implementation our swap function is actually called. With using std::swap; we pull in std::swap in the global namespace (for the current scope). Now all overloads of std::swap and our implementation of swap are considered for overload resolution. Knowing that, we should now revisit our swap implementation as we did not considered such a case there.

template <typename T>
class optional {
 public:
 //...
  void swap(optional& other) {
    if (this->has_value() and other.has_value()) {
      using std::swap;
      swap(*(*this), *other);
    } else if (this->has_value()) {
      other.constructValue(*(*this));
      this->destructValue();
    } else if (other.has_value()) {
      this->constructValue(*other);
      other.destructValue();
    }
  }
 //...
};

This code will actually work for all type which have an implementation of swap within their namespace. The reason for that is called argument-dependent lookup. To put it quick and simple: ADL means that, if you call a function without any scope specificaion in front of it (any kind of ::) during overload resolution the compiler will also look in the namespaces of its operands. ADL has originally been added to C++ because of operator overloading, but works for every kind of function. This is the reason why the c++ core guidelines suggest to put operator overloads into the same namespace as their operands.

ADL makes also the “Making News Friends” idiom work which we are using for the comparison operators and swap. These functions are not part of the global namespace but part of the class namespace of optional. We can only call them because of ADL.

Conclusion

In this post we learned

• about std::swap and it’s merits especially in STL algorithms. If you want to see how commonly swap is used in the STL, just have a look in an implementation and count the occourances!
• how to implement swap for our optional,
• how to use swap in generic code and
• what ADL means and how to use it.

In a sense std::swap is a child of older C++ versions. With the introduction of move semantics in C++11 the need for providing a custom implementation of swap has become less urgent, as std::swap can be implemented in terms of move semenatics quite efficiently in general. However we will keep sticking with C++98 a bit further as there are still a few helpful thing we can implement in C++98 before we actually need to move on to C++11.