Có thể viết một biến thể chung chung trong C++ không?

Question

Tôi muốn có một hàm zipWith chung trong C++ của biến số. Tôi có hai vấn đề. Đầu tiên là tôi không thể xác định loại con trỏ hàm được truyền tới zipWith. Nó phải có cùng một số nguyên như số lượng vectơ truyền vào zipWith và nó phải chấp nhận tham chiếu đến các kiểu phần tử của vectơ tương ứng. Thứ hai là tôi không có ý tưởng làm thế nào để đi bộ các véc tơ song song để xây dựng một danh sách đối số, gọi func(), và bảo lãnh sau khi véc tơ ngắn nhất bị cạn kiệt.

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

Answer 1

Tôi đã có một câu trả lời dài, sau đó tôi đã thay đổi suy nghĩ của mình theo cách làm cho giải pháp ngắn hơn nhiều. Nhưng tôi sẽ cho thấy quá trình suy nghĩ của tôi và cung cấp cho bạn cả hai câu trả lời!

Bước đầu tiên của tôi là xác định chữ ký thích hợp. Tôi không hiểu hết, nhưng bạn có thể xử lý một gói tham số như một danh sách được phân cách bằng dấu phẩy của các mục thực tế với dấu văn bản bị ẩn. Bạn có thể mở rộng danh sách ở hai bên bằng nhiều mục được phân tách bằng dấu phẩy! Vì vậy, hãy áp dụng trực tiếp điều đó:

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

Bạn phải đặt "..." sau gói tham số cho phần biểu thức để xem danh sách mở rộng. Bạn cũng phải đặt một phần vào phần thông số thông thường:

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

Bạn đã nói rằng tham số chức năng của bạn là một loạt vectơ. Ở đây, bạn hy vọng rằng mỗi Vargs thực sự là một std::vector. Gõ biến đổi có thể được áp dụng cho một gói thông số, vậy tại sao chúng ta không đảm bảo rằng bạn có vectơ:

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

Vectors có thể đối tượng rất lớn, vì vậy hãy sử dụng tài liệu tham khảo const l-giá trị. Ngoài ra, chúng ta có thể sử dụng std::function vì vậy chúng tôi có thể sử dụng lambda hoặc std::bind biểu thức:.

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) { 
    ??? 
} 

(Tôi chạy vào vấn đề ở đây từ việc sử dụng std::pow để thử nghiệm trình biên dịch của tôi sẽ không chấp nhận một con trỏ hàm cổ điển được chuyển đổi thành một đối tượng std::function Vì vậy, tôi đã phải quấn nó trong một lambda. Có lẽ tôi nên hỏi ở đây về điều đó ....)

Tại thời điểm này, tôi tải lại trang và thấy một response (by pmr). Tôi không thực sự hiểu được điều này, gấp, nổ tung, bất cứ thứ gì, vì vậy tôi nghĩ rằng giải pháp của anh ấy/cô ấy quá phức tạp.Vì vậy, tôi nghĩ về một giải pháp trực tiếp hơn:

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; 
} 

tôi sẽ tạo ra một vector của các bộ, trong đó mỗi tuple được làm từ tuốt phần tử tương ứng từ mỗi vector. Sau đó, tôi sẽ tạo một véc tơ gồm kết quả đánh giá khi chuyển một bộ túp và func mỗi lần.

Các rearrange_vectors có để làm cho bảng giá trị trước (mặc định-xây dựng) và điền vào mỗi mục một sub-object tại một thời điểm:

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; 
} 

Phần đầu tiên của dòng đầu tiên cho phép người truy cập chức năng loại trả về của riêng nó mà không cần sao chép và dán. Thông báo trước duy nhất là các thông số tham chiếu giá trị r phải được bao quanh bởi std::forward (hoặc move), do đó quá tải giá trị l của cuộc gọi đệ quy không được chọn do nhầm lẫn. Hàm làm biến đổi một phần của mỗi phần tử tuple phải lấy chỉ mục hiện tại một cách rõ ràng. Chỉ số di chuyển lên một trong khi bóc gói tham số:

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...); 
} 

Bảng này miễn là vector đầu vào ngắn nhất, vì vậy chúng tôi phải cắt bảng bất cứ khi nào vector đầu vào hiện tại kết thúc trước. (Tôi ước mình có thể đánh dấu fe là const trong khối for.) Ban đầu tôi có first và rest là std::vector, nhưng tôi nhận ra rằng tôi có thể trừu tượng hóa điều đó; tất cả những gì tôi cần là các loại khớp với các thùng chứa tiêu chuẩn (chuỗi) trong giao diện lặp lại. Nhưng bây giờ tôi đang bối rối về evaluate:

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

tôi có thể làm các trường hợp cá nhân:

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)); } 

nhưng tôi không thể khái quát nó cho một trường hợp đệ quy. IIUC, std::tuple không hỗ trợ lột đuôi (và/hoặc đầu) như là một phụ tuple. Cũng không std::bind hỗ trợ các đối số currying thành một hàm theo từng phần và hệ thống giữ chỗ của nó không tương thích với các gói tham số có độ dài tùy ý. Tôi ước gì tôi có thể chỉ cần liệt kê mỗi tham số như tôi có thể nếu tôi có quyền truy cập vào các vectơ đầu vào gốc ....

... Chờ đã, tại sao bạn không tôi làm việc đó?! ...

