Внутренность boolinq для взрослых / Хабр

Статья для тех, кому интересна реализация библиотеки boolinq из предыдущего моего поста. В этой статье я копну в исходники и покажу несколько интересных приёмов, которые позволили сделать библиотеку «ленивой» и расширяемой.

Что не так с итераторами?

Прежде чем мы посмотрим в код библиотеки, хотелось бы обратить ваше внимание на STL. Это стандартная библиотека шаблонов, содержит контейнеры, алгоритмы и т.д. Одним из самых интересных элементов библиотеки является сущность — итератор. Итераторы были придуманы для того чтобы быть прослойкой между контейнерами и алгоритмами. Чтобы любой алгоритм можно было применить к любому контейнеру (ну почти любые).

На первый взгляд — всё хорошо. Алгоритмы и контейнеры связаны через промежуточную сущность — итератор. Но это только на первый взгляд, если присмотреться к коду:

int sum = 0;
for (std::vector<int>::iterator it = candles.begin(); it != candles.end(); it++)
    sum += it->ClosePrice;

Есть один минус у STL-итераторов не заметный на первый взгляд, итераторы Java этого минуса лишены.

int sum = 0;
Iterator it = al.iterator(); 
while (it.hasNext()) {    
    it = it.next();
    sum += it.ClosePrice;
}

Да, это .begin() и .end() — это две части одной сущности. Если бы эти две части взять и объединить в одну сущность… Сказано — сделано (идея заимствована у Александреску из презентации «Iterators Must Go»):

template<typename TIter> 
class IterRange
{
public:
    typedef typename std::iterator_traits<TIter>::value_type value_type;
    
    IterRange(TIter b, TIter e)
        : b(b), e(e)
    {
    }

    bool empty()
    {
        return (b == e);
    }

    value_type popFront()
    {
        assert(!empty());
        return *(b++);
    }

    value_type popBack()
    {
        assert(!empty());
        return *(--e);
    }

    value_type front()
    {
        assert(!empty());
        return *b;
    }

    value_type back()
    {
        assert(!empty());
        TIter tmp = e;
        return *(--tmp);
    }

private:
    TIter b;
    TIter e;
};

Таким образом мы имеем одну сущность, можем спросить её есть ли ещё элементы в последовательности, запросить элемент и запросить перейти к следующему элементу. На самом деле также не помешают методы back() и popBack().

Ну а дальше не трудно догадаться как выглядят все классы библиотеки — это обертки над таким Range-ем. Например WhereRange выглядит так:

template<typename R, typename F> 
class WhereRange
{
public:
    typedef typename R::value_type value_type;
    
    WhereRange(R r, F f)
        : r(r), f(f)
        , frontReady(false)
        , backReady(false)
    {
    }

    bool empty() 
    { 
        if (!frontReady)
            seekFront();
        return r.empty();
    }

    value_type popFront() 
    { 
        if (!frontReady)
            seekFront();

        auto tmp = *this;
        r.popFront();
        frontReady = false;
        return tmp.front();
    }

    value_type popBack() 
    {
        // аналогично
    }

    value_type front()
    { 
        if (!frontReady)
            seekFront();
        return r.front();
    }

    value_type back() 
    { 
        // аналогично
    }

private:
    void seekFront()
    {
        while(!r.empty() && !f(r.front()))
            r.popFront();
        frontReady = true;
    }

    void seekBack()
    {
        // аналогично
    }

private:
    R r;
    F f;
    bool frontReady;
    bool backReady;
};

В двух словах: класс принимает в конструктор другой Range, из которого ему предстоит брать элементы, и предикат, определяющий принадлежность каждого из элементов к результирующей выборке. Имеются 2 переменных, определяющих найдено ли значение «с начала» и «с конца» Range-а. Функции seekFront() и seekBack() непосредственно занимаются поиском следующего front-а и следующего back-а.

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

Хочу точечную нотацию

С одной стороны хотелось сделать использование методов также как они используются в .NET LINQ, но ведь в C++ нет Extension Methods как в C#:

int max = arr.Where(...).OrderBy(...).Select(...).Max();

С другой стороны хотелось сделать библиотеку расширяемой… и тут пришла такая мысль)) Сверху всех Range-ей будет обернут класс Linq, при вызове преобразующих последовательность методов — оборачиваться будет вложенный в Linq класс, а класс Linq так и будет оставаться сверху всех.

Каждому классу Range-а сделал по оборачивающему классу Mixin-у следующего вида:

template<template<typename> class TLinq, typename R>
class WhereRange_mixin
{
public:
    template<typename F>
    TLinq<WhereRange<R,F> > where(F f) const
    {
        return boolinq::where(((TLinq<R>*)this)->r,f);
    }
};

Потом, отнаследовал класс Linq от всех необходимых Mixin-ов:

template<typename R>
class Linq
    : public SkipRange_mixin<Linq,R>
    , public TakeRange_mixin<Linq,R>
    , public WhereRange_mixin<Linq,R>
    , public SelectRange_mixin<Linq,R>
    , public ReverseRange_mixin<Linq,R>
    , public OrderByRange_mixin<Linq,R>
    // ... много классов ...
{
public:
    typedef typename R::value_type value_type;

    Linq(const R & r)
        : r(r)
    {
    }

    bool empty()          { return r.empty();    }
    value_type popFront() { return r.popFront(); }
    value_type popBack()  { return r.popBack();  }
    value_type front()    { return r.front();    }
    value_type back()     { return r.back();     }

public:
    R r;
};

