Sắp xếp lại các tham số biến thể

Question

Tôi đã đi qua sự cần thiết phải sắp xếp lại một danh sách các tham số của Variad được cung cấp cho hàm tạo của một cấu trúc. Sau khi được sắp xếp lại dựa trên loại của chúng, các tham số sẽ được lưu trữ dưới dạng bộ tuple. Câu hỏi của tôi là làm thế nào điều này có thể được thực hiện để trình biên dịch C++ hiện đại (ví dụ: g++-4.7) sẽ không tạo ra các hướng dẫn tải hoặc lưu trữ không cần thiết. Đó là, khi hàm tạo được gọi với một danh sách các tham số của kích thước biến, nó đẩy hiệu quả mỗi tham số vào vị trí dựa trên một thứ tự trên các kiểu tham số.

Dưới đây là ví dụ cụ thể. Giả sử rằng loại cơ sở của mọi thông số (không có tham chiếu, tham chiếu rvalue, con trỏ hoặc vòng loại) là char, int hoặc float. Làm thế nào tôi có thể làm cho nó để tất cả các thông số của loại cơ sở char xuất hiện đầu tiên, theo sau là tất cả các loại cơ sở int (để lại các thông số của loại cơ sở float cuối cùng). Thứ tự tương đối trong đó các tham số được đưa ra không nên bị vi phạm trong các danh sách con của loại cơ sở đồng nhất.

Ví dụ: foo::foo() được gọi với đối số float a, char&& b, const float& c, int&& d, char e. Tuple tupe là std::tuple<char, char, int, float, float>, và nó được xây dựng như vậy: tuple_type{std::move(b), e, std::move(d), a, c}.

Xem xét cấu trúc được xác định bên dưới và giả sử rằng metafunction deduce_reordered_tuple_type đã được triển khai. Làm thế nào bạn sẽ viết các nhà xây dựng để nó hoạt động như dự định? Nếu bạn nghĩ rằng mã cho deduce_reodered_tuple_type, sẽ hữu ích cho bạn, tôi có thể cung cấp mã đó; đó là một chút dài.

template <class... Args> struct foo 
{ 
    // Assume that the metafunction deduce_reordered_tuple_type is defined. 
    typedef typename deduce_reordered_tuple_type<Args...>::type tuple_type; 
    tuple_type t_; 

    foo(Args&&... args) : t_{reorder_and_forward_parameters<Args>(args)...} {} 
}; 

Sửa 1 Kỹ thuật tôi mô tả ở trên không có ứng dụng trong khuôn khổ toán học mà sử dụng nhiều các mẫu biểu, mẫu variadic, và Lập trình meta để thực hiện nội tuyến hung hăng. Giả sử bạn muốn xác định toán tử lấy sản phẩm của một số biểu thức, mỗi biểu thức có thể được chuyển qua tham chiếu, tham chiếu đến const hoặc tham chiếu rvalue. (Trong trường hợp của tôi, các biểu thức là các bảng xác suất có điều kiện và hoạt động là sản phẩm yếu tố, nhưng giống như phép nhân ma trận cũng phù hợp.)

Bạn cần truy cập dữ liệu được cung cấp bởi mỗi biểu thức để đánh giá sản phẩm . Do đó, bạn phải di chuyển các biểu thức được truyền dưới dạng tham chiếu rvalue, sao chép các biểu thức được chuyển bởi tham chiếu đến const và lấy các địa chỉ của các biểu thức được truyền theo tham chiếu. Sử dụng kỹ thuật tôi mô tả ở trên bây giờ đặt ra một số lợi ích.

1. Các biểu thức khác có thể sử dụng cú pháp đồng nhất để truy cập các phần tử dữ liệu từ biểu thức này, vì tất cả công việc lập trình siêu hạng nặng được thực hiện trước đó.
2. Chúng tôi có thể tiết kiệm dung lượng ngăn xếp bằng cách nhóm các con trỏ lại với nhau và lưu trữ các biểu thức lớn hơn vào cuối bộ tuple.
3. Việc triển khai một số loại truy vấn nhất định trở nên dễ dàng hơn nhiều (ví dụ: kiểm tra xem có bất kỳ con trỏ nào được lưu trữ trong bí danh tuple của một con trỏ đã cho) hay không.

Cảm ơn bạn rất nhiều vì đã giúp đỡ!

Answer 1

Chúc mừng ngày 4 tháng 7! OK ở đây bạn đi.

Nó chỉ ra rằng g++-4.7 là khá awesome lúc iniling và tạo ra mã máy giống hệt nhau theo thử nghiệm của tôi (hướng dẫn để tái tạo các kết quả dưới mã).

#include <iostream> 
#include <tuple> 
#include <typeinfo> 
#include <type_traits> 

