Yet another Pythonic range implementation for C++

Question

I recently had the need to loop from zero to some limit only known at runtime. Instead of writing:

for(int i = 0; i < limit; ++i)
{
    // Some repetitive thing
}

I wanted to write something similar to what I often use in Python and D:

for i in range(0, limit):
    # Some repetitive thing

foreach(i; 0 .. limit)
{
    // Some repetitive thing
}

So I ended up with the following:

#include <iterator>

namespace detail
{
    template< typename T >
    class basic_range
    {
    public:
        explicit basic_range(T const last, int const step = 1)
            : basic_range(T{ 0 }, last, step)
        {}

        explicit basic_range(T const first, T const last, int const step = 1)
            : first{ first, last, step }, last{ last, last, step }
        {}

        basic_range(basic_range const& other) = delete;
        basic_range(basic_range && other) = default;
        basic_range operator=(basic_range const& other) = delete;
        basic_range operator=(basic_range && other) = delete;

    public:
        struct iterator : std::iterator< std::forward_iterator_tag, T >
        {
            explicit iterator(T const from, T const to, int const step = T{ 1 })
                : from{ from }, to{ to }, step{ step }
            {}

            iterator(iterator const& other) = default;
            iterator(iterator && other) = delete;
            iterator operator=(iterator const& other) = delete;
            iterator operator=(iterator && other) = delete;

            T const operator*() const { return from; }

            bool operator==(iterator const& other) const { return from == other.from; }
            bool operator!=(iterator const& other) const { return from != other.from; }

            void operator++()
            {
                from += step;
                check_limit();
            }

        private:
            void check_limit()
            {
                if (step > 0)
                {
                    if (from > to)
                    {
                        from = to;
                    }
                }
                else
                {
                    if (from < to)
                    {
                        from = to;
                    }
                }
            }

        private:
            T         from;
            T   const to;
            int const step;
        };

        typedef iterator       iterator;
        typedef iterator const const_iterator;

        const_iterator begin() const { return first; }
        const_iterator end()   const { return last; }

    private:
        const_iterator first;
        const_iterator last;
    };

    template< typename T, bool is_enum = std::is_enum< T >::value >
    struct get_integral_type
    {
        typedef std::underlying_type_t< T > type;
    };

    template< typename T >
    struct get_integral_type< T, false >
    {
        typedef T type;
    };

    template< typename T, bool is_enum = std::is_enum< T >::value >
    using get_integral_type_t = typename get_integral_type< T >::type;
}

With some supporting functions to aid in constructing a range:

template< typename T >
auto range(T const begin, T const end, int const step = 1)
{
    typedef detail::get_integral_type_t< T > type;

    static_assert(std::is_integral< type >::value,
                  "Only integer-based types allowed!");

    return detail::basic_range< type >{
        static_cast<type>(begin),
        static_cast<type>(end),
        step
    };
}

template< typename T, typename U >
auto range(T const begin, U const end, int const step = 1)
{
    typedef std::common_type_t
    <
        detail::get_integral_type_t< T >,
        detail::get_integral_type_t< U >
    > type;

    static_assert(std::is_integral< type >::value,
                  "Only integer-based types allowed!");

    return detail::basic_range< type >{
        static_cast<type>(begin),
        static_cast<type>(end),
        step
    };
}

template< typename T >
auto reverse_range(T const from, T const to, int const step = -1)
{
    return range(from, to, step);
}

template< typename T, typename U >
auto reverse_range(T const from, U const to, int const step = -1)
{
    return range(from, to, step);
}

This allows for syntax very close to the Python version:

for(auto const i: range(0, limit))
{
    // Some repetitive task
}

I am, so far, pleased with how well it works both forwards and backwards, however, I feel that the iterator implementation is sloppy and, since documentation on correct iterator implementation is hard to come by, I turn to the community to help me further refine this design. Of course, you are free to pick holes elsewhere. For example, I should probably check the inputs to the range functions before blindly returning an object that will misbehave...

A more complete example of usage can be found here which includes some simple unit tests to help debug the code. Any insights are appreciated

Answer 1

So I came up with a solution that should be as fast a "normal" loop. As already discussed your main problem is the check_limits function that is called on every iteration.

I removed the check (see Change 4 comments) and instead added a function to calculate a range that is compatible with the size of step (see Change 1 comments).

This function is now used instead of just using T last (see Change 2 comments).

Also: To prevent someone from messing around with the iterator I made the constructor private and added basic_range<T> as friend class (see Change 3 comments).

#include <iterator>

namespace detail
{
    template< typename T >
    class basic_range
    {
    private:

        //Change 1: Calculate end
        static T adjustedLast(T const first, T const last, T const step)
        {
            //Using modulo on signed types is UB
            using UT = typename std::make_unsigned<T>::type;
            UT difference = std::abs(last - first);
            UT stepping = std::abs(step);

            T underflow = T(difference % stepping) * (step / T(stepping));
            if (underflow == 0) return last;

            return last + (step - underflow);
        }

    public:
        explicit basic_range(T const last, T const step = 1)
            : basic_range(T{ 0 }, last, step)
        {}

        explicit basic_range(T const first, T const last, T const step = 1)
            : first{ first, adjustedLast(first, last, step), step }, last{ adjustedLast(first, last, step), adjustedLast(first, last, step), step } //Change 2: use calculated last
        {}

        basic_range(basic_range const& other) = delete;
        basic_range(basic_range && other) = default;
        basic_range operator=(basic_range const& other) = delete;
        basic_range operator=(basic_range && other) = delete;

    public:
        struct iterator : std::iterator< std::forward_iterator_tag, T >
        {
            //Change 3: Make constructor private
            friend class basic_range<T>;

        private: //Change 3: Make constructor private
            explicit iterator(T const from, T const to, int const step = T{ 1 })
                : from{ from }, to{ to }, step{ step }
            {
            }

        public:
            iterator(iterator const& other) = default;
            iterator(iterator && other) = delete;
            iterator operator=(iterator const& other) = delete;
            iterator operator=(iterator && other) = delete;

            T const operator*() const { return from; }

            bool operator==(iterator const& other) const { return from == other.from; }
            bool operator!=(iterator const& other) const { return from != other.from; }

            void operator++()
            {
                from += step;
                //Change 4: Remove check()
            }


            //Change 4: Remove check()

        private:
            T         from;
            T   const to;
            int const step;
        };

        typedef iterator       iterator;
        typedef iterator const const_iterator;

        const_iterator begin() const { return first; }
        const_iterator end()   const { return last; }

    private:
        const_iterator first;
        const_iterator last;
    };

    template< typename T, bool is_enum = std::is_enum< T >::value >
    struct get_integral_type
    {
        typedef std::underlying_type_t< T > type;
    };

    template< typename T >
    struct get_integral_type< T, false >
    {
        typedef T type;
    };

    template< typename T, bool is_enum = std::is_enum< T >::value >
    using get_integral_type_t = typename get_integral_type< T >::type;
}

template< typename T >
auto range(T const begin, T const end, int const step = 1)
{
    typedef detail::get_integral_type_t< T > type;

    static_assert(std::is_integral< type >::value,
        "Only integer-based types allowed!");

    return detail::basic_range< type >{
        static_cast<type>(begin),
            static_cast<type>(end),
            step
    };
}

template< typename T, typename U >
auto range(T const begin, U const end, int const step = 1)
{
    typedef std::common_type_t
        <
        detail::get_integral_type_t< T >,
        detail::get_integral_type_t< U >
        > type;

    static_assert(std::is_integral< type >::value,
        "Only integer-based types allowed!");

    return detail::basic_range< type >{
        static_cast<type>(begin),
            static_cast<type>(end),
            step
    };
}

template< typename T >
auto reverse_range(T const from, T const to, int const step = -1)
{
    return range(from, to, step);
}

template< typename T, typename U >
auto reverse_range(T const from, U const to, int const step = -1)
{
    return range(from, to, step);
}

#include <iostream>

int main()
{
    for (auto const i : range(0, -100, -3))
    {
        std::cout << i << std::endl;
    }
}

---

The new function adjustedLast might seem a little bit difficult in the beginning. All it does is to calculate the next step equal or greater than the current last in the direction of step:

//Change 1: Calculate end
static T adjustedLast(T const first, T const last, T const step)
{
    //Using modulo on signed types is UB
    using UT = typename std::make_unsigned<T>::type;
    UT difference = std::abs(last - first);
    UT stepping = std::abs(step);

    T underflow= T(difference % stepping) * (step / T(stepping));
    if (underflow== 0) return last;

    return last + (step - underflow);
}

using UT = typename std::make_unsigned<T>::type; is used to get the unsigned equivalent of T as the function makes use of the modulo operator. Modulo operations on signed types is UB.

Next is to get the difference between first an last and store it in the unsigned type. This is perfectly fine since std::abs will only return positive values. Also we are getting the absolute value of step.

It doesn't matter if we are going from 0 to 1000 in steps of 5 or from 1000 to 0 in steps of -5... all we need is if we exactly hit last when iterating.

difference % stepping will give us this value. e.g. when using range(0,100,3) the last value we hit is 99 which is 1 short of 100. difference % stepping will give us this 1.

What we need now is the value being signed again in the direction of step. step / T(stepping) will return -1 if step is negative and 1 if step is positve.

If there is no underflow if (underflow== 0) we can just return the last we were provided with. Otherwise we need to calculate the next last that can be "hit" with step. So we use (step - underflow) to find the difference we need and add it to last.

Example:

adjustedLast(0,100,3)

• difference = 100
• stepping = 3
• underflow = (100%3) * (3/3) = 1 * 1 = 1
• returns: 100 + (3-1) = 102

adjustedLast(0,-100,-3)

• difference = 100
• stepping = 3
• underflow = (100%3) * (-3/3) = 1 * -1 = -1
• returns: -100 + (-3-(-1)) = -100 + (-3+1) = -102

---

Comparing the new code to a normal for loop with the same range actually shows us no difference in compiler instructions:

for (int i = 0; i < 100; i+=1)

std::ctype<char>::do_widen(char) const:
        mov     eax, esi
        ret
main:
        push    r12
        push    rbp
        xor     ebp, ebp
        push    rbx
        jmp     .L6
.L14:
        movsx   esi, BYTE PTR [rbx+67]
.L5:
        mov     rdi, r12
        add     ebp, 1
        call    std::basic_ostream<char, std::char_traits<char> >::put(char)
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >::flush()
        cmp     ebp, 100
        je      .L12
.L6:
        mov     esi, ebp
        mov     edi, OFFSET FLAT:std::cout
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        mov     r12, rax
        mov     rax, QWORD PTR [rax]
        mov     rax, QWORD PTR [rax-24]
        mov     rbx, QWORD PTR [r12+240+rax]
        test    rbx, rbx
        je      .L13
        cmp     BYTE PTR [rbx+56], 0
        jne     .L14
        mov     rdi, rbx
        call    std::ctype<char>::_M_widen_init() const
        mov     rax, QWORD PTR [rbx]
        mov     esi, 10
        mov     rax, QWORD PTR [rax+48]
        cmp     rax, OFFSET FLAT:std::ctype<char>::do_widen(char) const
        je      .L5
        mov     rdi, rbx
        call    rax
        movsx   esi, al
        jmp     .L5
.L12:
        pop     rbx
        xor     eax, eax
        pop     rbp
        pop     r12
        ret
.L13:
        call    std::__throw_bad_cast()
        sub     rsp, 8
        mov     edi, OFFSET FLAT:std::__ioinit
        call    std::ios_base::Init::Init()
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:std::__ioinit
        mov     edi, OFFSET FLAT:std::ios_base::Init::~Init()
        add     rsp, 8
        jmp     __cxa_atexit

for (auto const i : range(0, 100))

std::ctype<char>::do_widen(char) const:
        mov     eax, esi
        ret
main:
        push    r12
        push    rbp
        xor     ebp, ebp
        push    rbx
        jmp     .L6
.L14:
        movsx   esi, BYTE PTR [rbx+67]
.L5:
        mov     rdi, r12
        add     ebp, 1
        call    std::basic_ostream<char, std::char_traits<char> >::put(char)
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >::flush()
        cmp     ebp, 100
        je      .L12
.L6:
        mov     esi, ebp
        mov     edi, OFFSET FLAT:std::cout
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        mov     r12, rax
        mov     rax, QWORD PTR [rax]
        mov     rax, QWORD PTR [rax-24]
        mov     rbx, QWORD PTR [r12+240+rax]
        test    rbx, rbx
        je      .L13
        cmp     BYTE PTR [rbx+56], 0
        jne     .L14
        mov     rdi, rbx
        call    std::ctype<char>::_M_widen_init() const
        mov     rax, QWORD PTR [rbx]
        mov     esi, 10
        mov     rax, QWORD PTR [rax+48]
        cmp     rax, OFFSET FLAT:std::ctype<char>::do_widen(char) const
        je      .L5
        mov     rdi, rbx
        call    rax
        movsx   esi, al
        jmp     .L5
.L12:
        pop     rbx
        xor     eax, eax
        pop     rbp
        pop     r12
        ret
.L13:
        call    std::__throw_bad_cast()
        sub     rsp, 8
        mov     edi, OFFSET FLAT:std::__ioinit
        call    std::ios_base::Init::Init()
        mov     edx, OFFSET FLAT:__dso_handle
        mov     esi, OFFSET FLAT:std::__ioinit
        mov     edi, OFFSET FLAT:std::ios_base::Init::~Init()
        add     rsp, 8
        jmp     __cxa_atexit