effective way to select last parameter of variadic template

Question

I know how to select first parameter of variadic template:

template< class...Args> struct select_first;
template< class A, class ...Args> struct select_first<A,Args...>{  using type = A;};

It's a very simple. However, select_last is not similar:

template< class ...Args> struct select_last;
template< class A> struct select_last<A> { using type = A; };
template< class A, class Args...> struct select_last<A,Args...>{ 
        using type = typename select_last<Args...>::type;
};

This solution needed deep recursive template instantinations. I try to solve this with as:

template< class A, class Args...>
struct select_last< Args ... , A>{  using type = A; }; // but it's not compiled.

Q: exist more effective way to selecting last parameter of variadic templates?

Sherard

There's at least a way to do it in O(logN) instantiation depth, but it isn't necessarily more efficient.... oh wait. That was your question :D – Myongmyopia

@DyP ohh!! Thanks. I forgot. Can I select last parameter by this way in O(1) instantinations? – Sherard

No, at least not with this method. It requires creating a sequence (of integers) to know which type is the last one, and the best algorithm I know of to create these sequences still uses O(logN) instantiation depth. As jrok pointed out, you can create templates via the preprocessor, but it isn't as flexible and might not be faster. – Myongmyopia

Answer 1

With C++17, the cleanest way is

template<typename T>
struct tag
{
    using type = T;
};

template<typename... Ts>
struct select_last
{
    // Use a fold-expression to fold the comma operator over the parameter pack.
    using type = typename decltype((tag<Ts>{}, ...))::type;
};

with O(1) instantiation depth.

Cigarette

You can also make tag local to select_last to avoid polluting the global namespace. – Amagasaki

Is there a reason not to use std::declval<T>() instead of tag<T>() e.g. template<typename... Ts> struct select_last { using type = decltype((std::declval<Ts>{}, ...)); }; ? – Milamilady

@marco6, std::declval<T>() returns a reference type, and you'll have to chop that reference off. But then you'll have a problem if T is a reference type itself. In C++20 we'll have std::type_identity for tag. – Overcrop

Answer 2

Same approach as last time, O(logN) instantiation depth. Using only one overload, so it should consume less resources.

Warning: it currently removes references from the tuple types. Note: Removed the reference from pack::declval. I think it still works in every case.

indices trick in O(log(N)) instantiations, by Xeo; modified to use std::size_t instead of unsigned

    #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>{};

---

Today, I realized there's a different, simpler and probably faster (compilation time) solution to get the nth type of a tuple (basically an implementation of std::tuple_element). Even though it's a direct solution of another question, I'll also post it here for completeness.

namespace detail
{
    template<std::size_t>
    struct Any
    {
        template<class T> Any(T&&) {}
    };

    template<typename T>
    struct wrapper {};

    template<std::size_t... Is>
    struct get_nth_helper
    {
        template<typename T>
        static T deduce(Any<Is>..., wrapper<T>, ...);
    };

    template<std::size_t... Is, typename... Ts>
    auto deduce_seq(seq<Is...>, wrapper<Ts>... pp)
    -> decltype( get_nth_helper<Is...>::deduce(pp...) );
}

#include <tuple>

template<std::size_t n, class Tuple>
struct tuple_element;

template<std::size_t n, class... Ts>
struct tuple_element<n, std::tuple<Ts...>>
{
    using type = decltype( detail::deduce_seq(gen_seq<n>{},
                                              detail::wrapper<Ts>()...) );
};

Helper for last element:

template<typename Tuple>
struct tuple_last_element;

template<typename... Ts>
struct tuple_last_element<std::tuple<Ts...>>
{
    using type = typename tuple_element<sizeof...(Ts)-1,
                                        std::tuple<Ts...>> :: type;
};

Usage example:

#include <iostream>
#include <type_traits>
int main()
{
    std::tuple<int, bool, char const&> t{42, true, 'c'};

    tuple_last_element<decltype(t)>::type x = 'c'; // it's a reference

    static_assert(std::is_same<decltype(x), char const&>{}, "!");
}

---

Original version:

#include <tuple>
#include <type_traits>

namespace detail
{
    template<typename Seq, typename... TT>
    struct get_last_helper;

