From what I've read on mailing lists and whatnot, it seems a lot of complexity comes from explicit choices made, like iterators being unaffected by insertions[1] for maps and such, or time complexity guarantees that forces the implementation into certain corners.

[1]: https://kera.name/articles/2011/06/iterator-invalidation-rul...