Range, return types and references

During BoostCon 2009 the keynote speaker was Andrei Alexandrescu, who wrote the book Modern C++ Design in 2001. Andrei held a fabulous presentation with the name "Iterators Must Go", in which he point out several serious drawbacks of iterators. Iterators have been the basic mechanism to use the Standard Template Library classes, so this speach was revolutionary, and enjoyable. Andrei not only critized iterators, he also gave an alternative: ranges. Ranges are for him the basic piece.

The keynote was the forenote for an article that Andrei wrote, now with the title "On Iteration". The title is changed into a more subtile, but the message is more or less the same. I quote: "STL iterators are marred by lack of safety, difficulty of usage, difficulty of definition" .

Before BoostCon '09 with its famous keynote, I already knew the Boost.Range library quite well. Most of the algorithms in Boost.Geometry are based on ranges. We use Boost.Range everywhere. Ranges are very nice. A std::vector is a range, but a std::pair of iterators is also handled as a range, and a Boost.Array is also handled as a range, and you can create your own ranges. Yes, like iterators, but ranges are more elegant.

Andrei Alexandrescu mentioned Boost.Range during his keynote, of course. He said that Boost.Range was a good start, but should be worked out way further. Until now, that has not been realized as far as I know. But even without changes, Boost.Ranges are far more convenient than iterators.

Iterators

People reading this blog will know iterators and otherwise will have stopped reading here. However, I like to explain the very basics shortly because of the point that Andrei made: "iterators are unnecessary difficult", I've always found that. This is how standard iterators work:

std::vector<int> a;
// fill a
for (std::vector<int>::const_iterator it = a.begin(); it != a.end(); ++it)
// do something with *it

When I first worked with the std::library, somewhere in 199X, I refused to do this and wrote:

for (int i = 0; i < a.size(); i++)
// do something with a[i]

This is half the size, easier to write, easier to read. But it is (much) less efficient and should therefore not be done like that.

Note also that C++ programmers always write ++it and not it++ because it is slightly (and detectably) more efficient.

Boost.Ranges

A Boost.Range is a sort of view on a std::vector, or on any other iterable instance. Boost.Range still defines and works with iterators. It is another level of abstraction above the std:: library. With iterators you iterate like this (still vector a):

for (boost::range_iterator<std::vector<int> const>::type it = boost::begin(a); it != boost::end(a); ++it)
// do something with *it

Hey, this is even much longer! Yes, in this sample this is true and in general it is true, but ranges are normally (at least within Boost.Geometry) used in a template environment, where it becomes:

for (typename boost::range_iterator<Range const>::type it = boost::begin(a); it != boost::end(a); ++it)

Not shorter but more generic: a Range can be anything.

There are shortcuts as well: with BOOST_FOREACH or BOOST_AUTO. They are macro's, so often avoided, but they make things more readable and can save template metaprogramming, see below. But first we will see why ranges are so convenient.

From Iterators to Ranges

Boost.Geometry supports geometry algorithms such as distance. They are defined in a generic way, so

template <typename Geometry1, typename Geometry2>
double distance(Geometry1 const& g1, Geometry2 const& g2)

(The real version does not have the double there but a metafunction). With distance users can calculate the distance between two points, or a point and a line (linestring), or a point and a polygon, etc.

The earlier version of Boost.Geometry (then called GGL), before going to ranges, could calculate the distance to of a part of a linestring by specifying two iterators as well:

template <typename Geometry1, typename Iterator>
double distance(Geometry1 const& g1, Iterator it1, Iterator it2)

This is great functionality, but it is completely inconvenient to implement:

all other functions are generic, having two arguments, why does this one has three arguments?
all other functions are reversable, the distance from a point to a line, and from a line to a point, both result into the same implementation. For iterator support we would need to create an overload having the iterators first
there are more versions (for example: with a strategy), we would need those overloads for those two, leading into another combinatorial explosion (there are more algorithms too...)

When we discussed the GGL previews on the list, Mathias Gaunard suggested to use ranges instead of Boost.Geometries and we took this over and were very glad with this change.

This is quite an argument for ranges instead of iterators in a template-library environment, and this is why I emphasis this at this point.

So let me state: Ranges are compatible with other objects, while iterator-pairs are not.

References

After this lengthy introduction we consider how iterators and ranges are passed.

Iterators are normally passed by value. The main reason for this is explained nicely in StackOverflow: by passing by value you can create local copies, like v.begin().

Ranges are normally passed by reference. Ranges might be non-copyable containers, so passing by reference is required. Besides the non-copyable issue, a std::vector is a range. You definitely don't want to pass a std::vector by value.

Boost.Geometry's polygon

Boost.Geometry contains models of geometries like linestring and ring. They are defined as std::vector or a std::deque, but handled in the code as a range. Any linestring or ring fulfilling the Range Concept can be handled by Boost.Geometry, at least that is the basic idea. A polygon is more more complex because it might contain holes, in the definition of OGC and Boost.Geometry. So a polygon has an exterior ring and zero or more interior rings, defining the holes. The exterior ring fulfills the Ring Concept, the interior ring is a Range of Rings, so a Range of Ranges, a collection or rings.

Boost.Geometry contains a free function exterior_ring which returns the exterior ring by reference. And it also contains a free function interior_rings where the collection of interior rings are returned by reference. Both functions have a const and a non-const version. Of course they don't return the rings by value: polygons can be huge geometries, I've recently processed a polygon of 6 megabytes (in WKT-format). They should never be returned by value.

Other polygons

With Boost.Geometry, geometry classes of other libraries can be adapted, such that Boost.Geometry can run algorithms on them as if it was one of its own geometry classes. There are examples showing this with libgd's points, WxWidgets's points, Qt's polygons, etc. With traits classes these geometry classes can be adapted.

