Можно ли написать общий переменный zipWith в C++?

Question

Мне нужна общая функция zipWith в C++ переменной arity. У меня две проблемы. Во-первых, я не могу определить тип указателя функции, переданного zipWith. Он должен быть такой же, как и число векторов, переданных в zipWith, и должно принимать ссылки на типы элементов векторов соответственно. Во-вторых, я понятия не имею, как перемещаться по этим векторам параллельно, чтобы построить список аргументов, вызвать func() и залог после исчерпания самого короткого вектора.

template <typename R, typename T, typename... Vargs> 
std::vector<R> zipWith (R func(???<what goes here>), std::vector<T> first, Vargs rest) { 
    ??? 
} 

Answer 1

У меня был длинный ответ, затем я передумал так, что решение было намного короче. Но я собираюсь показать свой мыслительный процесс и дать вам оба ответа!

Мой первый шаг - определить правильную подпись. Я не понимаю все это, но вы можете рассматривать пакет параметров как список фактических элементов, разделенных запятыми, с скрытым текстовым дампом. Вы можете расширить список с обеих сторон более разделенными запятыми элементами! Поэтому непосредственное применение, что:

template <typename R, typename T, typename... Vargs> 
std::vector<R> zipWith (R func(T,Vargs...), std::vector<T> first, Vargs rest) { 
    ??? 
} 

Вы должны поставить «...» после параметра обновления для секции выражения, чтобы увидеть расширенный список. Вы должны поставить один в очередной порции параметра тоже:

template <typename R, typename T, typename... Vargs> 
std::vector<R> zipWith (R func(T,Vargs...), std::vector<T> first, Vargs... rest) { 
    ??? 
} 

Вы сказали, что ваши параметры функции куча векторов. Здесь вы надеетесь, что каждый из Vargs действительно является std::vector. Преобразования типа могут быть применены к параметру пачке, так почему мы не гарантировать, что у вас есть векторы:

template <typename R, typename T, typename... Vargs> 
std::vector<R> zipWith (R func(T,Vargs...), std::vector<T> first, std::vector<Vargs> ...rest) { 
    ??? 
} 

Векторы могут быть огромные объекты, поэтому давайте использовать const ссылки л-значение. Кроме того, мы могли бы использовать std::function поэтому мы можем использовать лямбду или std::bind выражение:.

template <typename R, typename T, typename... Vargs> 
std::vector<R> zipWith (std::function<R(T, Vargs...)> func, std::vector<T> const &first, std::vector<Vargs> const &...rest) { 
    ??? 
} 

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

На этом этапе я перезагрузил страницу и увидел один response (by pmr). Я действительно не понимаю эту застежку, фальцовку, взрыва, все, что угодно, поэтому я подумал, что его решение слишком сложно.Так я думал о более прямом решении:

template < typename R, typename T, typename ...MoreTs > 
std::vector<R> 
zip_with(std::function<R(T,MoreTs...)> func, 
const std::vector<T>& first, const std::vector<MoreTs>& ...rest) 
{ 
    auto const  tuples = rearrange_vectors(first, rest...); 
    std::vector<R> result; 

    result.reserve(tuples.size()); 
    for (auto const &x : tuples) 
     result.push_back(evaluate(x, func)); 
    return result; 
} 

Я хотел бы создать вектор кортежей, где каждый кортеж был сделан из выщипывания соответствующих элементов из каждого вектора. Затем я создавал бы вектор оценки результатов прохождения кортежа и func каждый раз.

rearrange_vectors должен сделать таблицу значений заранее (по умолчанию возведенного) и заполнить каждую запись суб-объект в то время:

template < typename T, typename ...MoreTs > 
std::vector<std::tuple<T, MoreTs...>> 
rearrange_vectors(const std::vector<T>& first, 
const std::vector<MoreTs>& ...rest) 
{ 
    decltype(rearrange_vectors(first, rest...)) 
     result(first.size()); 

    fill_vector_perpendicularly<0>(result, first, rest...); 
    return result; 
} 

Первая часть первой линии позволяет доступ функции его собственный тип возврата без копирования и вставки. Единственное предостережение заключается в том, что опорные параметры r-значения должны быть окружены std::forward (или move), поэтому ошибка перегрузки рекурсивного вызова l не будет выбрана по ошибке. Функция, которая мутирует часть каждого элемента tuple, должна явно принимать текущий индекс. Индекс перемещается вверх по одному параметру во время упаковки пилинга:

