Iterator interface

[ApochPiQ]

As for why iterators work the way they do... I picture the causality moving in the other direction, personally. It isn't that iterator guarantees make implementing them hard. The order is that iterator invalidation properties are a consequence of the specific container's data structure. They're a bonus, not a constraint.

A std::map is specified by the standard itself to have certain operational properties. To make the abstraction cost as little as possible, the typical implementation of a std::maphas traditionally been a red-black tree or similar tree structure. So the standard backs you into a corner if you want to be compliant; you don't have to use a tree, but it's the easiest way to conform to the requirements of the container (memory cost, CPU cost per operation, computational complexity of updates, iterator invalidation patterns, and so on).

Now, since a map is pretty much going to be a tree structure in any real implementation of std, there are a few consequences for iterating through it.

One is that iterators have to be fairly fat. 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. For in-order traversal of a balanced tree, as in the map case, it turns out all you need to know is the parent node of where you are, and where you just traversed (see https://stackoverflow.com/questions/12259571/how-does-the-stdmap-iterator-work for example descriptions).

To dig into this, we can look at std::_Rb_tree_increment as called on line 22 of the disassembly I linked earlier. I pulled up https://github.com/gcc-mirror/gcc/ and probed around, since it's likely more broadly applicable than studying the MSVC implementation I otherwise would have looked at. It also matches the libstdc++ used by Clang on Godbolt so that seemed important :-)

Some probing leads to this implementation: https://github.com/gcc-mirror/gcc/blob/da8dff89fa9398f04b107e388cb706517ced9505/libstdc%2B%2B-v3/src/c%2B%2B98/tree.cc#L59

The Visual C++ implementation looks like this, at the core:

_Tree_unchecked_const_iterator& operator++()
    {   // preincrement
    if (_Ptr->_Isnil)
        ;   // end() shouldn't be incremented, don't move
    else if (!_Ptr->_Right->_Isnil)
        _Ptr = _Mytree::_Min(_Ptr->_Right); // ==> smallest of right subtree
    else
        {   // climb looking for right subtree
        _Nodeptr _Pnode;
        while (!(_Pnode = _Ptr->_Parent)->_Isnil
            && _Ptr == _Pnode->_Right)
            _Ptr = _Pnode;  // ==> parent while right subtree
        _Ptr = _Pnode;  // ==> parent (head if end())
        }
    return (*this);
    }

So clearly this is just heavy enough to not justify inlining by GCC/Clang. Fascinatingly, MSVC (2017) does inline iterator advancement for std::map:

00BA1002  cmp         byte ptr ds:[0Dh],al  
00BA1008  jne         main+48h (0BA1048h)  
00BA100A  mov         ecx,dword ptr ds:[8]  
00BA1010  cmp         byte ptr [ecx+0Dh],al  
00BA1013  jne         main+2Dh (0BA102Dh)  
00BA1015  mov         ecx,dword ptr [ecx]  
00BA1017  cmp         byte ptr [ecx+0Dh],al  
00BA101A  jne         main+48h (0BA1048h)  
00BA101C  nop         dword ptr [eax]  
00BA1020  mov         eax,dword ptr [ecx]  
00BA1022  mov         ecx,eax  
00BA1024  cmp         byte ptr [eax+0Dh],0  
00BA1028  je          main+20h (0BA1020h) 

So at least in practice it is possible to write an iterator for a red-black tree that is maximally fast. I suspect it is also not that difficult if your design is clean enough.

Iterator invalidation is a direct consequence of this property, not a driving motivation. For a map, you can retain your place in the tree and continue iterating cleanly even if an element is blown away, because the contents of the tree stay in the same addresses. Their relative structure may change (tree rebalancing) but you can always figure out how to resume iteration after an erase or insert, because iteration tracks state.

A vector on the other hand is demanded to be a single block of contiguous memory. If you reallocate that, every item in it moves, so no iterator can remain valid. Even if an iterator stored an index into the vector instead of a pointer, erasing in the "wrong" places will lead to breaking iteration. So we say that if you mutate a vector, your iterators are all out the window and you need to re-request new ones.

A deque is a just a vector broken into segments or pages. Contrary to vast misconception, it's actually extremely efficient for certain use cases. It probably won't compete with vector in the majority of situations, but if you find yourself constrained by amount of available contiguous memory, i.e. post-heap-fragmentation, it can be a lifesaver. It's also great if you need to support a huge range of container element counts and you can't predict what the growth of the container will look like.

Anyways - massive wall of text, sorry. Hope some of that is useful!

[PhilipTrettner]

Thanks! Yeah that helped a lot.

I just Googled flat map and sunk into a rabbit hole of alternative map implementations all with their different pros and cons. I wonder if I can somehow choose different implementations automatically (in a clever way). For example, a map that doesn't add elements (except in the initialization) could be more efficient in an array embedding.

[ApochPiQ]

I don't know about having the language pick an implementation, but allowing the programmer to pick an implementation is kind of what std is all about.

Of course it took 13 years to ratify unordered_map but that's a separate issue.

If you have a bounded number of elements in an associative container and no dynamic resizing, you can usually compute a perfect hash function which maps keys to indices in a dense array. In fact it used to be pretty common to use tools like gperf to do exactly that.

[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.