Возможно ли реализовать нерекурсивную реализацию at_c?
Долгое время назад я видел нерекурсивную реализацию, чтобы получить последнее значение/тип из последовательности последовательностей/значений типа. Он имеет приятное свойство, что количество созданных шаблонов является независимым (и постоянным) количеством элементов, содержащихся в последовательности.
Реализация прост, как следует
// a struct that eats anything and everything
struct eat { template<class T> eat(T&&) {} };
// generates V matching with U
template<class U, class V> struct match { using type = V; };
template<class... X> struct back_
{
template<class U>
static U&& get(typename match<X, eat>::type..., U&& u)
{
return static_cast<U&&>(u); // forward
}
};
// simple macro to avoid repetition for trailing return type.
#define RETURNS(exp) -> decltype(exp) { return exp; }
// get the last value in meta O(1)
template<class T, class... Ts>
auto back(T&& t, Ts&&... ts) RETURNS( back_<Ts...>::get(static_cast<T&&>(t), static_cast<Ts&&>(ts)...))
Он использует простой факт, что с учетом вариационного типа X... компилятор может не рекурсивно генерировать другой тип T, где есть X.
Итак, я хочу знать, есть ли способ расширить его для реализации функции at_c или nth с постоянным количеством экземпляров шаблонов (независимо от количества элементов).
Он также может быть выражен как, дать вариационный тип X... и некоторое целое число N, можно ли нерекурсивно генерировать подпоследовательность X..., состоящую из N элементов?
Ответы
Ответ 1
std::cout << back((int)(0),
(int*)(0),
(int**)(0),
(int***)(0),
(int****)(0),
(int*****)(0),
(int******)(0),
(int*******)(0),
1) << std::endl;
======================================================
nm -C que | fgrep eat
080489e2 W eat::eat<int*******>(int*******&&)
080489dc W eat::eat<int******>(int******&&)
080489d6 W eat::eat<int*****>(int*****&&)
080489d0 W eat::eat<int****>(int****&&)
080489ca W eat::eat<int***>(int***&&)
080489c4 W eat::eat<int**>(int**&&)
080489be W eat::eat<int*>(int*&&)
080489b8 W eat::eat<int>(int&&)
080489e2 W eat::eat<int*******>(int*******&&)
080489dc W eat::eat<int******>(int******&&)
080489d6 W eat::eat<int*****>(int*****&&)
080489d0 W eat::eat<int****>(int****&&)
080489ca W eat::eat<int***>(int***&&)
080489c4 W eat::eat<int**>(int**&&)
080489be W eat::eat<int*>(int*&&)
080489b8 W eat::eat<int>(int&&)
080489e7 W int&& back_<int*, int**, int***, int****, int*****, int******, int*******, int>::get<int>(eat, eat, eat, eat, eat, eat, eat, eat, int&&)
080489e7 W _ZN5back_IJPiPS0_PS1_PS2_PS3_PS4_PS5_iEE3getIiEEOT_3eatSB_SB_SB_SB_SB_SB_SB_SA_
Ответ 2
Мое решение:)), скомпилированное с помощью gcc 4.6.4 -std = С++ 0x
Основная идея: для любых "i" и 0,1,2,... n-1 (где n > i) (0 ^ i), (1 ^ i),... (j ^ i)..., ((n-1) ^ i) - единственная последовательность, и только позиция значения в "i" равна нулю.
Это не O (1) решение, O (log (n)) решение. Но он основан на С++ 14 make_index_sequence. Компилятор Iff компилирует make_index_sequence в O (1), поэтому мое решение также стало O (1).
#include <cstddef>
#include <iostream>
#include <type_traits>
namespace mpl
{
// C++14 index_sequence struct
template< int ... i >
struct index_sequence
{
typedef index_sequence type;
typedef int value_type;
static constexpr std::size_t size()noexcept{ return sizeof...(i); }
};
namespace details
{
#if 1
template< int s, typename T, typename U> struct concate_c;
template<int s, int ...i, int ...j>
struct concate_c< s, index_sequence<i...>, index_sequence<j...> >
: index_sequence<i..., (j + s ) ... > {};
template< int s, typename T, typename U> struct concate : concate_c< s, typename T::type, typename U::type > {};
template< int n>
struct make_index_sequence : concate< n / 2,
make_index_sequence< n / 2 >,
make_index_sequence< n - n / 2 >
>{};
#else
template< typename T, typename U> struct concate_c;
template< int ...i, int ...j>
struct concate_c< index_sequence<i...>, index_sequence<j...> >
: index_sequence<i..., (j + sizeof...(i) ) ... > {};
template< typename T, typename U> struct concate : concate_c< typename T::type, typename U::type > {};
template< int n>
struct make_index_sequence : concate<
make_index_sequence< n / 2 >,
make_index_sequence< n - n / 2 >
>{};
#endif
template<> struct make_index_sequence<0> : index_sequence<>{};
template<> struct make_index_sequence<1> : index_sequence<0>{};
} // namespace details
template< int n> struct make_index_sequence : details::make_index_sequence<n> {};
template< typename ...Args>
struct make_index_sequence_for : make_index_sequence< sizeof...(Args) > {};
// helper for at_c, I - index_sequence,
template< typename I, typename ...p >
struct at_ch;
// only zero index have `type`.
template< int i, typename T> struct id{};
template< typename T>struct id<0,T>{ typedef T type;};
// based from all parameters.
template< typename ...T> struct base_all : T... {};
template< int ... i, typename ...p>
struct at_ch< index_sequence<i...>, p... >
{
struct base : base_all< id<i,p> ... > {};
typedef typename base::type type;
};
// 0 1 2 3 4 5 6 7 8 9
// 0: 0 1 2 3 4 5 6 7 8 9
// 1: 1 0 3 2 5 4 7 6 9 8
template< int i, typename I>
struct xor_index_sequence;
template< int i, int ...k>
struct xor_index_sequence< i, index_sequence<k...> > : index_sequence< (k xor i) ... > {};
template< int i, typename ...T>
struct at_c: at_ch<
typename xor_index_sequence< i,
typename make_index_sequence< sizeof...(T)> ::type
>::type,
T...
> {};
}
int main()
{
typedef mpl::at_c< 2, int, double , float >::type G;
static_assert( std::is_same<G, float>::value ,"!");
return 0;
}
