Очередь STL в C ++ реализует очередь с использованием круговых массивов или связанных списков

Question

Поскольку очередь может быть реализована обоими способами, мне интересно, какой из них используется в очереди STL.

Answer 1

A queue - контейнерный адаптер;он обеспечивает поведение, подобное очереди, используя другой контейнер для основного хранилища. Либо deque, либо list подходят для базового хранилища очереди. См. http://eel.is/c++draft/queue для всех кровавых деталей.

Ни один из них не является круговым массивом.

Answer 2

Проверяя некоторую документацию, сложность вставки для этого типа контейнера постоянна, если вы используете вектор, у которого не может быть постоянной сложности, потому что вам может потребоваться изменить размер вектора, тогда он использует связанный список.