紧凑简单 std::tuple 反演

Question

我是元编程的新手。我看过其他类似的问题，但其中 none 做了我真正想要的。

这是我尝试反转 std::tuple 的尝试。我遇到的主要问题是反转输入元组中的数据。

反转索引的逻辑令人不快，我无法从这个阶段继续。

目前的代码：

//===========================================================!
// type inversion of a tuple

template < typename Tuple, typename T >
struct tuple_push;

template < typename T, typename ... Args >
struct tuple_push<std::tuple<Args...>, T>
{
    typedef std::tuple<Args..., T> type;
};

template < typename Tuple >
struct tuple_reverse;

template < typename T, typename ... Args >
struct tuple_reverse<std::tuple<T, Args...>>
{
    typedef typename tuple_push<typename tuple_reverse<std::tuple<Args...>>::type, T>::type type;
};

template < >
struct tuple_reverse<std::tuple<>>
{
    typedef std::tuple<> type;
};
//===========================================================!


template <typename First, typename ...Tails>
auto inverse(std::tuple<First, Tails...> & data) 
-> decltype(tuple_reverse<std::tuple<First,Tails...>>::type)
    {
        using reverse_tup = tuple_reverse<std::tuple<First, Tails...>>::type;
        static_assert(false, "Confused!")
        return reverse_tup();
    }

期待紧凑简单的解决方案。

Answer 1

这是使用 C++14 的可能解决方案：

template <typename T, std::size_t... indices>
auto invert(T &&tuple, std::index_sequence<indices...>) {
  // Using decay_t as the argument must be a tuple, and this shortens the code
  using tuple_t = std::decay_t<T>;
  constexpr auto tuple_size = std::tuple_size<tuple_t>{};
  return std::tuple<std::tuple_element_t<tuple_size - indices - 1, tuple_t>...>(
      std::get<tuple_size - indices - 1>(std::forward<T>(tuple))...);
}

template <typename T>
auto invert(T &&tuple) {
  return invert(std::forward<T>(tuple),
                std::make_index_sequence<std::tuple_size<std::decay_t<T>>{}>());
}

Demo。对于 C++11，可以执行相同的过程，但必须提供像 make_index_list 这样的辅助模板。

Answer 2

The logic to inverse the indices is not palatable and I could not proceed from this stage.

我认为你指的是使用 std::index_sequence (C++14) 的解决方案，等等，such as Jonathan Wakeley's'，而且@Columbo 同样的解决方案也会令人不快，即使它这是一个 C++11 的。

可能你不喜欢 "the logic to inverse the indices" 因为你认为有不必要的运行时间成本。它没有运行时间成本。它在编译时执行。

更有可能的是，您知道这一点，但只是认为这种解决方案风格不够优雅，而不是尽可能简单或紧凑。

嗯，你知道这个用于反转序列的经典递归算法S：依次取S项并将它们推到另一个最初为空的序列 S' 的前面。最后，S' 是 S.

的倒数

没有比这更简单的了，这里是一个紧凑的 C++11 实现，适用于元组。假定 header "tuple_plus.h" 提供您现有的 meta-function tuple_reverse 定义及其先决条件。

#include "tuple_plus.h"

namespace detail {

template <size_t I, class Wip, typename ...Ts>
Wip
inverse(std::tuple<Ts...> const & model, Wip && wip = std::tuple<>(),
            typename std::enable_if<(I >= sizeof...(Ts))>::type * = nullptr)
{
    return wip;
}

template <size_t I, class Wip, typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & model, Wip && wip = std::tuple<>(),
            typename std::enable_if<(I < sizeof...(Ts))>::type * = nullptr)
{
    return
    inverse<I + 1>(model,std::tuple_cat(std::make_tuple(std::get<I>(model)),wip));
}

} // namespace detail

template<typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & tup)
{
    return detail::inverse<0,std::tuple<>>(tup);
}

当然我们不能只循环遍历元组元素，因为它们只能通过std::get<I>(tup)访问，常数索引I。因此，实现不可能像 std::vector<T> 那样紧凑。我们必须在索引常量上遵循通常的 template-meta-recursion 模式。我们需要一对 SFINAE 重载，当 I 具有限制值（I >= sizeof...(Ts)）时编译器选择一个，而当 I 具有任何其他值时另一个被编译器选择值（I < sizeof...(Ts)）。然后我们需要实现你真正想要的函数模板

template<typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & tup);

作为此实现的包装器来初始化和隐藏递归参数。但是有了这些不可避免的安排，这是经典的 sequence-reversing 算法，应用于 C++11 中的元组，没有任何 index_sequence 拐杖。

