In this section, we will implement the gather algorithm and a bonus variation of it. Afterward, we see how it can be put to use:

1. First, we add all the STL include statements. Then, we declare that we use the std namespace:

      #include <iostream>
      #include <algorithm>
      #include <string>
      #include <functional>      

      using namespace std;

2. The gather algorithm is a nice example of standard algorithm composition. gather accepts a begin/end iterator pair, and another iterator gather_pos, which points somewhere in between. The last parameter is a predicate function. Using this predicate function, the algorithm will push all that items that do satisfy the predicate near the gather_pos iterator. The implementation of the item movement is done by std::stable_partition. The return value of the gather algorithm is a pair of iterators. These iterators are returned from the stable_partition calls, and this way, they mark the beginning and the end of the now gathered range:

      template <typename It, typename F>
      pair<It, It> gather(It first, It last, It gather_pos, F predicate)
      {
          return {stable_partition(first, gather_pos, not_fn(predicate)),
                  stable_partition(gather_pos, last, predicate)};
      }

3. Another variant of gather is gather_sort. It basically works the same way as gather, but it does not accept a unary predicate function; it accepts a binary comparison function instead. This way, it is possible to gather the values near gather_pos, which appear smallest or largest:

      template <typename It>

      void gather_sort(It first, It last, It gather_pos)

      {

        using T = typename std::iterator_traits<It>::value_type;

        stable_sort(first, gather_pos, greater<T>{});

        stable_sort(gather_pos, last, less<T>{});

      }

4. Let's put those algorithms to use. We start with a predicate, which tells if a given character argument is the 'a' character. We construct a string, which consists of wildly interleaved 'a' and '_' characters:

      int main()
      {
          auto is_a ([](char c) { return c == 'a'; });
          string a {"a_a_a_a_a_a_a_a_a_a_a"};

5. We construct an iterator, which points to the middle of our new string. Let's call gather on it and see what happens. The 'a' characters should be gathered around the middle afterward:

          auto middle (begin(a) + a.size() / 2);

          gather(begin(a), end(a), middle, is_a);
          cout << a << 'n';

6. Let's call gather again, but this time, the gather_pos iterator is not in the middle but the beginning:

          gather(begin(a), end(a), begin(a), is_a);
          cout << a << 'n';

7. In a third call, we gather items around the end iterator:

          gather(begin(a), end(a), end(a), is_a);
          cout << a << 'n';

8. With a last call of gather, we try to gather all the 'a' characters around the middle again. This will not work as expected, and we will later see why:

          // This will NOT work as naively expected
          gather(begin(a), end(a), middle, is_a);
          cout << a << 'n';

9. We construct another string with underscore characters and some number values. On that input sequence, we apply gather_sort. The gather_pos iterator is the middle of the string, and the binary comparison function is std::less<char>:

          string b {"_9_2_4_7_3_8_1_6_5_0_"};
          gather_sort(begin(b), end(b), begin(b) + b.size() / 2, 
                      less<char>{});
          cout << b << 'n';
      }

10. Compiling and running the program yields the following interesting output. The first three lines look like expected, but the fourth line looks like gather did nothing to the string.
    In the last line, we can see the result of the gather_short function. The numbers appear sorted towards either direction:

      $ ./gather 
      _____aaaaaaaaaaa_____
      aaaaaaaaaaa__________
      __________aaaaaaaaaaa
      __________aaaaaaaaaaa
      _____9743201568______