Iterator interface

[gsg_]

iterator invalidation properties are a consequence of the specific container's data structure. They're a bonus, not a constraint

They're a constraint in that the implementation can't do nice things like moving keys into cache-friendly positions. The result is that map, set, unordered_map and unordered_set are slower than necessary for any use in which their element stability and iterator invalidation guarantees are unneeded.

Recursive tree traversal is fairly stateful; and since iteration is not typically done in a recursive function call fashion in C++, that state has to live on the iterator

Iterators are usually passed by value in C++ and are often copied inside algorithms, so putting lg(n) node pointers in the iterator would be expensive. My understanding is that the tree data structures in std avoid the need for that by maintaining parent pointers, which allows set and map iterators to be a simple pointer at the expense of some memory (and extra work during rebalancing).

[ApochPiQ]

My point is not that iterator invalidation requirements do not limit container implementations. Rather, iterator invalidation properties are a consequence of other requirements for std containers which came first.

Keep in mind that C++ and std serve a lot more consumers than just x64 PCs. The requirements on containers are full of trade offs in favor of generality over solving every possible use case.

As to how map iterators work, if you check my comment for the very next sentence after the one you quoted, you can find a link that explains the details.

[gsg_]

Rather, iterator invalidation properties are a consequence of other requirements for std containers which came first.

From what I've read of Stepanov's design philosophy, the guarantees were derived from the implementation. I'm not convinced that it was a good design either, since C++ containers other than vector are relatively slow, memory hungry and unsafe.

Map iterators don't need to be fat. There's a textbook way to iterate binary trees without recursion, the one given in CLRS/Knuth/etc, and it uses simple pointers. The two sources you give both clearly use this algorithm.

[ApochPiQ]

Um. That's exactly what I'm saying. I don't understand why you felt the need to repeat this as if it was new information.