On Saturday, 2 September 2017 at 20:22:44 UTC, Robert M. Münch
wrote:
Iterators are not the silver bullet. But IIRC you can specify
if you want to iterate over a graph BF or DF. If you just need
to "iterate" over the elements things work pretty good IMO. If
you want to select a sub-set and then iterate things get much
complicater anyway.
There isn't really some finite (or small, anyway) choice here. I
may want to iterate over a binary tree in
preorder/inorder/postorder DF order. I may want to iterate over
it in BF order. I may want to handle the left son before the
right one, or vice versa. This is already 8 iterators. In C++
land I also need to provide const and non-const versions of each
iterator, which brings it up to 16 iterators (I'm not sure what's
the situation in D - can you have const ranges and still be able
to call popFront on them?)
From the implementor's side, this is a headache. However, it's
not that bad in a language in D, since "static if" saves you a
lot of code in cases like this.
The bigger problem is on the user's side: Which iterator should
she use? For most applications more than one type of iterator
will be adequate, but the "right" choice will often be
implementation-dependent. For instance, if the tree in question
is a complete binary tree, then it is often implemented as an
array that contains the tree's elements in BF order. Therefore,
if some operation on the tree can be done by traversing it BF
then the user should probably use a BF iterator, for performance
reasons. But the user doesn't know how the tree is implemented,
so she can't make that choice...
If the implementor informs the user about the implementation in
the documentation, then his data structure is a cost-free
abstraction (assuming that the user always chooses wisely...) but
also a leaky one. If he doesn't, then the abstraction doesn't
leak but it is no longer cost-free. He can't have both.
A simpler example is a class interface for a (two-dimensional)
matrix. You would expect the interface to provide a row-major
order iterator and a column-major order one. Again, from the
user's POV, the right choice (performance wise) will be dependent
on the implementation. Asymptotic complexity is sometimes
considered an essential detail of a "true" abstraction but this
doesn't help here since the difference in performance is only
observed in practice.
This is why I find the presentation in the OP - "Why iterators
got it all wrong" - a bit iffy. Iterators did get a lot of things
wrong, but the presentation focuses on relatively mundane issues
- ugly syntax and somewhat annoying semantics.
