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.
Hashmaps would be the most common example. Usually implemented
as a linked list of key-value pairs along with a vector of list
iterators.
In theory. But the .NET hashtables are implemented with an
*array* of key-value pairs and an array of *indexes*. The former
forms a virtual linked list that is more efficient than a
traditional linked list, and the latter is more efficient than a
vector of iterators (especially on x64, as the indexes can be
32-bit.)
Iterators are also useful for constructing sub-ranges, which
proves useful in the implementation of some algorithms. Writing
std::next_permutation in D with ranges is quiet frustrating
compared to C++.
https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm.d#L10901
http://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01045_source.html#l03619
Notice that in D you need to maintain a count of the elements
popped off the back and then use takeExactly to retrieve that
portion again. In C++ you just move the iterators around and
create "ranges" from pairs of iterators as you need them.
When I implemented nextPermutation in D, I constantly felt as
if I was fighting with ranges instead of working with them - I
knew exactly what I wanted to do, but ranges only provide a
roundabout way of doing it.
Hmm, very interesting. I suppose the problem with C++ iterators
is that they are useless without external context: you can't
increment or decrement one without also comparing it to begin()
or end() in its container, which implies that the caller must
manually keep track of which container it came from. Thus, an
iterator is hardly an improvement over a plain-old integer index,
the only advantages being
1. You can dereference it (*if* you can be sure it doesn't point
to end())
2. Unlike an index, it's compatible with non-random-access data
structures
But perhaps the iterator concept could be improved by being made
self-aware: if the iterator "knew" and could tell you when it was
at the beginning or end of its container. This would increase the
storage requirement in some circumstances but not others. For
example, an iterator to a doubly-linked list node can tell when
it is at the beginning or end, but an iterator to a singly-linked
list node can only tell when it is at the end. A pointer inside
an array may or may not be able to tell if it is at the end
depending on how arrays work, e.g. perhaps the way D heap arrays
work would allow an array iterator, implemented as a simple
pointer, to still know when it is safe to increment and decrement.
The simplest possible .NET array iterator is an array reference
plus an index, and again the iterator can know when it is at the
beginning or end of the array--except that if the iterator came
from inside a range, it would be unaware of the range's
boundaries, which may be smaller than the array's boundaries.
