KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Recently, I noticed some people mentioning that std::list::size() has a linear complexity. According to some sources , this is in fact implementation dependent as the standard doesn't say what the complexity has to be. The comment in this blog entry says: Actually, it depends on which STL you are using. Microsoft Visual Studio V6 implements size() as {return (_Size); } whereas gcc (at least in versions 3.3.2 and 4.1.0) do it as { return std::distance(begin(), end()); } The first has constant speed, the second has o(N) speed So my guess is that for the VC++ crowd size() has constant complexity as Dinkumware probably won't have changed that fact since VC6. Am I right there? What does it look like currently in gcc ? If it is really O(n), why did the developers choose to do so?
Tags (comma-separated)
Save Edits
Cancel