... Ồ, tôi chưa bao giờ nghe về nó. Tôi đã thấy chuyển một gói tham số mẫu tới các tham số hàm; Tôi chỉ hiển thị nó trong zipWith. Tôi có thể làm điều đó từ danh sách tham số chức năng cho nội bộ của hàm không? (Như tôi đang viết, bây giờ tôi nhớ nhìn thấy nó trong phần khởi tạo thành viên của các nhà xây dựng lớp, cho các thành viên không tĩnh là mảng hoặc loại lớp.) Chỉ có một cách để tìm hiểu:

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; 
} 

Tôi buộc phải tính tổng số cuộc gọi trước:

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...)); } 

và chắc chắn đủ, nó đã hoạt động! Tất nhiên, điều này có nghĩa là tôi đã suy nghĩ quá mức về vấn đề cũng tệ như người trả lời khác (theo một cách khác). Nó cũng có nghĩa rằng tôi không cần thiết chán bạn với hầu hết các bài đăng này. Khi tôi bọc nó lên, tôi nhận ra rằng việc thay thế std::vector bằng các loại hộp chứa chung có thể được áp dụng trong zip_width.Và tôi nhận ra rằng tôi có thể làm giảm bắt buộc một vector để không vectơ bắt buộc:

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; 
} 

tôi thêm static_assert như tôi sao chép mã ở đây, kể từ khi tôi quên để đảm bảo rằng số lập luận của func và số của vectơ đầu vào đồng ý. Bây giờ tôi nhận ra rằng tôi có thể sửa chữa các đấu tay đôi hàm con trỏ vs std::function đối tượng bằng cách trừu tượng cả hai đi:

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; 
} 

Đánh dấu một tham số chức năng với một tham chiếu r có giá trị là phương pháp đi qua phổ quát. Nó xử lý tất cả các loại tài liệu tham khảo và const/volatile (cv) trình độ chuyên môn. Đó là lý do tại sao tôi đã chuyển đổi containers cho nó. func có thể có bất kỳ cấu trúc nào; nó thậm chí có thể là một đối tượng lớp với nhiều phiên bản operator(). Vì tôi đang sử dụng giá trị r cho các vùng chứa, chúng sẽ sử dụng cv-qualification tốt nhất cho phần tử dereferencing và chức năng có thể sử dụng để giải quyết quá tải. "Gọi" đệ quy để xác định nội bộ loại kết quả cần sử dụng std::forward để ngăn bất kỳ "hạ cấp" nào thành tham chiếu giá trị l. Nó cũng cho thấy một lỗ hổng trong lần lặp lại này: I phải cung cấp kiểu trả về.

Tôi sẽ sửa lỗi đó, nhưng trước tiên tôi muốn giải thích cách STL. Bạn không xác định trước một loại vùng chứa cụ thể và trả lại cho người dùng. Bạn yêu cầu một đối tượng đặc biệt, một trình lặp đầu ra, mà bạn gửi kết quả đến. Trình lặp có thể được kết nối với một thùng chứa, trong đó tiêu chuẩn cung cấp một số giống. Nó có thể được kết nối với một dòng đầu ra thay vào đó, trực tiếp in kết quả! Phương thức iterator cũng giúp tôi khỏi lo lắng trực tiếp về những lo ngại về bộ nhớ.

#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; 
} 

tôi sao chép minimum_common_size ở đây, nhưng nêu rõ kiểu dữ liệu kết quả đối với trường hợp nhất-base, chống chống lại các loại container khác nhau sử dụng các loại kích thước khác nhau.

Các hàm lấy trình vòng lặp đầu ra thường trả về trình vòng lặp sau khi tất cả các trình vòng lặp được thực hiện. Điều này cho phép bạn bắt đầu một đầu ra mới chạy (ngay cả với một chức năng đầu ra khác nhau), nơi bạn rời đi. Nó không quan trọng đối với các trình vòng lặp đầu ra tiêu chuẩn, vì chúng là tất cả các trình lặp giả. Điều quan trọng là khi sử dụng trình chuyển tiếp (hoặc ở trên) làm trình lặp đầu ra vì chúng làm vị trí theo dõi. (Sử dụng trình chuyển tiếp tiến trình làm đầu ra an toàn miễn là số lần chuyển tối đa không vượt quá không gian lặp còn lại.) Một số hàm đặt trình vòng lặp đầu ra ở cuối danh sách tham số, các trình khác ở đầu; zip_width phải sử dụng sau vì gói thông số phải đi vào cuối.

Di chuyển đến loại trả về hậu tố trong zipWith làm cho mọi phần của trò chơi công bằng chữ ký của hàm khi tính toán biểu thức kiểu trả về. Nó cũng cho phép tôi biết ngay lập tức nếu không thể thực hiện tính toán do không tương thích tại thời gian biên dịch. Hàm std::back_inserter trả về một trình vòng lặp đầu ra đặc biệt cho vectơ thêm các phần tử thông qua hàm thành viên push_back.

Answer 2

Dưới đây là những gì tôi gom góp:

#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; 
} 

Đây là một biến thể cải thiện nhẹ so với phiên bản trước. Vì mọi chương trình tốt nên bắt đầu bằng cách xác định một lần hiển thị bên trái.

Nó vẫn không giải quyết được vấn đề của vòng lặp được đóng gói theo cặp.

Trong thuật ngữ stdlib, chức năng này sẽ được gọi là transform và sẽ yêu cầu chỉ có độ dài của một chuỗi được chỉ định và số khác ít nhất là dài. Tôi gọi nó là transformV ở đây để tránh xung đột tên.