4

I have following structure, I want remove last argument from index_sequence :

template< std::size_t ... values>
struct index_sequence{};

// I need something like
template< typename IndexSequence>
struct pop_back;

template< std::size_t ... values >
struct pop_back< index_sequence< values... > >
{
    typedef index_sequence< /** values except last one*/ > type;
};

How to implement this pop_back structure?

I know implementation, only it requires deep recursion, I want without deep recursion instantination.

My implementation:

template< std::size_t i, typename IndexSequence >
struct insert_head;

template< std::size_t i, std::size_t ...values>
struct insert_head< i, index_sequence<values...> >
{
   typedef index_sequence< i, values... > type;
};

template< > 
struct pop_back< index_sequence<> > 
{ 
typedef index_sequence<> type; // no element will removed 
}; 

template< std::size i > struct pop_back< index_sequence< i > >
{
   typedef index_sequence<> type; // i - will removed
};

template< std::size_t i, std::size_t ...values> 
struct pop_back< index_sequence<i,values...>>
{
    typedef typename pop_back< index_sequence<values...> >::type tail;
    typedef typename insert_head< i, tail>::type type;
};

Edit2: Another useful algo, select i-th element !!!

template< std::size ...i> struct index_sequence;

template< std::size_t index, typename IndexSeq> struct at;

template< std::size_t index, std::size_t ... values> 
struct at< index, index_sequence<values...> >
{
     static constexpr std::size_t get_value()noexcept
     {
          using list = std::size_t [];
          return list{ values...}[index];
     }

    static constexpr std::size_t value = get_value();
}

// test
//                  -- 0 1 2 3 4
typedef index_sequence<2,4,6,8,10>  even_t;

