Введение
После продолжительного перерыва мне пришлось вернуться к программированию на C++. После C# очень не хватало ключевого слова var и возможностей построения запросов linq. Однако как оказалось прогресс не стоит на месте и за время моего отсутствия вышла новая версия С++11, имеющая новые интересные возможности, к тому же реализованная в большинстве компиляторов. Я занимался кросс-платформенным проектом и меня интересовали компиляторы GCC для Linux, Visual Studio и mingw для мира Windows. Попытка найти linq-like библиотеку не увенчались успехом, все, что я находил, было нежизнеспособной поделкой на коленке. Смирившись, я бросил поиски, однако в апреле 2012 вышла обнадеживающая статья LINQ to Objects на языке C++, в которой описывалась библиотека, которая мне подходила. Попробовав ее в деле и разобравшись в ее устройстве, я был разочарован неэффективностью, но некоторые идеи я подчерпнул. Оставалось одно – написать такую же, только с блэк-джеком, что я и сделал github.com/drbasic/CppLinq, заодно разобравшись автоматическим выводом типа (auto) и лямбда выражениями.
Проектировалась библиотека так, что бы с помощью fluent – синтаксиса и лямбда выражений пользователь мог построить граф преобразований. Эти графы можно копировать, достраивать, объединять, т.е. реализовать поведение максимально близкое к прообразу Linq to Objects из мира C#. Функционал библиотеки, недолго думая, я позаимствовал из C#, добавив, явный left join и full join. Важным ограничением библиотеки является перемещение по графу преобразования не копий, а указателей на элементы исходной последовательности. Это позволяет эффективно обходиться со сложными элементами коллекций, ведь теперь не происходит накладных расходов на копирование, но исходная последовательность из-за этого не должна быть «виртуальной». Т.е. к началу работы у каждого элемента исходной последовательности должен быть уникальный адрес и элементы не должны перемещаться в памяти во время работы linq-преобразований. В общем, для этого подходят массивы, контейнеры Qt, все стандартные контейнеры, кроме std::bitset. Сложности возникли лишь с константными последовательностями, которые так и не доделал, так как мне они были не особо нужны. Библиотека проверена и успешно компилируется Visual Studio 2010 и 2012, gcc 4.8, mingw 4.8. Проще всего совладать оказалось с компилятором Microsoft, сделать счастливыми gcc было куда сложнее, причем с внутренней ошибкой бывало падали все компиляторы, порой даже без вразумительных криков.
В бой
Итак, для примера использования CppLinq возьмем последовательность из 10 элементов, отберем те, у кого поле iVal > 5, отсортируем по полю sVal, и результат поместим в std::vector:
TestClass1 data[10];
auto t1 = Linq::from(data)
.where([](const TestClass1 &a){return a.iVal >= 5; })
.orderBy([](const TestClass1 &a){return a.sVal; })
.toVector();
В данном случае сначала создается адаптер к исходным данным from, затем строится граф из оператора фильтрации where, оператора сортировки orderBy. К этому моменту никаких действий с данными еще не произошло, но вот toVector наконец запускает конвейер обработки, который будет работать по следующему алгоритму. toVector начнет запрашивать у последнего фильтра в цепочке обработки все элементы по очереди и формировать из них std::vector. Последним фильтром в цепочке является orderBy, но так как ему для правильного упорядочивания необходимы сразу все элементы, то он запросит из своего вышележащего фильтра where все указатели на элементы последовательности, поместит их в буфер и отсортирует. Фильтр where имеет возможность выбирать нужные элементы «на лету», по этому на каждый запрос нового элемента последовательности снизу он запрашивает элементы из своего вышележащего фильтра from, пока не найдёт удовлетворяющий условию. Адаптер последовательности from на каждый запрос снизу возвращает адрес следующего элемента, а когда элементы кончаться ответит отказом.
Графы можно строить динамически, например, добавляя необходимые фильтры в цепочку в runtime:
auto src = Linq::from(data)
.where([](const TestClass1 &a){return a.iVal >= 5; });
if (order == ascending)
src = src.orderBy([](const TestClass1 &a){return a.sVal; });
else
src = src.orderByDesc([](const TestClass1 &a){return a.sVal; });
auto result = src.toVector();
При формировании графа делаются оптимизации по объединению нескольких последовательных сортировок в одну операцию сортировки, для этого объединяются вместе все функция сравнения элементов. Например, для случая ниже, не смотря на задание двух фильтров сортировки последовательности, будет выполнена всего одна сортировка.
auto t4 = Linq::from(src1)
.orderByDesc([](const TestClass1 &a){return a.sVal; })
.thenBy([](const TestClass1 &a){return a.iVal; })
.toVector();В чисто академических целях реализована оптимизация, когда два последовательных реверса последовательности аннигилируют и не формируют фильтра в цепочке. Все фильтры по возможности сделаны не жадными, т.е. если есть возможность не запрашивать лишних элементов у верхней последовательности, то будет вестись работа «с колес». Но если данные были получены, и они наверняка потребуются еще раз, то указатели обязательно сохраняются в собственный кэш, чтобы минимизировать обращения к верхнему фильтру, так как неизвестна стоимость получения элемента из верхнего фильтра. Баланс сдвинут в сторону использования лишней памяти, нежели дополнительным проходам по цепочке фильтров за очередным элементом. К тому же в буферах сохраняются указатели, а не сами элементы, что не должно приводить к большому расходу памяти при адекватных размерах последовательностей.
При реализации join была дилемма, как реализовать сравнение элементов последовательностей на равенство, через operator==, или эквивалентность, через operator<. Оба варианта имеют плюсы и минусы. В случае применения операции меньше можно было бы отсортировать обе входные последовательности и провести слияние эффективнее, так как не требуется сравнить каждый элемент первой последовательности с каждым элементов второй последовательности. Однако в Linq to Objects принято реализовывать сравнение именно на равенство через operator==, по этому я сделал также, получив алгоритмическую сложность O(n*m).
Как это работает.
Имеется интерфейсный класс Linq, в котором описаны все методы преобразований. Методы можно разделить на две группы, те которые приводят к дальнейшему построению графа, они возвращают Linq<?> например where:
template <typename U>
Linq<T> where(U f);И «терминальные», которые запускают выполнение графа, например:
size_t count();
std::vector<T> toVector();Граф преобразований всегда предается по значению, но это не является проблемой, так как с использованием семантики перемещения получилось обойтись в большинстве случаев без полного копирования. Например, в первом примере не происходит ни одного глубокого копирования.
Интересно сделаны операции дополнительного упорядочивания thenBy и thenByDesc. Так как они должны быть доступны, только если предыдущим оператором является orderBy или orderByDesc, то для этого сделан наследник от Linq, класс LinqOrd, в который вынесены эти операции, и методы orderBy или orderByDesc объявлены как возвращающие LinqOrd:
LinqOrd<T> orderBy();
LinqOrd<T> orderByDesc();Таким образом, после операции orderBy возвращается объект типа LinqOrd, в котором уже имеются дополнительные операции упорядочивания.
Внутри класса Linq имеется единственный член данных, указатель на интерфейсный класс Range. Это и есть шестеренка графа преобразований, выполняющая все работу.
template<typename T>
class Range
{
public:
Range(){}
virtual ~Range(){}
virtual bool empty() = 0;
virtual T& popFront() = 0;
virtual T& front() = 0;
virtual void rewind() = 0;
virtual Range* clone() = 0;
};Интерфейс достаточно прост, представляет собой по большому счету однонаправленный итератор. Метод empty() возвращает, имеются ли еще элементы. Метод popFront() извлекает следующий элемент последовательности, а front() возвращает текущий элемент. Метод rewind() переводит указатель на начало последовательности. Метод clone() создает новый объект и производит глубокое копирование всей внутренней цепочки фильтров.
Операции преобразования реализуют интерфейс Range. Для примера приведу код трансформации для операции where: WhereRange<T,F>. Где T – это тип элемента, а F это класс объекта, используемого для фильтрации. В данном случае у F должен быть определен метод, принимающий T или ссылку на T и возвращающий true, если элемент подходит под условия фильтрации.
template<typename T, typename F>
class WhereRange : public Range<T>
{
public:
WhereRange(Range<T> *src, F f)
: src_(src)
, f_(f)
, frontReady(false)
{
}
~WhereRange()
{
delete src_;
};
bool empty() override
{
if (!frontReady)
seekFront();
return src_->empty();
}
T& popFront() override
{
if (!frontReady)
seekFront();
auto &result = src_->front();
frontReady = false;
src_->popFront();
seekFront();
return result;
}
T& front() override
{
return src_->front();
}
void rewind() override
{
frontReady = false;
src_->rewind();
}
Range<T>* clone() override
{
auto result = new WhereRange(CloneRange(src_), f_);
return result;
}
private:
Range<T> *src_;
F f_;
bool frontReady;
void seekFront()
{
while(!src_->empty() && !f_(src_->front()))
src_->popFront();
frontReady = true;
}
};Чтобы еще больше работы возложить на компилятор, в лямбда выражениях можно выводить тип элемента автоматически, с помощью ключевого слова decltype. Можно первый пример переписать так:
TestClass1 data[10];
auto src = Linq::from(data);
auto result = src
.where([](decltype(src.const_reference()) a){return a.iVal >= 5; })
.orderBy([](decltype(src.const_reference()) a){return a.sVal; })
.toVector();Как видите, нигде явно не фигурирует тип элемента TestClass1. Иногда это удобно, а иногда сложно разобраться с каким же все-таки типом имеем дело.
В примере с объединением последовательностей ниже промежуточные типы также выводятся компилятором:
auto data1 = testData1();
auto data2 = testData2();
auto src1 = Linq::from(data1);
auto src2 = Linq::from(data2);
auto result = src1
.join(
src2,
[](decltype(src1.const_reference()) a){ return a.iVal; },
[](decltype(src2.const_reference()) b){ return b.iVal2; },
[]
(decltype(src1.const_reference()) a, decltype(src2.const_reference()) b)
{
return std::make_pair(b.dVal, a.sVal);
}
)
.toVector();
}Здесь первая и вторая лямбды возвращают ключи, по которым будут объединяться последовательности, а третья лямбда возвращает результат, сформированный из совпадающих элементов обоих последовательностей. Затем все полученные элементы сохраняются в std::vector.
P.S. gcc 4.7 не переваривает ключевого слова override, по этому для него можно задать #define override
Автор: drBasic
