C++ Лучшая структура данных для хранения последних X входящих элементов?

Question

Я изначально хранили «входящие элементы» с помощью вектора, но даже с большим объемом оперативной памяти это было непрактично. Поэтому я решил сохранить последние X полученных предметов.

Какая будет лучшая структура данных? Я думал о std :: queue? Это псевдо-код, который я имел в виду:

if(queue.size() == max_size){ 
    queue.pop() 
} 

queue.push(new_item); 

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

Answer 1

Try Deque, IMO это то, что вы ищете:

http://www.cplusplus.com/reference/deque/deque/

Answer 2

Я хотел бы использовать структуру ring buffer данных. C++ STL не предоставляет один, но это тривиально. Все, что вам нужно - это массив фиксированного размера и индекс.

Вот пример реализации, похожий на тот, который я использую:

#include <iostream> 
template <typename T, size_t TSize> 
struct RingBuffer{ 
    enum{array_size = TSize+1}; 
    T array[array_size]; 
    size_t read; 
    size_t write; 
    RingBuffer():read(0),write(0){} 

    T& pop(){ 
     T* p = NULL; //Return NULL reference if empty intentionally 
     if(read!=write){ 
      p=array+read; 
      read = (read+1)%array_size; 
     } 
     return *p; 
    } 
    bool is_empty(){return write==read;} 
    bool is_full(){return (write+1)%array_size == read;} 
    void push(T& v){ 
     array[write]=v; 
     write = (write+1)%array_size; 
     //Gracefully handle write overflow 
     if(write==read)read=(read+1)%array_size; 

    } 
}; 
int main(int argc, const char * argv[]) 
{ 
    RingBuffer<int, 10> r; 
    for(int i=0;i<15;++i) r.push(i); 
    while (!r.is_empty()) std::cout<<r.pop()<<"\n"; 
    return 0; 
} 

Answer 3

http://www.boost.org/doc/libs/1_55_0/doc/html/circular_buffer.html

Это может быть то, что вы ищете?