Compile time sequences of integers in C++: std::integer_sequence
std::integer_sequence는 컴파일 타임에 수열을 표현하기 위한 보조 클래스이다. C++14에 도입되었지만, C++11에도 다음 snippet을 참조하여 사용할 수 있다. 이를 사용하여 컴파일 타임에 반복문을 생성하거나 특정 크기의 std::array 객체를 생성하거나 할 수 있다. std::index_sequence는 각 수의 타입이 size_t로 고정된 클래스이다.
std::integer_sequence의 원리는 std::tuple과 유사하게 parameter pack을 사용한다. tuple의 구현을 먼저 간단 살펴보면 다음과 같다. (gnu)
template<typename... _Elements>
class tuple : public _Tuple_impl<0, _Elements...> {};
template<std::size_t _Idx, typename _Head, typename... _Tail>
struct _Tuple_impl<_Idx, _Head, _Tail...>
: public _Tuple_impl<_Idx + 1, _Tail...>,
private _Head_base<_Idx, _Head> {};
template<std::size_t _Idx, typename _Head>
struct _Tuple_impl<_Idx, _Head>
: private _Head_base<_Idx, _Head> {};
_Head_base는 tuple의 각각의 아이템을 저장하는 클래스이므로 무시하면, variadic template의 인자들을 한 개씩 풀면서 (그리고 size_t 형식의 _Idx 값을 1씩 증가하면서) 반복적으로 상속을 통해 처리하고 있다. 여기서 템플릿 인자들이 타입을 나타내는 지정자 였지만, 숫자를 나타내는 값일 수 도 있다. 인자들이 모두 같은 타입의 숫자 값인 클래스가 integer_sequence 이다. 그러나, integer_sequence는 그저 숫자 값을 나타낼 뿐인데 어떻게 활용할 수 있을까? 이를 보조해 주는 것이 std::make_integer_sequence 라는 보조 클래스의 역할이다.
make_integer_sequence
make_integer_sequence는 어떤 값을 넣으면 그 값에 해당하는 수열을 담는 integer_sequence를 만들어 준다. (정확히는 그러한 클래스의 aliasing이 된다.) 예를 들면 다음과 같다.
std::make_integer_sequence<size_t, 10>
//==
std::integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>
tuple과 유사하게 템플릿 인자들을 반복적으로 처리하며 aliasing을 반복 시키면 만들 수 있다는 것을 짐작할 수 있다. 서두에서 링크해둔 gist의 snippet의 코드를 보면 이를 쉽게 확인할 수 있다.
template<typename T, std::size_t N, T... Is>
struct make_integer_sequence : make_integer_sequence<T, N-1, N-1, Is...> {};
template<typename T, T... Is>
struct make_integer_sequence<T, 0, Is...> : integer_sequence<T, Is...> {};
template<typename T, T... Ints>
struct integer_sequence {
typedef T value_type;
static constexpr std::size_t size() { return sizeof...(Ints); }
};
이 코드를 바탕으로, 위 예제를 풀어나가면 다음과 같을 것이다.
std::make_integer_sequence<size_t, 10>
//=>
std::make_integer_sequence<size_t, 9, 9>
//=>
std::make_integer_sequence<size_t, 8, 8, 9>
//=>
//...
//=>
std::make_integer_sequence<size_t, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9>
//=>
std::make_integer_sequence<size_t, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>
//=>
std::integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>
gnu 계열에서는 이를 순차적으로 반복하지 않고 매번 절반으로 나누면서 컴파일 속도의 상승을 추구하는 것으로 추측된다. std::make_integer_sequence<size_t, 10>을 처리할 때, gnu에서는 _Build_index_tuple<5> 까지만 클래스를 정의해도 된다.
template<size_t... _Ind1, size_t... _Ind2>
struct _Itup_cat<_Index_tuple<_Ind1...>, _Index_tuple<_Ind2...>> {
using __type = _Index_tuple<_Ind1..., (_Ind2 + sizeof...(_Ind1))...>;
};
template<size_t _Num>
struct _Build_index_tuple
: _Itup_cat<
typename _Build_index_tuple<_Num / 2>::__type,
typename _Build_index_tuple<_Num - _Num / 2>::__type
> { };
작동 방식을 알아봤으니 이제 이를 어떻게 활용할 수 있는지 살펴보자. std::array를 std::tuple로 바꾸거나, std::tuple을 출력하는 함수를 작성하는 등의 예제는 cppreference에서 찾을 수 있으므로, 다른 없는 예제를 참고해 본다.
Instantiate std::array<T, N> and fill it in compile time
가장 쉬운 예제 중 하나는 std::array값을 균일한 값으로 채운 뒤 생성하는 것이다. 다음 코드를 보자. std::array를 출력하기 위한 함수는 cppreference의 것을 차용했다. 대신 C++14에도 돌아갈 수 있도록 재귀로 처리하였다. (본래 std::tuple 출력하는 함수를C++17의 fold expression을 통해 구현해 놓은 코드였다.)
template<class T, size_t... Is>
constexpr std::array<T, sizeof...(Is)>
array_with_one(const T& value, std::index_sequence<Is...>) {
return {{(static_cast<void>(Is), value)...}};
}
template<class Ch, class Tr, class Arr>
void print_impl(std::basic_ostream<Ch,Tr>& os,
const Arr& t,
std::index_sequence<>) {
}
template<class Ch, class Tr, class Arr, std::size_t I, std::size_t... Is>
void print_impl(std::basic_ostream<Ch,Tr>& os,
const Arr& t,
std::index_sequence<I, Is...>) {
os << (I == 0? "" : ", ") << t[I];
print_impl(os, t, std::index_sequence<Is...>{});
}
template<class Ch, class Tr, class Ty, size_t ArrSize>
auto& operator<<(std::basic_ostream<Ch, Tr>& os,
const std::array<Ty, ArrSize>& t)
{
os << "[";
print_impl(os, t, std::make_index_sequence<ArrSize>{});
return os << "]";
}
int main() {
auto arr = array_with_one<double>(12.0, std::make_index_sequence<8>{});
std::cout << arr << std::endl;
return 0;
}
// output:
// [12, 12, 12, 12, 12, 12, 12, 12]
array_with_one 함수는 T 타입의 값 한 개와 index_sequence를 받아서 T로 초기화된 index_sequence의 크기 만큼의 T의 배열을 반환한다. array_with_one 함수를 수정하면 다음과 같은 경우도 가능하다.
template<class T, class I>
inline constexpr T pow(const T base, I exp) {
static_assert(std::is_integral<I>::value, "Integral required in pow.");
return (exp == 0) ? 1 :
(exp % 2 == 0) ?
pow(base, exp/2)*pow(base, exp/2) :
base * pow(base, (exp-1)/2) * pow(base, (exp-1)/2);
}
template<class T, class I>
inline constexpr T pow2(I exp) {
return (exp == 0) ? 1 :
(exp % 2 == 0) ?
pow2<T>(exp/2)*pow2<T>(exp/2) :
2 * pow2<T>((exp-1)/2) * pow2<T>((exp-1)/2);
}
template<class T, size_t... Is>
constexpr std::array<T, sizeof...(Is)>
array_with_pow(std::index_sequence<Is...>) {
return {{(pow2<T>(Is + 1))...}};
}
int main() {
auto arr = array_with_pow<double>(std::make_index_sequence<10>{});
std::cout << arr << std::endl;
return 0;
}
// output:
// [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
인자로 들어온 T의 값을 그대로 사용하는 대신에, integer_sequence의 template 들을 한 개씩 다른 함수의 인자로 사용하여 함수의 리턴값으로 이루어진 array객체를 만들어 내었다.
Concatenate two std::arrays
integer_sequence는 2개 이상을 동시에 사용할 수 있다. 이를 이용하면 다음과 같이 2개의 std::array를 이을 수 도 있다. 2개의 integer_sequence와 2번의 parameter pack expansion을 사용해서 순서대로 새로운 객체의 생성자 인자로 넣어주게 된다.
template<class LA, class RA, size_t... LIs, size_t... RIs>
constexpr std::array<typename LA::value_type, sizeof...(LIs) + sizeof...(RIs)>
merge_array_internal(
const LA& lh,
const RA& rh,
std::index_sequence<LIs...>,
std::index_sequence<RIs...>
) {
return {{
lh[LIs]...,
rh[RIs]...
}};
}
template<class T1, class T2, size_t LSize, size_t RSize>
constexpr std::array<T1, LSize + RSize>
merge_array(
const std::array<T1, LSize>& lh,
const std::array<T2, RSize>& rh
) {
return merge_array_internal(
lh, rh,
std::make_index_sequence<LSize>{},
std::make_index_sequence<RSize>{}
);
}
int main() {
std::array<int, 6UL> a = {1,2,3,4,5,6};
std::array<int, 4UL> b = {7,8,9,10};
auto arr = merge_array(a, b);
std::cout << arr << std::endl;
return 0;
}
// output:
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
뿐만 아니라, 일반적인 variadic template (class... Args)와 함께 사용할 수 도 있다.
template<class T, size_t... Is, class... Args>
constexpr std::array<T, sizeof...(Is) + sizeof...(Args)>
pad_right_array_internal(
const std::array<T, sizeof...(Is)>& tgt,
std::index_sequence<Is...>,
Args&&... args
) {
return {
tgt.at(Is)...,
static_cast<T>(args)...
};
}
template<class T, size_t Size, class... Args>
constexpr std::array<T, Size + sizeof...(Args)>
pad_right_array(
const std::array<T, Size>& tgt,
Args&&... args
) {
return pad_right_array_internal(
tgt, std::make_index_sequence<Size>{}, std::forward<Args>(args)...
);
}
int main() {
std::array<double, 6UL> a = {1,2,3,4,5,6};
auto arr = pad_right_array(a, 7, 8, 9, 10);
std::cout << arr << std::endl;
return 0;
}
// output:
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
이러한 복수의 tuple-like 클래스를 합치는 다른 방법은 tuple_cat 함수를 참조하자.
정리
이렇듯, integer_sequence를 사용하면 컴파일 타임에 수열을 활용한 코드 생성을 쉽게 할 수 있다. 만약 C++17이상을 활용할 수 있다면, std::apply 같은 함수를 활용하는 방법도 있으나, C++11을 유지해야 한다면 도움이 될 것이라 기대한다.