template <class... Args> 
struct sequence 
{ 
    typedef std::tuple<Args...> tuple_type; 
}; 

template <class U, class V> 
struct sequence_cat; 

template <class... U, class... V> 
struct sequence_cat<sequence<U...>, sequence<V...>> 
{ 
    typedef sequence<U..., V...> type; 
}; 

template <class... V> 
struct sequence_cat<void, sequence<V...>> 
{ 
    typedef sequence<V...> type; 
}; 

template <class... U> 
struct sequence_cat<sequence<U...>, void> 
{ 
    typedef sequence<U...> type; 
}; 

template <> 
struct sequence_cat<void, void> 
{ 
    typedef void type; 
}; 

template <class T> 
struct undecorate 
{ 
    typedef typename std::remove_reference<T>::type noref_type; 
    typedef typename std::remove_pointer<noref_type>::type noptr_type; 
    typedef typename std::remove_cv<noptr_type>::type type; 
}; 

template <class T> 
struct deduce_storage_type 
{ 
    typedef T type; 
}; 

template <class T> 
struct deduce_storage_type<T&> 
{ 
    typedef T* type; 
}; 

template <class T> 
struct deduce_storage_type<const T&> 
{ 
    typedef T type; 
}; 

template <class T> 
struct deduce_storage_type<T&&> 
{ 
    typedef T type; 
}; 

template <class T, class... Args> 
struct filter_type; 

template <class T, class Arg, class... Args> 
struct filter_type<T, Arg, Args...> 
{ 
    static constexpr bool pred = 
    std::is_same<typename undecorate<Arg>::type, T>::value; 

    typedef typename deduce_storage_type<Arg>::type storage_type; 

    typedef typename 
    std::conditional< 
     pred, 
     typename sequence_cat< 
      sequence<storage_type>, 
      typename filter_type<T, Args...>::type 
     >::type, 
     typename filter_type<T, Args...>::type 
    >::type type;  
}; 

template <class T, class Arg> 
struct filter_type<T, Arg> 
{ 
    static constexpr bool pred = 
    std::is_same<typename undecorate<Arg>::type, T>::value; 

    typedef typename deduce_storage_type<Arg>::type storage_type; 

    typedef typename 
    std::conditional<pred, sequence<storage_type>, void>::type 
    type; 
}; 

template <class... Args> 
struct deduce_sequence_type 
{ 
    typedef typename filter_type<char, Args...>::type char_sequence; 
    typedef typename filter_type<int, Args...>::type int_sequence; 
    typedef typename filter_type<float, Args...>::type float_sequence; 

    typedef typename 
    sequence_cat< 
     char_sequence, 
     typename sequence_cat< 
      int_sequence, 
      float_sequence 
     >::type 
    >::type type; 
}; 

template <class T> 
struct get_storage_type 
{ 
    static T apply(T t) { return t; } 
}; 

template <class T> 
struct get_storage_type<T&> 
{ 
    static T* apply(T& t) { return &t; } 
}; 

template <class T> 
struct get_storage_type<const T&> 
{ 
    static T apply(const T& t) { return t; } 
}; 

template <class T> 
struct get_storage_type<T&&> 
{ 
    static T&& apply(T&& t) { return std::move(t); } 
}; 

template <class T, class Arg> 
struct equals_undecorated_type 
{ 
    static constexpr bool value = 
    std::is_same<typename undecorate<Arg>::type, T>::value; 
}; 

template <bool Pred, bool IsNextVoid, class T, class... Args> 
struct filter_parameter_impl; 

template <class T, class Arg1, class Arg2, class... Args> 
struct filter_parameter_impl<false, false, T, Arg1, Arg2, Args...> 
{ 
    typedef typename filter_type<T, Arg2, Args...>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    static constexpr bool pred = equals_undecorated_type<T, Arg2>::value; 

    static constexpr bool is_next_next_void = 
    std::is_same<typename filter_type<T, Args...>::type, void>::value; 

    static tuple_type apply(Arg1&&, Arg2&& arg2, Args&&... args) 
    { 
     return filter_parameter_impl< 
      pred, is_next_next_void, T, Arg2, Args... 
     >::apply(
      std::forward<Arg2>(arg2), 
      std::forward<Args>(args)... 
     ); 
    } 
}; 

template <class T, class Arg1, class Arg2, class... Args> 
struct filter_parameter_impl<false, true, T, Arg1, Arg2, Args...> 
{ 
    static void apply(Arg1&&, Arg2&&, Args&&...) {} 
}; 

template <class T, class Arg1, class Arg2, class... Args> 
struct filter_parameter_impl<true, false, T, Arg1, Arg2, Args...> 
{ 
    typedef typename 
    filter_type<T, Arg1, Arg2, Args...>::type 
    sequence_type; 

