Design review

So the goal is to recreate Python’s range type. This isn’t a bad idea, and could even be useful in current versions of C++ that have views::iota, because views::iota doesn’t have a customizable step. range is also always bounded, so it can be less complex than views::iota in that sense at least.

Because the requirements restrict us to C++17, we are severely crippled in what we can do. Nevertheless, we have to presume the intention is not to write code that we’ll use for a year or two and then dump in the trash because we finally got C++20 support. In other words, even though we must support C++17, we should still target C++20 (and, nowadays, C++23), and beyond. “I’m stuck in C++17” is not an excuse to be lazy, and ignore the fact that we are no longer living in the year 2017 and C++ has moved on.

So even though we cannot make a C++20-compatible range… we should still try to get as close as possible, and maybe even have conditional support so that in C++20, it will be a C++20-compatible range. At the very least, we should take design cues from C++20 (and beyond) ranges (or maybe coroutines), because people much smarter than us have already tackled this problem and moved beyond it. It would behoove us to learn from their progress.

The iterator is severely restricted

Consider a reasonable use case for this (I’m using modern code to illustrate because it’s simpler, but the issues exist in C++17 too):

Range(10000) | std::ranges::to<vector>;
// produces a vector<int> with contents [0.. 9999]

This innocuous code is surprisingly evil.

The reason is that the iterators produced by range are severely restricted. There is no logical reason why they cannot model the random-access iterator concept. In this case, the start value is 0 and the one-past-end value is 10000, so you know the number of iterations will be 10 000 (\$10000 - 0\$). More generally, it will be \$\left\lceil \left( STOP - START \right) \div STEP \right\rceil\$. Because you can know this analytically, ranges::to<vector> could do a single allocation when creating the vector.

However, because RangeIterator doesn’t model random-access, the vector will have to be constructed piece-by-piece, with dozens of allocations.

But it gets worse.

The iterator is not even an iterator

Using C++20 concepts, we can do some quick tests on RangeIterator… and… it fails every one of them. Not only does it not meet even the most basic, minimal requirements to be a valid iterator, it doesn’t even satisfy weakly_incrementable.

To figure out what’s going on, we can start by analyzing the weakly_incrementable requirements. The movable requirement is not a problem. Neither are the ++i or i++ requirements; RangeIterator has those. So the problem is likely that iter_difference_t<RangeIterator> doesn’t yield a valid type. What does iter_difference_t require? Well, iterator_traits<RangeIterator> isn’t specialized, so it uses incrementable_traits<RangeIterator>. And there’s the problem.

Of the 4 ways that incrementable_traits can be satisfied:

• RangeIterator is not a pointer (case 2)
• RangeIterator is not const qualified (case 3)
• RangeIterator does not have a nested difference_type (case 4)
• RangeIterator is not subtractible (case 5)

So as far as standard C++ is concerned, RangeIterator is not incrementable. Yes, it supports the increment operators, but that does not mean it’s incrementable. (Much in the same way that IOstreams support the bit shift operators, but are not bit-shiftable.)

So, to start to bring RangeIterator up to par, you first need to include the standard iterator type aliases:

• difference_type
• value_type
• pointer
• reference
• iterator_category

Adding difference_type alone will make RangeIterator satisfy weakly_incrementable and the basic iterator concept (input_or_output_iterator)… but not yet input_iterator.

The next step to satisfying input_iterator is indirectly_readable. This requires quite a bit, but it turns out that just adding value_type allows iterator_traits to guess the rest, and that’s enough to get you a valid input iterator. Still, you should really define all the aliases.

Once you get to input iterator, you’re probably already a forward iterator, so to go further you need to start adding new functionality, like operator-- and the random-access stuff.

This should be two types

Supporting steps sizes other than one is a good thing… but it comes at a cost.

Consider the difference between ++_cursor and _cursor += _step. The former is a single load, a single increment, then a store (which can be done with a single instruction at least on x86-64). The latter is two loads (one for _cursor, one for _step), an add, then a store. This is true even if _step is 1.

Considering that the primary use case will be with a step of 1 (which is why the step argument is not only last, it’s defaulted), that means you are making majority of users pay for complexity they don’t need. Trying to shoehorn everything into a single type may make things simpler for you, the library writer… but the users of the library will pay for it. And that’s always the wrong calculus; it should always be the library writer who has to work harder, so the users can reap the benefits.

