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

Логиката за обръщане на индексите не е приятна и не можах да продължа от този етап.

Предполагам, че имате предвид решения, които използват std::index_sequence (C++14) или подобни, като тези на Джонатан Уейкли и че решението на @Columbo в същия дух също би било неприятно, дори ако беше C++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 патерици.

N.B. Тази декларация се различава леко от тази в публикацията ви:-

• Той ще приеме кортеж с дължина 0, 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.

Ако C++14 е абсолютно забранен, може да приемете слаб C++11 заместител на std::index_sequence с любезното съдействие на 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) е изключително елегантен и основен инструмент за ефективен TMP в C++. Ето защо е в стандартната библиотека от C++14. (BTW, Джонатан Уейкли е негов автор`)

Това е възможно решение с помощта на 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>>{}>());
}

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