[Bug libstdc++/66059] make_integer_sequence should use a log(N) implementation

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66059

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #7)
> The version I came up with is very close to Xeo's at stackoverflow. I tried
> something more like yours and it used a LOT more memory.
> 
> Here's what I tested:
> 
> #include <stddef.h>
> 
> namespace std
> {
>   template<size_t... _Indexes> struct _Index_tuple { };
> 
> #if DUP
>   template<typename _ITup, int _Odd> struct _Itup_dup;
> 
>   template<size_t... _Ind>
>     struct _Itup_dup<_Index_tuple<_Ind...>, 0>
>     {
>       static constexpr size_t _Nm = sizeof...(_Ind);
>       using __type = _Index_tuple<_Ind..., _Nm + _Ind...>;
>     };

It turns out that the huge cost of this version is not due to sizeof... it's
due to the static variable, _Nm

Avoiding sizeof... helps too, but not as much as eliminating the variable and
writing it as:

      using __type = _Index_tuple<_Ind..., sizeof...(_Ind) + _Ind...>;