如何理解libcxx对make_integer_sequence的实现?
How to understand libcxx's implementation of make_integer_sequence?
我发现了两个相关的提交:
- https://github.com/llvm-mirror/libcxx/commit/42e55e932e173eb224997fe11f0d15a1d74b29dc
- https://github.com/llvm-mirror/libcxx/commit/a3ccd96ede26a2f383328234e01eb7a9f870691e
The previous __make_tuple_indices implementation caused O(N) instantiations
and was pretty inefficient. The C++14 __make_integer_sequence implementation
is much better, since it either uses a builtin to generate the sequence or
a very nice Log8(N) implementation provided by richard smith.
This patch moves the __make_integer_sequence implementation into __tuple
and uses it to implement __make_tuple_indices.
Since libc++ can't expose the name 'integer_sequence' in C++11 this patch
also introduces a dummy type '__integer_sequence' which is used when generating
the sequence. One the sequence is generated '__integer_sequence' can be
converted into the required type; either '__tuple_indices' or 'integer_sequence'.
从提交中,我知道它是一个 Log8(N) 实现,它手动展开循环(如果不正确,请纠正我,thx)。但是我无法理解 namespace detail
work with __integer_sequence. I have tried to use debugger, but it always uses the __has_builtin(__make_integer_seq) branch。
所以,请帮我理解这个实现,主要代码在this commit and this part of <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
提前致谢。
如果你觉得这个问题太border/ruder,欢迎告诉我。我会尽快删除,虽然这个问题确实很困扰我。
您还需要了解 __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;
}
它需要两个模板参数:一个整数序列和一个 _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 添加剩余的项目(此处称为 "parity")为 _Extra
.
没那么多"manually unrolling the loop"。只是递归地把make_integer_sequence<N>
分成repeat_8_times<make_integer_sequence<N / 8>> /* + remainder */
,所以就是"recursion with a base case"
if N
is (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
,Artyer已经给出了很好的解释。让我补充
案例:
例如:__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
是 16, 17
typename __make<_Np / 8>::type
=> typename __make<2>::type
=>
__integer_sequence<size_t, 0, 1>
, sizeof...(_Np)
是 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)
我发现了两个相关的提交:
- https://github.com/llvm-mirror/libcxx/commit/42e55e932e173eb224997fe11f0d15a1d74b29dc
- https://github.com/llvm-mirror/libcxx/commit/a3ccd96ede26a2f383328234e01eb7a9f870691e
The previous __make_tuple_indices implementation caused O(N) instantiations and was pretty inefficient. The C++14 __make_integer_sequence implementation is much better, since it either uses a builtin to generate the sequence or a very nice Log8(N) implementation provided by richard smith.
This patch moves the __make_integer_sequence implementation into __tuple and uses it to implement __make_tuple_indices.
Since libc++ can't expose the name 'integer_sequence' in C++11 this patch also introduces a dummy type '__integer_sequence' which is used when generating the sequence. One the sequence is generated '__integer_sequence' can be converted into the required type; either '__tuple_indices' or 'integer_sequence'.
从提交中,我知道它是一个 Log8(N) 实现,它手动展开循环(如果不正确,请纠正我,thx)。但是我无法理解 namespace detail
work with __integer_sequence. I have tried to use debugger, but it always uses the __has_builtin(__make_integer_seq) branch。
所以,请帮我理解这个实现,主要代码在this commit and this part of <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
提前致谢。
如果你觉得这个问题太border/ruder,欢迎告诉我。我会尽快删除,虽然这个问题确实很困扰我。
您还需要了解 __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;
}
它需要两个模板参数:一个整数序列和一个 _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 添加剩余的项目(此处称为 "parity")为 _Extra
.
没那么多"manually unrolling the loop"。只是递归地把make_integer_sequence<N>
分成repeat_8_times<make_integer_sequence<N / 8>> /* + remainder */
,所以就是"recursion with a base case"
if N
is (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
,Artyer已经给出了很好的解释。让我补充
案例:
例如:__make_integer_sequence<10>
=>
__repeat<typename __make<_Np / 7>::type,
_Np - 2, _Np - 1>
:
Extra
是 8, 9typename __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
是 16, 17typename __make<_Np / 8>::type
=>typename __make<2>::type
=>__integer_sequence<size_t, 0, 1>
,sizeof...(_Np)
是 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)