Tag Archives: Range

Range : Be expressive using smart iterators with Range based containers

Hi !
Today I am not going to talk about rendering. This article will deal with expressiveness in C++. Expressiveness? Yes, but about containers, range, and iterators.
If you want to know more about writing expressive code in C++, I advise you to go on fluentcpp.
If you want to know more about range, I advise you to take a look at the Range V3 written by Eric Niebler.
The code you will see may not be the most optimized, but it gives one idea behind what ranges are and how to implement it.

Introduction

How could we define a Range ?

The objective

Prior to defining what a Range is, we are going to see what Range let us do.

Isn’t it amazing to write things like that? Okay for direct operation inside the container, it could be better in two ways:

  1. It is not “easy” to read if you want to compose operation : (unique(sort(range)) is less readable than range | sort | unique in my opinion. But it is juste one “optimisation” to do :).
  2. It may be not optimized since sort returns a Container : here a vector, and build also.

The overloading of operator<< is quite easy though:

Okay, there are a lot of templates. I hope you will not get an allergy to them. All the lines that follow will use and abuse of templates and SFINAE.

The definition of a Range

A range is a way to traverse a container. They are at one abstraction above of iterators. To be simple, a Range own the first iterator, and the final one. It comes with a begin and one end function.

Smart (Or proxy) iterator

Okay, now things are becoming tricky. I hope that I lost no one.

What exactly is an iterator ?

To be simple, an iterator is an abstraction of a pointer.
It exists several catetegories of iterators, to be simple, here is the list:

  1. input : They can be compared, incremented, and dereferenced as rvalue (output ones can be dereferenced as lvalue).
  2. Forward : not a lot of difference with the prior.
  3. Bidirectional: They can be decremented.
  4. Random Access : They support arithmetic operators + and -, inequality comparisons.

Smart Iterator in details

Lazy Initialization

This statement tells us “If the result of the operation is not needed right now, there is no need to compute it”. To be simple, the operation will be done when we will need to get the result. With iterator, it could be done when you dereference it for instance.

Different types of smart iterator

Filter iterator

This iterator will jump a lot of values that do not respect a predicate. For example, if you want only the odd values of your container, when you increment the iterator, it will advance until the next odd value and will skip all the even ones.

Transform iterator

This iterator will dereference the iterator, apply a function to the dereferenced value and returns the result.

Implementation

Basics

Here we are going to implement our own iterator class. This class must be templated twice times.
The first template argument is the iterator we want to iterate on. The second template argument is a tag that we use to perform a kind of tag dispatching.
Moreover, this iterator must behave as … an iterator !

So, we begin to write :

One of above typename will fail if Iterator does not behave like one iterator.
The Tag has a constructor and can own several data (function / functor / lambda), other iterators(the end of the range?) or other things like that.

The iterator must respect the Open Closed Principle. That is why you must not implement the methods inside the class but outside (in a namespace detail for instance). We are going to see these methods later. To begin, we are going to stay focused on the RangeIterator class.

Constructors

We need 3 constructors.
1. Default constructor
2. Variadic templated constructor that build the tag
3. Copy constructor

And we need as well an assignment operator.

There are no difficulties here.

They also need comparison operators !

And they are quite easy !

Reference or value_type dereferencement

I hesitate a lot between return either a reference or a copy. To make transform iterator easier, I make the return by copy.
It means that you cannot dereference them as a lvalue :

The code is a bit tricky now because the dereferencement could not be the value you are waiting for. See the std::back_insert_iterator for instance.

Forward iterator to go farther !

Again, simple code !

Backward iterator, to send you in hell !

Okay, now as promised, we are going to see how beautiful C++ templates are. If you don’t want to be driven crazy, I advise you to stop to read here.
So, we saw that not all iterators have the “backward” range. The idea is to enable this feature ONLY if the iterator (the first template argument) supports it also.
It is the moment to reuse SFINAE (the first time was for the “is_range” structure we saw above).
We are going to use the type_trait std::enable_if<Expr, type>.
How to do that?

You MUST template this function, else the compiler can not delete it !!!

FYI : If you have C++17 enabled, you can use concepts (at least for GCC).

Random iterator

Now you can do it by yourself.
But here some code to help you (because I am a nice guy :p)

Details

Okay, now we are going to see what is hiden by detail::RangeIterator.

Normal iterators

In this namespace, you MUST put the tag and the function on it.

Here are the functions for normal iterator.

It is simple, if it is a normal iterator, it behaves like a normal one.

Transform iterator

I will not talk about the filter iterator since it is not complicated to make it once we understand the ideas. Just be careful about the construct function…

The tag

So, what is a Transform iterator? It is simply one iterator that dereference the value, and apply a function to it.
Here is the Tag structure.

It owns one std::function and that’s it.

The usefulness of the transform iterator is when you dereference it. So you need to reimplement only the dereference function.

Thanks to overloading via tag dispatching this function should (must??) be called without any issues (actually you hope :p).

However, if you want to use several files (thing that I only can to advise you), you cannot do it by this way but specialize your templates. But you cannot partially specialize template function. The idea is to use functor!

Here is a little example using dereference function.

The builder : pipe operator (|)

Okay, you have the iterator, you have the range class, you have your function, but now, how to gather them?

What you want to write is something like that:

First, you need a function that Create one range that own two iterators.
One that begins the set, and the other one that ends it.

Once you have that, you want to overload the pipe operator that makes it simple :

Warning : Don’t forget to take care about rvalue references to be easy to use !

Conclusion

So this article presents a new way to deal with containers. It allows more readable code and take a functional approach. There is a lot of things to learn about it, so don’t stop your learning here. Try to use one of the library below, try to develop yours. Try to learn a functional language and … Have fun !!!!

I hope that you liked this article. It is my first article that discuss only C++. It may contains a lot of errors, if you find one or have any problems, do not forget to tell me!

Reference

Range V3 by Eric Niebler : His range library is really powerfull and I advice you to use it (and I hope that it will be a part of the C++20).
Ranges: The STL to the Next Level : because of (thanks to?) him, I am doing a lot of modifications in all my projects… x).
Range Library by me : I will do a lot of modifications : Performance, conveniance and others.