Last week when working on an experimental project at my daily job, I remarked that I ended up making lots of range base loops and lots of for loops. These for loops were basically simple 0..K ranges where K was dynamic, then I asked myself if there were Python-like range iterators for sequences instead of for loops in the standard library. I found none. Then I decided to give it a try and code one by myself.

Definition

To achieve the range iteration we first define two helper structs that specify the iteration order.

template < typename T >
struct Incr
{
	inline static bool lt(const T& left, const T& right)
	    { return left < right; }

	inline static void next(T& it) 
	    { ++it; }
};

template < typename T >
struct Decr
{
	inline static bool lt(const T& left, const T& right)
	    { return left > right; }

	inline static void next(T& it) 
	    { --it; }
};

Then we define the range template itself. To respect the range iteration contract, it has to provide two member functions begin and end that return iterators. These iterators are used to initialize the loop. The TRange template is parametrized by the Order policy that specifies the iteration order and how the next value within the range is computed. Additionally for correctness we add a check in the begin function. We have to ensure that begin is smaller than end with respect to the order we use, if this condition is not satisfied then we simply return the end iterator.

template< typename T, 
		  template< typename > class Order = Incr >
class TRange final
{
private:
    struct RangeIt;

public:
    using value_t = T;
	using order_t = Order<T>;

	inline TRange(value_t beg, value_t end)
        : mBegin(beg), mEnd(end) {}
	
    inline RangeIt begin() const
	    { return (order_t::lt(mBegin, mEnd) ? RangeIt(mBegin) : RangeIt(mEnd)); }

    inline const RangeIt end() const
	    { return RangeIt(mEnd); }

private:
    const value_t mBegin, mEnd;

private:
    struct RangeIt final
    {
        inline RangeIt(value_t beg)
			: mBegin(beg) {}

        inline bool operator != (const RangeIt& other) const
            { return mBegin != other.mBegin; }

        inline void operator ++ ()
		    { order_t::next(mBegin); }

        inline value_t operator* () const
            { return mBegin; }

        value_t mBegin;
    };
};

The RangeIt Iterator has to provide an inequality check predicate, the pre-increment operator ++ to get next value, and the dereference operator * to retrieve values. The increment operator uses the ordering policy to get next values which makes it easily customizable.

The last step is to make this range easy to use by inferring argument types and instancing the TRange object. To do so we provide a helper range function.

template< template <typename> class Order = Incr, typename T = int >
inline TRange<T, Order> range(T beg, T end)
{ return TRange<T, Order>(beg, end); }

Usage

Now we can use function range in the for loop.

for (auto i : range(0, 10)) {
	std::cout << i << " ";
}
std::cout << std::endl;

This will print: 0 1 2 3 4 5 6 7 8 9

Of course because we have the order predicate we can have decreasing loops too.

for (auto i : range<Decr>(10, 2)) {
	std::cout << i << " ";
}
std::cout << std::endl;

This will print: 10 9 8 7 6 5 4 3

And we can nest these:

for (int i : range(0, 256)) {
	for (int j : range(i, i*2)) {
		...				
	}
}	

Performance

Using the function range is of course slower in debug builds, however when we enable compiler optimizations and we compare this range based loop to the classic for loop, we observe that:

• if the bounds are constant expressions then the assembly produced is the same for both approaches.
• if the bounds are dynamic for example when nesting loops with dependent bounds, then the assembly is different but there is no noticeable difference in performances.

Both these observations were done using gcc-4.9.2.