12
\$\begingroup\$

This is a follow-up of an old question by @LokiAstari, modified for the current community challenge. The idea is to provide a compile-time integer range. I applied all the modifications that I proposed to Loki at the time and tried to write a class as close as possible to the standard library class std::integer_sequence:

  • This is a [begin, end) range instead of a [begin, end] one.
  • The range can be ascending or descending.
  • The class is templated so that it is possible to choose the integer type to use.
  • In order to match the standard library utilities, I also provide the template index_range which is an alias of integer_range for the type std::size_t.

Here is the implementation:

#include <cstddef>
#include <tuple>
#include <type_traits>
#include <utility>

namespace details
{
    ////////////////////////////////////////////////////////////
    // implementation details

    template<typename Int, typename, Int Begin>
    struct increasing_integer_range;

    template<typename Int, Int... N, Int Begin>
    struct increasing_integer_range<Int, std::integer_sequence<Int, N...>, Begin>:
        std::integer_sequence<Int, N+Begin...>
    {};

    template<typename Int, typename, Int Begin>
    struct decreasing_integer_range;

    template<typename Int, Int... N, Int Begin>
    struct decreasing_integer_range<Int, std::integer_sequence<Int, N...>, Begin>:
        std::integer_sequence<Int, Begin-N...>
    {};
}

////////////////////////////////////////////////////////////
// integer_range

template<typename Int, Int Begin, Int End,
         bool Increasing=(Begin<End)>
struct integer_range;

template<typename Int, Int Begin, Int End>
struct integer_range<Int, Begin, End, true>:
    details::increasing_integer_range<
        Int,
        std::make_integer_sequence<Int, End-Begin>,
        Begin>
{};

template<typename Int, Int Begin, Int End>
struct integer_range<Int, Begin, End, false>:
    details::decreasing_integer_range<
        Int,
        std::make_integer_sequence<Int, Begin-End>,
        Begin>
{};

template<std::size_t Begin, std::size_t End>
using index_range = integer_range<std::size_t, Begin, End>;

I don't ask for a specific kind of review. If you see anything that can be improved, do not hesitate.


And as a bonus, take this test cases. Since integer_range uses some heavy template wizardry, I had troubles coming with decent test cases that are easy enough to read, write and understand. They are not really beautiful, but they work as expected; that may help you if you want to try modifications:

template<std::size_t N>
void test(std::integer_sequence<int>)
{
    static_assert(N == 0, "");
}

template<std::size_t N>
void test(std::integer_sequence<int, 0, 1, 2, 3, 4>)
{
    static_assert(N == 1, "");
}

template<std::size_t N>
void test(std::integer_sequence<int, 5, 4, 3, 2, 1>)
{
    static_assert(N == 2, "");
}

template<std::size_t N>
void test(std::integer_sequence<int, -3, -2, -1, 0, 1>)
{
    static_assert(N == 3, "");
}

template<std::size_t N>
void test(std::integer_sequence<int, -1, -2, -3>)
{
    static_assert(N == 4, "");
}

template<std::size_t N>
void test(std::integer_sequence<int, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7>)
{
    static_assert(N == 5, "");
}

int main()
{
    using namespace polder;

    test<0>(integer_range<int, 8, 8>());
    test<1>(integer_range<int, 0, 5>());
    test<2>(integer_range<int, 5, 0>());
    test<3>(integer_range<int, -3, 2>());
    test<4>(integer_range<int, -1, -4>());
    test<5>(integer_range<int, 3, -8>());
}

Note: if you're interested, I wrote a follow-up to this question which incorporates most of the suggestions from the accepted answer and adds the possibility to specify a Step parameter.

