Недавно на Хабре проскакивала новость о Magnit Tech++ Meet Up, и в ней упоминалась задачка, которая меня заинтересовала. В оригинале задачка формулируется так:
Определена функция с сигнатурой:
void do_something(bool a, int b, std::string_view c)Определить функцию, принимающую в произвольном порядке аргументы типов
bool,int,std::string_viewи вызывающую функциюdo_somethingс переданными параметрами в качестве аргументов.
Я придумал несколько решений этой задачки, а здесь предлагаю два варианта ее решения - сначала банальный (и плохой), а затем самый с моей точки зрения оптимальный. Промежуточные варианты приводить не буду.
Вариант первый, банальный и плохой
Итак, начнем с объявления этой самой функции-обертки:
template<typename... Ts>
void wrapper(Ts&&... args)
{
static_assert(sizeof...(args) == 3, "Invalid number of arguments");
[...]
}Принимаем произвольное количество универсальных ссылок на объекты различных типов в качестве аргументов, и сразу проверяем, что переданных аргументов ровно три. Пока все идет хорошо. Дальше нам нужно как-то выстроить их в правильном порядке и засунуть в do_something. Первая (и самая глупая) мысль - использовать std::tuple:
template<typename... Ts>
void wrapper(Ts&&... args)
{
static_assert(sizeof...(args) == 3, "Invalid number of arguments");
std::tuple<bool, int, std::string_view> f_args;
[... как-то заполняем f_args ...]
// и вызываем do_something с аргументами в нужном порядке
std::apply(do_something, f_args);
}Следующий вопрос - как заполнить f_args? Очевидно, нужно как-то пройтись по изначальным аргументам (args) и распихать их по элементам std::tuple в правильном порядке с использованием вспомогательной лямбды вроде такой:
auto bind_arg = [&](auto &&arg) {
using arg_type = typename std::remove_reference<decltype(arg)>::type;
if constexpr (std::is_same<arg_type, bool>::value) {
std::get<0>(f_args) = std::forward<decltype(arg)>(arg);
} else if constexpr (std::is_same<arg_type, int>::value) {
std::get<1>(f_args) = std::forward<decltype(arg)>(arg);
} else if constexpr (std::is_same<arg_type, std::string_view>::value) {
std::get<2>(f_args) = std::forward<decltype(arg)>(arg);
} else {
static_assert(false, "Invalid argument type"); // не сработает
}
};Но тут нас ждет мелкая помеха - эта лямбда не компилируется. Причина в том, что поскольку проверяемое выражение вstatic_assert (тупо false) не зависит от аргумента лямбды, то static_assert срабатывает не тогда, когда создается конкретный экземпляр лямбды из ее шаблона, а еще во время компиляции самого шаблона. Решение простое - заменить false на что-то, зависящее от arg. Например, крайне сомнительно, что arg здесь когда-нибудь будет иметь тип void:
static_assert(std::is_void<decltype(arg)>::value, "Invalid argument type");Так, с этим понятно. Как дальше вызвать эту bind_arg для каждого элемента из args? На помощь приходят свертки:
(bind_arg(std::forward<decltype(args)>(args)), ...);Здесь мы выполняем унарную свертку с использованием comma operator, что в нашем случае преобразуется компилятором в примерно следующее выражение (я использовал индексы в квадратных скобках исключительно для наглядности):
(bind_arg(std::forward<decltype(args[0])>(args[0])),
(bind_arg(std::forward<decltype(args[1])>(args[1])),
(bind_arg(std::forward<decltype(args[2])>(args[2])))));Так, хорошо. Но есть одна проблема: как узнать, все ли элементы std::tuple инициализированы правильно? Ведь wrapper может быть вызван как-нибудь вот так:
wrapper(false, false, 1);и в первый элемент f_args значение будет записано дважды, а последний так и останется value-initialized в значение по умолчанию. Непорядок. Придется налепить рантайм-костылей:
template<typename... Ts>
void wrapper(Ts&&... args)
{
static_assert(sizeof...(args) == 3, "Invalid number of arguments");
std::tuple<bool, bool, bool> is_arg_bound;
std::tuple<bool, int, std::string_view> f_args;
auto bind_arg = [&](auto &&arg) {
using arg_type = typename std::remove_reference<decltype(arg)>::type;
if constexpr (std::is_same<arg_type, bool>::value) {
std::get<0>(is_arg_bound) = true;
std::get<0>(f_args) = std::forward<decltype(arg)>(arg);
} else if constexpr (std::is_same<arg_type, int>::value) {
std::get<1>(is_arg_bound) = true;
std::get<1>(f_args) = std::forward<decltype(arg)>(arg);
} else if constexpr (std::is_same<arg_type, std::string_view>::value) {
std::get<2>(is_arg_bound) = true;
std::get<2>(f_args) = std::forward<decltype(arg)>(arg);
} else {
static_assert(std::is_void<decltype(arg)>::value, "Invalid argument type");
}
};
(bind_arg(std::forward<decltype(args)>(args)), ...);
if (!std::apply([](auto... is_arg_bound) { return (is_arg_bound && ...); }, is_arg_bound)) {
std::cerr << "Invalid arguments" << std::endl;
return;
}
std::apply(do_something, f_args);
}Да, это работает, но... как-то не радует. Во-первых, рантайм-костыли, а хотелось бы, чтобы все проверки выполнялись исключительно в compile time. Во-вторых, при засовывании в std::tuple происходит совершенно лишнее копирование или перемещение аргумента. В-третьих, происходят совершенно лишние value initialization элементов при создании самого std::tuple. Да, для типов аргументов из задачи это не выглядит страшным, а что, если будет что-то потяжелее? Плохо, громоздко, некрасиво, неэффективно.
А что, если подойти с другой стороны?
Вариант второй, окончательный
Что, если вместо промежуточного хранения аргументов в кортеже мы будем сразу получать аргумент нужного типа? Что-нибудь вроде:
template<typename... Ts>
void wrapper(Ts&&... args)
{
static_assert(sizeof...(args) == 3, "Invalid number of arguments");
do_something(get_arg_of_type<bool>(std::forward<Ts>(args)...),
get_arg_of_type<int>(std::forward<Ts>(args)...),
get_arg_of_type<std::string_view>(std::forward<Ts>(args)...));
}Дело за малым - написать эту самую get_arg_of_type(). Начнем с простого - с сигнатуры:
template<typename R, typename... Ts>
R get_arg_of_type(Ts&&... args)
{
[...]
}То есть мы имеем в составе аргументов шаблона тип R (тот, что функция должна найти и вернуть), а в составе аргументов функции - набор разнотипных аргументов args, среди которых, собственно, и нужно искать. Но как же по ним пройтись? Воспользуемся compile time рекурсией:
template<typename R, typename T, typename... Ts>
R get_arg_of_type(T&& arg, Ts&&... args)
{
using arg_type = typename std::remove_reference<decltype(arg)>::type;
if constexpr (std::is_same<arg_type, R>::value) {
return std::forward<T>(arg);
} else if constexpr (sizeof...(args) > 0) {
return get_arg_of_type<R>(std::forward<Ts>(args)...);
} else {
static_assert(std::is_void<decltype(arg)>::value, "An argument with the specified type was not found");
}
}Модифицируем сигнатуру, выделяя первый аргумент отдельно, сверяем его тип с R, если совпал - сразу возвращаем, если нет - смотрим, остались ли у нас еще аргументы в args и вызываем get_arg_of_type() рекурсивно (сдвинув аргументы на один влево), если нет - печатаем ошибку времени компиляции.
Почти хорошо, но... не совсем. Остается одно лишнее копирование/перемещение - ведь, возвращая объект типа R, компилятор вынужден его создать, а RVO здесь не сработает. Что же делать? На помощь приходит decltype(auto):
template<typename R, typename T, typename... Ts>
decltype(auto) get_arg_of_type(T&& arg, Ts&&... args)
{
[... все остальное без изменений ...]
}и вуаля - теперь get_arg_of_type() вместо объекта возвращает ссылку строго того же типа, что и у первого аргумента arg.
Итак, никаких рантайм-костылей, никаких лишних копирований или перемещений (обертка совершенно прозрачна в этом смысле), никаких дополнительных инициализаций. На этом варианте я решил остановиться, но будет любопытно увидеть какой-нибудь еще более эффективный вариант в комментариях. Поиграться с последним решением вживую можно здесь (std::string_view там заменен на более "тяжелый" std::string для более наглядной демонстрации работы perfect forwarding).
Комментарии (35)
oleg-m1973
04.12.2021 20:19+1С универсальной ссылкой remove_reference недостаточно. Там может быть передана константная ссылка или volatile. Тогда is_same не сработает.
KanuTaH Автор
04.12.2021 20:20Да, правильное замечание, согласен! В свое оправдание скажу, что в изначальной формулировке задачи допустимые типы аргументов у обертки строго определены.
oleg-m1973
04.12.2021 20:29+1В обобщённом коде, лучше не смотреть на "допустимые типы аргументов". Здесь воспользуйся std::remove_cvref - std::remove_cv_t<std::remove_reference_t<T>>
moonground
05.12.2021 12:02+1Правильно ли я понимаю, что это можно было бы заменить на std::decay_t<T> ?
Dlougach
04.12.2021 22:00Мне кажется, можно было бы ещё сделать интереснее, если вместо чистого равенства типов проверять, что соответствующий вызов к do_something скомпилируется. Но тогда надо вообще все перестановки аргументов проверять.
KanuTaH Автор
04.12.2021 22:06Вы имеете в виду - с неявными преобразованиями? Так-то это можно устроить через
std::is_convertible, но тут могут быть неоднозначности. Скажем, вот такой вызов сам по себе вполне легитимен:do_something(0, true, s);так как
0будет неявно преобразован вfalse, аtrue- в1.
nickolaym
04.12.2021 23:32Предлагаю упороться и сделать что-то в таком ключе:
Для каждого сочетания формального и фактического типов ввести оценку совместимости (штраф за конверсию): 0 = точное совпадение (с точностью до добавления cv), 1 = арифметическое продвижение, 2 = арифметическое преобразование (например, float в int или наоборот), 3 = пользовательские преобразования; отдельные преобразования - такие, как апкастинг ссылок и указателей (включая умные) и строку к вьюшке, - сделать дешевле, на уровне 1 или 2. Для несовместимых - штраф бесконечный.
Для всех перестановок найти суммарную оценку совместимости
Выбрать абсолютный минимум; если таковых несколько, то считать ситуацию ошибкой неоднозначного сопоставления.
А ещё можно пойти от противного.
На основе имеющейся функции породить семейство обёрток со всеми перестановками. И пусть компилятор сам потрахается, находя наилучшую, как это он делает в обычной жизни.Как можно порождать? Думаю, придётся колдовать с наследованием. Если не хочется писать все перестановки руками
struct wrapper_0 { static R foo(A1 a1, A2 a2, A3 a3, A4 a4) { return f(a1,a2,a3,a4); } }; struct wrapper_1 : wrapper_1 { using wrapper_0::foo; static R foo(A1 a1, A2 a2, A4 a4, A3 a3) { return f(a1,a2,a4,a3); } }; // и т.д. (где, конечно, все wrapper'ы рожаются шаблоном) struct wrapper_23 : wrapper_22 { using wrapper_22::foo; static R foo(A4 a4, A3 a3, A2 a2, A1 a1) { return f(a4,a3,a2,a1); } }; struct wrapper : wrapper_23 { using wrapper_23::foo; }; auto foo(auto... args) { return wrapper::foo(args...); }Я тут не придумал пока, как именно написать рекурсивную перебиралку перестановок, просто показываю идею.
Возможно, что там будет вот такое
template<class... Args> struct wrapper { static size_t N = sizeof...(Args); using Start = std::index_sequence<N>; template<class Seq> using Next = ?????; // next_permutation template<class Seq> using IsLast = std::is_same<Next<Seq>, Start>; template<class IntSequence> struct caller; template<size_t... Ixs> struct caller<std::index_sequence<Ixs...> { // для конкретной перестановки static auto foo(auto fun, type_at<Ixs, Args...>... args) { return fun(arg_at<Ixs>(args...)...); } }; template<class Seq, bool Stop = IsLast<Seq>> struct stacker; template<class Seq> struct stacker<Seq, false> : caller<Seq>, stacker<Next<Seq>> { using caller<Seq>::foo; using stacker<Next<Seq>>::foo; }; template<class Seq> struct stacker<Seq, true> : caller<Seq> {}; static auto foo(auto fun, auto... args) { return stacker<Start>::foo(fun, args...); } }; template<class R, class... FormalArgs> auto make_permutable_function(R (*fun)(FormalArgs...)) { return [fun](auto... args) { return wrapper<FormalArgs...>::foo(args...); } }Понятно, я тут тоже посрезал лишние углы, чисто обозначил подход. Надо ещё перфект форвардинг добавить, потом протащить произвольные функции / функциональные объекты, бла-бла-бла...
lamerok
04.12.2021 23:56+4Я может не до конца понял условие задачи, но если вы проверяете статик ассертом, что параметров 3, то почему в шаблон нельзя просто передать три разных типа?
template<typename T1, typename T2, typename T3> void wrapper(T1&& arg1, T2&& arg2, T3&& arg3)...И проверяйте внутри типы... И весь этот гемор с поиском типа по паку уйдёт.
KanuTaH Автор
05.12.2021 00:02"Гемор с поиском типа по паку" мне видится более универсальным решением, потому что если разнотипных аргументов у
do_somethingбудет не три, а, скажем, 10, то в коде поменяется толькоstatic_assertв началеwrapperи собственно вызовdo_somethingи все. Впрочем, если вы напишете свое видение решения целиком, то будет интересно взглянуть :)
KanuTaH Автор
05.12.2021 00:58+1Кстати, если уж на то пошло, то паки позволяют написать обобщенную обертку вроде такой:
template<typename... As, typename... Ts> void wrapper(const std::function<void(As...)>& f, Ts&&... args) { static_assert(sizeof...(As) == sizeof...(args), "Invalid number of arguments"); f(get_arg_of_type<As>(std::forward<Ts>(args)...)...); }и оборачивать функцию с любыми аргументами:
int main() { std::function<void(bool, int, std::string)> f {&do_something}; wrapper(f, 1, false, std::string("s")); wrapper(f, false, 1, std::string("s")); wrapper(f, std::string("s"), 1, false); }lamerok
05.12.2021 10:36Ок, тогда условие задачи немного другое, мы не знаем какого типа и сколько параметров у функции do_something, и должны „прибиндить" параметры, передаваемые во врапер в произвольном порядке к параметрам этой функции.
encyclopedist
05.12.2021 00:46+3template<typename... Ts> void wrapper(Ts&&... args) { static_assert(sizeof...(args) == 3, "Wrapper takes exactly 3 arguments"); auto t = std::make_tuple(args...); do_something(std::get<bool>(t), std::get<int>(t), std::get<std::string_view>(t)); }Если бы типы были более сложными, пришлось бы подумать как избежать лишних копий.
KanuTaH Автор
05.12.2021 01:07Да, хороший вариант, у меня был такой в качестве одного из промежуточных, когда я вспомнил, что в C++14 в
std::getдобавили извлечение из кортежа не только по номеру, но и по типу, но я его отбросил, поскольку принципиальную проблему лишних копий он не решал.encyclopedist
05.12.2021 04:52Тогда перейти на forwad_as_tuple:
template<typename... Ts> void wrapper(Ts&&... args) { static_assert(sizeof...(args) == 3, "Wrapper takes exactly 3 arguments"); auto t = std::forward_as_tuple(args...); do_something(std::get<bool&>(t), std::get<int&>(t), std::get<std::string_view&>(t)); }KanuTaH Автор
05.12.2021 10:41Тут perfect forwarding не сработает, и при вызове оконечной функции для нессылочных аргументов вместо конструктора перемещения будет всегда вызываться конструктор копии, что может оказаться дороже.
Paulus
05.12.2021 01:25будет любопытно увидеть какой-нибудь еще более эффективный вариант в комментариях.
boost parameter library?
KanuTaH Автор
05.12.2021 01:30Думаю, что составителями задачки подразумевалось, что она должна быть решена без использования сторонних библиотек :) Хотя все может быть. В любом случае, вручную интереснее.
ncr
05.12.2021 06:34+10*Пожимая плечами*
3 аргумента это всего 6 комбинаций…void wrapper(bool a, int b, string_view c) { do_something(a, b, c); } void wrapper(bool a, string_view c, int b) { do_something(a, b, c); } void wrapper(int b, bool a, string_view c) { do_something(a, b, c); } void wrapper(int b, string_view c, bool a) { do_something(a, b, c); } void wrapper(string_view c, bool a, int b) { do_something(a, b, c); } void wrapper(string_view c, int b, bool a) { do_something(a, b, c); }KanuTaH Автор
05.12.2021 10:20Ну так-то да :) А если аргументов больше? А если произвольное количество? :)
rsashka
05.12.2021 11:03+6А если два аргумента будут одного типа???
KanuTaH Автор
05.12.2021 20:05Можно добавить проверку на это, что-нибудь типа такого:
template<typename T, typename... Ts> constexpr bool check_unique() { using type = typename std::decay<T>::type; if constexpr ((std::is_same<type, Ts>::value || ...)) { return false; } else if constexpr (sizeof...(Ts) > 0) { return check_unique<Ts...>(); } else { return true; } }и вызвать ее в составе
static_assert:static_assert(check_unique<Ts...>(), "Duplicate parameter types are not allowed");
kovserg
05.12.2021 11:35+3Еще лучше так, дешево и сердито :)
struct Fn { bool a; int b; string_view c; void call() { do_something(a,b,c); } };
dsavenko
05.12.2021 11:47+8Так вот чем они там занимаются, на своих С++ митапах! Так и знал, что ничего хорошего там не происходит!
Whiteha
05.12.2021 14:47+4Не раскрыто - зачем это может быть нужно, кто пользователь такого кода и почему он не знает порядок аргументов для функции которую вызывает, но знает адрес функции и типы аргументов.
Также сильное ограничение этого подхода, поправьте если не прав - не может быть двух аргументов одного типа, ради чего?
Также как справедливо указали в комментариях выше - подобный код трудносопрвождаем.
В обычной ситуации для передачи n параметров в произвольном порядке используют какой-то вариант map и эта фишка обычно нужна для параметризации единичных вызовов на уровне бизнес логики, или близко к ней. А не для алгоритмов, которые дергаются 100500 раз в секунду и создают узкое место.
mikhainin
05.12.2021 14:58Ну это же разминка для мозгов :)
А из практических кейсов - может быть полезно для автосгенерённого кода, например в сочетании с мета-программированием, когда всё на типы завязано.
KanuTaH Автор
05.12.2021 15:05Да это просто абстрактная задача для разминки мозга. Поэтому и тег "ненормальное программирование". В том и интерес, чтобы реализовать это как можно универсальнее и эффективнее.
oleg1977
05.12.2021 15:34+1void do_something(bool b, int n, std::string_view s) { std::cout << b << n << s; } template<typename T1, typename T2, typename T3> void wrapper(T1 t1, T2 t2, T3 t3) { std::tuple<T1, T2, T3> input_args(t1, t2, t3); do_something(std::get<bool>(input_args), std::get<int>(input_args), std::get<std::string_view>(input_args)); } int main(int argc, char* argv[]) { using namespace std::string_view_literals; wrapper("Hello"sv, false, 5); return 0; }
Borjomy
06.12.2021 11:17-2Теперь понятно, почему мощности современных процессоров все не хватает и не хватает. Потому что на каждый сэкономленный такт приходится по десять таких решений и, что главное, задач. Вы посчитайте, в какое количество процессорного времени выходят ваши разборы. А потом подумайте, зачем они нужны и нельзя ли выполнить ИСХОДНУЮ задачу проще, до того, как пришлось придумывать функцию с произвольным порядком аргументов. Да ещё и со странным условием, что типы разные.
В брутальном решении аргументы передаются массивом типов Variant. Каждый параметр подписывается атрибутом Name. И разбирай-не хочу.
Здесь должна быть картинка с Khaby LAME
KanuTaH Автор
06.12.2021 12:21+1Вы посчитайте, в какое количество процессорного времени выходят ваши разборы.
И в какое же?
goldrobot
06.12.2021 17:54Здесь небудет никаких картинок, потому что в отличии от вашего массива с Variant, все будет посчитано в compile-time.
mayorovp
06.12.2021 20:52Вот как раз из-за таких людей, которые считают нормальным передать параметры массивом Variant с атрибутом Name и не хватает мощности современных процессоров...
Ingulf
06.12.2021 18:10можно еще поюзать синтаксический сахар, не имеющий отношения к задаче, и использовать что-то типа:
std::is_same_v<>
segment
Как в этом потом разбираться…