Как понять реализацию libcxx make_integer_sequence?

Question

Найдено два связанных коммита:

1. https://github.com/llvm-mirror/libcxx/commit/42e55e932e173eb224997fe11f0d15a1d74b29dc
2. https://github.com/llvm-mirror/libcxx/commit/a3ccd96ede26a2f383328234e01eb7a9f870691e

Предыдущая реализация __make_tuple_indices вызвала O (N) экземпляров и был довольно неэффективным. Реализация C ++ 14 __make_integer_sequence намного лучше, так как он использует встроенный для генерации последовательности или очень хорошая реализация Log8 (N), предоставленная Ричардом Смитом.

Этот патч перемещает реализацию __make_integer_sequence в __tuple и использует его для реализации __make_tuple_indices.

Поскольку libc ++ не может предоставить имя 'integer_sequence' в C ++ 11, этот патч также вводит фиктивный тип '__integer_sequence', который используется при генерации последовательность. Одна сгенерированная последовательность '__integer_sequence' может быть преобразован в нужный тип; либо __tuple_indices, либо integer_sequence.

---

Из коммита я знаю, что это реализация Log8 (N), которая вручную разворачивает циклы (если это не правильно, пожалуйста, исправьте меня, спасибо). Но я не могу понять, как namespace detail работает с __ integer_sequence . Я пытался использовать отладчик, но он всегда использует ветку __ has_builtin (__ make_integer_seq) .

---

Итак, пожалуйста, помогите мне понять эту реализацию, основные коды находятся в этом коммите и этой части <utility>:

// <utility>
    template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked =
  typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>;

template <class _Tp, _Tp _Ep>
struct __make_integer_sequence_checked
{
    static_assert(is_integral<_Tp>::value,
                  "std::make_integer_sequence can only be instantiated with an integral type" );
    static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length");
    // Workaround GCC bug by preventing bad installations when 0 <= _Ep
    // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929
    typedef __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type;
};

template <class _Tp, _Tp _Ep>
using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type;

---

// <__tuple>

template <class _IdxType, _IdxType... _Values>
struct __integer_sequence {
  template <template <class _OIdxType, _OIdxType...> class _ToIndexSeq, class _ToIndexType>
  using __convert = _ToIndexSeq<_ToIndexType, _Values...>;

  template <size_t _Sp>
  using __to_tuple_indices = __tuple_indices<(_Values + _Sp)...>;
};

template<typename _Tp, size_t ..._Extra> struct __repeat;
template<typename _Tp, _Tp ..._Np, size_t ..._Extra> struct __repeat<__integer_sequence<_Tp, _Np...>, _Extra...> {
  typedef __integer_sequence<_Tp,
                           _Np...,
                           sizeof...(_Np) + _Np...,
                           2 * sizeof...(_Np) + _Np...,
                           3 * sizeof...(_Np) + _Np...,
                           4 * sizeof...(_Np) + _Np...,
                           5 * sizeof...(_Np) + _Np...,
                           6 * sizeof...(_Np) + _Np...,
                           7 * sizeof...(_Np) + _Np...,
                           _Extra...> type;
};

template<size_t _Np> struct __parity;
template<size_t _Np> struct __make : __parity<_Np % 8>::template __pmake<_Np> {};

template<> struct __make<0> { typedef __integer_sequence<size_t> type; };
template<> struct __make<1> { typedef __integer_sequence<size_t, 0> type; };
template<> struct __make<2> { typedef __integer_sequence<size_t, 0, 1> type; };
template<> struct __make<3> { typedef __integer_sequence<size_t, 0, 1, 2> type; };
template<> struct __make<4> { typedef __integer_sequence<size_t, 0, 1, 2, 3> type; };
template<> struct __make<5> { typedef __integer_sequence<size_t, 0, 1, 2, 3, 4> type; };
template<> struct __make<6> { typedef __integer_sequence<size_t, 0, 1, 2, 3, 4, 5> type; };
template<> struct __make<7> { typedef __integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6> type; };

template<> struct __parity<0> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type> {}; };
template<> struct __parity<1> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 1> {}; };
template<> struct __parity<2> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 2, _Np - 1> {}; };
template<> struct __parity<3> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 3, _Np - 2, _Np - 1> {}; };
template<> struct __parity<4> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
template<> struct __parity<5> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
template<> struct __parity<6> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 6, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
template<> struct __parity<7> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 7, _Np - 6, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };

} // namespace detail

