C++17 STL Стандартная библиотека шаблонов

3. Еще одним вариантом реализации является gather_sort. Он работает так же, как и gather, но принимает не унарную функцию-предикат, а бинарную функцию сравнения. Это позволит собрать значения вокруг позиции gather_pos, они могут быть как самыми маленькими, так и самыми большими:

template

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

{

  auto inv_comp_func ([&](const auto &...ps) {

    return !comp_func(ps...);

  });

  stable_sort(first, gather_pos, inv_comp_func);

  stable_sort(gather_pos, last, comp_func);

}

4. Воспользуемся этими алгоритмами. Начнем с предиката, который указывает, является ли заданный символьный аргумент символом 'a'. Мы создадим строку, состоящую из комбинации символов 'a' и '_':

int main()

{

  auto is_a ([](char c) { return c == 'a'; });

  string a {"a_a_a_a_a_a_a_a_a_a_a"};

5. Создадим итератор, который указывает на середину нашей новой строки. Вызовем для нее алгоритм gather и посмотрим, что произойдет. В результате вызова символы 'a' будут собраны в середине строки:

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

  gather(begin(a), end(a), middle, is_a);

  cout << a << '\n';

6. Снова вызовем данный алгоритм, но в этот раз итератор gather_pos будет указывать не на середину строки, а на ее начало:

  gather(begin(a), end(a), begin(a), is_a);

  cout << a << '\n';

7. В третьем вызове соберем элементы вокруг конечного итератора:

  gather(begin(a), end(a), end(a), is_a);

  cout << a << '\n';

8. При последнем вызове алгоритма gather снова попробуем собрать все символы в середине. Этот вызов сработает не так, как нам бы того хотелось, и далее мы увидим почему:

  // Это работает не так, как вы того ожидаете

  gather(begin(a), end(a), middle, is_a);

  cout << a << '\n';

9. Создадим еще одну строку, содержащую символы подчеркивания и числа. Для этой входной последовательности вызовем функцию gather_sort. Итератор gather_pos находится в середине строки, воспользуемся бинарной функцией сравнения std::less:

  string b {"_9_2_4_7_3_8_1_6_5_0_"};

  gather_sort(begin(b), end(b), begin(b) + b.size() / 2,

              less{});

  cout << b << '\n';

}

10. Компиляция и запуск программы даст следующий интересный результат. Первые три строки выглядят так, как мы и ожидали, но четвертая строка — так, будто алгоритм gather не отработал.

В последней строке можно увидеть результат работы функции gather_short. Числа выглядят отсортированными в обоих направлениях.

$ ./gather

_____aaaaaaaaaaa_____

aaaaaaaaaaa__________

__________aaaaaaaaaaa

__________aaaaaaaaaaa

_____9743201568______

Как это работает

Изначально алгоритм gather сложно понять, поскольку он очень короткий, но при этом выполняет задачу, которая кажется сложной. Разберем ее по шагам (рис. 6.11).

1. В самом начале у нас есть диапазон элементов, для которого мы предоставляем функцию-предикат. На рис. 6.11 все элементы, для которых функция-предикат возвращает значение true, окрашены в серый цвет. Итераторы a и c отмечают весь диапазон, а итератор b указывает на направляющий элемент. Таковым является элемент, вокруг которого мы хотим собрать все серые элементы.

2. Алгоритм gather вызывает функцию std::stable_partition для диапазона данных [a, b] и в то же время использует инвертированную версию предиката. Он инвертирует предикат, поскольку функция std::stable_partition перемещает все элементы, для которых предикат возвращает значение true, в переднюю часть диапазона данных. Нужно, чтобы произошло противоположное.

3. Выполняется еще один вызов std::stable_partition, однако на сей раз для диапазона данных [b, c], без инвертирования предиката. Серые элементы перемещаются в начало входного диапазона данных; это значит, что они перемещаются к направляющему элементу, на который указывает итератор b.

4. Теперь элементы собраны вокруг итератора b и алгоритм возвращает итераторы, указывающие на начало и конец диапазона данных, содержащего серые элементы.