A list and its iterators (including their guarantees) cannot be looked at separately.

It can, when you're trying to implement your own.

Thanks for clearing everything up. I wasn't aware of the complexity requirements of STL. Maybe I'll stop being lazy and test it all myself one day, but for now I'm happy to believe you.

I'm a bit late to the party so what I'm going to say is a bit redundant, but as a digest:

STL containers have a very rigid contract to them. Trying to do better while adhering to that contract is going to be extremely difficult. Relaxing those constraints can afford you a lot of wins, but at that point you're no longer implementing the same container.