4 ms·
The standard in C++11 demands that size must be O(1). Also, there are some compilers that already are complaint in that regard.
by pmelendez 13y ago
The standard in C++11 demands that size must be O(1). Also, there are some compilers that already are complaint in that regard.
- ajross 13y agoThat'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.
- pmelendez 13y agoYeah, 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.