N.B. 该声明与您 post:-

中的声明略有不同

它将接受长度为 0 的元组，std::tuple<>，以及更长的元组。这个更好，因为您对 return-type tuple_reverse<Tuple>::type 的通用定义专用于 std::tuple<>。因此，只要 return-type是。
参数作为 const & 传递，而不仅仅是 &。您不会修改输入元组，因此该函数应接受 std::tuple<Ts...> const 个参数。

现在我将解释为什么这个优雅的解决方案是 non-starter，与其余的解决方案相比在 index_sequence 设备上。

这是一个程序，您可以使用它来测试 tuple-reversing 解决方案满足所需的接口。

#include "tuple_plus.h"
#include <type_traits>

///////////////////////////////////////////////////
//
// Paste your implementation here
//
///////////////////////////////////////////////////

///////////////////////////////////////////////////
// Testing it...

#include <iostream>

using namespace std;

struct item
{
    static unsigned ctor_count;
    static unsigned copy_count;
    item()
    : id(ctor_count++) {}
    item(item const & other)
    : id(other.id) {
        ++copy_count;
    }
    item & operator=(item const & other) {
        id = other.id;
        ++copy_count;
        return *this;
    }
    static void clear() {
        ctor_count = copy_count = 0;
    }
    unsigned id;
};

unsigned item::ctor_count;
unsigned item::copy_count;

ostream & operator<<(ostream & out, item const & e)
{
    return out << "item #" << e.id;
}

template<unsigned I = 0, typename ...Ts>
typename enable_if<(I >= sizeof...(Ts))>::type
tuple_print(tuple<Ts...> const &)
{
    cout << "\n";
}

template<unsigned I = 0, typename ...Ts>
typename enable_if<(I < sizeof...(Ts))>::type
tuple_print(tuple<Ts...> const & tup)
{
    cout << '[' << get<I>(tup) << "] ";
    tuple_print<I + 1>(tup);
}

template<unsigned I>
void test()
{
    auto tup_tup =
    tuple<
        tuple<>,
        tuple<item>,
        tuple<item,item>,
        tuple<item,item,item>,
        tuple<item,item,item,item>,
        tuple<item,item,item,item,item>,
        tuple<item,item,item,item,item,item>>();

    item::clear();
    auto const & tup = get<I>(tup_tup);
    cout << "In..." << endl;
    tuple_print(tup);
    cout << "Out..." << endl;
    tuple_print(inverse(tup));
    cout << "To invert a " << I << "-element tuple\n"
    << "I copied " << item::copy_count << " elements\n";
}

int main()
{
    test<0>(),test<1>(),test<2>(),test<3>(),test<4>(),test<5>(),test<6>();
    return 0;
}

在以下位置剪切并粘贴经典解决方案：

    // Paste your implementation here

然后编译，-std=c++11和运行。输出使用经典算法长度为 0 到 6 的样本元组，并在每种情况下向您展示 a) 该算法确实反转元组和 b) 反转该元组的成本，以 tuple-element 复制操作数衡量。

In...

Out...

