Как мы уже писали конференцию C++ Siberia в Новосибирске будет открывать Эрик Ниблер. Чтобы поближе познакомить Хабр с этим замечательным человеком, мы решили перевести цикл его статей об интервалах. Сейчас Эрик работает над реализацией библиотеки Ranges по гранту, полученному от комитета стандартизации.
В последнее время я плотно занимался интервалами, и мне стало понятно, что это нечто большее, чем просто пара итераторов. В нескольких постах я хочу объяснить понятие интервала, описать несколько интервалов, которые не получается просто или эффективно выразить при помощи 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
ссылка на оригинал статьи http://habrahabr.ru/post/264201/
Добавить комментарий