template < std::size_t, typename ...U > 
void fill_vector_perpendicularly(std::vector<std::tuple<U...>>&) 
{ } 

template < std::size_t I, class Seq, class ...MoreSeqs, typename ...U > 
void fill_vector_perpendicularly(std::vector<std::tuple<U...>>& 
table, const Seq& first, const MoreSeqs& ...rest) 
{ 
    auto  t = table.begin(); 
    auto const te = table.end(); 

    for (auto f = first.begin(), fe = first.end(); (te != t) && (fe 
    != f) ; ++t, ++f) 
     std::get<I>(*t) = *f; 
    table.erase(t, te); 
    fill_vector_perpendicularly<I + 1u>(table, rest...); 
} 

таблица до тех пор, как кратчайшее входного вектора, поэтому мы должны обрезать таблицу всякий раз, когда вектор тока входные концы первой. (Я хотел бы отметить fe как const в блоке for.) Первоначально я имел first и rest как std::vector, но я понял, что смогу абстрагировать это; все, что мне нужно, это типы, соответствующие стандартным (последовательностным) контейнерам в итерационном интерфейсе. Но теперь я озадачен на evaluate:

template < typename R, typename T, typename ...MoreTs > 
R evaluate(const std::tuple<T, MoreTs...>& x, 
std::function<R(T,MoreTs...)> func) 
{ 
    //??? 
} 

я могу сделать отдельные случаи:

template < typename R > 
R evaluate(const std::tuple<>& x, std::function<R()> func) 
{ return func(); } 

template < typename R, typename T > 
R evaluate(const std::tuple<T>& x, std::function<R(T)> func) 
{ return func(std::get<0>(x)); } 

, но я не могу обобщить его для рекурсивного случая. IIUC, std::tuple не поддерживает отслаивание хвоста (и/или головы) в виде кортежа. Кроме того, std::bind поддерживает аргументы каррирования в функции по частям, а его система замещения не совместима с пакетами параметров произвольной длины. Я хотел бы просто перечислить каждый параметр, как я мог бы, если бы я имел доступ к исходным входным векторам ....

... Подождите, почему не я только что?! ...

... Ну, я никогда не слышал об этом. Я видел, как переносить пакет параметров шаблона в параметры функции; Я просто показал это в zipWith. Могу ли я сделать это из списка параметров функции во внутренние функции? (Как я пишу, я теперь помню его в член-инициализации части класса конструкторов, для нестатических членов, которые являются массивами или типа класса.) Только один способ узнать:

template < typename R, typename T, typename ...MoreTs > 
std::vector<R> 
zip_with(std::function<R(T,MoreTs...)> func, const std::vector<T>& 
first, const std::vector<MoreTs>& ...rest) 
{ 
    auto const s = minimum_common_size(first, rest...); 
    decltype(zip_with(func,first,rest...))   result; 

    result.reserve(s); 
    for (std::size_t i = 0 ; i < s ; ++i) 
     result.push_back(func(first[i], rest[i]...)); 
    return result; 
} 

где Я вынужден заранее вычислить общее количество звонков:

inline std::size_t minimum_common_size() { return 0u; } 

template < class SizedSequence > 
std::size_t minimum_common_size(const SizedSequence& first) 
{ return first.size(); } 

template < class Seq, class ...MoreSeqs > 
std::size_t 
minimum_common_size(const Seq& first, const MoreSeqs& ...rest) 
{ return std::min(first.size(), minimum_common_size(rest...)); } 

и, конечно же, это сработало! Конечно, это означало, что я слишком много думал о проблеме так же плохо, как и другой респондент (по-другому). Это также означает, что я излишне скучал на вас с большей частью этого поста. Когда я завернул это, я понял, что замена std::vector на общие типы контейнеров-контейнеров может быть применена в zip_width.И я понял, что я мог бы уменьшить обязательный один вектор для каких-либо обязательных векторов:

template < typename R, typename ...T, class ...SizedSequences > 
std::vector<R> 
zip_with(R func(T...) /*std::function<R(T...)> func*/, 
SizedSequences const& ...containers) 
{ 
    static_assert(sizeof...(T) == sizeof...(SizedSequences), 
    "The input and processing lengths don't match."); 

    auto const s = minimum_common_size(containers...); 
    decltype(zip_with(func, containers...))  result; 

    result.reserve(s); 
    for (std::size_t i = 0 ; i < s ; ++i) 
     result.push_back(func(containers[i]...)); 
    return result; 
} 

Я добавил static_assert как я скопировал код здесь, так как я забыл, чтобы убедиться, что подсчет довода func «s и число входных векторов согласуются. Теперь я понимаю, что может исправить дуэли функции-указатель против std::function объекта путем абстрагирования и расстояние:

template < typename R, typename Func, class ...SizedSequences > 
std::vector<R> 
zip_with(Func&& func, SizedSequences&& ...containers) 
{ 
    auto const  s = minimum_common_size(containers...); 
    decltype(zip_with<R>(std::forward<Func>(func), 
    std::forward<SizedSequences>(containers)...)) result; 

    result.reserve(s); 
    for (std::size_t i = 0 ; i < s ; ++i) 
     result.push_back(func(containers[i]...)); 
    return result; 
} 

Пометка параметра функции с ссылкой г-значением является универсальным методом прохождения. Он обрабатывает все виды ссылок и const/volatile (cv) квалификации. Вот почему я переключил containers на него. func может иметь любую структуру; он может даже быть объектом класса с несколькими версиями operator(). Поскольку я использую r-значения для контейнеров, они будут использовать лучшую cv-квалификацию для разыменования элементов, и функция может использовать это для разрешения перегрузки. Рекурсивный «вызов» для внутреннего определения типа результата должен использовать std::forward, чтобы предотвратить «понижение» до ссылок на l-значение. Он также показывает недостаток в этой итерации: I должен указать тип возврата.

Я исправлю это, но сначала я хочу объяснить путь STL. Вы не предварительно определяете конкретный тип контейнера и возвращаете его пользователю. Вы запрашиваете специальный объект - вывод-итератор, на который вы отправляете результаты. Итератор может быть подключен к контейнеру, стандарт которого предоставляет несколько вариантов. Вместо этого он может быть подключен к выходному потоку, напрямую распечатывая результаты! Метод итератора также избавляет меня от непосредственного беспокойства по поводу проблем памяти.

#include <algorithm> 
#include <cstddef> 
#include <iterator> 
#include <utility> 
#include <vector> 

inline std::size_t minimum_common_size() { return 0u; } 

template < class SizedSequence > 
std::size_t minimum_common_size(const SizedSequence& first) 
{ return first.size(); } 

template < class Seq, class ...MoreSeqs > 
std::size_t minimum_common_size(const Seq& first, 
const MoreSeqs& ...rest) 
{ 
    return std::min<std::size_t>(first.size(), 
    minimum_common_size(rest...)); 
} 

template < typename OutIter, typename Func, class ...SizedSequences > 
OutIter 
zip_with(OutIter o, Func&& func, SizedSequences&& ...containers) 
{ 
    auto const s = minimum_common_size(containers...); 

    for (std::size_t i = 0 ; i < s ; ++i) 
     *o++ = func(containers[i]...); 
    return o; 
} 

template < typename Func, class ...SizedSequences > 
auto zipWith(Func&& func, SizedSequences&& ...containers) 
-> std::vector<decltype(func(containers.front()...))> 
{ 
    using std::forward; 

    decltype(zipWith(forward<Func>(func), forward<SizedSequences>(
    containers)...)) result; 
#if 1 
    // `std::vector` is the only standard container with the `reserve` 
    // member function. Using it saves time when doing multiple small 
    // inserts, since you'll do reallocation at most (hopefully) once. 
    // The cost is that `s` is already computed within `zip_with`, but 
    // we can't get at it. (Remember that most container types 
    // wouldn't need it.) Change the preprocessor flag to change the 
    // trade-off. 
    result.reserve(minimum_common_size(containers...)); 
#endif 
    zip_with(std::back_inserter(result), forward<Func>(func), 
    forward<SizedSequences>(containers)...); 
    return result; 
} 

Я скопировал minimum_common_size здесь, но явно упоминается тип результата для наименее базового случая, теплоизолирующие против различных типов контейнеров с использованием различных типов размеров.