    template<std::size_t... II, typename... TT>
    struct get_last_helper< seq<II...>, TT... >
    {
        template<std::size_t I, std::size_t L, typename T>
        struct pack {};
        template<typename T, std::size_t L>
        struct pack<L, L, T>
        {
            T declval();
        };

        // this needs simplification..
        template<typename... TTpacked>
        struct exp : TTpacked...
        {
            static auto declval_helper()
                -> decltype(std::declval<exp>().declval());
            using type = decltype(declval_helper());
        };

        using type = typename exp<pack<II, sizeof...(TT)-1, TT>...>::type;
    };
}

template< typename Tuple >
struct get_last;

template< typename... TT >
struct get_last<std::tuple<TT...>>
{
    template<std::size_t... II>
    static seq<II...> helper(seq<II...>);
    using seq_t = decltype(helper(gen_seq<sizeof...(TT)>()));

    using type = typename detail::get_last_helper<seq_t, TT...>::type;
};


int main()
{
    using test_type = std::tuple<int, double, bool, char>;

    static_assert(std::is_same<char, get_last<test_type>::type>::value, "!");
    // fails:
    static_assert(std::is_same<int, get_last<test_type>::type>::value, "!");
}

Myongmyopia

I get some strange incomplete type error when removing declval_helper. Not sure why. – Myongmyopia

Answer 3

The following is another lean C++17 approach which also uses a fold-expression; but avoids an ad-hoc class proxy, by using std::enable_if:

template <typename ...Ts>
struct select_last
{
  using type = typename decltype((std::enable_if<true,Ts>{}, ...))::type;
};

template <typename ...Ts>
using select_last_t = typename select_last<Ts...>::type;

static_assert(std::is_same_v<char, select_last_t<int,double,char>>);

In C++20 std::type_identity offers a more readable approach:

// C++20
template <typename ...Ts>
struct select_last
{
  using type = typename decltype((std::type_identity<Ts>{}, ...))::type;
};

In C++26 pack indexing from P2662 allows us to save a few more characters:

template <typename ...Ts>
Ts...[sizeof...(Ts)-1] select_last();

static_assert(std::is_same_v<char, decltype(select_last<int,double,char>())>);

Chian

In addition, you can use using without struct like: template <typename... Ts> using last_type = typename decltype((std::type_identity<Ts>{}, ...))::type; – Carom

Answer 4

If you are willing to strip references blindly from your type list (which is quite often the case: either you know they are references, or you don't care), you can do this with little machinery outside of std. Basically stuff the data into a tuple or tie, then use std::get<sizeof...(X)-1>( tuple or tie ) to extract the last element.

You can do this in a pure-type context using std::declval< std::tuple<Args...> >() and decltype, and possibly std::remove_reference.

As an example, suppose you have a variardic set of arguments, and you want to return the last argument ignoring the rest:

#define RETURNS(x) ->decltype(x) { return (x); }

template<typename ...Args>
auto get_last( Args&&... args )
  RETURNS( std::get< sizeof...(Args)-1 >( std::tie(std::forward<Args>(args)...) ) )

we can then use this in another function:

template<typename ...Args>
void foo( Args&&... args ) {
  auto&& last = get_last(std::forward<Args>(args)...);
}

Vantassel

Answer 5

This other solution is brilliant if C++17 is available and if one is interested in the last type only.

If C++14 support is required (C++11 plus index_sequence) or if one is interested in the nth type then a good solution is

#include <utility>

////////////////////////////////////////////////////////////////////////////////

template<std::size_t n, std::size_t i, class>
struct type_if_equal {
  static_assert(n != i, "see specialization");
// missing `type` typedef by purpose
};

template<std::size_t n, class T>
struct type_if_equal<n, n, T> {
  using type = T;
};

////////////////////////////////////////////////////////////////////////////////

template<std::size_t n, class Is, class... Ts>
struct select_nth;

template<std::size_t n, std::size_t... is, class... Ts>
struct select_nth<n, std::index_sequence<is...>, Ts...>
  : type_if_equal<n, is, Ts>...
{};

template<std::size_t n, class... Ts>
using select_nth_t = typename select_nth<
  n, std::index_sequence_for<Ts...>, Ts...
>::type;

////////////////////////////////////////////////////////////////////////////////

template<class T0, class... Ts>
using select_last_t = select_nth_t<sizeof...(Ts), T0, Ts...>;

////////////////////////////////////////////////////////////////////////////////

int main() {
  using T = select_last_t<int, double, double, long, long, long, int, char>;
  static_assert(std::is_same<T, char>{}, "");
}

Warning: Do not use a naive self-made solution like select_nth_t if you need fast compilation times for huge variadic lists. There are highly optimized template-metaprogramming libraries for this purpose. Have a look at metaben.ch for a comparison of compile-time performance of several algorithms. This algorithm is called at, and here is my measurement result of select_nth_t based on this code using GCC 10:

See blog posts by Louis Dionne and Odin Holmes for excellent background information regarding compile-time reduction of the at algorithm (a.k.a. std::tuple_element_t).

Ballata

Sorry, I hadn't seen that you provided a link to the code. I used my own benchmark, so that'd be the difference. I haven't times with Idione's code, but I'm not 100% sure that it's the best because the files should really be the same except for the call to the type trait that does the work, otherwise the difference in compile speeds could be due to #includes, etc. Of course those differences should plateau with larger instances, but 500 isn't so big. – Hilleary

@Hilleary ah, I see. (Micro-)benchmarking these kind of things is hard, and different method yield different answers. I believe we agree on the bottom line, though: this multiple-inheritance based method is generally faster than a recursion-based method, but way slower than a well optimized library (see the at benchmark on GCC 7 and Clang 7 for some well known libraries). – Ballata

Answer 6

template <class... Args>
struct select_last;

template <typename T>
struct select_last<T>
{
     using type = T;
};

template <class T, class... Args>
struct select_last<T, Args...>
{
    using type = typename select_last<Args...>::type;
};

Lepidopterous

I just wondered what you were doing here with the tuple ;) But now, you have duplicated the OP's code – Myongmyopia