Range should be a function, not a class (and… with a different name, obviously). Actually, a set of functions:

auto range(auto)             -> simple_range_t;
auto range(auto, auto)       -> simple_range_t;
auto range(auto, auto, auto) -> complex_range_t;

Where simple_range_t just uses ++, and complex_range_t uses += with a step value. simple_range_t will be… well… simple. And also much more efficient than complex_range_t. complex_range_t will be more-or-less what you have now.

Numeric issues

You mention that you want to support floating point types. To that I say: 😬

I don’t think you appreciate what it would mean to use something like this with floating point types. You will end up with absurdities similar to this (not exactly this, but I can’t be arsed to do the research to find example numbers that will actually do this):

Range(0.0, 5.0, 1.0) → produces → 0, 1, 2, 3, 4
Range(0.0, 4.0, 1.0) → produces → 0, 1, 2, 3, 4

Wut? 🤨

How could this happen? Well, remember that floating point numbers are not exact, and their “exactness” gets worse the more math operations you perform on them. When you have a floating point number 3.0 and you add 1.0 to it… you may not necessarily get 4.0. You may get 4.000001 or 3.999999.

It gets worse. Consider this:

Range(1.0e10, 1.1e10, 1.0) → produces → endless loop of 100 000 000 000

Again, wut? 🤨

Well, when numbers get large, they lose precision. 1.0e10 may be theoretically, mathematically 100 000 000 000, but if the value only has 9 decimal digits of precision, those last three zeroes are not really “there”. So when you do 100 000 000 000 + 1, you don’t get 100 000 000 001, because the last three digits are truncated. So you get effectively 100 000 000 000. Or in other words: (100 000 000 000 + 1) = 100 000 000 000. So doing (100 000 000 000 + 1) over and over 10 000 000 000 times will never get you to 110 000 000 000. That’s mathematically nonsensical, but that’s how floating points roll.

My advice: don’t fuck with floats. There is a good reason why neither std::views::iota nor Python’s range support floating point numbers.

Now, even if you stick with integers, you’re still not entirely safe, because unlike mathematical integers, computer integers have a finite range. You need to be careful of edge cases where you approach numeric_limits<T>::max().

Let’s keep the numbers small and think of a signed 8-bit type, so the max value is 127. Let’s say your start value is 0, your stop value is 150, and your step is 100. So the first value will be 0, and the second will be 100. No problems so far.

But then you do operator++ again… and now… 100 + 100 is 200… which overflows 127. That right there is UB. Game over.

Okay, but what if you used unsigned integers. In that case, the overflow would wrap around, and give you a small number. So you could get a sequence like: 0, 100, 73, 46, 19, 119, 92, 65, 38, ….

Now you see why C++ never standardized an iota with a step.

This is not impossible to deal with, but you need to be VERY CAREFUL. Your code is not, currently, very careful.

So you can’t simply keep incrementing and then check whether you’ve blown past the stop value. Indeed, in the general case, you can’t allow going past the stop value at all. Because, what if the stop value is numeric_limits<T>::max()?

I am not going to design a solution, but I suppose one possible direction would be to store: the current value, the step, the last valid value, and a flag indicating overflow. Then, at each increment, you just check whether (_last - _cursor) < _step. If no, then _cursor += _step. Otherwise, set the overflow flag. Then when you compare, everything compares less than overflow (except overflow equals overflow, obviously), and anything else is just a normal comparison of _cursor.

That’s just a basic idea, and you’d need to take into account complexities like negative steps and what happens if there are no valid values at all (an empty range? an error?).

Terminology

I know Python calls this type a “range”, but “range” means something different in C++. The situation is this: either you’re going to confuse Python coders (by calling it something other than “range”), or you’re going to confuse C++ coders (by calling it “range”). You have to choose which group to frustrate… but may I point out that this is C++ code… so, if you’re going to confuse people, it makes far less sense to confuse the C++ people than the Python people.

Answering issues

The RangeIterator class operator "!=" needs to perform three comparisons. One could possibly refactor the "_step > 0" comparison into a template parameter but I am not sure if it is worth it.

The comparison is currently broken, as mentioned above, because you are not taking integer over/underflow into consideration. (And don’t even get started with the floating point stuff!)

