On Saturday, 1 June 2013 at 16:30:05 UTC, David Piepgrass 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.
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 usually (but not always) faster, as they don't have
an extra level of indirection involved -- the iterators tell you
directly where to look in memory, whereas indices are useless
without containers (or iterators) backing them.
You shouldn't be using 32-bit indices on x64, that defeats the
whole point of x64.
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.
No, that's exactly the opposite of what happens.
The caller just accepts two iterators (like std::unique), so that
it has the end iterator as well as the begin iterator.
