В последнее время я плотно занимался интервалами, и мне стало понятно, что это нечто большее, чем просто пара итераторов. В нескольких постах я хочу объяснить понятие интервала, описать несколько интервалов, которые не получается просто или эффективно выразить при помощи STL: интервалы с ограничителями и бесконечные интервалы. В этом посте мы рассмотрим задачу представления интервалов с ограничителями через итераторы STL.
Интервалы с ограничителями
Чтобы разобраться в новых концепциях, нужно иметь несколько хороших примеров. Думая об интервале с ограничителями, представляйте себе строчку в С, заканчивающуюся нулевым символом. Но при этом нам не известно точное положение ограничителя. Ограничитель может встретиться нам на заранее неизвестной позиции, или, в общем случае, место ограничителя может занять некое утверждение, которое становится истинным. Ещё один пример – интервал istream. В этом случае ограничителем будет тот момент, когда экстрактор istream не срабатывает. При этом в стандарте ведь есть std::istream_iterator – следовательно, каким-то образом всё-таки можно впихнуть интервалы с ограничителями в STL. Сейчас я покажу, как именно.
Интервалы с ограничителями в STL
Чтобы показать сложность задачи, представляю вам интервал с ограничителем для С-строки с итераторами, полностью соответствующими стандартам STL.
#include <cassert>
#include <iostream>
#include <boost/iterator/iterator_facade.hpp>
struct c_string_range
{
private:
char const *str_;
public:
using const_iterator = struct iterator
: boost::iterator_facade<
iterator
, char const
, std::forward_iterator_tag
>
{
private:
friend class boost::iterator_core_access;
friend struct c_string_range;
char const * str_;
iterator(char const * str)
: str_(str)
{}
bool equal(iterator that) const
{
return str_
? (that.str_ == str_ ||
(!that.str_ && !*str_))
: (!that.str_ || !*that.str_);
}
void increment()
{
assert(str_ && *str_);
++str_;
}
char const& dereference() const
{
assert(str_ && *str_);
return *str_;
}
public:
iterator()
: str_(nullptr)
{}
};
c_string_range(char const * str)
: str_(str)
{
assert(str_);
}
iterator begin() const
{
return iterator{str_};
}
iterator end() const
{
return iterator{};
}
explicit operator bool() const
{
return !!*str_;
}
};
int main()
{
for(char c : c_string_range("hello world!"))
std::cout << c;
std::cout << 'n';
}
Код перебирает последовательность символов без предварительного поиска окончания. Это делается созданием конечного сигнального интератора-пустышки, который каждый раз при сверке с реальным итератором проверяет, показывает ли реальный итератор на нулевой символ. Вся логика находится в функции c_string_range::iterator::equal member function. Вряд ли кто-либо назовёт такое решение красивым.
В современном STL интервалы задаются двумя итераторами – начальным и конечным. Для итераторов вроде std::istream_iterator или c_string_range::iterator, где итератор может быть сигнальным, такой метод добавляет разветвления кода проверки итераторов, поскольку сначала вам нужно определить, не является ли один или оба итератора сигнальными. Выражение a == b вычисляется по следующей таблице:
| a == end? | b == end? | a == b? |
| true | true | true |
| true | false | *b == 0 |
| false | true | *a == 0 |
| false | false | &*a == &*b |
И эти проверки должны выполняться во время выполнения программы. Нельзя сказать заранее, окажется ли итератор реальным или пустышкой. И все эти проверки отнимают процессорное время. Так что впихивание интервалов в STL – дело не очень удобное.
Компилятор соглашается
И неудобство тут – не только лишь моё мнение. Я сгенерировал код для следующих двух функций:
int c_strlen(char const *sz)
{
int i = 0;
for(; *sz; ++sz)
++i;
return i;
}
int range_strlen(
c_string_range::iterator begin,
c_string_range::iterator end)
{
int i = 0;
for(; begin != end; ++begin)
++i;
return i;
}
Две этих функции делают ровно то же самое, и, в теории, они должны привести к генерации одинакового кода. Правда, интуиция подсказывает нам, что все эти сложные логические построения вокруг c_string_range::iterator::equal ни к чему хорошему не приведут. И в самом деле, две версии машинных кодов вовсе не похожи друг на друга.
|
|
Ну и ну! Сколько там ветвлений и проверок! Код получен при помощи clang 3.4 с -O3 -DNDEBUG. На практике для range_strlen компилятор сможет сгенерить код и получше. Если он сможет предположить, что «end» – это сигнальный итератор. Но это лишь предположение.
Кроме того, люди обычно не пишут класс c_string_range для работы со строчками с ограничителями. Они вызывают strlen, а затем делают алгоритм, проходя таким образом по строке дважды. Но возьмём тот же istream. С входным интервалом такой фокус не пройдёт, поскольку само нахождение конечного итератора поглощает весь интервал. Поэтому, не было другого выхода, кроме как сделать пустышку из std::istream_iterator.
Наконец, обратите внимание, что c_string_range::iterator – это прямой (forward) итератор, поскольку сигнальный итератор нельзя уменьшать. Итератор интервала настолько силён, насколько силён его сигнальный итератор – а он не особенно-то и силён.
И что теперь?
Теперь понятно, что эффективно использовать STL-алгоритмы на С-строках нельзя. Ну и что? Ну и то, что в общем случае все строковые алгоритмы нельзя использовать на С-строках. Посмотрите-ка на красивые строковые алгоритмы в Boost.String_algo. В документации написано насчёт поддержки типов строк:
«Определение: строка – интервал символов, к которым возможен последовательный доступ. Первое требование к строковому типу – к нему необходимо иметь доступ через Boost.Range. Эта библиотека позволяет получать доступ к элементам строки при помощи итераторов».
Вот и в Boost.String_algo не любят С-строки. Кстати, а что случится, если вы вызовете std::regex_search с С-строкой? Он сначала вызовет strlen! Даже если ваша строчка длиною в мегабайты, а нужная подстрока находится в начале – всё равно придётся перебрать всю строку, только чтобы узнать, где у неё конец. В чём смысла ровно ноль.
«Ну и не надо использовать С-строки», – скажете вы. Но проблема-то больше, чем С-строки. У всех интервалов с ограничителями есть та же проблема. Только в стандартной библиотеке существуют istream_iterator, istreambuf_iterator, regex_iterator и regex_token_iterator, и у всех есть сигнальные пустышки, и все они впихнуты в библиотеку тем же методом, что я демонстрировал ранее.
А не было ли у вас такого случая, что у вас появлялось желание вызвать некий общий алгоритм, но вы не могли этого сделать, потому что хотели выйти из середины цикла по какому-либо условию? Представьте, что вы можете построить интервал с ограничителем, у которого будет и такое условие, и итератор конца. И вы можете передать этот интервал в алгоритм, который остановится либо по выполнении условия, либо по достижении конца. Вуаля. Но этот тип итератора пришлось бы впихивать так же, как все остальные, да и алгоритмы, которым требуется нечто большее, нежели прямые итераторы, не получилось бы использовать, поскольку сигнальный итератор нельзя уменьшать…
Что делать
Я веду вот к чему: абстракция интервала с парой итераторов, знакомая всем нам, была сделана с целью несложного построения абстракций. Но, в случае интервалов с ограничителями, абстракции оказалось строить сложно. Кроме того, этим интервалам приходится моделировать менее сильные концепции, чем они могли бы в ином случае. Что же делать? Есть у меня решение, но мы до него пока не добрались – сначала я хочу порассуждать о бесконечных интервалах. Так что оставайтесь с нами.
Первым пяти добравшимся до конца статьи маленький подарок: 30% скидка на билет на конференцию по промокоду Ranges
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий