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

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

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

PS произвольный доступ не нужен

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

Используйте файл 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, с другой стороны, выделяет блоки. Он будет выделять реже, чем файл list. Думайте об этом как о списке, но каждый блок памяти может содержать несколько узлов. (Конечно, я бы посоветовал вам действительно узнать, как это работает .)

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

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

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

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

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

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

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

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

Если производительность действительно имеет значение, обратите внимание на библиотеку циклических буферов Boost .

Я постоянно добавляю push_backновые элементы, пока pop_frontобрабатываю самый старый элемент (около миллиона раз).

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

А почему бы и нет std::queue? Все, что у него есть, это push_backи pop_front.

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

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

Используйте std::queue, но помните о компромиссах производительности двух стандартных Containerклассов.

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

Однако не закрывайте глаза на реализацию std :: deque . В частности:

"... двухсторонние очереди обычно имеют большую минимальную стоимость памяти; двухсторонняя очередь, содержащая только один элемент, должна выделить весь свой внутренний массив (например, в 8 раз больше размера объекта в 64-битной libstdc ++; в 16 раз больше размера объекта или 4096 байт, в зависимости от того, что больше , на 64-битной libc ++) ".

Чтобы понять это, предположим, что запись в очереди - это то, что вы хотите поставить в очередь, то есть достаточно маленького размера, тогда, если у вас есть 4 очереди, каждая из которых содержит 30 000 записей, std::dequeреализация будет вариантом выбора. И наоборот, если у вас 30 000 очередей, каждая из которых содержит 4 записи, то, скорее всего, std::listреализация будет оптимальной, так как std::dequeв этом сценарии вы никогда не окупите накладные расходы.

Вы прочтете множество мнений о том, насколько важен кеш, как Страуструп ненавидит связанные списки и т. Д., И все это правда при определенных условиях. Только не принимайте это на веру, потому что в нашем втором сценарии очень маловероятно, что std::dequeреализация по умолчанию будет работать. Оцените свое использование и измерьте.

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

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};