    typedef typename sequence_type::tuple_type tuple_type; 

    static constexpr bool pred = equals_undecorated_type<T, Arg2>::value; 

    static constexpr bool is_next_next_void = 
    std::is_same<typename filter_type<T, Args...>::type, void>::value; 

    static tuple_type apply(Arg1&& arg1, Arg2&& arg2, Args&&... args) 
    { 
     return std::tuple_cat(
      std::make_tuple(get_storage_type<Arg1>::apply(arg1)), 
      filter_parameter_impl< 
       pred, is_next_next_void, T, Arg2, Args... 
      >::apply(
       std::forward<Arg2>(arg2), 
       std::forward<Args>(args)... 
      ) 
     ); 
    } 
}; 

template <class T, class Arg1, class Arg2, class... Args> 
struct filter_parameter_impl<true, true, T, Arg1, Arg2, Args...> 
{ 
    typedef typename filter_type<T, Arg1>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    static tuple_type apply(Arg1&& arg1, Arg2&&, Args&&...) 
    { 
     return std::make_tuple(get_storage_type<Arg1>::apply(
      std::forward<Arg1>(arg1) 
     )); 
    } 
}; 

template <class T, class Arg1, class Arg2> 
struct filter_parameter_impl<false, false, T, Arg1, Arg2> 
{ 
    typedef typename filter_type<T, Arg2>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    static tuple_type apply(Arg1&&, Arg2&& arg2) 
    { 
     return std::make_tuple(get_storage_type<Arg2>::apply(
      std::forward<Arg2>(arg2) 
     )); 
    } 
}; 

template <class T, class Arg1, class Arg2> 
struct filter_parameter_impl<false, true, T, Arg1, Arg2> 
{ 
    static void apply(Arg1&&, Arg2&&) {} 
}; 

template <class T, class Arg1, class Arg2> 
struct filter_parameter_impl<true, false, T, Arg1, Arg2> 
{ 
    typedef typename filter_type<T, Arg1>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    static tuple_type apply(Arg1&& arg1, Arg2&& arg2) 
    { 
     return std::make_tuple(
      get_storage_type<Arg1>::apply(std::forward<Arg1>(arg1)), 
      get_storage_type<Arg2>::apply(std::forward<Arg2>(arg2)) 
     ); 
    } 
}; 

template <class T, class Arg1, class Arg2> 
struct filter_parameter_impl<true, true, T, Arg1, Arg2> 
{ 
    typedef typename filter_type<T, Arg1, Arg2>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    static tuple_type apply(Arg1&& arg1, Arg2&&) 
    { 
     return std::make_tuple(
      get_storage_type<Arg1>::apply(std::forward<Arg1>(arg1)) 
     ); 
    } 
}; 

template <class T, class... Args> 
struct filter_parameter; 

template <class T, class Arg, class... Args> 
struct filter_parameter<T, Arg, Args...> 
{ 
    typedef typename filter_type<T, Arg, Args...>::type sequence_type; 

    typedef typename std::conditional< 
     std::is_same<sequence_type, void>::value, 
     void, 
     typename sequence_type::tuple_type 
    >::type tuple_type; 

    static constexpr bool pred = equals_undecorated_type<T, Arg>::value; 

    static constexpr bool is_next_void = 
    std::is_same<typename filter_type<T, Args...>::type, void>::value; 

    static tuple_type apply(Arg&& arg, Args&&... args) 
    { 
     return filter_parameter_impl< 
      pred, is_next_void, T, Arg, Args... 
     >::apply(std::forward<Arg>(arg), std::forward<Args>(args)...); 
    } 
}; 

template <bool Is1Void, bool Is2Void, bool Is3Void, class... Args> 
struct get_tuple_impl; 

template <class... Args> 
struct get_tuple_impl<false, false, false, Args...> 
{ 
    typedef typename deduce_sequence_type<Args...>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    static tuple_type apply(Args&&... args) 
    { 
     return std::tuple_cat(
      filter_parameter<char, Args...>::apply(
       std::forward<Args>(args)... 
      ), 
      filter_parameter<int, Args...>::apply(
       std::forward<Args>(args)... 
      ), 
      filter_parameter<float, Args...>::apply(
       std::forward<Args>(args)... 
      ) 
     ); 
    } 
}; 

template <class... Args> 
struct get_tuple 
{ 
    typedef typename deduce_sequence_type<Args...>::type sequence_type; 

    typedef typename std::conditional< 
     std::is_same<sequence_type, void>::value, 
     void, 
     typename sequence_type::tuple_type 
    >::type tuple_type; 

