On Tue, 20 Jul 2010 13:53:37 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
Steven Schveighoffer wrote:
On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
On 07/20/2010 03:01 AM, Peter Alexander wrote:
Some more arguments for iterators/cursors:
1. How would you implement Floyd's cycle finding algorithm using
ranges?
(http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
It uses two iterators over the same range. You would have to
wastefully
use 2 ranges that have the same end coordinate.
I think there's a confusion somewhere. You may want to check out the
SList definition in std.algorithm. A SList range is exactly one
pointer thick. With singly-linked lists it's the iterator approach
that is wasteful because it canonically transports a null pointer as
end().
That is an example of a single exception to the rule :) AFAIK, no
other container types have ranges with no end pointer or length.
C-style strings and generally all sentinel-terminated sequences.
As long as the sentinel is null or some invalid value. I have
sentinel-style containers that use a specific sentinel element, which must
be used as the second endpoint. These ranges are generally more flexible
in terms of expressing a range over a container.
The OP's point is pretty accurate IMO, *most* ranges require two pieces of
info, and I agree with you that the cost of extra storage is worth it for
the benefits you get. Your singling out of SList as an example of how
some containers can implement falsely implies IMO that there are many
containers with that style of range, when in fact, most of the ranges are
at least two words thick. SList stands alone in that category, at least
for the moment. I also expect the majority of containers to not use
single-pointer ranges.
It also makes SList ranges less expressive. For example, what if I
wanted a range between two elements in the list? Such a range is
actually unconstructable. SList is not a very good example of a
container, because it is so unique and limited.
To express such ranges in SList I used Take.
That is not the same. For instance, removing the tail of such a range
from a singly-linked list is O(n), where it could be O(1) if the range was
two end points.
-Steve
