Контейнер FIFO - Какой контейнер STL наиболее подходит и почему? - PullRequest
Новая
       28

Контейнер FIFO - Какой контейнер STL наиболее подходит и почему?

5 голосов
/ 05 ноября 2011

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

Теперь проблема заключается здесь:

У нас есть опция ведения журнала трассировки, которая используется для отладки. Когда эта опция включена, количество сообщений в секунду увеличивается в геометрической прогрессии. В коде выпуска кода трассировка отключена, однако буфер, который может хранить фиксированное количество сообщений, например, 10000 сбрасывается в журнал ЕСЛИ возникает ошибка, так что разработчики могут определить корень проблемы.

Если буфер заполнен, самое старое сообщение удаляется, чтобы освободить место для самого нового сообщения. 

void Log::storeToBuffer(const LogType_E & type_in, const LogDomain_E & domain_in,const int & id_in, const char * msg_in)
{
    if(this->myEnableTraceBuffer)
    {
        if(static_cast<std::list<Message> * >(this->myRingBuffer)->size() < this->myRingBufferMaxSize)
        {
            static_cast<std::list<Message> * >(this->myRingBuffer)->push_back(Message(type_in, domain_in, id_in, msg_in));
        }
        else
        {
            //buffer full so remove oldest element and add new
            if(static_cast<std::list<Message> * >(this->myRingBuffer)->size() > 0) static_cast<std::list<Message> * >(this->myRingBuffer)->pop_front();
            static_cast<std::list<Message> * >(this->myRingBuffer)->push_back(Message(type_in, domain_in, id_in, msg_in));
        }
    }
}

Я реализовал это с помощью std :: list, очень просто используя push_back / pop_front, чтобы использовать постоянное время выполнения удаления / вставки. ( не спрашивайте о лишении свободы, не мое решение ).

Но так как размер буфера фиксирован и вряд ли изменится в течение времени жизни объекта, может быть, вектор с явным манипулированием индексом более подходит? Например, может быть два индекса: начальный / текущий, начиная с позиции 0. Когда вектор заполнен, и мы добавляем что-то, начало перемещается в положение 1, а текущее в положение 0, поэтому при печати результата мы имеем правильный порядок.

Может быть, другой контейнер STL больше подходит для такого рода вещей?

Спасибо за ваше терпение прочитать эту длинную стену текста. Я здесь, чтобы ответить на любые вопросы.

Ответы [ 4 ]

3 голосов
/ 05 ноября 2011

std::deque может эффективно вставлять или удалять либо в начале, либо в конце, что делает его отличной структурой для буфера.Его можно использовать как тип шаблона для std::queue, который идеально подходит для вашего приложения - просто проверяйте размер очереди каждый раз, когда вы делаете push и pop, если размер превышает максимальный.

2 голосов
/ 05 ноября 2011

То, что вы ищете, это двусторонняя очередь, в которую можно добавлять элементы, удаляемые из передней / задней части, и версия стандартной библиотеки C ++ это std::deque. Он похож на std::vector по своей функциональности (например, доступ по индексу, но будьте осторожны, нет гарантированного непрерывного хранения), но поддерживает быструю вставку и удаление спереди и сзади. Я думаю, что внутренне это фактически реализовано как простой массив, используемый как кольцевой буфер.

Единственная проблема, которую я вижу здесь, это то, что она не предоставляет reserve метод, я думаю. Таким образом, вы не можете сказать с самого начала, что это должно освободить место для ваших потенциальных 10000 элементов и принять во внимание некоторые перераспределения. Но они должны амортизировать, как для векторов. Все еще лучше, чем std::list 10000 или более небольших выделений. Как только он имеет размер 10000 элементов, выделений больше не должно быть, тогда как std::list будет постоянно освобождать и выделять новые объекты.

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

2 голосов
/ 05 ноября 2011

Несмотря на то, что push_back / pop_front в std :: list - это постоянное время, они будут использовать выделение кучи, что, вероятно, станет для вас узким местом.

Подход, который вы описываете с помощью std :: vector, устранит выделение кучи и в результате, вероятно, пойдет быстрее. Использование std :: vector, как вы описали, является кольцевым буфером, и если вы можете использовать boost, то здесь доступен stl-совместимый: http://www.boost.org/doc/libs/1_47_0/libs/circular_buffer/doc/circular_buffer.html

2 голосов
/ 05 ноября 2011

Когда-нибудь слышали о std::deque? :)
Это позволяет амортизировать произвольный доступ с постоянным временем и операции push / pop с постоянным временем с обеих сторон. Как таковой, он может быть легко использован как очередь FIFO.

Тем не менее, поскольку он может использоваться как таковой, есть контейнерный адаптер std::queue, хотя он не предлагает произвольного доступа и интерфейса итератора.

...