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:

and then use it like this:

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.

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.

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.

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

About these ads
Tagged with: , ,
Posted in coding
2 comments on “Pythonic ranges in C++11
  1. Nagadum says:

    Your implementation is interesting, especially the extensions to floats. I have a question, though. I see you are using a class to implement an iterator. I usually use a struct for this particular situation. Would you mind detailing the reasons behind your choice?

    By the way, if you are interested about implentation of python functions into C++ 2011, or want to compare your implementation with another one, you might want to look at :

    https://github.com/serge-sans-paille/pythran

    It is a python to c++ compiler. Inside the folder called “pythonic++”, you can find implementations of most python intrinsics (including both range and xrange), plus a few modules. The itertools module is currently being implemented, with tons of iterators.

    • ared38 says:

      AFAIK, the only difference between structs and classes in C++ is default visibility, to maintain compatibility with C-structs. Since I was going to hide some data, I thought a class was more appropriate. Really it’s just habit though. Pythran looks really cool, I’m definitely going to check it out more thoroughly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: