[hoseja]

Well it defines the big-O of the datastructure APIs. And to match all the requirements, the implementation is usually very constrained.

[leni536]

My impression is that it's typically the iterator/reference stability requirements that lock imlementations down, not the complexity requirements.

[hoseja]

Oh yeah, that too.