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

Question

Какой контейнер STL лучше всего подходит мне? У меня в основном есть контейнер с 10 элементами, в котором я постоянно push_back новых элементов, а pop_front Самый старый элемент (около миллиона раз).

Я в настоящее время использую std::deque для выполнения этой задачи, но было интересно, если std::list будет более эффективным, так как я не должен был бы перераспределить себя (или, может быть, я спутать с std::deque для std::vector?). Или есть еще более эффективный контейнер для моей потребности?

P.S. Мне не нужен произвольный доступ

Answer 1

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

Используйте 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()), так как мы решаем?

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

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

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

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

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

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

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

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

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

Answer 2

A queue, вероятно, более простой интерфейс, чем deque, но для такого небольшого списка разница в производительности, вероятно, незначительна.

То же самое касается list. Это просто выбор того, какой API вы хотите.

Answer 3

Отъезд std :: queue. Он обертывает базовый тип контейнера, а контейнер по умолчанию - std :: deque.

Answer 4

Почему не std::queue? Все, что есть, это push_back и pop_front.

Answer 5

I постоянно во push_back новые элементы в то время как pop_front ИНГ самый старый элемент (около миллиона раз).

Миллион действительно не большой номер в вычислительной технике. Как предложили другие, используйте std::queue в качестве своего первого решения. В маловероятном случае, когда он будет слишком медленным, определите узкое место с использованием профайлера (не угадайте!) И повторите реализацию с использованием другого контейнера с тем же интерфейсом.

Answer 6

Если производительность действительно имеет значение, проверьте Boost circular buffer library.