в конечном счете присваивает его итератору вывода. Помимо этого, он принимает элемент split_val и бинарную функцию. Снова взглянем на полную реализацию, чтобы полностью понять его:
template <typename InIt, typename OutIt, typename T, typename F>
InIt split(InIt it, InIt end_it, OutIt out_it, T split_val, F bin_func)
{
while (it != end_it) {
auto slice_end (find(it, end_it, split_val));
*out_it++ = bin_func(it, slice_end);
if (slice_end == end_it) { return end_it; }
it = next(slice_end);
}
return it;
}
Цикл требует выполнять перебор до конца входного диапазона данных. Во время каждой итерации вызов std::find используется для поиска следующего элемента входного диапазона, который равен split_val. В нашем случае этот элемент — дефис ('-'), поскольку мы хотим разбить входную строку на фрагменты, находящиеся между дефисами. Следующая позиция дефиса теперь сохраняется в slice_end. После перебора цикла итератор it перемещается на следующий после искомого элемент. Таким образом, цикл перескакивает от дефиса к дефису вместо того, чтобы проходить по отдельным элементам.
В данной комбинации итератор it указывает на начало последнего slice, а slice_end — на конец последней вырезки. Оба итератора отмечают начало и конец поддиапазона данных, который представляет собой ровно одну вырезку между двумя символами дефиса. Для строки "foo-bar-baz" это значит, что у нас будет три итерации цикла и всякий раз мы будем получать пару итераторов, которые окружают одно слово. Но нам нужны не итераторы, а подстроки. Бинарная функция bin_func помогает их получить. При вызове функции split мы передали ей следующую бинарную функцию:
[](auto it_a, auto it_b) {
return string(it_a, it_b);
}
Функция split пропускает каждую пару итераторов через функцию bin_func, прежде чем отправить их в конечный итератор. От функции bin_func мы получим строки "foo", "bar" и "baz".
Дополнительная информация
Интересной альтернативой реализации нашего алгоритма, разбивающего строки на части, является реализация итератора, который делает то же самое. Мы сейчас не будем реализовывать такой итератор, но кратко рассмотрим подобный сценарий.
Этот итератор должен перескакивать между разделителями при каждом инкременте. При разыменовании ему следует создавать объект строки на основе позиции, на которую он сейчас указывает, что можно сделать с помощью бинарной функции binfunc, уже применяемой нами ранее.
Если бы наш класс итератора назывался split_iterator и мы бы задействовали его вместо алгоритма split, то код пользователя выглядел бы так:
string s {"a-b-c-d-e-f-g"};
list<string> l;
auto binfunc ([](auto it_a, auto it_b) {
return string(it_a, it_b);
});
copy(split_iterator{begin(s), end(s), '-', binfunc},{}, back_inserter(l));
Недостатком описанного подхода служит тот факт, что реализовать итератор сложнее, чем одну функцию. Кроме того, существует множество узких моментов в коде итератора, которые могут привести к появлению ошибок, поэтому такое решение требует более серьезного тестирования. С другой стороны, очень легко объединить подобный итератор с другими алгоритмами библиотеки STL.
Создаем полезные алгоритмы на основе стандартных алгоритмов gather
Алгоритм gather — очень хороший пример компонуемости алгоритмов STL. Шон Пэрент (Sean Parent), будучи старшим научным сотрудником в компании Adobe Systems, популяризировал данный алгоритм, поскольку он полезен и краток. Способ его реализации идеально подчеркивает идею STL-компоновки алгоритмов.
Алгоритм gather работает для диапазонов данных произвольных типов. Он изменяет порядок элементов так, что конкретные элементы собираются вокруг заданной позиции, выбранной вызывающей стороной.
Как это делается
В данном примере мы реализуем алгоритм gather и его дополнительную вариацию. После этого посмотрим, как его можно использовать.
1. Сначала добавим все выражения include. Затем объявим об использовании пространства имен std:
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
using namespace std;
2. Алгоритм gather представляет собой хороший пример компоновки стандартных алгоритмов. Он принимает начальный и конечный итераторы, а также еще один итератор gather_pos, который указывает на какую-то позицию между ними. Последний параметр — функция-предикат. С ее помощью алгоритм поместит все элементы, соответствующие заданному условию, в позиции рядом с итератором gather_pos. Реализация перемещения элементов выполняется благодаря std::stable_partition. Алгоритм gather возвращает пару итераторов. Они возвращаются вызовом stable_partition и, таким образом, отмечают начало и конец полученного диапазона:
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. Еще одним вариантом реализации является gather_sort. Он работает так же, как и gather, но принимает не унарную функцию-предикат, а бинарную функцию сравнения. Это позволит собрать значения вокруг позиции gather_pos, они могут быть как самыми маленькими, так и самыми большими:
template <typename It, typename F>
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 снова попробуем собрать все символы в середине. Этот вызов сработает не так, как нам бы того хотелось, и далее
