Template integer range, version 2

Question

This question is a follow-up. The original question was itself a follow-up to an older question by @LokiAstari.

The idea is to provide a compile-time integer range.

This version incorporates almost everything from the answers and comments to the previous iteration of the review (except the handling of corner cases such as INT_MAX, which is kind of hard). Along with the fixes comes a new feature: the possibility to specify the « step » of the range. Here is the new implementation:

#include <cstddef>
#include <utility>
namespace detail
{
 template<
 typename Integer,
 typename SequenceBase,
 Integer Begin,
 Integer Step,
 bool IsIncreasing
 >
 struct integer_range_impl;
 template<
 typename Integer,
 Integer... N,
 Integer Begin,
 Integer Step
 >
 struct integer_range_impl<Integer, std::integer_sequence<Integer, N...>, Begin, Step, true>
 {
 using type = std::integer_sequence<Integer, (N * Step + Begin)...>;
 };
 template<
 typename Integer,
 Integer... N,
 Integer Begin,
 Integer Step
 >
 struct integer_range_impl<Integer, std::integer_sequence<Integer, N...>, Begin, Step, false>
 {
 using type = std::integer_sequence<Integer, (Begin - N * Step)...>;
 };
}
template<
 typename Integer,
 Integer Begin,
 Integer End,
 Integer Step
>
using make_integer_range = typename detail::integer_range_impl<
 Integer,
 std::make_integer_sequence<
 Integer,
 ((Begin < End ? End - Begin : Begin - End) - 1) / Step + 1
 >,
 Begin,
 Step,
 (Begin < End)
>::type;
template<std::size_t Begin, std::size_t End, std::size_t Step>
using make_index_range = make_integer_range<std::size_t, Begin, End, Step>;

Here is an example of how this template integer range can be used:

#include <array>
#include <iostream>
#include <iterator>
#include <numeric>
template<typename T, std::size_t N, std::size_t... Ind>
auto print(const std::array<T, N>& arr, std::index_sequence<Ind...>)
 -> void
{
 int dummy[] = {
 (std::cout << std::get<Ind>(arr) << ' ', 0)...
 };
 (void) dummy;
}
int main()
{ 
 std::array<int, 20u> arr;
 std::iota(std::begin(arr), std::end(arr), 0);
 // prints 15 12 9 6 3
 print(arr, make_index_range<15u, 0u, 3u>{});
}

I accept any kind of review, be it about style, correctness or possible improvements to the utility in general :)

Answer 1

I've recently had to implement compile-time integer ranges. I actually based my design on these bullet points in your original question as well as some of your code:

• The range can be ascending or descending.
• The class is templated so that it is possible to choose the integer type to use.

Originally, the ranges made were [lower, upper), but in practice, I found that [lower, upper] was more natural.

It's easier to say: I want a range from \$x\$ to \$y\$ using \$step\$

Than it is to say: I want a range from \$x\$ to \$y + step\$ using \$step\$.

Generating sequences in \$log(n)\$ template depth instantiations

In order to ensure that large ranges are supported, we must ensure that generating sequences doesn't cause too much depth, too soon. We can achieve \$O(log(n))\$ template instantiation depth complexity; our time and space complexities stay at \$O(n)\$. This comment tells us why.

All types are part of the (omitted) ct namespace.

Required #include directives

#include <cstddef>
#include <type_traits>

An integer pack type

A simple template type for an integer pack type; integer_pack<>. This can easily be replaced with std::integer_sequence; it is optional. I decided to differentiate them in order to make it clearer that it is to be used in conjunction with the other types in the same namespace.

template<class T, T... values>
struct integer_pack
{
 using type = integer_pack<T, values...>;
};

A merger type

A merger type that creates one integer_pack<> from two integer_pack<> types. The second integer_pack<> type is a continuation of the first.

Note that RIntegerPack is a simple sequence with the same start value as LIntegerPack. This is fine because integer_pack_merge is simply a helper type that won't normally be used on its own.

template<class T, class LIntegerPack, class RIntegerPack>
struct integer_pack_merge;
template<class T, T... As, T... Bs>
struct integer_pack_merge<T, integer_pack<T, As...>, integer_pack<T, Bs...>>
 : integer_pack<T, As..., sizeof...( As ) + Bs...>
{};

Example behaviour in pseudo-code:

list_a = <0, 1, 2>
list_b = <0, 1>
merge<list_a, list_b> = <0, 1, 2, ( 3 + 0 ), ( 3 + 1 )>
 = <0, 1, 2, 3, 4>

A logarithmic generator of integer sequences

A logarithmic generator of integer_pack type; integer_sequence_generate.

template<class T, T n, class = void>
struct integer_sequence_generate
 : integer_pack_merge
 <
 T,
 typename integer_sequence_generate<T, n / 2>::type,
 typename integer_sequence_generate<T, n / 2 + n % 2>::type
 >
{};
template<class T, T n>
struct integer_sequence_generate<T, n, std::enable_if_t<( n == 1 )>>
 : integer_pack<T, n - 1>
{};
template<class T, T n>
struct integer_sequence_generate<T, n, std::enable_if_t<( n == 0 )>>
 : integer_pack<T>
{};
template<class T, T n>
using make_integer_sequence = typename integer_sequence_generate<T, n>::type;

The make_integer_range<> implementation

Using integer sequences, we can generate ranges. If the sequence cannot actually be generated, we provide a compile-time error through static_assert.

We determine if it is a increasing/decreasing range and how many values the range contains.

