Компактная и простая инверсия std::tuple

Логика инвертирования индексов неприятна, и я не мог продолжить этот этап.

Я так понимаю, вы имеете в виду решения, использующие std::index_sequence (С++ 14) или подобные, например, Jonathan Wakeley's', и решение @Columbo в том же духе тоже было бы неприятным, даже если бы оно было на С++ 11.

Возможно, вам не нравится «логика инвертирования индексов», потому что вы считаете, что она требует ненужных затрат времени выполнения. У него нет затрат времени выполнения. Он выполняется во время компиляции.

Скорее всего, вы это знаете, но просто считаете такой стиль решения неэлегантным, не таким простым и компактным, как вам хотелось бы.

Ну, вы знаете этот классический рекурсивный алгоритм обращения последовательности S: последовательно брать элементы S и помещать их в начало другой, изначально пустой последовательности S'. В конце S' является обратным S.

Вряд ли может быть что-то проще, и вот компактная реализация C++11 применительно к кортежам. Предполагается, что заголовок "tuple_plus.h" предоставляет существующее определение метафункции 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>. Мы должны следовать обычному шаблону шаблонной мета-рекурсии для индексных констант. Нам нужна пара перегрузок 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);

в качестве оболочки вокруг этой реализации для инициализации и сокрытия параметров рекурсии. Но с этими неизбежными механизмами это классический алгоритм обращения последовательности, применяемый к кортежам в C++11 без каких-либо index_sequence костылей.

Примечание Это заявление немного отличается от того, что в вашем посте:

• Он будет принимать кортеж нулевой длины, std::tuple<>, а также более длинные кортежи. Это лучше, потому что ваше общее определение возвращаемого типа tuple_reverse<Tuple>::type специализировано для std::tuple<>. Таким образом, функция определяется всякий раз, когда возвращается тип.

• Аргумент передается как const &, а не просто &. Вы не собираетесь изменять входной кортеж, поэтому функция должна принимать std::tuple<Ts...> const аргументов.

Сейчас объясню, почему это изящное решение не стартово, по сравнению с тем, что упирается в index_sequence аппарат.

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

#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 и показывает вам в каждом случае: а) что алгоритм действительно реверсирует кортеж и б) стоимость реверсирования этого кортежа, измеренная в операциях копирования элементов кортежа.

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

Таким образом, этот алгоритм квадратично затратен с размером кортежа.

Если вам нужно упражнение, вы можете придумать реализацию для кортежей другого стандартного рекурсивного алгоритма для обращения последовательности. Не такой простой или компактный, как этот, это тот, который идет: поменяйте местами первый и последний элементы последовательности после того, как вы уже поменяли местами последовательность между ними. Стоимость вполне может быть ниже, но она все равно будет квадратичной.

Что огорчает, потому что хорошо известно, что обращение последовательности вещей является линейной проблемой: например, очевидная адаптация классического алгоритма C++ к обращению std::vector будет иметь Cost(n) = 4n.

Неявное предположение, стоящее за этим хорошо известным фактом, заключается в том, что последовательность представляет собой Container<T> для некоторых Container и T; таким образом, реверсивный алгоритм может свободно изменять содержащуюся последовательность в одной позиции, не изменяя ее в других, при этом все еще имея Container<T>.

Но проблема с реверсированием std::tuple заключается в том, что std::tuple<....,A,....,B,....> — это нечто другого типа, чем std::tuple<....,B,....,A,....> и std::tuple<....,A,....>. Таким образом, вы не можете перевернуть std::tuple tup, поместив другой элемент перед tup; или поменять местами A и B в tup и т.п. Чтобы имитировать любую подобную операцию над элементом tup, вы должны построить совершенно новый кортеж другого типа, скопировав все элементы tup и, возможно, больше. Чтобы подобрать банан, вам нужно поднять всю гориллу.

Имея это в виду, вставьте реализацию @Columbo в тестовую программу. Вам нужно изменить invert в его коде на inverse. Скомпилируйте с std=c++14 и запустите. (Для этой опции вам понадобится gcc 4.9 или clang 3.5, а gcc 4.9 выдаст неважное предупреждение компилятора).

Теперь вывод:

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 в этом решении является сущностью его оптимальной эффективности. Если вы хотите избежать квадратичных затрат времени выполнения на реверсирование tup с помощью симулированных операций с элементами, единственная альтернатива — просто создать инвертированный кортеж, инициализированный элементами, которые уже сопоставлены во время компиляции, из их аналоги в tup, по сопоставлению:

Index I -> tuple_size - I - 1

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

Но для выполнения этого сопоставления во время компиляции у вас должен быть список индексов для элементов tup во время компиляции. Это то, что обеспечивает аппарат index_sequence.

Если С++ 14 абсолютно запрещен, вы можете принять легковесную замену С++ 11 для std::index_sequence любезно предоставленную Энди Проулом

При этом у вас может быть следующее решение:

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) — великолепно элегантный и фундаментальный инструмент для эффективной TMP в C++. Вот почему он находится в стандартной библиотеке с версии C++14. (Кстати, Jonathan Wakeley является его автором)

Это возможное решение с использованием С++ 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>>{}>());
}

Демо. Для C++11 возможна та же процедура, но должны быть предоставлены вспомогательные шаблоны, такие как make_index_list.