正确对齐内存模板,参数顺序不变

Properly align in-memory template, invariant of order of parameters

看看这个模板。

template < typename T1, typename T2, typename T3 >
struct Alignement {
    T1 first;
    T2 second;
    T3 third;
};

int main() {
    Alignement<char, int, double> a1;
    Alignement<char, double, int> a2;
    assert( sizeof(a1) < sizeof(a2) );
    return 0;
}

显然断言成立。在这种情况下,次优排序会导致内存使用量增加 50%。

我的问题是,除了善意地要求用户自己处理它(如果他不知道,这会让他遇到同样的问题)之外,有什么方法可以解决它并在模板结构中正确排序类型他的类型的大小)?

我的想法是在编译时使用宏或 TMP 动态生成最佳排序,但我对这些技术没有适当的了解。或者也许一大群部分专业化的模板可以完成这项工作?

关键方面是为客户端保留 AlignedObject.first 语法。

对于我的具体情况,我正在寻找恰好 3 个参数(3!可能的排序)的解决方案,但通用解决方案(包括可变长度模板)会很有趣。

#include <iostream>
#include <type_traits>

template <typename... O>
struct SizeOrder;

template <typename T1, typename T2, typename... Rest>
struct SizeOrder<T1, T2, Rest...> {
    using type = typename std::conditional<(T1::size::value > T2::size::value || (T1::size::value == T2::size::value && T1::order::value < T2::order::value)), typename SizeOrder<T2, Rest...>::type, int>::type;
};

template <typename T1, typename T2>
struct SizeOrder<T1, T2> {
    using type = typename std::conditional<(T1::size::value > T2::size::value || (T1::size::value == T2::size::value && T1::order::value < T2::order::value)), void, int>::type;
};

template <typename... T>
using Order = typename SizeOrder<T...>::type;

template <typename T1, int T2>
struct DeclarationOrder {
    using size = typename std::alignment_of<T1>;
    using order = typename std::integral_constant<int, T2>;
};

template <typename A, typename B, typename C, typename = void>
struct Alignement;

#define AO DeclarationOrder<A,1>
#define BO DeclarationOrder<B,2>
#define CO DeclarationOrder<C,3>

template <typename A, typename B, typename C>
struct Alignement<A, B, C, Order<AO, BO, CO>> {
    A first;
    B second;
    C third;
};

template <typename A, typename B, typename C>
struct Alignement<A, B, C, Order<AO, CO, BO>> {
    A first;
    C third;
    B second;
};

template <typename A, typename B, typename C>
struct Alignement<A, B, C, Order<BO, AO, CO>> {
    B second;
    A first;
    C third;
};

template <typename A, typename B, typename C>
struct Alignement<A, B, C, Order<BO, CO, AO>> {
    B second;
    C third;
    A first;
};

template <typename A, typename B, typename C>
struct Alignement<A, B, C, Order<CO, AO, BO>> {
    C third;
    A first;
    B second;
};

template <typename A, typename B, typename C>
struct Alignement<A, B, C, Order<CO, BO, AO>> {
    C third;
    B second;
    A first;
};


int main() {
    Alignement<char, int, double> t1;
    std::cout << sizeof(t1) << std::endl << sizeof(t1.first) << std::endl << sizeof(t1.second) << std::endl << std::endl;

    Alignement<char, double, int> t2;
    std::cout << sizeof(t2) << std::endl << sizeof(t2.first) << std::endl << sizeof(t2.second) << std::endl << std::endl;

    return 0;
}

编辑:添加了一个 Order<> 模板以递归检查任意数量参数的大小顺序,并扩展了 Aligenment 以容纳 3 个变量。

EDIT2:当使用相同大小的类型时,模板推导失败,所以我更改了 SizeOrder template 以采用 DeclarationOrder 模板来消除歧义,因为 [=14] 有 2 个可能的顺序=]

