That's new in C++11 though, isn't it? I'm pretty sure (i.e. I haven't checked the spec) that as far as C++03 the complexity was allowed to be linear. Honestly my sense of aesthetics agrees -- linked lists aren't supposed to have constant-time operations, there are better choices if that is a requirement. And if you want an augmented data structure you should cook your own: a list with extra tracking (i.e. ever node needs to have a pointer to the global thingy!) and insertion hooks isn't a "list" any more.
Yeah, they changed the wording from "should" to "must" be O(1) in C++11, which means that before, even when they encourage the implementer to do it constant, that was in fact optional.
I don't that tracking the size would be a big deal, if you think that doing that they wouldn't be a linked list any more, you could think it as a linked link wrapper.
In any case the complexity guarantees of all the other operations remain true so I don't think it is a big deal.
