Home > Articles > Programming > C/C++

  • Print
  • + Share This
From the author of Weaknesses

Weaknesses

My (and many others') natural inclination when switching from STL iterators to ranges was to think of iterator-based designs in terms of ranges, just as I'd think of writing programs in a new language by using idioms popular in languages I already knew. This approach has revealed a few iterator-based designs that can't be translated easily to ranges. One example is Boost MultiIndex [11], which stores iterators to containers in indexes. Storing one-element ranges instead doubles the size of the index.

Another weakness I noticed is visible when translating STL algorithms that return one iterator, such as find, which has this signature:

It find(It b, It e, E value)

where It is a one-pass iterator type and E is the type referenced by the iterator. STL's find returns the first iterator iter between b and (excluding) e that satisfies *iter == value. Once that iterator is returned, you can combine it with b to obtain the range before value, or with e to obtain the range after value.

Ranges lack such capabilities. The range-based find has this signature:

Range find(Range r, E value)

It consumes from r until it finds value and returns what's left of r. This means that you get access to the portion after the found value, but not before.

Fortunately, this problem is easily solved by defining a new range type, Until. Until is a range that takes another range r and a value v, starts at the beginning of r, and ends just before r.front() == v (or at the natural end of r if v is not to be found). Lazy computation for the win!

There are likely other things that iterators can do that ranges can't—it's a given. The good news is that there don't seem to be many, so range-based designs don't lose many of the tricks you can do with iterators.

One weakness of ranges that is linked to the memory model of the underlying language is their propensity to invalidate when you mutate their underlying container. STL iterators obey well-specified but unchecked invalidation rules. Once a container is changed in a way that invalidates an iterator, using that iterator firmly steps into undefined behavior territory. Ranges inherit that problem. (As discussed in the section "A Fresh Approach to Iteration," ranges do improve safety when compared with iterators because they never allow invalid pairs of iterators.) Without having researched the matter, I believe that adding more safety checks to ranges should proceed more easily than with iterators.

  • + Share This
  • 🔖 Save To Your Account