Pull to refresh

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

Reading time6 min
Views25K
Original author: Eric Niebler
Как мы уже писали конференцию 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: к бесконечности и далее

Tags:
Hubs:
Total votes 16: ↑15 and ↓1+14
Comments8

Articles

Information

Website
cpp-russia.ru
Registered
Founded
Employees
2–10 employees
Location
Россия