Boost logo

Boost :

Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-28 10:36:08

Thorsten Ottosen wrote:
> Stewart, Robert skrev:
>> Steven Watanabe wrote:
>>>> How about another try: traversing a range with changing criteria?
>>>> A particular range class can take a predicate or some other
>>>> traversal influencing argument that can change with each
>>>> advance. How would you express that with iterator pairs?
>>> Easily. First of all, consider what's possible if the two iterators
>>> are allowed to be different types. Then all the actual state can
>>> be put in the first iterator and comparison to the second iterator
>>> can just check whether the range is empty. Once you have that,
>>> you can use boost::variant to store both iterators as the same type.
>>> This will not be efficient, but it will work.
>> That may well work, but the range version would certainly be more
>> straightforward and,
> >as you noted, efficient. Of course, once you permit the iterators to
> have different types,
> >you also increase the opportunity for mixing them incorrectly, which
> won't happen with an Alexandrescu range.
> I think we all agree that Alexandrescu ranges are conceptually simpler
> to implement and specify; however, from a user perspective the two
> approaches should be be similar.

Well ranges seem to make functional composition easier because one
object represents what you need, not two.


P.S. True story: the entire range thing, which is actually painfully
obvious, occurred to me when I was finishing D's iterator-based STL. I
was dissatisfied with it and was looking for a more expressive
abstraction. Somehow an information I got all the way back from 2003
popped up into consciousness. Back then, a visitor gave a talk at
University of Washington about a static code analysis tool they had
developed at Microsoft Research.

Now, the guy said that that tool, whenever it sees a function taking a
pointer followed by a size_t, it assumes the size_t is supposed to
encode the length of the array pointed to by the pointer. Although the
heuristic seems rather wobbly, it turns to be right for virtually all of
Microsoft's APIs. (I think they had a way to encode exceptions so as to
avoid false positives.) So then the static analysis tool would look at
all call sites and make sure the passed arguments would satisfy this
constraint. Turns out they found a ton of bugs in Microsoft Office that
way - callers would pair pointer and size improperly.

During the talk, he mentioned that of course the problem would have been
obviated if the APIs used a little abstraction that packaged the pointer
and the size together.

This information, corroborated with positive experience with built-in
slices in D, prompted me to look into an abstraction that encapsulates
the iteration limits, not makes them separate entities.

Boost list run by bdawes at, gregod at, cpdaniel at, john at