Alex Rivera | Logout

size() complexity of STL containers in G++: which containers are O(n)?

Asked 2011-12-12T02:13:20.757
14

I guess most people understand that the complexity of size() function is not guaranteed to be constant. Though in some implementations, it is constant.

The G++ compiler is probably the most commonly used compiler. So, in G++'s implementation, what's the complexity of size()? If it varies by different containers, what containers have linear complexity? For the most commonly used ones (such as list, vector, deque, set, & map), are they all constant?

c++ stl g++ complexity-theory
Edit
Report

1 Answer

17

For C++11, the standard (23.2.1) specifies that size is O(1) for all containers in conformant implementations of the standard library (unfortunately this doesn't mean that all implementations are conformant; e.g. gcc has this issue).

For C++03, the standard (23.1) says that size "should have constant complexity", which as it turns out (thank you, commenters) is a strong but non-binding suggestion; that means you have to read the documentation for the implementation provided with each compiler.

answered 2011-12-12T02:19:16.607

Your Answer