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()?

All standard containers' `size()` functions must be constant time. See [container.requirements.general]. — chris, Feb 11 '14 at 22:01
C++11 mandates O(1) for size() of all containers. I believe that was not mandated before, though. — dragonroot, Feb 11 '14 at 22:02
@juanchopanza, Good point. The reference (and the standard) even explicitly says it meets every requirement but `size()`. — chris, Feb 11 '14 at 22:05

Shoe · Answer 1 · 2014-02-11T22:28:40.637

9

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.

edited Feb 11 '14 at 22:28

answered Feb 11 '14 at 21:59

Shoe

74,840
36
166
272

I am glad to hear about that, but would like to know more about this that I just found. http://stackoverflow.com/questions/7808916/stdqueuet-listt-size-is-slow-in-on – Mark Gerolimatos Feb 11 '14 at 22:01
2

I don't think that is guaranteed. – juanchopanza Feb 11 '14 at 22:01
Precisely. I am a bit troubled by this. So let me be more explicit: What is the order of size() of: std::queue In other words, the default backing store. – Mark Gerolimatos Feb 11 '14 at 22:03
@MarkGerolimatos In that case, it is constant time. – juanchopanza Feb 11 '14 at 22:04
@Praetorian Typo. Anyway, there is an exception. – juanchopanza Feb 11 '14 at 22:18
3

@juanchopanza Yeah, `forward_list` is an odd duck. But it doesn't meet the requirements for underlying container for `queue` anyway because it doesn't have `push_back`' – Praetorian Feb 11 '14 at 22:20

score 3 · Accepted Answer · answered Feb 11 '14 at 22:59

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.

Casey · Answer 3 · 2014-02-12T07:32:13.740

std::queue::size is specified exactly in C++11 23.6.3.1/1:

size_type size() const { return c.size(); }

where c is a protected data member whose type is that of the second template parameter. Ergo, its complexity is exactly that of the size member function of said template parameter. The default is std::deque<T> - where T is the first template parameter passed to std::queue - which has the default O(1) complexity requirement common to all containers unless otherwise specified (per Table 96 in 23.2.1).

score 0 · Answer 4 · answered Feb 11 '14 at 22:01

0

The complexity is constant O(1).

Constant (calling size on the underlying container). http://www.cplusplus.com/reference/queue/queue/size/

answered Feb 11 '14 at 22:01

gabrielbecker

29
5

score 0 · Answer 5 · answered Feb 11 '14 at 22:07

0

It may depend on the implementation you use, and it's best to check this yourself. Hopefully inspecting header files are not that hard. Even though newer standards mandate that it should be constant, that's the only way to be sure. For one example worth noting, gcc's libstdc++ still has O(n) for std::list.

answered Feb 11 '14 at 22:07

dragonroot

5,653
3
38
63

Wow. When it comes to libraries, especially the STD, "use the source Luke" is not a happy answer. However, glad to hear that in C++11 things are a bit more stringent. – Mark Gerolimatos Feb 11 '14 at 22:11
3

@MarkGerolimatos To clarify: whether `size()` in a default queue is constant time **is not** implementation dependent. The standard mandated the default container used to be `std::deque`, and `std::deque::size` is constrained to be constant time. – juanchopanza Feb 11 '14 at 22:14
Indeed it's not. However, to quote one DMV handbook loosely, 'the fact that drivers are not allowed to run over you doesn't really prevent them from doing so'. – dragonroot Feb 11 '14 at 22:19
On the other hand, who would want to use an implementation that is non-standards compliant on such a basic level? – juanchopanza Feb 11 '14 at 22:23
I believe C++03 never required this. And the question did not refer to either any specific standard or any specific implementation. So the only answer I could have provided in that case is that nuking from the orbit is the only way to be sure. – dragonroot Feb 11 '14 at 22:31
@juanchopanza lots of people. Pretty much anyone who uses GCC. It's not the only noncompliance in libstdc++. (their std::string still uses COW too) – jalf Feb 11 '14 at 23:36

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

5 Answers5