Как можно использовать шаблон с переменным числом аргументов для генерации левоассоциативного выражения (или левой складки) в c ++ 11? - PullRequest
Новая
       56

Как можно использовать шаблон с переменным числом аргументов для генерации левоассоциативного выражения (или левой складки) в c ++ 11?

0 голосов
/ 19 февраля 2019

Я хотел бы использовать шаблон c ++ для агрегирования (свертывания) нескольких аргументов с помощью бинарной операции.

Такой шаблон можно использовать следующим образом:

fold<add>(100,10,5) расширяется до add(add(100, 10), 5)

Конкретное расширение, показанное выше, это "левый сгиб".Расширение add(100, add(10, 5)) - это "правильная складка".Предполагая, что функция add выполняет простое сложение целых чисел, правое и левое сгибы дают одинаковый результат, 115.

Но рассмотрим функцию div, которая выполняет целочисленное деление (div(a,b)=a/b).В этом случае ассоциативность имеет значение, и левый и правый сгибы приводят к разным результатам: 

fold_left<div>(100,10,5)  --> div(div(100, 10), 5) --> div(10, 5) -->  2
fold_right<div>(100,10,5) --> div(100, div(10, 5)) --> div(100, 2) --> 50

Использовать шаблон с вариационной формой для получения правоассоциативной версии (fold_right) несложно, но у меня нетудалось выяснить, как создать левоассоциативную версию (fold_left).Попытка реализации fold_left, приведенная ниже, приводит к ошибке компилятора: 

#include <iostream>

template <typename T> using binary_op = T(*)(const T& a, const T& b);

// The terminal (single-argument) cases of the variadic functions defined later. 
template<typename T, binary_op<T> Operation> inline T fold_right(const T& t) { return t; }
template<typename T, binary_op<T> Operation> inline T fold_left(const T& t) { return t; }

// Combines arguments using right-associative operation
// i.e. fold_right<T,op>(A,B,C) --> op(A, op(B,C))
template<typename T, binary_op<T> Operation, typename ... Rest> 
inline T fold_right(const T& t, Rest... rest) {
    return Operation(t, fold_right<T, Operation>(rest...));
}

// Combines arguments using left-associative operation
// i.e. fold_left<T,op>(A,B,C) --> op(op(A,B), C)
template<typename T, binary_op<T> Operation, typename ... Rest> 
inline T fold_left(Rest... rest, const T& t) {
    return Operation(fold_left<T, Operation>(rest...), t);
}

inline int add(const int& a, const int& b) { return a+b; }
inline int div(const int& a, const int& b) { return a/b; }

int main() {
    std::cout << fold_right<int,div>(100,10,5) //  (100 / (10 / 5))  = 50
              << "\n"
              << fold_left<int,div>(100,10,5)  //  Compiler error!
              << std::endl;
    return 0;
}

Как можно использовать шаблоны с переменными координатами (в c ++ 11) для корректной реализации fold_left?

IЯ думаю, что это сводится к возможности «вытолкнуть» последний аргумент из пакета параметров, что я попытался сделать в шаблоне left_fold выше, но, как я уже сказал, это привело к ошибке компилятора.

Примечание: я использовал простые арифметические операции и целые числа в качестве примера в этом вопросе, но ответ (ы) должен быть достаточно общим, чтобы обрабатывать агрегацию объектов с использованием произвольной функции (при условии, что она возвращает тот же тип объекта, что и ее аргументы).

Примечание 2: Для тех, кто знаком с c ++ 17, выражения сгиба могут использоваться для создания как левого, так и правого сгиба с помощью бинарных операторов.Но они недоступны в c ++ 11.

В связи с этим связанный вопрос: приведенные выше шаблоны требуют явного указания типа T, как в fold_right<int,div>(...).Есть ли способ сформулировать шаблон так, чтобы требовалась только операция, например fold_right<div>(...).Я думаю, что тип T может быть выведен, но я не вижу способа упорядочить аргументы шаблона, чтобы поставить binary_op<> первым.

Спасибо!

Ответы [ 3 ]

0 голосов
/ 19 февраля 2019

Пакеты параметров слева проблематичны.Лучше переопределить его как пакет параметров справа: 

template<typename T, binary_op<T> Operation> 
inline T fold_left(const T& t) { return t; }

template<typename T, binary_op<T> Operation, typename ... Rest>
inline T fold_left(const T& a, const T& b, Rest... rest) {
    return fold_left<T, Operation>(Operation(a,b), rest...);
}
0 голосов
/ 19 февраля 2019

Майкл ответил на ваш 1-й вопрос. У 2-го могут быть разные ответы.Мой предпочтительный способ - определить ваши операции как функторы с элементами шаблона: 

#include <type_traits>
struct homogene_add{
    template<typename T>
    T operator()(T const& lhs, T const& rhs){/*...*/}
};

struct mixed_add{
    template<typename L, typename R>
    std::common_type<L,R>::type
    operator()(L const& lhs, R const& rhs){/*...*/}
};

template<typename binary_op, typename ... Args> 
std::common_type<Args...>::type
fold_right(const Args&... args);

template<typename binary_op, typename First, typename ... Args>
std::common_type<First, Args...>::type
fold_right(const First& init, const Args&... args) {
    binary_op op;
    return op(init, fold_right<binary_op>(args...));
};

template<typename binary_op, typename First>
const First& fold_right(const First& init) {
    return init;
};

Квалификация CV и правильность оценки, я оставляю в OP.

0 голосов
/ 19 февраля 2019

В этом и заключается магия пакетов параметров для конечных функций: они выводятся только из явно предоставленных параметров шаблона.

Это означает, что rest... пусто в вызове fold_left<int,div>(100,10,5).Следовательно, ваша функция имеет один аргумент, а не 3.

...