通过对 godbolt 的一些测试来找出宏部分,我们可以将整个事情浓缩为这个。

#include <iostream>
#include <type_traits>

template <typename... O>
struct SizeOrder;

template <typename T1, typename T2, typename... Rest>
struct SizeOrder<T1, T2, Rest...> {
    using type = typename std::conditional<(T1::size::value > T2::size::value || (T1::size::value == T2::size::value && T1::order::value < T2::order::value)), typename SizeOrder<T2, Rest...>::type, int>::type;
};

template <typename T1, typename T2>
struct SizeOrder<T1, T2> {
    using type = typename std::conditional<(T1::size::value > T2::size::value || (T1::size::value == T2::size::value && T1::order::value < T2::order::value)), void, int>::type;
};

template <typename... T>
using Order = typename SizeOrder<T...>::type;

template <typename T1, int T2>
struct DeclarationOrder {
    using size = typename std::alignment_of<T1>;
    using order = typename std::integral_constant<int, T2>;
};

template <typename A, typename B, typename C, typename = void>
struct Alignement;

#define AO DeclarationOrder<A,1>
#define BO DeclarationOrder<B,2>
#define CO DeclarationOrder<C,3>

#define Aname first
#define Bname second
#define Cname third

#define MAKE_SPECIALIZATION(FIRST, SECOND, THIRD) \
template <typename A, typename B, typename C> \
struct Alignement<A, B, C, Order<FIRST ## O, SECOND ## O,  THIRD ## O>> { \
    FIRST FIRST ## name; \
    SECOND SECOND ## name; \
    THIRD THIRD ## name; \
};

MAKE_SPECIALIZATION(A,B,C)
MAKE_SPECIALIZATION(A,C,B)
MAKE_SPECIALIZATION(B,A,C)
MAKE_SPECIALIZATION(B,C,A)
MAKE_SPECIALIZATION(C,A,B)
MAKE_SPECIALIZATION(C,B,A)


int main() {
    Alignement<char, int, double> t1;
    std::cout << sizeof(t1) << std::endl << sizeof(t1.first) << std::endl << sizeof(t1.second) << std::endl << std::endl;

    Alignement<char, double, int> t2;
    std::cout << sizeof(t2) << std::endl << sizeof(t2.first) << std::endl << sizeof(t2.second) << std::endl << std::endl;

    return 0;
}

要将其扩展到 4、5 或 6 个变量,我们需要更新 struct Alignement 以在 template = void 之前添加 template D。然后我们 #define DO DeclarationOrder<D,4>#define Dname fourth.

然后我们向 MAKE_SPECIALIZATION 宏添加 DFOURTH 并定义所有(16?)可能的布局。

远非干净利落,但可行。

For my specific case, I'm looking for solution for exactly 3 parameters (3! possible orderings) but general solution (including variadic-length-templates) would be interesting to see.

我提出了一个通用的解决方案:可变类型排序器和使用它的可变类型 Alignement

根据 Peter 的建议,想法是对类型进行排序,将较大的类型放在首位。

我使用 C++17,因为新的模板折叠允许我使用 C++11,因为 OP 必须使用仅兼容 C++11 的编译器来制作 非常简单 一种类型特征,说明列表的第一种类型是否更大(根据 sizeof())。我维护,评论,原来的 C++17 版本

// iftb = is first type bigger ?

// original C++17 version
//
// template <typename T0, typename ... Ts>
// struct iftb
//    : public std::integral_constant<bool,((sizeof(Ts) <= sizeof(T0)) && ...)>
//  { };

template <typename ...>
struct iftb;

template <typename T0>
struct iftb<T0> : public std::true_type
 { };

template <typename T0, typename T1, typename ... Ts>
struct iftb<T0, T1, Ts...>
   : public std::integral_constant<bool,
        (sizeof(T1) <= sizeof(T0)) && iftb<T0, Ts...>::value>
 { };