My advice would be to do all the heavy lifting at construction time, and keep the iteration as simple and cheap as possible. I mentioned a scheme using a flag above. With that scheme, at construction time, you would calculate the last valid value that can be reached, then store that rather than the requested stop value.

So, for example, for Range(0, 5, 2), you calculate ((5 - 0) / 2) to get the number of steps 2 (integer division), then multiply that by the step size (2 * 2) + 0 to get the final value 4. Now you store that in the iterator, along with the step and the current value (which will be 0 for begin, and equal to the final value for end), and also set the past-the-end flag for the end iterator.

With that data encoded, you can trivially calculate the distance between any two iterators (just the two current values divided by the step, but do keep the end flag in mind). You can also iterate backward from end to beginning… something you currently can’t do if you just store the given stop value.

Of course, there are more complications to consider, like a negative step. But that should give you random-access iterators, and save you from over/underflow worries.

I don’t see the point of encoding _step > 0 as a template parameter. If you’re going to do that, you might as well encode _step, period.

Currently, all three constructor arguments are of template parameter type. This sounds sensible at first but it makes writing some code ugly. E.g.

std::vector<int> v{1, 2, 3, 4};
for (auto n : stdx::Range{0, v.size(), -1})
    std::cout << n << "\n";

will not compile as -1 is deduced as int and v.size() as size_t, of course. One would have to static_cast the v.size() which kind of defeats the purpose of writing short and concise code, imho. Maybe it is an idea to make the "step" parameter to be an int32_t and drop support for floating point iteration. I am not sure if this is a usecase at all?

I don’t really see why it’s necessary to have a single template parameter. Why not:

template <
    typename Start,
    typename Stop = Start,
    typename Step = Start
>
class Range

Or, even better would be if range() were a function, not a class, that took three potentially different types and then calculated the common type. So

template <typename T, typename U, typename V>
auto range(T start, U stop, V step) -> Range<std::common_type_t<T, U, V>>;

In any case, hard-coding the step int32_t is absurd, for a lot of reasons (not least being that int32_t is an optional type that is not guaranteed to be supported). The loss of ability to have fraction steps is not one of those reasons, because supporting floating point types at all is the path to madness.

Code review

namespace stdx

It’s good that you’re putting your code in a namespace. But this namespace is not a good idea.

It is technically legal just by virtue of x being a letter and not a digit, but still, namespace stdx is conventionally used for things being proposed for the standard library. If you were proposing Range for standardization, then stdx would make sense. But you are clearly not; it wouldn’t even work as a first draft of an idea because it defies standard conventions (type names are snake_case not PascalCase).

template<typename T>
struct RangeIterator {

It doesn’t really make a lot of sense for this type to be independent of the range type. It should be a nested type.

    constexpr RangeIterator(T cursor, T stop, T step)
        : _cursor{cursor}
        , _stop{stop}
        , _step{step}
    {}

It shouldn’t be possible for any rando to construct these iterators. This constructor should be private, and the range class should be a friend.

The exception is that iterators are usually default constructible. I don’t know how you’d manage that here (it may be possible with the overflow flag idea), and it’s not required, so you should decide whether you want to allow it.

    constexpr RangeIterator& operator++() noexcept
    {
        _cursor += _step;
        return *this;
    }

As mentioned above, watch out for integer over/underflow when doing that unconditional add.

    [[nodiscard]] constexpr bool operator!=(const RangeIterator &other) const noexcept
    {
        return _step > 0 ? (_cursor < other._stop || other._cursor < _stop)
                         : (_cursor > other._stop || other._cursor > _stop);
    }

You’ve kinda painted yourself into a corner with your design here. Apparently, all RangeIterator value objects are never equal… except when both of them are past their stop value. But that’s obviously nonsense. It’s certainly not what “equal” means.

Additionally, having operator!= but not having operator==… little weird. You’ve obviously coded with a very, very narrow use case in mind, and ignored the bigger picture of what all this stuff means.

};

You don’t need to close namespaces with a semicolon, and in fact you should not do that, because some people compile with “warn on unnecessary semicolons” and “warnings are errors”. You would break their builds, for no good reason.

        if (step == T{})
            throw std::runtime_error{"stdx::Range step must be != 0"};

This is not a runtime error, it is a logic error. Specifically, it is an invalid_argument error.

