Pythonic ranges in C++11

tl;dr: Implemented an efficient Python-style range() in C++11, then extended it to support floats. It’s MIT licensed and has no dependencies. Check it out on my github page.

C++11 may have directly grown out of the efforts of the Boost libraries, but philosophically the newest iteration of C++ reminds me most of Python. The new for-loop syntax exemplifies this. Let’s be honest: iterators are brilliant, but using them was always a bit of a chore. Now compare this C++ snippet using the new for-each syntax against a Python equivalent:

for(int i:some_vector){
    cout<<i<<endl;
}
for i in some_list:
    print i

Python doesn’t even have the traditional C-style for loop, instead using the range() function. C++ lacks an equivalent, but we can add it.

A naive implementation

Since we’ve already used the for-each syntax with vectors, we can easily create a range function that returns a vector containing the integers in the range:

[gist https://gist.github.com/aduchene/5182635 /]

and then use it like this:

[gist https://gist.github.com/aduchene/6ed67affd95c1517fd6d]

This has a two main problems. The first, functionality, could be easily fixed by adding support for a beginning value and a variable step size. But the more important is efficiency. Even though we only use a single value at a time, the entire range is allocated. This won’t have much of an effect if the vector is small, but if your iterating over a million elements…

Iterators to the rescue

Although iterators are introduced as a tool for existing collections of data, there’s no reason they have to be. We can write an iterator to generate elements in our range on the fly like Python’s xrange. Before we start coding, let’s think about what we need. Under the hood, the C++11 for-each loop is just syntactic sugar for the traditional begin()/end() method. So, our range class must satisfy 3 requirements:

  1. Implement a begin() function that returns an iterator to the first element of the range
  2. Provide a way to compare an iterator against the end of the range
  3. Allow forward traversal of the range

Now we can get down to implementation.  Since writing iterators from scratch is difficult the standard library provides the std::iterator class as a base for user implemented iterators.

[gist https://gist.github.com/aduchene/998902e2c564602ceff6 /]

Completing functionality

Our last implementation provides a convenient way of going from 0 to n-1, but we’d like to be able to do more than that. Python’s range() function further allows specifying an arbitrary beginning of the range and an (integer) step between elements. It even allows a negative step! We have to make a few modifications for this to work in our code. With a step of 1, the last element of the range will always be n-1, so generating the end() iterator is trivial. This isn’t the case with different stepsizes. For example,


range(0,10,8)

produces [0,8]. We’ll need our range class to figure out what the last element will be. While we’re at it, there’s no reason to stop at being a forward iterator. Making a random access iterator requires only a few additions.

[gist https://gist.github.com/aduchene/27e17149c2f553f27de0 /]

Going beyond Python

Devoted Pythonistas will no doubt explain why I’m wrong, but I’ve always been disappointed that the range() function doesn’t work with non-integers. Now that I’m writing my own, I’d have no one to complain to but myself. Since modulus isn’t defined with floating points, the calculation of the end needs to be modified. Additionally, since classes require explicit template types we lose the elegance of range(n). This can be fixed with helper functions and decltype.

[gist https://gist.github.com/aduchene/84b5818b34da336719f6 /]

If you like this code, it’s MIT licensed. Check it out on my github page.

Advertisements
Tagged with: , ,
Posted in coding