现在有一个类型特征可以知道类型容器是否包含有序类型列表

// ifctb = is first contained type bigger ?
template <typename>
struct ifctb;

template <template <typename ...> class C, typename ... Tc>
struct ifctb<C<Tc...>> : public iftb<Tc...>
 { };

现在类型排序器很容易写了(但效率不是特别高;抱歉)

// to = type orderer
template <typename, typename Cd, bool = ifctb<Cd>::value>
struct to;

template <template <typename...> class C, typename ... To,
          typename T0, typename ... Tu>
struct to<C<To...>, C<T0, Tu...>, true> : public to<C<To..., T0>, C<Tu...>>
 { };

template <template <typename...> class C, typename ... To,
          typename T0, typename ... Tu>
struct to<C<To...>, C<T0, Tu...>, false> : public to<C<To...>, C<Tu..., T0>>
 { };

template <template <typename...> class C, typename ... To, typename T>
struct to<C<To...>, C<T>, true>
 { using type = C<To..., T>; };

现在我提出一个索引包装器,它必须通过部分特化来定义 firstsecondthird(等等,如果你想扩展解决方案)

template <std::size_t, typename>
struct wrapper;

template <typename T>
struct wrapper<0U, T>
 { T first; };

template <typename T>
struct wrapper<1U, T>
 { T second; };

template <typename T>
struct wrapper<2U, T>
 { T third; };

我们需要仅从 C++14 开始可用的 std::index_sequencestd::make_index_sequence;但是 OP 必须在仅兼容 C++11 的编译器中编译此代码,因此我提出了一个简单的仿真 C++11 兼容

// std::index_sequence and std::make_index_sequence simplified emulators
template <std::size_t...>
struct indexSequence
 { using type = indexSequence; };

template <typename, typename>
struct concatSequences;

template <std::size_t... S1, std::size_t... S2>
struct concatSequences<indexSequence<S1...>, indexSequence<S2...>>
   : public indexSequence<S1..., ( sizeof...(S1) + S2 )...>
 { };

template <std::size_t N>
struct makeIndexSequenceH
   : public concatSequences<
               typename makeIndexSequenceH<(N>>1)>::type,
               typename makeIndexSequenceH<N-(N>>1)>::type>::type
 { };

template<>
struct makeIndexSequenceH<0> : public indexSequence<>
 { };

template<>
struct makeIndexSequenceH<1> : public indexSequence<0>
 { };

template <std::size_t N>
using makeIndexSequence = typename makeIndexSequenceH<N>::type;

std::tuplestd::index_sequencestd::make_index_sequenceindexSequencemakeIndexSequence的帮助下(C+ +11 兼容 std::index_sequencestd::make_index_sequence) 的简化仿真,我为 Alignement

添加了几个助手 structs
template <typename>
struct AlH2;

template <typename ... Ts>
struct AlH2<std::tuple<Ts...>> : public Ts...
 { };

template <typename...>
struct AlH1;

template <std::size_t ... Is, typename ... Ts>
struct AlH1<indexSequence<Is...>, Ts...>
   : public AlH2<typename to<std::tuple<>,
                             std::tuple<wrapper<Is, Ts>...>>::type>
 { };

现在Alignement可以写成

template <typename ... Ts>
struct Alignement
  : public AlH1<makeIndexSequence<sizeof...(Ts)>, Ts...>
 { };

以下是完整的(我记得:C++17) C++11 编译示例,其中包含一些 assert() 以验证正确的顺序。

#include <tuple>
#include <cassert>
#include <iostream>
#include <type_traits>

// std::index_sequence and std::make_index_sequence simplified emulators
template <std::size_t...>
struct indexSequence
 { using type = indexSequence; };

template <typename, typename>
struct concatSequences;

template <std::size_t... S1, std::size_t... S2>
struct concatSequences<indexSequence<S1...>, indexSequence<S2...>>
   : public indexSequence<S1..., ( sizeof...(S1) + S2 )...>
 { };

