Статья для тех, кому интересна реализация библиотеки 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), [](...){...}), [](...){...}));
В ближайшем будущем планируется добавить классу Linq методы .begin() и .end() для обратной совместимости с STL.
Автор: k06a