    static constexpr bool is1void = 
    std::is_same<typename filter_type<char, Args...>::type, void>::value; 
    static constexpr bool is2void = 
    std::is_same<typename filter_type<int, Args...>::type, void>::value; 
    static constexpr bool is3void = 
    std::is_same<typename filter_type<float, Args...>::type, void>::value; 

    static tuple_type apply(Args&&... args) 
    { 
     return get_tuple_impl<is1void, is2void, is3void, Args...>:: 
      apply(std::forward<Args>(args)...); 
    } 
}; 

template <class... Args> 
struct foo 
{ 
    typedef typename deduce_sequence_type<Args...>::type sequence_type; 
    typedef typename sequence_type::tuple_type tuple_type; 

    tuple_type t_; 

    foo(Args&&... args) : t_{} {} 
}; 

int main() 
{ 
    char a = 5; 
    const int b = 6; 
    float c = 7; 
    int d = 8; 
    float e = 9; 
    char f = 10; 

    auto x = get_tuple<char&, const int&, float&, int&, float&&, char&>:: 
     apply(a, b, c, d, std::move(e), f); 
    //std::tuple<char*, char*, int, int*, float*, float> x{&a, &f, b, &d, &c, std::move(f)}; 

    std::cout << typeid(x).name() << std::endl; 

    return 0; 
} 

Để tái tạo kết quả, hãy làm như sau (giả sử bạn đã cài đặt g ++ - 4.7).

g++ -std=c++11 -Wall -Ofast -march=native variadic_reorder.cpp -S -o with_templates.s 
// Comment out the line in main, and comment the line containing auto x, as well as the line below it. 
g++ -std=c++11 -Wall -Ofast -march=native variadic_reorder.cpp -S -o without_templates.s 
vimdiff with_templates.s without_templates.s 

Sự khác biệt duy nhất tôi nhận thấy là những thứ như tên nhãn; nếu không, mã máy được tạo giống hệt nhau.

Chỉnh sửa 1 Tôi sẽ chấp nhận câu trả lời của riêng mình cho đến khi người khác đăng nội dung nào đó tao nhã hơn những gì tôi có.

Answer 2

Tôi không có thời gian để thử nghiệm điều này, nhưng nếu trình biên dịch của bạn tạo quá nhiều chuyển động khi tính toán đối số được chuyển tiếp, tôi khuyên bạn nên chuyển tiếp qua std::forward_as_tuple.Tuple là một cấu trúc dữ liệu với một bố trí cụ thể, và xây dựng nó khuyến khích trình biên dịch đưa mọi thứ vào bộ nhớ cùng một lúc, theo thứ tự bạn muốn.

Mặt khác, ít có khả năng quảng bá đối số cho thanh ghi và bỏ qua ngăn xếp cho các hàm đơn giản. Và không có gì thực sự được đảm bảo miễn là tuple chỉ được sử dụng như một giá trị thuần túy (không có tham chiếu), bởi vì theo quy tắc as-if không cần các thành viên của nó có bất kỳ địa chỉ nào.

Chúng tôi có thể tiết kiệm dung lượng ngăn xếp bằng cách nhóm các con trỏ lại với nhau và lưu trữ các biểu thức lớn hơn vào cuối bộ tuple.

Tham chiếu giá trị được thực hiện dưới dạng con trỏ bởi ABI mà bạn đã chỉ định để nhóm chúng làm giá trị dữ liệu. Tham chiếu Rvalue phải được xử lý giống như tham chiếu giá trị lvalue nếu bạn muốn tuân theo ngữ nghĩa đi qua. (Tôi cho rằng bạn sẽ chỉ di chuyển các loại lớp). Vì vậy, vấn đề sắp xếp hơi phức tạp hơn so với đã nêu, bởi vì bạn muốn sắp xếp các tham số thành các giá trị và các loại con trỏ, sau đó sắp xếp chúng theo loại cơ sở.

Đối với thuật toán sắp xếp, tôi sẽ thử popping từ gói đầu vào và đẩy tới một tập hợp các bộ dữ liệu đầu ra, kiểu hàng đợi và sau đó chạm vào bộ đầu ra với std::tuple_cat. Đó sẽ là cách đơn giản nhất để thực hiện, ổn định và nên nhấn tối ưu hóa các trường hợp phổ biến của trình biên dịch. Không thực hiện một thuật toán nhằm chạy tại chỗ trong bộ nhớ vì TMP không hoạt động như thế.

Để dịch kết quả sắp xếp thành hàm cho phép tham số vào đối số là forward_as_tuple, tôi không chắc lắm. Có thể bạn sẽ phải đối phó với các chỉ mục.

Bạn muốn chắc chắn rằng lợi ích có giá trị trước khi cam kết tất cả điều này.