Answer 7

Sorry for being a bit late to the party, but I just ran across the same problem , looked up for an answer, didn't like what I see here and realised it can be done using a tuple. Please see C++11 implementation below. Note: one can also get access to an Nth type of a variadic template this way. (The example doesn't check that N exceeds the number of variadic arguments , however the check can be done with SFINAE technique (enable_if) for instance) Is that an acceptable answer or I'm missing anything in the question?

#include <tuple>
#include <iostream>

struct A
{
    char ch = 'a';
};
struct B
{
    char ch = 'b';
};
struct C
{
    char ch = 'c';
};


template <typename... Types>
struct SomeVariadic {

    using TypesTuple = std::tuple<Types...>;

    using LastType = typename std::tuple_element<sizeof...(Types)-1, TypesTuple>::type;

    template <int N>
    using NthType = typename std::tuple_element<N, TypesTuple>::type;
};



int main(int argc, char* argv[]) {

    SomeVariadic<A,B,C>::LastType l;

    std::cout << SomeVariadic<A,B,C>::LastType().ch << " "
            << SomeVariadic<A,B,C>::NthType<1>().ch<< std::endl;
}

Inequality

Answer 8

With the introduction of C++26 Pack Indexing, now you can

template<class... Args> 
struct select_last { 
  using type = Args...[sizeof...(Args) - 1];
};

Demo

Puckett

Answer 9

A pretty dumb approach would be to write a helper class and specialize for each number of parameters (up to some limit of your choice). You could use preprocessor for that.

template<typename...>
struct select_last_helper;

template<typename T1>
struct select_last_helper<T1> {
    using type = T1;
};

template<typename T1, typename T2>
struct select_last_helper<T1,T2> {
    using type = T2;
};

template<typename T1, typename T2, typename T3>
struct select_last_helper<T1,T2,T3> {
    using type = T3;
};

template<typename... Ts>
struct select_last {
    using type = typename select_last_helper<Ts...>::type;
};

O(1) template instantiations :)

Schoolboy

Well, its true that in common cases nobody never have sets of thousands of parameters, have a little set of parameters, so this could be an approach. But, on the other hand, this breaks the power of variadic templates completely. This is the same horrible thing as Boost::Tuple or Loki Typelists – Diphtheria

@Manu343726, ugly, sure. But it could be made generic by having a last select_last_helper that handles - by recursion - cases where the variadic is larger. This way you could get O(max{1, n - k}), where k is the number of small cases that you handle. You could write a could of macros to generate this for you. However, I'm not sure how the compiler handles resolving template specialisation - it may linearly scan through the options and so be O(n) time anyway. shrug – Hilleary