Интервалы в С++, часть 1: Интервалы с ограничителями

Как мы уже писали конференцию C++ Siberia в Новосибирске будет открывать Эрик Ниблер. Чтобы поближе познакомить Хабр с этим замечательным человеком, мы решили перевести цикл его статей об интервалах. Сейчас Эрик работает над реализацией библиотеки Ranges по гранту, полученному от комитета стандартизации.

В последнее время я плотно занимался интервалами, и мне стало понятно, что это нечто большее, чем просто пара итераторов. В нескольких постах я хочу объяснить понятие интервала, описать несколько интервалов, которые не получается просто или эффективно выразить при помощи STL: интервалы с ограничителями и бесконечные интервалы. В этом посте мы рассмотрим задачу представления интервалов с ограничителями через итераторы STL.

Интервалы с ограничителями

Чтобы разобраться в новых концепциях, нужно иметь несколько хороших примеров. Думая об интервале с ограничителями, представляйте себе строчку в С, заканчивающуюся нулевым символом. Но при этом нам не известно точное положение ограничителя. Ограничитель может встретиться нам на заранее неизвестной позиции, или, в общем случае, место ограничителя может занять некое утверждение, которое становится истинным. Ещё один пример – интервал istream. В этом случае ограничителем будет тот момент, когда экстрактор istream не срабатывает. При этом в стандарте ведь есть std::istream_iterator – следовательно, каким-то образом всё-таки можно впихнуть интервалы с ограничителями в STL. Сейчас я покажу, как именно.

Интервалы с ограничителями в STL

Чтобы показать сложность задачи, представляю вам интервал с ограничителем для С-строки с итераторами, полностью соответствующими стандартам STL.

Код перебирает последовательность символов без предварительного поиска окончания. Это делается созданием конечного сигнального интератора-пустышки, который каждый раз при сверке с реальным итератором проверяет, показывает ли реальный итератор на нулевой символ. Вся логика находится в функции c_string_range::iterator::equal member function. Вряд ли кто-либо назовёт такое решение красивым.

Компилятор соглашается

И неудобство тут – не только лишь моё мнение. Я сгенерировал код для следующих двух функций:

Две этих функции делают ровно то же самое, и, в теории, они должны привести к генерации одинакового кода. Правда, интуиция подсказывает нам, что все эти сложные логические построения вокруг 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.String_algo не любят С-строки. Кстати, а что случится, если вы вызовете std::regex_search с С-строкой? Он сначала вызовет strlen! Даже если ваша строчка длиною в мегабайты, а нужная подстрока находится в начале – всё равно придётся перебрать всю строку, только чтобы узнать, где у неё конец. В чём смысла ровно ноль.

«Ну и не надо использовать С-строки», – скажете вы. Но проблема-то больше, чем С-строки. У всех интервалов с ограничителями есть та же проблема. Только в стандартной библиотеке существуют istream_iterator, istreambuf_iterator, regex_iterator и regex_token_iterator, и у всех есть сигнальные пустышки, и все они впихнуты в библиотеку тем же методом, что я демонстрировал ранее.

А не было ли у вас такого случая, что у вас появлялось желание вызвать некий общий алгоритм, но вы не могли этого сделать, потому что хотели выйти из середины цикла по какому-либо условию? Представьте, что вы можете построить интервал с ограничителем, у которого будет и такое условие, и итератор конца. И вы можете передать этот интервал в алгоритм, который остановится либо по выполнении условия, либо по достижении конца. Вуаля. Но этот тип итератора пришлось бы впихивать так же, как все остальные, да и алгоритмы, которым требуется нечто большее, нежели прямые итераторы, не получилось бы использовать, поскольку сигнальный итератор нельзя уменьшать…

Что делать

Я веду вот к чему: абстракция интервала с парой итераторов, знакомая всем нам, была сделана с целью несложного построения абстракций. Но, в случае интервалов с ограничителями, абстракции оказалось строить сложно. Кроме того, этим интервалам приходится моделировать менее сильные концепции, чем они могли бы в ином случае. Что же делать? Есть у меня решение, но мы до него пока не добрались – сначала я хочу порассуждать о бесконечных интервалах. Так что оставайтесь с нами.

Первым пяти добравшимся до конца статьи маленький подарок: 30% скидка на билет на конференцию по промокоду Ranges