However, until today, polygons were required to return the exterior ring and interior rings by reference. But what if those geometries do not use ranges?

We encountered this adapting Boost.Polygon, our sister library within the Boost family. Boost.Polygon defines a polygon-with-holes-concept, where iterators begin_holes and end_holes are returned.

So after successfully adapting Boost.Polygon's point, rectangle and polygon (without holes, so we call it a ring) to our library, I started with the polygon. It is no problem that Boost.Polygon do not use the range concept internally. Because we can build a sort of proxy, simulating a range. So the adaptation of a Boost.Polygon polygon-with-data consists of defining:

an iterator to iterate through holes
a ring-proxy with an iterator-pair (point-begin, point-end)
an interior-ring-collection-proxy with an iterator-pair (holes-begin, holes-end).

But there was one problem:

Returning local references?

Local variables can (of course) not be returned as references. So you can create ring-proxies, but they cannot be returned... That is to say, they cannot be returned as a reference. Of course, they can be returned by value.

There are several solutions to this problem:

Change the Boost.Geometry polygon concept to work with iterators, so let it return iterators. This would be quite a lot of rework, and sounds like going ten years back. So discarded.
Change Boost.Polygon's polygon concept. But that is of course not wished and not possible. Boost.Polygon is now an incorporated library. Besides that, Boost.Polygon is an example here, many polygon libraries will have polygon types having no ranges internally. For example, shapelib's geometry is just a set of pointers... Boost.Geometry should handle any geometry. So discarded
Let Boost.Geometry's polygon concept return ranges always as values. This is possible, but the return value for its own polygon should then not be the ring but a proxy containing the reference of the ring.
Let Boost.Geometry's polygon concept return ranges sometimes as value, sometimes as references

I've chatted with my companion Bruno Lalande about this. He had the opinion that we definitely not should go back to iterators. He suggested the fourth solution. Let me quote Bruno: in Boost.Geometry, generic functions like exterior_ring() or interior_ring() that only forward the job to the actual adapted function, shouldn't make any assumption on their return type. Currently they seem to be generic in this regard since they get the return type by calling a metafunction, but they're not fully generic because they arbitrarily add a "&" to it. Boost.Range returns ranges by reference and by value.

Andrei Alexandrescu returns ranges in his article, on various places. We might change our own polygon type, returning proxies to ranges, and returning them by value. This would be solution 3. However, as long as this is not necessary, we prefer solution 4, to avoid an unecessary proxy in between, and to enable range-based polygon-types to return references to ranges.

Exterior rings should sometimes be returned as values, and sometimes as references.

So I changed the Boost.Geometry library into range-return-type agnostic behaviour.

So let me summarize: Ranges can be returned as values or as references

More metaprogramming

To implement solution 4 mentioned above, Boost.Geometry's polygon needed two characters extra: two ampersands. So its traits function ring_type now reads:
template
<
    typename Point, bool ClockWise, bool Closed,
    template<typename, typename> class PointList,
    template<typename, typename> class RingList,
    template<typename> class PointAlloc, template<typename> class RingAlloc
>
struct ring_type
<
    model::polygon
        <
            Point, ClockWise, Closed,
            PointList, RingList, PointAlloc, RingAlloc
        >
>
{
    typedef typename model::polygon
        <
            Point, ClockWise, Closed,
            PointList, RingList,
            PointAlloc, RingAlloc
        >::ring_type& type;
};

where the ampersand is added... Meaning, the ring-returning-type is now a reference!

Of course some more changes were necessary, but not more. The free function exterior_ring now uses a meta-function to define its return type. That meta-function uses the traits-function ring_type, so returns sometimes a reference, sometimes a value. For const and non-const, another metafunction is created:
template <typename T>
struct ensure_const_reference
{
    typedef typename mpl::if_
        <
            typename boost::is_reference<T>::type,
            typename boost::add_reference
                <
                    typename boost::add_const
                        <
                            typename boost::remove_reference<T>::type
                        >::type
                >::type,
            T
        >::type type;
};

I like metaprogramming. If the type was a reference, it removes it, adds a const, and adds a reference again. If it was not a reference, it keeps it unchanged. This is type calculation, metaprogramming.

Iterating through const/non const collections of values/references

At every place where Boost.Range iterators were used to iterate through interior rings, a change was necessary. This was possible creating another metafunction, but Bruno suggested to use BOOST_AUTO here. This avoids new metafunctions, and makes all iterations more readable. This works perfectly for both const and non const iterators, so in fact it is all much more simple than before. Loops are now written like this:

for (BOOST_AUTO(it, boost::begin(interior_rings(polygon)));
it != boost::end(interior_rings(polygon));
++it)

This BOOST_AUTO word, which anticipates the C++0x auto keyword, saves defining and declaring metafunctions all the time. It is a macro (yack) but very valuable here, also because if we change things another time, this can stay as it is now.

One thing is noteworthy, there are two calls to interior_rings returning (in the return-by-value case) two copies. Because these copies are suspected to be proxies, containing references to the original (single) object, the iterator-behaviour will be all right, they are both pointing to the same original range.

However, better safe then sorry, better defensive, so we should write here:

BOOST_AUTO(irings, interior_rings(polygon));
for (BOOST_AUTO(it, boost::begin(irings)); it != boost::end(irings); ++it)

which might be also more efficient in some cases.

Conclusions

Ranges are great.
Ranges are compatible with other objects, while iterator-pairs are not
Ranges can be returned as values or as references
Boost.Geometry's polygon concept uses ranges, allowing adaption of other polygon types using implementation of range proxies

Barend's Blog (Boost.Geometry, Programming, Music, Languages)

Sunday, December 12, 2010