Функции, принимающие выходной итератор, обычно возвращают итератор после завершения всех итераторов. Это позволяет начать новый выход (даже с другой функцией вывода), где вы остановились. Это не критично для стандартных итераторов вывода, поскольку они все псевдотераторы. Это важно при использовании форварда-итератора (или выше) в качестве выходного итератора, так как они делают положение дорожки. (Использование передового итератора в качестве выходного является безопасным, если максимальное количество передач не превышает оставшееся пространство итераций.) Некоторые функции помещают выходной итератор в конец списка параметров, другие - в начале; zip_width должен использовать последний, поскольку пакеты параметров должны идти в конце.

Перемещение к типу возврата суффикса в zipWith делает каждую часть честной игры подписи функции при вычислении выражения типа возврата. Это также позволяет мне сразу узнать, невозможно ли вычислить из-за несовместимости во время компиляции. Функция std::back_inserter возвращает специальный выходной итератор к вектору, который добавляет элементы через функцию-член push_back.

Answer 2

Вот что я починил:

#include <iostream> 
#include <vector> 
#include <utility> 

template<typename F, typename T, typename Arg> 
auto fold(F f, T&& t, Arg&& a) 
    -> decltype(f(std::forward<T>(t), std::forward<Arg>(a))) 
{ return f(std::forward<T>(t), std::forward<Arg>(a)); } 

template<typename F, typename T, typename Head, typename... Args> 
auto fold(F f, T&& init, Head&& h, Args&&... args) 
    -> decltype(f(std::forward<T>(init), std::forward<Head>(h))) 
{ 
    return fold(f, f(std::forward<T>(init), std::forward<Head>(h)), 
       std::forward<Args>(args)...); 
} 

// hack in a fold for void functions 
struct ignore {}; 

// cannot be a lambda, needs to be polymorphic on the iterator type 
struct end_or { 
    template<typename InputIterator> 
    bool operator()(bool in, const std::pair<InputIterator, InputIterator>& p) 
    { return in || p.first == p.second; } 
}; 

// same same but different 
struct inc { 
    template<typename InputIterator> 
    ignore operator()(ignore, std::pair<InputIterator, InputIterator>& p) 
    { p.first++; return ignore(); } 
}; 

template<typename Fun, typename OutputIterator, 
     typename... InputIterators> 
void zipWith(Fun f, OutputIterator out, 
      std::pair<InputIterators, InputIterators>... inputs) { 
    if(fold(end_or(), false, inputs...)) return; 
    while(!fold(end_or(), false, inputs...)) { 
    *out++ = f(*(inputs.first)...); 
    fold(inc(), ignore(), inputs...); 
    } 
} 

template<typename Fun, typename OutputIterator, 
     typename InputIterator, typename... Rest> 
void transformV(Fun f, OutputIterator out, InputIterator begin, InputIterator end, 
       Rest... rest) 
{ 
    if(begin == end) return ; 
    while(begin != end) { 
    *out++ = f(*begin, *(rest)...); 
    fold(inc2(), ignore(), begin, rest...); 
    } 
} 

struct ternary_plus { 
    template<typename T, typename U, typename V> 
    auto operator()(const T& t, const U& u, const V& v) 
    -> decltype(t + u + v) // common type? 
    { return t + u + v; } 
}; 

int main() 
{ 
    using namespace std; 
    vector<int> a = {1, 2, 3}, b = {1, 2}, c = {1, 2, 3}; 
    vector<int> out; 

    zipWith(ternary_plus(), back_inserter(out) 
      , make_pair(begin(a), end(a)) 
      , make_pair(begin(b), end(b)) 
      , make_pair(begin(c), end(c))); 

    transformV(ternary_plus(), back_inserter(out), 
      begin(a), end(a), begin(b), begin(c)); 

    for(auto x : out) { 
    std::cout << x << std::endl; 
    } 

    return 0; 
} 

Это слегка улучшенный вариант по сравнению с предыдущими версиями. Поскольку каждая хорошая программа должна, она начинается с определения левого сложения.

Он по-прежнему не решает проблему итераторов, упакованных попарно.

В STDLIB терминах эта функция будет называться transform и будет требовать, чтобы только длина одной последовательности задается и другим быть, по крайней мере до тех пор. Я назвал это transformV здесь, чтобы избежать конфликтов .