Runtime errors are errors that can only be detected at run time. For example, a file being missing, or running out of memory, or the network being down; there is no code you can write that can protect you from running into one of those situations.

Logic errors are avoidable errors, simply by doing a check before trying an operation. In this case, all you’d need to do is check that the step is not zero before attempting to create the range.

If the programmer should be responsible for preventing the error, it’s a logic error; if the user should be responsible for preventing the error, it’s a runtime error.

I’m not going to review the test code, because I’m not a fan of GoogleTest. I will point out two things, though.

First, this pattern is unwise:

    std::vector<int> x;
    for (auto it = range.begin(); it != range.end(); ++it)
    {
        x.push_back(*it);
    }
    EXPECT_EQ(rangeVec, x);

    x.clear();
    for (auto it = range.begin(); it != range.end(); it++)
    {
        x.push_back(*it);
    }
    EXPECT_EQ(rangeVec, x);

    x.clear();
    for (auto it = range.begin(); range.end() != it; it++)
    {
        x.push_back(*it);
    }
    EXPECT_EQ(rangeVec, x);

Re-clearing and re-using the same vector over and over is brittle, and asking for trouble. The x.clear()s are hard to spot, and thus, easy to forget. A better pattern would be this:

TEST(RangeTest, byIteratorBackward) {
    auto const range = stdx::Range{3, -3, -1};
    auto const rangeVec = createVec(range);

    {
        std::vector<int> x;
        for (auto it = range.begin(); it != range.end(); ++it)
        {
            x.push_back(*it);
        }
        EXPECT_EQ(rangeVec, x);
    }

    {
        std::vector<int> x;
        for (auto it = range.begin(); it != range.end(); it++)
        {
            x.push_back(*it);
        }
        EXPECT_EQ(rangeVec, x);
    }

    {
        std::vector<int> x;
        for (auto it = range.begin(); range.end() != it; it++)
        {
            x.push_back(*it);
        }
        EXPECT_EQ(rangeVec, x);
    }

Note the const qualifiers on the objects that are reused.

The second thing I’m going to point out is that you have a lot of tests… but you test very little. Ultimately all you test are:

1. using the range in a range-for loop; and
2. getting the iterators and doing a simple, straight-though class for loop

… which are both really the same thing (a range-for is just a sugared classic for).

Indeed, most of the tests are literally identical except for the arguments and expected result. That is, the structure is identical. You basically only have two or three different tests, but each is done with a whole tone of different values.

I don’t use GoogleTest, so I don’t know what facilities it offers off-hand, but most test frameworks will allow you to do something like this:

struct three_arg_test_case_values_t
{
    int start;
    int stop;
    int step;
    std::vector<int> expected;
};

auto const three_arg_test_values = std::to_array<three_arg_test_case_values_t>({
    {-2,  3,  1, {-2, -1, 0, 1, 2}},
    { 0,  5,  1, {0, 1, 2, 3, 4}},
    { 2,  7,  1, {2, 3, 4, 5, 6}},
    // ... etc.
});

TEST(start_stop_step_case, three_arg_test_values, v)
{
    auto const rangeVec = createVec(stdx::Range{v.start, v.stop, v.step});

    EXPECT_EQ(rangeVec, v.expected);
}

TEST(by_iterator_case, three_arg_test_values, v)
{
    auto const range = stdx::Range{v.start, v.stop, v.step};

    std::vector<int> x;
    for (auto it = range.begin(); it != range.end(); ++it)
    {
        x.push_back(*it);
    }

    EXPECT_EQ(x, v.expected);
}

Fill in the test case data array, and that’s pretty much all of your StartStopStepForward, StartStopStepBackward, StartStopStepEmpty, byIteratorForward, and byIteratorBackward test cases… or about 80–85% of your test code. All you need for the rest are data sets for the one- and two-argument cases, and test cases for those. And it’s much simpler, which is good, because test code should be simple.

Basically, structure your testing like this: just set up a massive ton of data—arguments and expected value(s)—then use it in a bunch of very simple tests. Data is easy to set up, and very unlikely to have coding errors that will fuck up your tests (generally, if it compiles, it’s fine, unless you put the wrong data in, but in that case, even manually written-out tests would be wrong). Then the tests can be absolutely minimal, and you can write a bunch of them, and they will all get run with a fuck-ton of data, which will increase coverage, and confidence.