ном случае у нас получится новый язык общего назначения.
В этом примере мы реализуем алгоритм, который назовем
split
. Он может разбить любой диапазон данных, используя в качестве разделителя каждое включение конкретного значения, и скопировать полученный результат в выходной диапазон данных.
Как это делается
В данном примере мы реализуем собственный алгоритм
split
и проверим его работу, разбив на фрагменты строку-пример.
1. Сначала включим некоторые части библиотеки STL и объявим об использовании пространства имен
std
:
#include
#include
#include
#include
#include
using namespace std;
2. Алгоритм, показанный в этом разделе, предназначен для разбиения диапазонов данных. Он принимает начальный и конечный итераторы, а также итератор вывода, что поначалу делает его похожим на алгоритмы
std::copy
и std::transform
. Другими его параметрами являются split_val
и bin_func
. Параметр split_val
— значение, которое мы ищем во входном диапазоне данных; оно представляет собой точку разбиения, по которой мы отделяем входной диапазон данных. Параметр bin_func
— функция, преобразующая пару итераторов, которые отмечают начало и конец этого поддиапазона. Мы проитерируем по входному диапазону данных с помощью std::find
, так что будем перескакивать между включениями значений split_val
. При разбиении отдельной строки на отдельные слова мы станем перескакивать от пробела к пробелу. При нахождении искомого значения останавливаемся, чтобы сформировать фрагмент и передать его в выходной диапазон данных:
template
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;
}
3. Воспользуемся новым алгоритмом. Создадим строку, которую затем разобьем на части. Элементом, отмечающим конец последнего фрагмента и начало следующего, будет дефис
'-'
:
int main()
{
const string s {"a-b-c-d-e-f-g"};
4. Когда алгоритм вызывает функцию
bin_func
для пары итераторов, мы хотим создать на его основе новую строку:
auto binfunc ([](auto it_a, auto it_b) {
return string(it_a, it_b);
});
5. Выходной диапазон данных представляет собой список строк. Мы вызовем алгоритм
split
, который спроектирован так, что похож на другие алгоритмы STL:
list l;
split(begin(s), end(s), back_inserter(l), '-', binfunc);
6. Чтобы увидеть полученное, выведем на экран новый список разбитых строк:
copy(begin(l), end(l), ostream_iterator{cout, "\n"});
}
7. Компиляция и запуск программы дадут следующий результат. Он не содержит дефисов и показывает, что включает отдельные слова (которые в нашем примере являются отдельными символами):
$ ./split
a
b
c
d
e
f
g
Как это работает
Алгоритм
split
работает так же, как и std::transform
, поскольку принимает начальный и конечный итераторы входного диапазона данных и итератор вывода. Он выполняет какие-то действия с входным диапазоном и в конечном счете присваивает его итератору вывода. Помимо этого, он принимает элемент split_val
и бинарную функцию. Снова взглянем на полную реализацию, чтобы полностью понять его:
template
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 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.