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

Как мы уже писали конференцию 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 ни к чему хорошему не приведут. И в самом деле, две версии машинных кодов вовсе не похожи друг на друга.

; C_STRLEN pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx xorl %eax, %eax cmpb $0, (%ecx) je LBB1_3 xorl %eax, %eax .align 16, 0x90 LBB1_2: cmpb $0, 1(%ecx,%eax) leal 1(%eax), %eax jne LBB1_2 LBB1_3: popl %ebp ret

; RANGE_STRLEN pushl %ebp movl %esp, %ebp pushl %esi leal 8(%ebp), %ecx movl 12(%ebp), %esi xorl %eax, %eax testl %esi, %esi movl 8(%ebp), %edx jne LBB2_4 jmp LBB2_1 .align 16, 0x90 LBB2_8: incl %eax incl %edx movl %edx, (%ecx) LBB2_4: testl %edx, %edx jne LBB2_5 cmpb $0, (%esi) jne LBB2_8 jmp LBB2_6 .align 16, 0x90 LBB2_5: cmpl %edx, %esi jne LBB2_8 jmp LBB2_6 .align 16, 0x90 LBB2_3: leal 1(%edx,%eax), %esi incl %eax movl %esi, (%ecx) LBB2_1: movl %edx, %esi addl %eax, %esi je LBB2_6 cmpb $0, (%esi) jne LBB2_3 LBB2_6: popl %esi popl %ebp ret

Ну и ну! Сколько там ветвлений и проверок! Код получен при помощи 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

Продолжение:
Интервалы в С++, часть 2: Бесконечные интервалы
Интервалы в С++, часть 3: представляем инкременторы (Iterable)
Интервалы в С++, часть 4: к бесконечности и далее