Среди многих реализаций LINQ-подобных библиотек на C++, есть много интересных, полезных и эффективных. Но на мой взгляд, большинство из них написаны с неким пренебрежением к C++ как к языку. Весь код этих библиотек написан так, словно пытаются исправить его «уродливость». Признаюсь, я люблю C++. И как бы его не поливали грязью, моя любовь к нему едва ли пройдёт. Возможно, это отчасти потому, что это мой первый язык программирования высокого уровня и второй, который я изучил после Ассемблера.
Зачем?
Это извечный и, вполне, естественный вопрос. «Зачем, когда есть море LINQ-подобных библиотек — бери и пользуйся?». Отчасти, я написал её из-за своего собственного видения реализации таких библиотек. Отчасти, из-за желания пользоваться библиотекой, которая максимально полно реализует LINQ методы, чтобы при необходимости можно было бы переносить код с минимальными изменениями из одного языка в другой.
Особенности моей реализации:
- Использование стандарта C++14 (в частности, полиморфные лямбда выражения)
- Использование итераторов-адаптеров только c последовательным доступом (forward-only/input iterators). Это позволяет использовать любые типы контейнеров и объектов, которые не могут иметь произвольного доступа по разным причинам, например std::forward_list. Это, также, немного упрощает разработку пользовательских объектов-коллекций, которые должны поддерживать std::begin, std::end, а сами итераторы должны поддерживать только operator *, operator != и operator ++. Таким образом, кстати, работает новый оператор for для пользовательских типов.
- Relinx объект подходит для итерации в новом операторе for без конвертации в другой тип контейнера, а также в других STL функциях-алгоритмах в зависимости от типа итератора нативного контейнера.
- Библиотека реализует почти все варианты LINQ методов в том или ином виде.
- Relinx объект является очень тонкой прослойкой над нативной коллекцией, насколько это возможно.
- В библиотеке используется форвардинг параметров и реализуется move семантика вместо copy, где это уместно.
- Библиотека достаточно быстрая, за исключением операций, которые требуют произвольный доступ к элементам коллекции (например, last, element_at, reverse).
- Библиотека легко расширяемая.
- Библиотека распространяется под лицензией MIT.
Некоторые программисты C++ не любят итераторы и пытаются их как-то заменить, например на ranges, или обойтись вообще без них. Но, в новом стандарте C++11, чтобы поддерживать оператор for для пользовательских объектов-коллекций, необходимо предоставить для оператора for именно итераторы (или итерируемые типы, например, указатели). И это требование не просто STL, а уже самого языка.
Таблица соответствия LINQ методов Relinx методам:
| LINQ методы | Relinx методы |
|---|---|
| Aggregate | aggregate |
| All | all |
| none | |
| Any | any |
| AsEnumerable | from |
| Avarage | avarage |
| Cast | cast |
| Concat | concat |
| Contains | contains |
| Count | count |
| cycle | |
| DefaultIfEmpty | default_if_empty |
| Distinct | distinct |
| ElementAt | element_at |
| ElementAtOrDefault | element_at_or_default |
| Empty | from |
| Except | except |
| First | first |
| FirstOrDefault | first_or_default |
| for_each, for_each_i | |
| GroupBy | group_by |
| GroupJoin | group_join |
| Intersect | intersect_with |
| Join | join |
| Last | last |
| LastOrDefault | last_or_default |
| LongCount | count |
| Max | max |
| Min | min |
| OfType | of_type |
| OrderBy | order_by |
| OrderByDescending | order_by_descending |
| Range | range |
| Repeat | repeat |
| Reverse | reverse |
| Select | select, select_i |
| SelectMany | select_many, select_many_i |
| SequenceEqual | sequence_equal |
| Single | single |
| SingleOrDefault | single_or_default |
| Skip | skip |
| SkipWhile | skip_while, skip_while_i |
| Sum | sum |
| Take | take |
| TakeWhile | take_while, take_while_i |
| ThenBy | then_by |
| ThenByDescending | then_by_descending |
| ToArray | to_container, to_vector |
| ToDictionary | to_map |
| ToList | to_list |
| ToLookup | to_multimap |
| to_string | |
| Union | union_with |
| Where | where, where_i |
| Zip | zip |
Как?
Исходный код библиотеки документирован Doxygen блоками с примерами использования методов. Также, имеются простые юнит-тесты, в основном написанные мною для контроля и соответствия результатов исполнения методов результатам C#. Но, они сами могут служить простыми примерами использования библиотеки. Для написания и тестирования я использовал компиляторы MinGW / GCC 5.3.0, Clang 3.9.0 и MSVC++ 2015. C MSVC++ 2015 есть проблемы компиляции юнит тестов. Насколько мне удалось выяснить, этот компилятор неправильно понимает некоторые сложные lambda выражения. Например, я заметил, что если использовать метод from внутри лямбды, то вылетает странная ошибка компиляции. С другими перечисленными компиляторами таких проблем нет.
Библиотека представляет из себя только заголовочный файл, который необходимо включить в модуль, где она будет использована.
Перед использованием, для удобства, можно ещё заинджектить relinx namespace.
Несколько примеров использования:
Простое использование. Просто, посчитаем количество нечётных чисел:
auto result = from({1, 2, 3, 4, 5, 6, 7, 8, 9}).count([](auto &&v) { return !!(v % 2); });
std::cout << result << std::endl;
//Должно быть выведено: 5
Пример по-сложнее — группировка:
struct Customer
{
uint32_t Id;
std::string FirstName;
std::string LastName;
uint32_t Age;
bool operator== (const Customer &other) const
{
return Id == other.Id && FirstName == other.FirstName && LastName == other.LastName && Age == other.Age;
}
};
//auto group_by(KeyFunction &&keyFunction) const noexcept -> decltype(auto)
std::vector<Customer> t1_data =
{
Customer{0, "John"s, "Doe"s, 25},
Customer{1, "Sam"s, "Doe"s, 35},
Customer{2, "John"s, "Doe"s, 25},
Customer{3, "Alex"s, "Poo"s, 23},
Customer{4, "Sam"s, "Doe"s, 45},
Customer{5, "Anna"s, "Poo"s, 23}
};
auto t1_res = from(t1_data).group_by([](auto &&i) { return i.LastName; });
auto t2_res = from(t1_data).group_by([](auto &&i) { return std::hash<std::string>()(i.LastName) ^ (std::hash<std::string>()(i.FirstName) << 1); });
assert(t1_res.count() == 2);
assert(t1_res.first([](auto &&i){ return i.first == "Doe"s; }).second.size() == 4);
assert(t1_res.first([](auto &&i){ return i.first == "Poo"s; }).second.size() == 2);
assert(from(t1_res.first([](auto &&i){ return i.first == "Doe"s; }).second).contains([](auto &&i) { return i.FirstName == "Sam"s; }));
assert(from(t1_res.first([](auto &&i){ return i.first == "Poo"s; }).second).contains([](auto &&i) { return i.FirstName == "Anna"s; }));
assert(t2_res.single([](auto &&i){ return i.first == (std::hash<std::string>()("Doe"s) ^ (std::hash<std::string>()("John"s) << 1)); }).second.size() == 2);
assert(t2_res.single([](auto &&i){ return i.first == (std::hash<std::string>()("Doe"s) ^ (std::hash<std::string>()("Sam"s) << 1)); }).second.size() == 2);
Результатом группировки является последовательность из std::pair, где first является ключом, а second — это сгруппированные по этому ключу элементы Customer в контейнере std::vector. Группировка по нескольким полям одного класса производиться по хэш-ключу в данном примере, но это не обязательно.
А вот, пример использования group_join, который, кстати, не компилируется только в MSVC++ 2015 из-за вложенного relinx запроса в самих lambda выражениях:
struct Customer
{
uint32_t Id;
std::string FirstName;
std::string LastName;
uint32_t Age;
bool operator== (const Customer &other) const
{
return Id == other.Id && FirstName == other.FirstName && LastName == other.LastName && Age == other.Age;
}
};
struct Pet
{
uint32_t OwnerId;
std::string NickName;
bool operator== (const Pet &other) const
{
return OwnerId == other.OwnerId && NickName == other.NickName;
}
};
//auto group_join(Container &&container, ThisKeyFunction &&thisKeyFunction, OtherKeyFunction &&otherKeyFunction, ResultFunction &&resultFunction, bool leftJoin = false) const noexcept -> decltype(auto)
std::vector<Customer> t1_data =
{
Customer{0, "John"s, "Doe"s, 25},
Customer{1, "Sam"s, "Doe"s, 35},
Customer{2, "John"s, "Doe"s, 25},
Customer{3, "Alex"s, "Poo"s, 23},
Customer{4, "Sam"s, "Doe"s, 45},
Customer{5, "Anna"s, "Poo"s, 23}
};
std::vector<Pet> t2_data =
{
Pet{0, "Spotty"s},
Pet{3, "Bubble"s},
Pet{0, "Kitty"s},
Pet{3, "Bob"s},
Pet{1, "Sparky"s},
Pet{3, "Fluffy"s}
};
auto t1_res = from(t1_data).group_join(t2_data,
[](auto &&i) { return i.Id; },
[](auto &&i) { return i.OwnerId; },
[](auto &&key, auto &&values)
{
return std::make_pair(key.FirstName + " "s + key.LastName,
from(values).
select([](auto &&i){ return i.NickName; }).
order_by().
to_string(","));
}
).order_by([](auto &&p) { return p.first; }).to_vector();
assert(t1_res.size() == 3);
assert(t1_res[0].first == "Alex Poo"s && t1_res[0].second == "Bob,Bubble,Fluffy"s);
assert(t1_res[1].first == "John Doe"s && t1_res[1].second == "Kitty,Spotty"s);
assert(t1_res[2].first == "Sam Doe"s && t1_res[2].second == "Sparky"s);
auto t2_res = from(t1_data).group_join(t2_data,
[](auto &&i) { return i.Id; },
[](auto &&i) { return i.OwnerId; },
[](auto &&key, auto &&values)
{
return std::make_pair(key.FirstName + " "s + key.LastName,
from(values).
select([](auto &&i){ return i.NickName; }).
order_by().
to_string(","));
}
, true).order_by([](auto &&p) { return p.first; }).to_vector();
assert(t2_res.size() == 6);
assert(t2_res[1].second == std::string() && t2_res[3].second == std::string() && t2_res[5].second == std::string());
В примере, результатом первой операции является объединение двух различных объектов по ключу методом inner join, а затем их группировка по ним.
Во второй операции, происходит объединение по ключу методом left join. Об этом говорит последний параметр метода установленный в true.
А вот, пример использования фильтрации полиморфных типов:
//auto of_type() const noexcept -> decltype(auto)
struct base { virtual ~base(){} };
struct derived : public base { virtual ~derived(){} };
struct derived2 : public base { virtual ~derived2(){} };
std::list<base*> t1_data = {new derived(), new derived2(), new derived(), new derived(), new derived2()};
auto t1_res = from(t1_data).of_type<derived2*>();
assert(t1_res.all([](auto &&i){ return typeid(i) == typeid(derived2*); }));
assert(t1_res.count() == 2);
for(auto &&i : t1_data){ delete i; };
Я разместил код на нескольких площадках:
GitHub: https://github.com/Ptomaine/Relinx
CodePlex: https://relinx.codeplex.com/
Sourceforge: https://sourceforge.net/projects/relinx/
Готов ответить на вопросы по использованию библиотеки и буду очень благодарен за конструктивные предложения по улучшению функционала и замеченные ошибки.
Поделиться с друзьями
Комментарии (22)
izvolov
18.06.2016 18:24-2На первый взгляд всё достаточно печально:
- Внезапные аллокации внутри обработчиков.
- Копирование класса
relinx_objectнекорректно. - Не везде, где нужно, используется
std::forward. - Всё в одном файле (как так-то?!).
К тому же невозможно скачать и сразу собрать проект (пришлось собирать вручную), а ещё куча предупреждений на самые простые флаги (
-Wall -Wextra -Wpedantic).
arlen_albert
19.06.2016 05:421. Укажите, пожалуйста, где происходят внезапные аллокации, чтобы, если это верно, я мог поправить код.
2. Что значит, копирование класса relinx_object? Конструктор копирования или что?
3. Я проверю на предмет forward. Мог пропустить где-то.
4. И что?
У clang-а вообще никаких претензий нет:
clang++.exe -Wall -std=c++14 -fexceptions -O3 -Wnon-virtual-dtor -Wbind-to-temporary-copy -Wambiguous-member-template -pedantic-errors -pedantic -Wall -target x86_64-w64-mingw32 -c D:\Projects\relinx\main.cpp -o obj\Release\main.o
clang++.exe -o bin\Release\relinx.exe obj\Release\main.o -s -target x86_64-w64-mingw32
Output file is bin\Release\relinx.exe with size 464.00 KB
Process terminated with status 0 (0 minute(s), 18 second(s))
0 error(s), 0 warning(s) (0 minute(s), 18 second(s))izvolov
19.06.2016 11:09+3Аллокации
Аллокации происходят, например, при каждом вызове конструктора класса
relinx_object. Это функцияfrom, а также всякие обработчики типаcast,cycleи т.д.
Копирование (и перенос тоже)
В языке C++ существует две операции копирования. Это конструктор копирования и оператор копирующего присвоения.
Класс
relinx_objectпри конструировании создаёт ссылки на самого себя — итераторы на внутренний контейнер. Вызов генерируемых компилятором операций копирования (и переноса) по-умолчанию для такой структуры приведёт к созданию некорректного объекта.
Запустите у себя такой код:
const auto l = [] {return from({1, 2, 3, 4, 5});}; const auto y = l(); std::cout << y.sum() << std::endl;
arlen_albert
19.06.2016 21:031. Я понял Вас. Спасибо, поправлю. Но, тем не менее, я не считаю эти «аллокации» слишком большой проблемой. Просто, простор для оптимизации ;) Хотя, Ваше замечание считаю было по делу )
2. Ваш код, с последними моими изменениями в коде relinx_object (где я удалил конструктор копирования), выводит результат 15.izvolov
19.06.2016 21:24+2я не считаю эти «аллокации» слишком большой проблемой
Значит, вы не пишете программы, требовательные к производительности.
И это самые настоящие аллокации, без кавычек.
выводит результат 15
Повезло. Как я уже писал, перенос по-умолчанию в вашем случае также некорректен.
Ну и простой запрет копирования — это, скорее, костыль, чем решение проблемы.arlen_albert
19.06.2016 22:56Везение тут не причём. Либо работает, либо нет.
Запрет копирования — это не костыль, а by design.
Простите, но Ваша манера тыкать носом без объяснения причин выглядит не по-людски, я бы сказал даже агрессивно.
перенос по-умолчанию в вашем случае также некорректен
Ну так и поясните почему. Или я недостоин? :)izvolov
20.06.2016 00:56+2Везение тут не причём. Либо работает, либо нет.
Вы не сталкивались с ситуациями, когда объект недействителен, но к его данным всё ещё есть доступ? Висячие ссылки?
… без объяснения причин ...
Вообще-то я уже объяснил причину. Но давайте повторю.
Класс relinx_object при конструировании создаёт ссылки на самого себя.
Из этого моментально следует, что генерируемые компилятором операции копирования будут работать неправильно, потому что они реализуют почленное копирование. Следовательно, в скопированном объекте будут ссылки уже не на себя, а на копируемый объект.
То же самое относится и к операциям переноса.
В общем-то, это задача на собеседование для начинающего плюсовика, только на собеседованиях она обычно подаётся в виде "напишите конструктор копирования для класса, который управляет голым указателем".
МанерыЕсли говорить о манерах, то мне, например, не нравится манера огрызаться вместо того, чтобы пять минут подумать.arlen_albert
20.06.2016 04:02Да, Вы правы насчёт ссылок. Поправил. Данные переносятся теперь в новые экземпляры relinx_object.
lemelisk
20.06.2016 15:00+3В репозитории на github у вас по-прежнему:
relinx_object(relinx_object &&) = default;
Если вы, возможно, не поняли в чем её проблема, то попробую объяснить ещё раз: не для всех контейнеров move-конструктор реализован, как простой swap указателей на данные. Соответственно, итераторы (которые у вас просто копируются при таком задании конструктора), указывающие на данные старого контейнере, могут не быть корректными итераторами для перемещенного контейнера. Самый простой пример: массивы статической длины, если у васContainerбудет типаstd::array<int>, то перемещение этого массива — это просто побитовое копирование данных из старого объекта в новый, а, соответственно,_beginи_endнового объекта будут указывать внутрь старого массива. Если старый объект после этого уничтожается (например, он был временным объектом), то имеем use-after-free. Я бы накидал вам код для наглядности, но не смог быстро разобраться, что за новый параметрStoreTypeвы добавили в последней редакции, надеюсь и так понятно.
Причем из-за выбранного вами дизайна, когда у вас один и тот же объект может быть как простой невладеющей парой итераторов, так и владеть собственным контейнером, кроме того для второго случая не всегда_beginуказывает на начало владеемого контейнера (т.к. он может быть сдвинут с помощьюskip, может и каких-то других функций), я не представляю как это можно легко исправить, не теряя при этом в эффективности (потому что понятно, что данные, лежащие по_beginи_end, всегда можно просто тупо скопировать).
Что ещё бросилось в глаза при беглом изученииtemplate<typename Container> auto from(Container &&c) -> decltype(auto) { return relinx_object<typename std::decay<decltype(std::begin(c))>::type>( std::begin(c), std::end(c)); }
Даже для prvalue аргумента (когда параметр выводится как rvalue ссылкаContainer&&) все равно используется невладеющий вип конструктора (по паре итераторов), соответственно, какой-нибудь такой код не сработает:
vector<int> func(); auto r = from(func()); // ниже этой строчки r использовать нельзя, // т.к. вектор, который вернула func(), уже уничтожен
Более того, версияfrom, принимающаяstd::initializer_list, благодаря какой-то неочевидной шаблонной магии, вызывает вышеупомянутую версию функции, поэтому даже такой код не будет работать:
auto r = from({1, 2, 3}); // дальше этой строчки r использовать нельзя
В общем, пока у вас все экземплярыrelinx_objectживут только до конца выражения, то всё хорошо, при более длительном времени жизни начинаются приключения.
Вторая проблема — у вас внутри объекта лежит огромная куча каких-то непонятных данных, объект, создаваемый из простой пары указателей (Iterator = T*), занимает в памяти вместо ожидаемых 16 байт аж целых 128. Не знаю как насчет остальных, но_indexer,_def_val_containerи_default_valueопределенно лишние, они используются везде как типичные временные переменные:
template<typename ForeachFunctor> auto for_each_i(ForeachFunctor &&foreachFunctor) const noexcept -> void { auto begin = _begin; auto end = _end; _indexer = 0; while (begin != end) { foreachFunctor(*begin, _indexer); ++_indexer; ++begin; } }
В чем смысл помещения их внутрь объекта я не понимаю.
Дальше:
template<typename AvgFunctor> auto avarage(AvgFunctor &&avgFunctor) const noexcept -> decltype(auto) { return (sum(std::forward<AvgFunctor>(avgFunctor)) / std::distance(_begin, _end)); }
Во-первых, конечно, average, во-вторых, в случае неRandomAccessIteratorреализация неэффективна (два прохода вместо одного), а в случаеInputIterator(по которым можно сделать только один проход, например,std::istream_iterator) вообще не сработает.
Ну и по мелочи:
using self_type = relinx_object<Iterator, ContainerType>;
с последней редакцией указывает на неверный тип.
relinx_object(ContainerType &&container) noexcept : _container(std::forward<ContainerType>(container)) , _begin(std::begin(_container)) , _end(std::end(_container)) {}
Напишите по-русски_container(std::move(container)), у вас тут аргумент нешаблонный, никакой тип не выводится.arlen_albert
20.06.2016 18:41Спасибо большое за дельные советы и замечания. Попытаюсь в ближайшее время поправить.
arlen_albert
20.06.2016 19:46Я, скорее всего, изменю архитектуру...
lemelisk
20.06.2016 23:02Да, я бы на вашем месте хорошенько продумал и в явном виде прописал, кто чем владеет и как и кому это владение в процессе переходит. Мы же на языке без сборки мусора программируем, тут это важно. Ещё бы подумал над тем, что одни функции-члены класса у вас возвращают новый экземпляр
relinx_object, а другие — меняют сам исходной объект (например,skip, мб какие-то ещё). Я понимаю, что в случаеskipэто вызвано идеей оптимизации, но выглядит такой интерфейс контринтуитивно.
arlen_albert
20.06.2016 04:14-1МанерыМанеры… Всем что-то и как-то не нравиться в этой жизни. Я считаю, главное в хороших манерах, подумать что и как ты говоришь. Взаимоуважение, я считаю, это необходимое качество для нормального общения. Но, по большей части, Ваши слова в комментариях имеют унизительный характер в мой адрес. Может Вы и отличный программист, а вот как человек в общении как-то не очень, извините.
arlen_albert
19.06.2016 06:06Кстати, GCC с флагами -Wall -Wextra -Wpedantic ругался только 'warning: unused parameter 'v' [-Wunused-parameter]' с сопутствующей кучей воды. Я убрал неиспользуемые параметры и вуаля:
— Build: Release-GCC in relinx (compiler: GNU GCC Compiler)---------------
x86_64-w64-mingw32-g++.exe -Wall -std=c++14 -fexceptions -O3 -pedantic -Wextra -Wall -c D:\Projects\relinx\main.cpp -o obj\Release\main.o
x86_64-w64-mingw32-g++.exe -o bin\Release\relinx.exe obj\Release\main.o -s
Output file is bin\Release\relinx.exe with size 385.00 KB
Process terminated with status 0 (0 minute(s), 12 second(s))
0 error(s), 0 warning(s) (0 minute(s), 12 second(s))
— Закомител код.
snizovtsev
А есть какие-либо принципиальные идейные отличия между LINQ и Ranges? Если нет, то не логичнее ли (если уж выбрали путь идеоматичности) использовать Ranges, тем более они претендуют на включение в стандарт?
Vadem
Основное отличие(если я правильно понимаю) в том, что LINQ предназначен для работы с разными источниками данных, а не только с коллекциями в памяти. Например есть провайдеры для работы с БД, xml, json и т.д. Плюс вы можете написать свой провайдер для нужного источника данных.
encyclopedist
В range-v3 поддерживается любой источник удовлетворяющий довольно либеральным требованиям — требуется только возможноть итерации с помощью
begin()иend()(причём они не обязаны возвращать один и тот же тип, что делает удобным, например, остановку по условию или количеству). Никакого требования чтобы источник был коллекцией в памяти нет.В качестве примера смотрите
ranges::getlines, который итерирует по строкам файла.Пример: читаем файл по строкам, пропускаем пустые и закомментированные строки, и парсим каждую строку в вектор даблов:
(signal::io:: определены в моём проекте)
Ну и конечно же можно оперелить свои источники данных.
kekekeks
Суть в том, что шарповый LINQ умеет генерить, например, SQL-запросы из вашего кода. Сделано это за счёт того, что при использовании LINQ поверх IQueryable компилятором генерируется не код выражения, а код, создающий в памяти структуру под названием дерево выражений (expression tree), которую в дальнейшем LINQ-провайдер может анализировать. К примеру код
или эквивалентный ему
компилятор превратит в
Соответственно LINQ-провайдер через рефлексию разберётся, к чему относится IQueryable и что есть Bar, и в дальнейшем сгенерит запрос к базе «SELECT * FROM Foos WHERE Bar = 1», который и выполнится при попытке перечислить IQueryable (что происходит при вызове ToList, который как раз работает через IEnumerable). Как это вообще на C++ переносить — мне не особо понятно.
hasu0
На чистые плюсы, насколько я понимаю, никак.
А в целом для построения какой-никакой рефлексии и вообще сохранения некоторой информации из исходного кода есть обычный подход — делаете внешнюю тулзу, которая умеет по некоторой разметке в исходном коде генерить нужную вам информацию, а потом встраиваете как шаг сборки. Так например делает Qt moc, он генерит реализацию методов рефлексии для наследников QObject'а в отдельный файл.
Если не хочется делать спец-разметку, то по-идее можно подумать насчет внешней тулзы на основе libclang или вообще плагина для clang'а.
Ariox41
Судя по исходникам, from возвращает тот же диапазон, но алгоритмы работы с ним жестко зашиты в его методах, и предназначены только для forward-only/input iterators. Концепция Ranges в этом плане более универсальна, ограничения на итераторы задается на уровне алгоритма, а не диапазона. И синтаксис подобный синтаксису из статьи поддерживается: auto res = data | transform([](auto&&){...})
arlen_albert
Спасибо за информацию… Я рассмотрю Ranges как вариант…
arlen_albert
Я хотел написать именно LINQ-подобную библиотеку, для переноса LINQ выражений из C# в C++ и наоборот.
Вариант с Ranges я рассмотрю. Спасибо.