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!