Реверсирование порядка элементов

Хотел отдельно остановиться на этой функции. Она примечательна тем, что уж очень мне хотелось прибить двойной реверс последовательности. Причём прибить не ошибкой компиляции, а по-хорошему. Код класса довольно прост:

template<typename R>
class ReverseRange
{
public:
    typedef typename R::value_type value_type; 
    
    ReverseRange(R r)
        : r(r) 
    {
    }

    bool empty()          { return r.empty();    }
    value_type popFront() { return r.popBack();  }
    value_type popBack()  { return r.popFront(); }
    value_type front()    { return r.back();     }
    value_type back()     { return r.front();    }

    template<typename R2>
    friend R2 reverse(ReverseRange<R2> r); // smart needed

private:
    R r;
};

Всё в этом коде именно так, как вы ожидали: методы работающие с front и back — изменены на противоположные, но среди них затерялась дружественная функция. А Дружественная она затем, чтобы подлезть к приватному полю — оборачиваемому Range-у, вот собственно код этой функции:

template<typename R>
ReverseRange<R> reverse(R r)
{
    return r;
}

// Unwrap for double-reverse case
template<typename R>
R reverse(ReverseRange<R> r)
{
    return r.r; // smart
}

Да! Функция не одна — их целых две. Первая работает как должна — оборачивает Range нашим ReaverseRange-ем (тут происходит неявный вызов конструктора). Вторая же, наоборот разворачивает ReverseRange. Важно что это происходит на уровне компиляции, а не на этапе выполнения. Но это ещё не самое сложное — ад начался когда я попытался изобразить это в Mixin-е:

template<template<typename> class TLinq, typename R>
class ReverseRange_mixin
{
public:
    TLinq<ReverseRange<R> > reverse() const
    {
        return boolinq::reverse(((TLinq<R>*)this)->r);
    }
};

// Unwrap for double-reverse case
template<template<typename> class TLinq, typename T>
class ReverseRange_mixin<TLinq,ReverseRange<T> >
{
public:
    TLinq<T> reverse() const
    {
        return boolinq::reverse(((TLinq<ReverseRange<T> >*)this)->r);
    }
};

Опять же таки — первый Mixin не делает ничего необычного, а вот второй на стадии компиляции выявляет тип Linq<ReverseRange<XxxRange<...>>> и разворачивает его в Linq<XxxRange<...>>. Мозг сломал пока добился компилируемого кода.

Как пользователю расширять библиотеку?

Идея была в следующем, пусть создает свой волшебный Range-класс, затем создаёт Mixin-класс по образу и подобию других Mixin-ов. А после этого создаёт свой класс CustomLinq и использует его при создании н��чальной последовательности (отнаследоваться от Linq не получится, ибо его Mixin-ы будут оборачивать все не в CustomLinq, а в Linq):

boolinq::from<CustomLinq>(arr)

вместо:

boolinq::from(arr)

Ну и пользователь может обойтись без всего этого и вовсе не использовать точечную нотацию. Ведь можно написать код и так:

using namespace boolinq;
int sum = sum(select(where(from(arr), [](...){...}), [](...){...}));

Тесты производительности

Проведу тест специально для интересующихся: будем считать дисперсию случайной величины. Сначала найдём среднее значение всех нечетных элементов вектора, затем посчитаем среднеквадратичное отклонение нечетных элементов от среднего.

1. Сгенерируем 100 млн псевдослучайных элементов:

srand(0xDEADBEEF);
std::vector<int> vec(100000000, 0);

for (unsigned i = 0; i < vec.size(); i++)
    vec[i] = rand();

2. Напишем алгоритм на языке C++

// Находим среднее значение нечётных элементов
double sum = 0;
int count = 0;
for (unsigned i = 0; i < vec.size(); i++)
{
    if (vec[i] % 2 == 1)
    {
        sum += vec[i];
        count++;
    }
}
double avgValue = sum / count;

// Считаем среднеквадратичное отклонение нечетных элементов от avgValue
double disperSum = 0;
for (unsigned i = 0; i < vec.size(); i++)
    if (vec[i] % 2 == 1)
        disperSum += (vec[i] - avgValue)*(vec[i] - avgValue);
double disper = disperSum / count;

3. Напишем алгоритм на boolinq

// Находим среднее значение нечётных элементов
double avgValue = from(vec).where( [](int a){return a%2 == 1;})
                           .cast<double>()
                           .avg();

// Считаем среднеквадратичное отклонение нечетных элементов от avgValue
double disper = from(vec).where(  [](int a){return a%2 == 1;})
                         .select([=](int a){return (a-avgValue)*(a-avgValue);})
                         .cast<double>()
                         .avg();

Не смотрите, что в коде на C++ не используются итераторы. Код с итераторами я написал, но позвольте не выкладывать его — он абсолютно аналогичный. Теперь скомпилируем в релизе в MS Visual C++ 2010 и запустим на моей машине…

Код на C++	1207 ms
Код на C++ с итераторами	1224 ms
Код на boolinq	1564 ms

Boolinq, конечно, немного (на треть) проигрывает — но опять же таки зависит от задач. По идее нужно все методы тестировать отдельно. Кстати, .NET LINQ проигрывает аналогу на циклах гораздо-гораздо сильнее.

В ближайшем будущем планируется добавить классу Linq методы .begin() и .end() для обратной совместимости с STL.