CODEWITHSUNDEEP
c++vectorstack
user997112
user997112

Reputation: 30615

C++ Best data structure to store last X incoming items?

I was originally storing "incoming items" using a vector, but even with a large amount of RAM this was not practical. I therefore decided to store the last X received items.

What would be the best data structure to use? I was thinking of a std::queue? This is the pseudo code I was thinking of:

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

queue.push(new_item);

The usage for the data structure would be to store a history of events and if used, would be to rollback- therefore iterating through each item in the structure.

Upvotes: 0

Views: 1770

Answers (3)

Skyler Saleh
Skyler Saleh

Reputation: 3991

I'd use a ring buffer data structure. The C++ STL doesn't provide one but it is trivial to make. All you need is a fixed size array and an index.

Here is an example implementation, similar to the one I use:

#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;
}

Upvotes: 8

cageman
cageman

Reputation: 333

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

That might be what you are looking for?

Upvotes: 0

smrt28
smrt28

Reputation: 469

Try deque, IMO it's what you are searching for:

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

Upvotes: 0

Related Questions