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

Поскольку существует множество ответов, вы можете запутаться, но резюмируем:

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

Это проясняет ваши намерения для всех, и даже для вас самих. A std :: list или std :: deque - нет. Список можно вставлять и удалять где угодно, что не является тем, что предполагает структура FIFO, и двухсторонняя очередь может добавлять и удалять с любого конца, что также не может сделать структура FIFO.

Вот почему вам следует использовать очередь .

Теперь вы спросили о производительности. Во-первых, всегда помните это важное практическое правило: Хороший код в первую очередь, производительность в последнюю очередь.

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

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

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

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

Во-первых, поймите, что выделение (и освобождение) памяти - это не быстрое дело, как правило, потому что для этого нужно обратиться к ОС и попросить ее что-то сделать. Список должен выделять память каждый раз, когда что-то добавляется, и освобождать ее при удалении.

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

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

Вторая вещь, которую следует понять, это ] производительность кеша . Выход в ОЗУ происходит медленно, поэтому, когда ЦП действительно в этом нуждается, он максимально использует это время, забирая с собой часть памяти обратно в кеш. Поскольку двухсторонняя очередь выделяется в блоках памяти, вполне вероятно, что доступ к элементу в этом контейнере заставит ЦП также вернуть остальную часть контейнера. Теперь любые дальнейшие обращения к двухсторонней очереди будут быстрыми, потому что данные находятся в кэше.

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

Таким образом, учитывая это, двухсторонняя очередь должна быть лучшим выбором. Вот почему это контейнер по умолчанию при использовании очереди . Тем не менее, это все еще (очень) обоснованное предположение: вам нужно профилировать этот код, используя deque в одном тесте и список в другом, чтобы действительно знать

Но помните: заставьте код работать с чистым интерфейсом, а затем беспокойтесь о производительности.

Джон выражает обеспокоенность тем, что упаковка списка или двухсторонней очереди вызовет снижение производительности. Еще раз, он и я не можем сказать наверняка, не анализируя сами, но есть вероятность, что компилятор встроит вызовы, которые делает очередь . То есть, когда вы говорите queue.push () , на самом деле он просто скажет queue.container.push_back () , полностью пропуская вызов функции.

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

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

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