Hacker News Reader

The STL guarantees both iterator and address stability for the elements of a set, map, or the unordered variants. Those guarantees can't be provided by many more compact representations.

Note that this rules out more than just B-trees: open addressed hash tables and judy array like structures have the same issue.

View on HN

What do you mean by "iterator and address stability"?

Iterator stability means iterators that point into a container are not invalidated by operations (such as insertions or deletions) on that container.

Address stability means that addresses of elements are not changed by container operations. If you think about it, you can see that maintaining this property rules out contiguous storage of any subset of a container's elements, hence my comment about "compact representations".

Reply on news.ycombinator.com