On Sat, 01 Jun 2013 04:11:59 -0400, bearophile <[email protected]>
wrote:
David Piepgrass:
In fact, most STL algorithms require exactly two iterators--a
range--and none require only a single iterator<
I think there are some C++ data structures that store many single
iterators. If you instead store ranges you double the data amount.
This is true. In dcollections, I have the concept of cursors. These are
1 or 0 element ranges (they are 0 after the first popFront). For almost
all cases, they require an extra boolean to designate the "empty" state.
So while not consuming 2x, it's more like 1.5x-ish. Because of alignment,
it pretty much requires 2x. There have been suggestions on utilizing
perhaps unused bits in the pointer to designate the empty flag, but I'm a
bit aprehensive on that, especially if the node is GC-managed.
But besides the space requirements the *concept* of a single-element
pointer is very much needed. And cursors fill that role.
As an example, std.algorithm.find consumes a range until it finds the
specific value. It then returns a range of the remaining data. But what
if you wanted the range of the data UNTIL the first value?
In std.container, we have three functions to deal with this, upperBound,
lowerBound, and equalRange. But even with these, it can be difficult to
construct intersections of these two ranges.
In dcollections, we have one function, find, which returns a cursor. Then
using the cursor, you can construct the range you need:
auto r = mymap[mymap.find(5)..$]; // opDollar not supported yet, but will
be.
auto rbefore = mymap[mymap.begin()..mymap.find(5)];
All of this is safe and correct, and I think it reads rather well.
There are other good places where single-element ranges are useful. It is
important to note that a cursor is NOT equivalent to a range of one
element. Such a range in a node-based container has two node pointers. A
cursor MUST only point at exactly one element. This is important when
considering cursor invalidation -- removing an element unreferenced by a
cursor should not invalidate that cursor (depending on how the container
is structured). For example, adding a new value to a hash set, or
removing an unrelated value from a hash set may invalidate all ranges, but
not cursors.
-Steve
