Какой контейнер STL следует использовать для FIFO?

Поскольку существует множество ответов, вы можете быть смущены, но подведем итог:

Используйте a std::queue. Причина этого проста: это структура FIFO. Вы хотите FIFO, вы используете std::queue.

Это делает ваше намерение ясным для всех остальных, и даже для вас самих. А std::list или std::deque - нет. Список может вставлять и удалять в любом месте, что не является тем, что должна делать структура FIFO, а deque может добавлять и удалять с любого конца, что также является что-то, чего не может сделать структура FIFO. Вот почему вы должны использовать queue. Теперь вы спросили о производительности. Во-первых, всегда помните это важное эмпирическое правило: сначала хороший код, потом производительность. Причина этого проста: люди, которые стремятся к производительности перед чистотой и элегантностью, почти всегда заканчивают последними. Их код превращается в кашу, потому что они отказались от всего хорошего, чтобы действительно ничего не получить из этого. оно.

Написав сначала хороший, читаемый код, большинство из вас проблемы с производительностью решат сами. И если позже вы обнаружите, что вам не хватает производительности, теперь легко добавить профилировщик в ваш хороший, чистый код и выяснить, в чем проблема.

Что все сказанное, std::queue является только адаптером. Он обеспечивает безопасный интерфейс, но использует другой контейнер внутри. Вы можете выбрать этот базовый контейнер, и это обеспечивает большую гибкость.

Итак, который базовый контейнер следует использовать? Мы знаем, что std::list и std::deque оба обеспечивают необходимые функции (push_back(), pop_front(), и front()), так как же мы решаем?

Во-первых, поймите, что выделение (и освобождение) памяти не является быстрым делом, как правило, потому что оно включает в себя обращение к операционной системе и просьбу ее что-то сделать. A list должен выделять память каждый раз, когда что-то добавляется, и освобождать ее, когда она уходит.

A deque, с другой стороны, выделяет в куски. Он будет выделять реже, чем A list. Думайте об этом как о списке, но каждый кусок памяти может содержать несколько узлов. (Конечно, я бы предложил вамдействительно узнать, как это работает .)

Таким образом, только с этим dequeдолжен работать лучше, потому что он не имеет дело с памятью так часто. В сочетании с тем фактом, что вы обрабатываете данные постоянного размера, ему, вероятно, не придется выделять после первого прохождения данных, в то время как список будет постоянно выделять и освобождение. Вторая вещь, которую нужно понять, - это производительность кэша . Выход в оперативную память происходит медленно, поэтому, когда процессор действительно нуждается в этом, он делает лучшее из этого времени, забирая кусок памяти обратно в кэш. Поскольку deque выделяет в памяти куски, вполне вероятно, что доступ к элементу в этом контейнере приведет к тому, что процессор вернет и остальную часть контейнера. Теперь любой дальнейший доступ к deque будет быстрым, потому что данные находятся в кэш. Это не похоже на список, где данные распределяются по одному за раз. Это означает, что данные могут быть распределены по всему пространству в памяти, и производительность кэша будет плохой. Таким образом, учитывая это, dequeдолжен быть лучшим выбором. Вот почему он является контейнером по умолчанию при использовании queue. Что все сказанное, это все еще только (очень) образованная догадка: вам придется профилировать этот код, используя deque в одном тесте и list в другом, чтобы действительно знать для определенный. Но помните: пусть код работает с чистым интерфейсом, а затем позаботьтесь о производительности. Джон высказывает опасение, что обертывание list или deque приведет к снижению производительности. Опять же, ни он, ни я не можем сказать наверняка, не профилируя его сами, но есть вероятность, что компилятор встроит вызовы, которые делает queue. То есть, когда вы говорите queue.push(), он действительно просто скажет queue.container.push_back(), полностью пропуская вызов функции.

Еще раз, это это только обоснованное предположение, но использование queue не ухудшит производительность, по сравнению с использованием базового контейнера raw. Как я уже говорил, используйте queue, потому что он чистый, простой в использовании и безопасный, и если он действительно становится профилем проблемы и тестом.