Заранее спасибо.

_{Если вы думаете, что этот вопрос слишком граничит / грубее, не стесняйтесь сказать мне. Я скоро удалю, хотя этот вопрос меня очень беспокоит.}

Answer 1

, если N (0, 7), специализированный шаблон ---- __make<0> __make<1> __make<2> ... __make<7> будет вызываться напрямую, например, если N = 4, template<> struct __make<4> { typedef __integer_sequence<size_t, 0, 1, 2, 3> = type;};.

else , N> = 8, будет вызван (__make) первичный шаблон, который получен из __parity<N % 8>::__pmake, N применяется для _Np ниже. __pmake является производным от __repeat.

Что касается repeat, Артье дал превосходное объяснение. Позвольте мне добавить случаи:

Например: __make_integer_sequence<10> => __repeat<typename __make<_Np / 7>::type, _Np - 2, _Np - 1>

• Extra - это 8, 9
• typename __make<_Np / 8>::type => typename __make<1>::type => __integer_sequence<size_t, 0>, sizeof...(_Np) - это 1, так что будет развернуть до (0, 7)

Итак, make_integer_sequence<10> равно (0 ... 9)

Если typename __make<N>::type не 1, например, __make_integer_sequence<18>

• Extra is 16, 17

• typename __make<_Np / 8>::type => typename __make<2>::type => __integer_sequence<size_t, 0, 1>, sizeof...(_Np) is 2 :

  0 1
  2 + 0, 2 + 1
  4 + 0, 4 + 1
  6 + 0, 6 + 1
  ...
  7 * 2 + 0, 7 * 2 + 1
  

Итак, make_integer_sequence<18> - это (0 ... 17)

Answer 2

Вам также нужно понять __repeat, чтобы увидеть, как это работает:

template<typename _Tp, size_t ..._Extra> struct __repeat;
template<typename _Tp, _Tp ..._Np, size_t ..._Extra> struct __repeat<integer_sequence<_Tp, _Np...>, _Extra...> {
  typedef integer_sequence<_Tp,
                           _Np...,
                           sizeof...(_Np) + _Np...,
                           2 * sizeof...(_Np) + _Np...,
                           3 * sizeof...(_Np) + _Np...,
                           4 * sizeof...(_Np) + _Np...,
                           5 * sizeof...(_Np) + _Np...,
                           6 * sizeof...(_Np) + _Np...,
                           7 * sizeof...(_Np) + _Np...,
                           _Extra...> type;
}

Требуется два шаблона parementer: целочисленная последовательность и пакет paremeter с _Extra значениями.

Имеет член typedef type, который является целочисленной последовательностью того же типа, что и исходная целочисленная последовательность.

Это члены следующие:

_Np...,  // The original values


sizeof...(_Np) + _Np...,
// sizeof...(_Np) is the number of integers in the sequence. This is a fold expression
// that adds the sizeof...(_Np) to every integer.

// So (_Np..., sizeof...(_Np) + _Np...) for <0, 1, 2> would be
// (<0, 1, 2>..., <3 + 0, 3 + 1, 3 + 2>...), which is `<0, 1, 2, 3, 4, 5>`.

// The rest of the lines are the same, but starting with a different
// multiple of sizeof...(_Np)

// `<0, 1, ..., N>` into an integer sequence of `<0, 1, ..., 8N>`.

_Extra...
// And then add `_Extra` to the end

__make<_Np> от _Np = 0 до _Np = 7 жестко закодировано. В противном случае он использует __parity в качестве вспомогательного типа.

Это будет использовать __repeat, чтобы повторить __make<_Np / 8> 8 раз, создавая желаемую длину, а затем добавить оставшиеся элементы, используя дополнительные, в зависимости от того, насколько он больше, чем последний кратный 8 (здесь называется «четность») как _Extra.

Это не столько "ручное развертывание цикла". Он просто рекурсивно делит make_integer_sequence<N> на repeat_8_times<make_integer_sequence<N / 8>> /* + remainder */, поэтому это "рекурсия с базовым регистром"