To invert a 0-element tuple
I copied 0 elements
In...
[item #20]
Out...
[item #20]
To invert a 1-element tuple
I copied 3 elements
In...
[item #19] [item #18]
Out...
[item #18] [item #19]
To invert a 2-element tuple
I copied 7 elements
In...
[item #17] [item #16] [item #15]
Out...
[item #15] [item #16] [item #17]
To invert a 3-element tuple
I copied 12 elements
In...
[item #14] [item #13] [item #12] [item #11]
Out...
[item #11] [item #12] [item #13] [item #14]
To invert a 4-element tuple
I copied 18 elements
In...
[item #10] [item #9] [item #8] [item #7] [item #6]
Out...
[item #6] [item #7] [item #8] [item #9] [item #10]
To invert a 5-element tuple
I copied 25 elements
In...
[item #5] [item #4] [item #3] [item #2] [item #1] [item #0]
Out...
[item #0] [item #1] [item #2] [item #3] [item #4] [item #5]
To invert a 6-element tuple
I copied 33 elements

调查成本顺序：

0, 3, 7, 12, 18, 25, 33,...

你可以确信它是由函数给出的：

Cost(n) = (n squared + 5n) / 2

所以这个算法的成本是 tuple-size 的二次方。

如果你想练习，你可以为元组找出另一个的实现用于反转序列的股票递归算法。不那么简单或像这个一样紧凑，它是这样的：交换第一个和最后一个元素序列，在你已经颠倒了两者之间的序列之后。成本可能会更低，但仍将是二次方的。

这令人苦恼，因为众所周知，颠倒事物的顺序是一个线性问题：例如，经典算法的明显 C++ 改编反转 std::vector 将有 Cost(n) = 4n.

这个众所周知的事实背后的隐含假设是序列是 Container<T>，对于某些 Container 和 T；所以逆向算法是自由的在一个位置修改包含的序列而不在其他位置修改它，所有同时还有 Container<T>.

但是反转 std::tuple 的问题在于 std::tuple<....,A,....,B,....> 与 type 不同 std::tuple<....,B,....,A,....>，并来自 std::tuple<....,A,....>。所以你不能实际上通过 推另一个元素来反转 std::tuple tup 前面tup；或交换 A 和 B 在 tup , 等等。要在 tup 上模拟任何此类 member-wise 操作，您必须构建一个整体不同类型的新元组，复制所有 tup 的元素，也许更多。要拿起香蕉，你必须举起整个大猩猩。

考虑到这一点，将@Columbo 的实现粘贴到测试程序中。你会需要将他的代码中的 invert 更改为 inverse。编译 std=c++14 和运行。（您需要 gcc 4.9 或 clang 3.5 才能使用此选项，而 gcc 4.9 将发出一个不重要的 compiler-warning).

现在输出是：

In...

Out...

To invert a 0-element tuple
I copied 0 elements
In...
[item #20]
Out...
[item #20]
To invert a 1-element tuple
I copied 1 elements
In...
[item #19] [item #18]
Out...
[item #18] [item #19]
To invert a 2-element tuple
I copied 2 elements
In...
[item #17] [item #16] [item #15]
Out...
[item #15] [item #16] [item #17]
To invert a 3-element tuple
I copied 3 elements
In...
[item #14] [item #13] [item #12] [item #11]
Out...
[item #11] [item #12] [item #13] [item #14]
To invert a 4-element tuple
I copied 4 elements
In...
[item #10] [item #9] [item #8] [item #7] [item #6]
Out...
[item #6] [item #7] [item #8] [item #9] [item #10]
To invert a 5-element tuple
I copied 5 elements
In...
[item #5] [item #4] [item #3] [item #2] [item #1] [item #0]
Out...
[item #0] [item #1] [item #2] [item #3] [item #4] [item #5]
To invert a 6-element tuple
I copied 6 elements

成本的顺序是0,1,2,3,4,5,6,...。对于此解决方案，Cost(n) = n：它是最有效的。

index_sequence设备的使用在这个解决方案中是本质其最佳效率。如果要避免二次运行时间成本通过模拟 member-wise 操作来反转 tup，唯一的选择是简单地 construct 反转元组，用元素初始化已经在编译时从 tup 中的对应项映射到映射：

Index I -> tuple_size - I - 1

在运行的时候，除了逆元组的构造，什么也没有发生，一存在就完成。

但是要执行该映射，在编译时，您必须拥有一个索引的列表 tup 的元素，在编译时。这就是 index_sequence 设备交付。

如果 C++14 绝对是 off-limits，您可能会接受享元 C++11 的替代品 std::index_sequencecourtesty of Andy Prowl

有了这个，你可以有以下解决方案：

namespace detail {

// This is...

template<int... Is>
struct seq { };

template<int N, int... Is>
struct gen_seq : gen_seq<N - 1, N - 1, Is...> { };

template<int... Is>
struct gen_seq<0, Is...> : seq<Is...> {};

// ... the flyweight index_sequence apparatus.
// You can put it in a header.

template<typename Tuple, int ...Is>
typename tuple_reverse<typename std::decay<Tuple>::type>::type
invert(Tuple && tup, seq<Is...>)
{
    return
        std::make_tuple(
            std::get<std::tuple_size<
                typename std::decay<Tuple>::type>::value - Is - 1>
                    (std::forward<Tuple>(tup))...);
}

} //namespace detail

template<typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & tup)
{
    return detail::invert(tup,detail::gen_seq<(sizeof...(Ts))>());
}

在测试程序中，其输出与@Columbo 的相同。

道德：std::index_sequence（或更一般地说，std::integer_sequence）是用于 C++ 中有效 TMP 的极其优雅和基本的工具。这就是它在 C++14 标准库中的原因。（顺便说一句，乔纳森韦克利是它的作者`)

紧凑简单 std::tuple 反演

Compact and Simple std::tuple inversion

c++

template-meta-programming

c++11