\$\endgroup\$
  • \$\begingroup\$ In python, there is a convenient range(start, end, increment) and slicing notation list[start:end:increment] which also supports negative numbers and wraparound. Perhaps you could extend your C++ integer sequence implementation to do something similar? \$\endgroup\$ – mleyfman Aug 5 '14 at 4:03
  • \$\begingroup\$ @mleyfman The problem with the increment is that there are non-obvious design choices to make for the increment: in Python, range(5, 1) won't return anything, while integer_range<5, 1> will be a std::integer_sequence<5, 4, 3, 2>. That means that either I have to choose whether ranges with a bad increment (e.g. negative increment for ascending range) yield an empty range or whether the increment is always positive (as it is now, but extended to any positive integer). \$\endgroup\$ – Morwenn Aug 5 '14 at 7:00
  • 2
    \$\begingroup\$ I think template<typename Int, /*other stuff*/> is misleading at a passing glance; people used to seeing int may overlook the typename part and think it's an integer param rather than a type param. If you are designing this to accept non integer numeric types, then you should change typename Int into typename Number or typename TNumeric or something suitably similar. \$\endgroup\$ – Pharap Aug 5 '14 at 9:55
  • \$\begingroup\$ @Pharap The standard goes with template<typename T, /* other stuff */>. That could be both simple and sufficient. \$\endgroup\$ – Morwenn Aug 6 '14 at 15:47
4
\$\begingroup\$

IMO, your test cases would be vastly more readable if you wrote them simply in terms of std::is_same. If you were going to write a lot of test cases, you could wrap all that boilerplate up in a macro such as

#define TEST(type, start, end, ...) \
    static_assert(std::is_same< \
        polder::integer_range<type, start, end>, \
        std::integer_sequence<type ,##__VA_ARGS__ > >::value)

which reduces your test cases to the tiny amount of code they actually are.

TEST(int, 8,8);
TEST(int, 0,5, 0,1,2,3,4);
TEST(int, 5,0, 5,4,3,2,1);
TEST(int, -3,2, -3,-2,-1,0,1);
TEST(int, -1,-4, -1,-2,-3);
TEST(int, 3,-8, 3,2,1,0,-1,-2,-3,-4,-5,-6,-7);

This shorter formulation incidentally makes it more obvious that you didn't test any corner cases or types other than int — which is why I'm a strong proponent of "shorter code is better code." We've now made the code short enough that we can see where the bugs are.

Okay, let's move on to looking at the actual code. It actually looks very clean and simple. Admittedly I did think at first that you were doing the bad O(n) approach where integer_range<N> inherits from integer_range<N-1>; it took me a moment to see that you were in fact doing the right thing. I see only two issues with

template<typename Int, Int... N, Int Begin>
struct increasing_integer_range<Int, std::integer_sequence<Int, N...>, Begin>:
    std::integer_sequence<Int, N+Begin...>
{};

The first problem is that our new test cases don't pass, because your increasing_integer_range is not actually a synonym for std::integer_sequence; instead it's merely derived from std::integer_sequence. This is good enough for the average codebase, but for a library implementation we'd want to make sure that the two types are actually equal. Fortunately, C++11 template typedefs make this easy. Rewrite it as

namespace details
{
    template<typename Int, typename, Int Begin, bool Increasing>
    struct integer_range_impl;

    template<typename Int, Int... N, Int Begin>
    struct integer_range_impl<Int, std::integer_sequence<Int, N...>, Begin, true> {
        using type = std::integer_sequence<Int, N+Begin...>;
    };

    template<typename Int, Int... N, Int Begin>
    struct integer_range_impl<Int, std::integer_sequence<Int, N...>, Begin, false> {
        using type = std::integer_sequence<Int, Begin-N...>;
    };
}

template<typename Int, Int Begin, Int End>
using integer_range = typename details::integer_range_impl<
    Int,
    std::make_integer_sequence<Int, (Begin<End) ? End-Begin : Begin-End>,
    Begin,
    (Begin<End) >::type;

template<std::size_t Begin, std::size_t End>
using index_range = integer_range<std::size_t, Begin, End>;

The second problem is that this implementation does not work for some obvious corner cases, such as integer_range<int, INT_MIN, INT_MAX>, because in general the result of End-Begin is not guaranteed to be representable in Int.

Fixing the second problem is left as an exercise for the reader, because I believe it's pretty darn hard. I think you might have to abandon the (really clever) idea of using std::integer_sequence to do your heavy lifting, and resign yourself to reimplementing integer_sequence something like Xeo did here except harder.

EDIT TO ADD a third "problem" I just thought of: The name integer_range could be considered misleading. If I were proposing this for the standard library, I'd name it make_integer_range, by analogy with make_integer_sequence.

\$\endgroup\$
  • \$\begingroup\$ Thanks. The tests are actually simpler to write with std::is_same once *_integer_range are really std::integer_range<something>. Your comments were really valuable :) \$\endgroup\$ – Morwenn Oct 4 '14 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.