template<class T, T from, T to, T step, T n_vals = ( from < to ? to - from : from - to )>
struct integer_range_generate
{
private:
 static_assert( n_vals % step == 0,
 "unreachable integer range; invalid step value" );
 template<class IntegerPack, bool is_increasing>
 struct integer_range_generate_impl;
 template<T... ints>
 struct integer_range_generate_impl<integer_pack<T, ints...>, true>
 : integer_pack<T, ( from + step * ints )...>
 {};
 template<T... ints>
 struct integer_range_generate_impl<integer_pack<T, ints...>, false>
 : integer_pack<T, ( from - step * ints )...>
 {};
public:
 using type = typename integer_range_generate_impl
 <
 make_integer_sequence<T, 1 + n_vals / step>, ( from < to )
 >::type;
};
template<class T, T n, T step, T n_vals>
struct integer_range_generate<T, n, n, step, n_vals>
 : integer_pack<T, n>
{};

Things to consider

• Adding type aliases for convenience, i.e.: index_pack<>, make_index_range<>, etc.
• This implementation's step is always a positive value, so it might feel a bit unnatural to specify range<10, 0, 1> instead of range<10, 0, -1>, however:
  • There is no need to specify a type for the step argument.
  • The step's type is the same as the range's type; no integer math issues.
• Barry's suggestions, such as default values for the step, etc.

In conclusion, your implementation was pretty good and did what it was meant to do. However, it couldn't generate large sequences and lacked some meaningful error messages.

• Morwenn: Note that I stuck to a [begin, end) range, but I was never sure that it was the best solution for numerics; it seems to match the design of std::make_index_sequence though. Nice logarithmic implementation, I didn't bother because I didn't think there would be use cases for integer sequences, but I'm not sure I could have designed such an elegant solution, thanks :p
• ruds: Note that this is \$O(log n)\$ template instantiation depth, which may lead to \$O(log n)\$ stack space being used, but that there are still \$O(n)\$ "leaves" in your tree and the sequence has \$O(n)\$ elements, so you'll need at least \$O(n)\$ space and time in the end.
• user2296177: @ruds You're right of course, I've clarified and added a link to your comment.
• user2296177: @Morwenn I agree with Barry in that it can be surprising, but I also agree that [begin, end) is the common pattern. I lean towards Barry's suggestions, though.
• Deduplicator: Your integer_pack has incompatible members to std::integer_sequence.

Answer 2

My main objection to your code is:

Principle of Least Surprise

I was pretty surprised that:

make_index_range<15u, 0u, 3u>

is the sequence

std::index_sequence<15, 12, 9, 6, 3>

given that it sure looks like we're going from 15 to 0 by 3s... which intuitively should produce std::index_sequence<>. You already do correctly provide two type aliases, where make_index_range is an alias for make_integer_range... so if somebody wants a negative range, they should have to do:

make_integer_range<int, 15, 0, -3>.

That change will also simplify your implementation, which leads into...

Simplify, Simplify, Simplify

Once you drop the increasing/decreasing check, the code becomes simpler. We are always going from Begin to End by Step.

First, let's determine the size of our sequence. For signed integers, we can just divide by Step and floor at 0. For unsigned integers, we have to ensure that End is at least as big as Begin:

template <class T, T Begin, T End, T Step>
struct sequence_size
: std::conditional_t<
 std::is_signed<T>::value,
 std::integral_constant<T, std::max<T>(0, (End - Begin)/Step)>,
 std::integral_constant<T, (End >= Begin) ? (End - Begin)/Step : 0>
 >
{ };

And then, with a default template parameter, our detail::make_integer_range can just be a simple pack expansion. No need for separate cases for increasing/decreasing sequences, since that would be handled by simply having a negative Step for signed integral types:

namespace detail {
 template <class T, T Begin, T End, T Step, 
 typename = std::make_integer_sequence<T, sequence_size<T, Begin, End, Step>::value>
 >
 struct make_integer_range;
 template <class T, T Begin, T End, T Step, T... Idx>
 struct make_integer_range<T, Begin, End, Step, std::integer_sequence<T, Idx...>>
 {
 using type = std::integer_sequence<T, Idx * Step + Begin...>;
 };
}
template <class T, T Begin, T End, T Step>
using make_integer_range = typename detail::make_integer_range<T, Begin, End, Step>::type;
template <std::size_t Begin, std::size_t End, std::size_t Step>
using make_index_range = make_integer_range<std::size_t, Begin, End, Step>;

Add Default Step

Using 1 as a default is pretty standard, so let's just do that:

template <class T, T Begin, T End, T Step=1>
using make_integer_range = typename detail::make_integer_range<T, Begin, End, Step>::type;
template <std::size_t Begin, std::size_t End, std::size_t Step=1>
using make_index_range = make_integer_range<std::size_t, Begin, End, Step>;

Add Default Start

You could also provide a default beginning by having your aliases take a pack of ints. Something like:

template <class T, T... Vals>
using make_integer_range = typename detail::make_integer_range_variadic<T, Vals...>::type;
template <std::size_t... Vals>
using make_index_range = make_integer_range<std::size_t, Vals...>;

With:

template <class T, T... Vals>
struct make_integer_range_variadic
: make_integer_range<T, Vals...>
{ };
template <class T, T End>
struct make_integer_range_variadic<T, End>
: make_integer_range<T, 0, End, 1>
{ };
template <class T, T Begin, T End>
struct make_integer_range_variadic<T, Begin, End>
: make_integer_range<T, Begin, End, 1>
{ };

This would allow:

make_index_range<5> ==> <0, 1, 2, 3, 4>
make_index_range<2, 5> ==> <2, 3, 4>
make_index_range<2, 5, 2> ==> <2, 4>

YMMV on whether or not you want to allow this, but just throwing this out as an option in case you do.

• Morwenn: To be honest about the first point, we probably have different intuitions then: my intuition says « go from there to there with such gap », where a gap is a mere size, but... well, there may be use cases where the other intuition is more convenient, but I still have to learn about them. I like the other points.