What are the drawbacks of using a std::vector for simulating a queue? I am naively thinking that push_back is used for push and for pop one just stores the position of the first element and increments it. Why does not std::queue allow a std::vector implementation like this in principle (I know the reason is it has no push_front method, but maybe there is something deeper that makes it slow this way)? Thank you for helping.

CodePudding user response：

Why does not std::queue allow a std::vector implementation like this

std::queue is a simple container adapter. It works by delegating pop function to the pop_front function of the underlying container. Vector has no pop front operation, so std::queue cannot adapt it.

but maybe there is something deeper that makes it slow this way

Pushing and popping from the front of the vector is slow because it has to shift all elements which has linear cost. This is why vector doesn't provide pop_front.

stores the position of the first element and increments it.

It's possible to implement a container that does store the position of first element within a buffer, but vector is not an implementation of such container. Storing that position has an overhead that vector doesn't need to pay, and so it doesn't.