Swapping, reversing, and partitioning

The STL contains a surprisingly large number of permutative algorithms besides std::sort. Many of these algorithms can be seen as "building blocks" that implement just a small part of the overall sorting algorithm.

std::swap(a,b) is the most basic building block; it just takes its two arguments and "swaps" them--which is to say, it exchanges their values. This is implemented in terms of the given type's move constructor and move assignment operator. swap is actually a little special among the standard algorithms because it is such a primitive operation, and because there is almost always a faster way to swap two arbitrary objects than by performing the equivalent of temp = a; a = b; b = temp;. The usual idiom for standard library types (such as std::vector) is for the type itself to implement a swap member function (as in a.swap(b)), and then to add a function overload of swap in the same namespace as the type--that is, if we're implementing my::obj, we'd add the overload in namespace my--such that swap(a,b) for that particular type, will call a.swap(b) instead of doing the three move operations. Here's an example:

    namespace my {
      class obj {
        int v;
      public:
        obj(int value) : v(value) {}

        void swap(obj& other) {
          using std::swap;
          swap(this->v, other.v);
        }
      };

      void swap(obj& a, obj& b) {
        a.swap(b);
      }
    } // namespace my

    void test()
    {
      int i1 = 1, i2 = 2;
      std::vector<int> v1 = {1}, v2 = {2};
      my::obj m1 = 1, m2 = 2;
      using std::swap;
      swap(i1, i2); // calls std::swap<int>(int&, int&)
      swap(v1, v2); // calls std::swap(vector&, vector&)
      swap(m1, m2); // calls my::swap(obj&, obj&)
    }

Now that we have swap and bidirectional iterators, we can build std::reverse(a,b), a permutative algorithm that simply reverses the order of a range of elements by swapping the first item with the last item, the second item with the penultimate item, and so on. One common application of std::reverse is to reverse the order of larger chunks of a string--for example, to reverse the order of the words in a sentence:

    void reverse_words_in_place(std::string& s)
    {
      // First, reverse the whole string.
      std::reverse(s.begin(), s.end());

      // Next, un-reverse each individual word.
      for (auto it = s.begin(); true; ++it) {
        auto next = std::find(it, s.end(), ' ');
        // Reverse the order of letters in this word.
        std::reverse(it, next);
        if (next == s.end()) {
          break;
        }
        it = next;
      }
    }

    void test()
    {
      std::string s = "the quick brown fox jumps over the lazy dog";
      reverse_words_in_place(s);
      assert(s == "dog lazy the over jumps fox brown quick the");
    }

A small tweak to the implementation of std::reverse gives us another building block of sort, namely std::partition. Whereas std::reverse walks through the range from both ends swapping each pair of elements unconditionally, std::partition swaps them only if they are "out of order" with respect to a certain predicate function. In the following example, we're partitioning all even elements to the front of our range and all odd elements to the back. If we were using std::partition to build a Quicksort sorting routine, we'd be partitioning elements less than the pivot element to the front of the range and elements greater than the pivot element to the back:

    template<class BidirIt>
    void reverse(BidirIt first, BidirIt last)
    {
      while (first != last) {
        --last;
        if (first == last) break;
        using std::swap;
        swap(*first, *last);
        ++first;
      }
    }

    template<class BidirIt, class Unary>
    auto partition(BidirIt first, BidirIt last, Unary p)
    {
      while (first != last && p(*first)) {
        ++first;
      }

      while (first != last) {
        do {
          --last;
        } while (last != first && !p(*last));
        if (first == last) break;
        using std::swap;
        swap(*first, *last);
        do {
          ++first;
        } while (first != last && p(*first));
      }
      return first;
    }

    void test()  
    {
      std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
      auto it = std::partition(v.begin(), v.end(), [](int x) {
        return x % 2 == 0;
      });
      assert(it == v.begin() + 3);
      assert((v == std::vector{6, 2, 4, 1, 5, 9, 1, 3, 5}));
    }

You might notice something interesting about the preceding code: The code for reverse and the code for partition are almost identical! The only difference is that partition contains an awkward do-while loop where reverse has just a simple increment or decrement.

You might also have noticed that the first do-while loop in partition is equivalent to a standard algorithm we've already seen; namely, std::find_if_not. And the second do-while loop is sort of equivalent to std::find_if... except that it needs to run backwards, not forwards! Unfortunately for us, there is no such algorithm as std::rfind_if. But--as you might have suspected by now--the standard library isn't going to leave us in the lurch.

We need something that behaves just like an iterator for the purposes of std::find_if, but iterates "backwards." The standard library provides this exact thing in the form of the std::reverse_iterator adaptor. We won't show the code for it; revisit Chapter 2, Iterators and Ranges, if you need a refresher on how it might be implemented. Suffice it to say, a std::reverse_iterator<FwdIt> object wraps and behaves just like a FwdIt object, except that when you increment the wrapper, it decrements the wrapped object, and vice versa. So we can write partition in terms of reverse_iterator as follows:

    // Shorthands for "reversing" and "unreversing".
    template<class It>
    auto rev(It it) {
      return std::reverse_iterator(it);
    };

    template<class InnerIt>
    auto unrev(std::reverse_iterator<InnerIt> it) {
      return it.base();
    }

    template<class BidirIt, class Unary>
    auto partition(BidirIt first, BidirIt last, Unary p)
    {
      first = std::find_if_not(first, last, p);

      while (first != last) {
        last = unrev(std::find_if(rev(last), rev(first), p));
        if (first == last) break;
        using std::swap;
        swap(*first++, *--last);
        first = std::find_if_not(first, last, p);
      }
      return first;
    }

Of course, sometimes it's useful to partition a range without changing the relative order of the elements in either partition. For those times, there's std::stable_partition(a,b,p) (but see the section Merges and mergesort for a caveat about stable_partition: It may allocate memory using operator new).

There are a few non-permutative algorithms that also deal with partitions:

std::is_partitioned(a,b,p) returns true if the given range is already partitioned by the predicate p (so that all the elements satisfying p come at the front and all the ones not satisfying p come at the back).

std::partition_point(a,b,p) uses binary search to find the first element in an already partitioned range that doesn't satisfy p.

std::partition_copy(a,b,ot,of,p) copies each of the elements in the range [a,b) to one or the other of the output iterators: *ot++ = e for elements where p(e) is true, and *of++ = e for elements where p(e) is false.

Incidentally, if you only want one output sequence or the other, then you can use std::copy_if(a,b,ot,p) or std::remove_copy_if(a,b,of,p) respectively.