what is the Big O( ) order of std::queue::size?

Question

The std::queue class is unclear as to the complexity of the size member function. It appears to be based on the data structure implementation used at the time.

One would assume that size would be O(C), but it's totally possible for it to be O(N). Obviously, I can keep my own size, but I would rather just call size.

(Question modified): since deque is the default container, what is O ( ) of std::deque::size()?

Answer 1

At least since C++11, the complexity of std::queue::size is constant: O(1).

This is guaranteed by the fact that the underlying container of std::queue, as per §23.6.3.1/1, have to fit the requirements of SequenceContainer, that inherits the requirement of Container, which, in turn, as per §23.2.1, requires the member function size to have a constant time complexity.

Answer 2

To sum up the very good answers here:

• C++11: O(1) (@Jeffrey)
• C++98: unenforced, need to do experimentation based on the container class
• C++98 with default container: the default container for std::queue is std::deque, which calculates size by subtracting two iterators, which is not O(1), but at least O(C). (@juanchopanza)

Thus, if you need to ensure O(1)-ness of size() in C++98, you must keep your own count.

If I might, I would like to step on my soap box and thank the C++11 group for closing this horrendous specification hole. Many languages/libraries (such as Scala) take great pains to define the BIG-O of an operator. Given that the main use case of C++ is performance, I find this lack of specification amazing. It is completely unacceptable that one should have to inspect header code to determine performance characteristics of std classes.