static_assert( at<2, even_t>::value == 6, "!");
Khurshid
  • 2,654
  • 2
  • 21
  • 29
  • Did you want to avoid deep recursion just as an exercise, or are you handling lists so big that it breaks the compiler? – uk4321 Nov 17 '13 at 20:02
  • I read some tricks in stackoverflow about how avoid deep recursion, so I believe that in my case also possible avoid it. Only I myself couldn't find it. – Khurshid Nov 17 '13 at 20:10
  • Is this your second account? [Khurshid Normuradov](http://stackoverflow.com/users/2614655/khurshid-normuradov) If so, welcome back ;) – dyp Nov 17 '13 at 20:26
  • Thanks. Actually this is my first account, Khurshid Normuradov was second. I remove my facebook account, so instead of it my second account removed also, because I was log in stackoverflow from facebook account. – Khurshid Nov 17 '13 at 20:36
  • I since many time exprement how reduce long compile time problem. I like boost mpl library - this is excellent library for c++03, but C++11 now actually (GCC, CLang, Intel (full), Visual Studio (partially) supported C++11). So I exprement with variadic templates. I know many companies until use C++03, because it is testing for many years, all c++ compiler can good optimization. But, I believe that from next year or next two years C++11 replace c++03 fully. – Khurshid Nov 17 '13 at 20:46
  • Oops I somehow didn't see you're strictly talking about *values* this time, not types. (Well of course you can use my solution as well via `std::integral_constant`, but it's obviously not very elegant for this case.) Why don't you post your solution also as an answer, instead of adding it to your question? – dyp Nov 18 '13 at 10:21
  • oh, is this possible? – Khurshid Nov 18 '13 at 10:26
  • I guess you're referring to *"Why don't you post your solution also as an answer"* -- yes it is possible, just click at the "Answer your own question" button at the bottom of the page. – dyp Nov 18 '13 at 10:28

2 Answers2

1

Again, using Xeo's O(logN) instantiation depth version of gen_seq, slightly modified:

#include <cstddef>

    // using aliases for cleaner syntax
    template<class T> using Invoke = typename T::type;

    template<std::size_t...> struct seq{ using type = seq; };

    template<class S1, class S2> struct concat;

    template<std::size_t... I1, std::size_t... I2>
    struct concat<seq<I1...>, seq<I2...>>
      : seq<I1..., (sizeof...(I1)+I2)...>{};

    template<class S1, class S2>
    using Concat = Invoke<concat<S1, S2>>;

    template<std::size_t N> struct gen_seq;
    template<std::size_t N> using GenSeq = Invoke<gen_seq<N>>;

    template<std::size_t N>
    struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

    template<> struct gen_seq<0> : seq<>{};
    template<> struct gen_seq<1> : seq<0>{};

Now, using one of my former tricks via a friend function & ADL:

#include <tuple>
#include <type_traits>

template<class T, std::size_t I>
struct type_index_pair
{
    friend T my_declval(type_index_pair,
                        std::integral_constant<std::size_t, I>);
};

template<class, class>
struct pop_back_helper;

template<class... TT, std::size_t... Is>
struct pop_back_helper<std::tuple<TT...>, seq<Is...>>
{
    struct base : type_index_pair<TT, Is>...
    {};

    template<std::size_t... Is2>
    using join = std::tuple< decltype(my_declval(base{},
                             std::integral_constant<std::size_t, Is2>{}))... >;
};

template<class... TT, std::size_t... Is, std::size_t... Is2>
auto deduce(seq<Is...>, seq<Is2...>)
-> typename pop_back_helper<std::tuple<TT...>, seq<Is...>>
   ::template join<Is2...>
{  return {};  } // definition not required, actually

template<class... TT>
using pop_back = decltype(deduce<TT...>(gen_seq<sizeof...(TT)>{},
                                        gen_seq<sizeof...(TT)-1>{}));

Usage example:

#include <iostream>
template<class T>
void pretty_print(T)
{
    std::cout << __PRETTY_FUNCTION__ << std::endl;
}

int main()
{
    pretty_print( pop_back<int, bool, char, double>{} );
    pretty_print( pop_back<double, int, int>{} );
}

I'm not particularly happy with it, as it requires two sequences plus the ADL (which requires resources and is slow, AFAIK). Maybe I'll be able to come up with something better in one of next days.

Community
  • 1
  • 1
dyp
  • 38,334
  • 13
  • 112
  • 177
  • Using [my technique to get the nth_element of a tuple](http://stackoverflow.com/a/18594309/420683) might even be faster, even though requiring O(N) instantiations with O(logN) instantiation depth. I.e. do the nth_element K-1 times, where K is the number of types in the original sequence. – dyp Nov 17 '13 at 21:08
  • I'd like someone with compiler/ASM expertise to chime in - intuitively, I believe that this should be no slower (as in, equivalent after compilation) as the "helpers" are reduced away and the ordered instructions are inlined. ([Wrinkles](https://isocpp.org/wiki/faq/inline-functions#inline-and-perf)) @dyp, assuming my intuition is correct, your instantiations and instantiation depth would correspond to compile-time behavior - not including dependent compile-time algorithms like reductions - which is nothing to scoff at, but should be distinguished from runtime. – John P Jun 29 '18 at 05:05
  • IIRC from ADL with tag dispatch, many layers of recursion which do nothing but juggle tags are (or can be) telescoped at compile time, leaving just the tail call as if the intermediate calls were made. The discarded tags shouldn't impact any runtime time/resources or even bloat. With that said, I understand that the compile-time behavior can also impact correctness, e.g. compile failure due to "bottoming out" when intermediates exceed the compiler's max recursion depth. I'm looking into something tangentially related, so I'd love to know if I'm wrong or there's more to it. – John P Jun 29 '18 at 06:38
  • 1
    @JohnP Yeah I was talking about compilation speed only (sorry if this was unclear). Since this is pure metaprogramming with types, no function calls or runtime code is needed. I expect a reasonable optimising compiler to just produce some static strings and calls to `cout` as the only runtime code (this comes from `main`). Take a look at the code e.g. with `godbolt.org` (don't forget `-O3` or so). – dyp Jul 12 '18 at 17:04
  • Excellent, that's what I thought, sorry for the rant. I do quite a lot with TMP, but my tests / static assertions are only proof-of-concepts, so I've never bumped into the recursion limit (without screwing up) or noticed compile scaling. My TMP stuff compiles lightning-fast compared to anything that depends on 3rd-party libraries, so up until now I've dismissed compile-time complexity. Am I right to assume that the optimizations are super-linear w/respect to the instantiated calls/types, e.g. compile-time behavior could be O(N log N) given a TMP algorithm that's O(N)? That's a wrinkle if so. – John P Jul 29 '18 at 04:20
  • @JohnP Well I did this more as a fun exercise than out of necessity or experience, to be honest. The only further resource I have on this matter is this interesting blog post: http://ldionne.com/2015/11/29/efficient-parameter-pack-indexing/ From my memory and current superficial reading, I think it suggests *compilation time* is not necessarily linear in the *instantiations* or *instantiation depth*, at least not in a practically relevant way (very fast growth for small inputs, soon leading to resource exhaustion). – dyp Jul 30 '18 at 19:12
1

there is solution my own question:

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

   // GCC couldn't optimize sizeof..(i) , 
   //see http://stackoverflow.com/questions/19783205/why-sizeof-t-so-slow-implement-c14-make-index-sequence-without-sizeof
   //so I use direct variable `s` instead of it.
   // i.e.  s == number of variadic arguments in `I`.
    template< int s, typename I, typename J > struct concate;

    template< int s, int ...i, int ...j>
    struct concate<s, seq<i...>, seq<j...> >
    { 
        typedef seq<i..., (s  + j)...> type;
    };

    template<int n> struct make_seq_impl;
    template< int n> using make_seq = typename make_seq_impl<n>::type;

    template<> struct make_seq_impl<0>{ typedef seq<> type;};
    template<> struct make_seq_impl<1>{ typedef seq<0> type;};

    template<int n> struct make_seq_impl: concate< n/2, make_seq<n/2>, make_seq<n-n/2>>{};

    //----------------------------------------------------
    // Our solution: 

    template< std::size_t ...> struct index_sequence{};

    template< typename IndexSequence> struct pop_back;

    // empty index_sequence 
    template<>struct pop_back< index_sequence<> >
    { 
        typedef index_sequence<> type;
    };

    template< std::size_t ...i>
    struct pop_back< index_sequence<i...> >
    {
         static constexpr std::size_t size = sizeof...(i);
         static constexpr std::size_t values[] = {i...};

         template< typename sq> struct apply;
         template< int ...j> struct apply< seq<j...> >
         {
             typedef index_sequence< values[j]... > type;
         };

         typedef typename apply< make_seq< size - 1 > >::type type;
    };

    // test
    int main()
    {
         typedef index_sequence< 2, 4, 6, 8, 10>  ievens;

         typedef pop_back< ievens>::type  jevens;

         static_assert( std::is_same< jevens, index_sequence<2,4,6,8> >::value ,"!");
}
Khurshid
  • 2,654
  • 2
  • 21
  • 29