Поскольку существует множество ответов, вы можете быть смущены, но подведем итог:
Используйте std::queue. Причина этого проста: это структура FIFO. Вы хотите FIFO, вы используете std::queue.
Это проясняет ваши намерения кому-либо еще, и даже вам самим. A std::list или std::deque нет. Список можно вставлять и удалять в любом месте, что не является тем, что должна делать структура FIFO, а deque может добавлять и удалять с любого конца, что также не может делать структура FIFO.
Вот почему вы должны использовать queue.
Теперь вы спросили о производительности. Во-первых, всегда помните это важное правило: Сначала хороший код, а производительность в последнюю очередь.
Причина этого проста: люди, которые стремятся к производительности раньше, чем чистота и элегантность, почти всегда заканчивают последними. Их код превращается в кашу, потому что они отказались от всего хорошего, чтобы действительно ничего не извлечь из него.
Сначала, написав хороший, читаемый код, большинство из вас решает проблемы с производительностью. И если позже вы обнаружите, что вашей производительности не хватает, теперь легко добавить профилировщик в ваш красивый, чистый код и выяснить, в чем проблема.
Все это говорит, std::queue это всего лишь адаптер. Он обеспечивает безопасный интерфейс, но использует другой контейнер внутри. Вы можете выбрать этот базовый контейнер, и это обеспечивает большую гибкость.
Итак, какой контейнер следует использовать? Мы знаем, что std::list и std::deque оба предоставляют необходимые функции (push_back(), pop_front() и front()), так как мы решим?
Во-первых, следует понимать, что выделение (и освобождение) памяти не является быстрым делом, как правило, потому что оно предполагает выход в ОС и обращение к нему с просьбой сделать что-то. list должен выделять память каждый раз, когда что-то добавляется, и освобождать ее, когда она исчезает.
A deque, с другой стороны, выделяется кусками. Он будет выделяться реже, чем list. Думайте об этом как о списке, но каждый кусок памяти может содержать несколько узлов. (Конечно, я бы посоветовал вам действительно узнать, как это работает .)
Итак, с этим одним deque должен работать лучше, потому что он не так часто работает с памятью. Смешанный с фактом, что вы обрабатываете данные постоянного размера, он, вероятно, не должен будет выделяться после первого прохода данных, тогда как список будет постоянно выделяться и освобождаться.
Второе, что нужно понять, это производительность кеша . Выход в ОЗУ медленный, поэтому, когда процессору это действительно необходимо, он извлекает максимальную выгоду из этого времени, забирая часть памяти обратно в кэш. Поскольку deque выделяется в блоках памяти, вполне вероятно, что доступ к элементу в этом контейнере приведет к тому, что ЦП также вернет остальную часть контейнера. Теперь любой дальнейший доступ к deque будет быстрым, поскольку данные находятся в кеше.
Это не похоже на список, в котором данные размещаются по одному за раз. Это означает, что данные могут быть распределены по всей памяти, и производительность кеша будет плохой.
Итак, учитывая это, deque должен быть лучшим выбором. Вот почему это контейнер по умолчанию при использовании queue. Тем не менее, это все еще только (очень) образованное предположение: вам придется профилировать этот код, используя deque в одном тесте и list в другом, чтобы действительно знать наверняка.
Но помните: получите код, работающий с чистым интерфейсом, затем беспокойтесь о производительности.
Джон высказывает опасение, что перенос list или deque приведет к снижению производительности. Еще раз, он и я не можем сказать наверняка, не профилируя это сами, но есть вероятность, что компилятор встроит вызовы, которые делает queue. То есть, когда вы говорите queue.push(), на самом деле он просто скажет queue.container.push_back(), полностью пропуская вызов функции.
Еще раз, это только обоснованное предположение, но использование queue не приведет к снижению производительности по сравнению с использованием базового контейнера raw. Как я уже говорил, используйте queue, потому что он чистый, простой в использовании и безопасный, и если он действительно становится проблемным профилем и тестирует.