template <std::size_t N>
struct makeIndexSequenceH
   : public concatSequences<
               typename makeIndexSequenceH<(N>>1)>::type,
               typename makeIndexSequenceH<N-(N>>1)>::type>::type
 { };

template<>
struct makeIndexSequenceH<0> : public indexSequence<>
 { };

template<>
struct makeIndexSequenceH<1> : public indexSequence<0>
 { };

template <std::size_t N>
using makeIndexSequence = typename makeIndexSequenceH<N>::type;

// iftb = is first type bigger ?

// original C++17 version
//
// template <typename T0, typename ... Ts>
// struct iftb
//    : public std::integral_constant<bool,((sizeof(Ts) <= sizeof(T0)) && ...)>
//  { };

template <typename ...>
struct iftb;

template <typename T0>
struct iftb<T0> : public std::true_type
 { };

template <typename T0, typename T1, typename ... Ts>
struct iftb<T0, T1, Ts...>
   : public std::integral_constant<bool,
        (sizeof(T1) <= sizeof(T0)) && iftb<T0, Ts...>::value>
 { };

// ifctb = is first contained type bigger ?
template <typename>
struct ifctb;

template <template <typename ...> class C, typename ... Tc>
struct ifctb<C<Tc...>>
   : public iftb<Tc...>
 { };

// to = type orderer
template <typename, typename Cd, bool = ifctb<Cd>::value>
struct to;

template <template <typename...> class C, typename ... To,
          typename T0, typename ... Tu>
struct to<C<To...>, C<T0, Tu...>, true> : public to<C<To..., T0>, C<Tu...>>
 { };

template <template <typename...> class C, typename ... To,
          typename T0, typename ... Tu>
struct to<C<To...>, C<T0, Tu...>, false> : public to<C<To...>, C<Tu..., T0>>
 { };

template <template <typename...> class C, typename ... To, typename T>
struct to<C<To...>, C<T>, true>
 { using type = C<To..., T>; };

template <std::size_t, typename>
struct wrapper;

template <typename T>
struct wrapper<0U, T>
 { T first; };

template <typename T>
struct wrapper<1U, T>
 { T second; };

template <typename T>
struct wrapper<2U, T>
 { T third; };

template <typename>
struct AlH2;

template <typename ... Ts>
struct AlH2<std::tuple<Ts...>> : public Ts...
 { };

template <typename...>
struct AlH1;

template <std::size_t ... Is, typename ... Ts>
struct AlH1<indexSequence<Is...>, Ts...>
   : public AlH2<typename to<std::tuple<>,
                             std::tuple<wrapper<Is, Ts>...>>::type>
 { };

template <typename ... Ts>
struct Alignement
  : public AlH1<makeIndexSequence<sizeof...(Ts)>, Ts...>
 { };


int main ()
 {
   Alignement<char, int, long long>  a0;

   a0.first  = '0';
   a0.second = 1;
   a0.third  = 2LL;

   assert( (std::size_t)&a0.third < (std::size_t)&a0.first );
   assert( (std::size_t)&a0.third < (std::size_t)&a0.second );
   assert( (std::size_t)&a0.second < (std::size_t)&a0.first );
 }

-- 编辑 --

OP 询问

using your solution, if I want to achieve N-argument template class, I need to define N wrapper classes, each containing single field name for n-th argument. Different Alignement<>'s should have different field names == set of N wrappers for each of them. Any good idea for a macro (or template...) to achieve that?

对我来说,C 风格的宏是邪恶的提炼物(我不太了解它们),但是...

我提出的不是完整的解决方案;只有草稿。

如果你定义了下面的一组宏

#define WrpNum(wName, num, fName) \
   template <typename T>\
   struct wrapper_ ## wName <num, T> \
    { T fName; };

#define Foo_1(wName, tot, fName) \
   WrpNum(wName, tot-1U, fName)

