C++ / Why Iterators Got It All Wrong

[Mark via Digitalmars-d]

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.