Geek Answers Handbook

What is the large O () order of std :: queue :: size?

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

It can be assumed that size will be O(C) , but it is possible that it would be O(N) . Obviously, I can save my own size, but I would just call size .

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

+6
source share
5 answers

To summarize the very good answers here:

  • C ++ 11: O(1) (@Jeffrey)
  • C ++ 98: unenforced, experiments need to be done based on container class
  • C ++ 98 with default container: default container for std :: queue std :: deque, which calculates the size by subtracting two iterators, not O(1) , but not less than O(C) . ( @juanchopanza )

Thus, if you need to provide O (1) -ness size () in C ++ 98, you have to keep your own score.

If I could, I would like to step on my soap box and thank the C ++ 11 group for closing this awful specification. Many languages ​​/ libraries (e.g. Scala) put a lot of effort into defining a BIG-O statement. Given that performance is the primary use case for C ++, I find this lack of specs amazing. It is completely unacceptable that you need to check the header code to determine the performance characteristics of the std classes.

+2
source

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

This is guaranteed by the fact that the base container std::queue , according to §23.6.3.1 / 1, must comply with the requirements of the SequenceContainer , which inherits the Container requirement, which, in turn, according to §23.2.1, requires a size member function in order to have constant time complexity.

+8
source

Complexity is constant O (1).

Constant (call size in the base container). http://www.cplusplus.com/reference/queue/queue/size/

0
source

This may depend on the implementation you are using, and it is best to verify this yourself. Hopefully checking the header files is not that difficult. Although new standards require it to be permanent, it is the only way to be sure. For one example, it's worth noting that gcc libstdc ++ still has O (n) for std::list .

0
source

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

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

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

0
source

More articles:


All Articles