#define Foo_2(wName, tot, fName, ...) \
   WrpNum(wName, tot-2U, fName) \
   Foo_1(wName, tot, __VA_ARGS__)

#define Foo_3(wName, tot, fName, ...) \
   WrpNum(wName, tot-3U, fName) \
   Foo_2(wName, tot, __VA_ARGS__)

// Foo_4(), Foo_5(), ...

#define Foo(wName, num, ...) \
   template <std::size_t, typename> \
   struct wrapper_ ## wName; \
   Foo_ ## num(wName, num, __VA_ARGS__)

您可以定义一个索引为 struct wrapper_wrp1 的模板,其中包含专业化和 first 成员在 wrapper_wrp1<0U, T> 专业化中, second 成员在 wrapper_wrp1<1U, T>,等等,调用

Foo(wrp1, 3, first, second, third)

请注意,您需要将专业化总数作为第二个参数。

也许可以做得更好(使用递归可变参数宏?)但是,坦率地说,我对宏不太感兴趣。

接到这个电话

Foo(wrp1, 3, first, second, third)

您可以(注意:未测试)修改 AlH1 特定的包装器结构 (wrapper_wrp1)

template <std::size_t ... Is, typename ... Ts>
struct AlH1<std::index_sequence<Is...>, Ts...>
   : public AlH2<typename to<std::tuple<>,
                             std::tuple<wrapper_wrp1<Is, Ts>...>>::type>
 { };

对于三成员情况(或任何其他固定数量),您可以使用 排序网络 来有效地减少专业化的数量(最多 log^2n 交换 AFAIR );在 C++11 中,类似于(未测试):

template <typename T,std::size_t> struct MemberSpec: std::alignment_of<T> {};

struct NoMember{};
template<typename, typename = NoMember> struct MemberDecl{};
template<typename T, typename B> struct MemberDecl<MemberSpec<T,0>,B>: B { T first; };
template<typename T, typename B> struct MemberDecl<MemberSpec<T,1>,B>: B { T second; };
template<typename T, typename B> struct MemberDecl<MemberSpec<T,2>,B>: B { T third; };

template<typename M0,typename M1,typename M2>
struct Alignement_01: std::conditional_t<( M0::value < M1::value ),
  MemberDecl<M0,MemberDecl<M1,MemberDecl<M2>>>, MemberDecl<M1,MemberDecl<M0,MemberDecl<M2>>> >{};

template<typename M0,typename M1,typename M2>
struct Alignement_02: std::conditional_t<( M0::value < M2::value ),
  Alignement_01<M0,M1,M2>, Alignement_01<M2,M1,M0> >{};

template<typename M0,typename M1,typename M2>
struct Alignement_12: std::conditional_t<( M1::value < M2::value ),
  Alignement_02<M0,M1,M2>, Alignement_02<M0,M2,M1> >{};

template<typename T0,typename T1,typename T2>
struct Alignement: Alignement_12<MemberSpec<T0,0>,MemberSpec<T1,1>,MemberSpec<T2,2>> {};

在上面,生成的 Alignment<T0,T1,T2> 是自 C++14 以来的标准布局(以及自 C++17 以来的聚合),只要 Tj 是。这意味着您需要放置断言来检查 C++14 之前的正确字段顺序和总大小。

编辑:我忘记了,即使在 >=C++14 中,基数 class 最多也可以有非静态数据成员;所以,我的 Alignment<> 几乎从来不是标准布局;无论如何,任何体面的编译器都应该以预期的方式放置字段,或者如果合适的话更好。考虑到您的目标是帮助编译器生成更优化的布局,这可能是可以接受的。

一般情况可以通过实现排序算法来解决,或者将上述算法概括为处理一些排序网络抽象;无论如何,你仍然需要专门化 MemberDecl 这样的东西来让你的数据成员命名正确(first,second,third,fourth,... whatever.