Efficient circular list

Question

I want a simple yet efficient circular buffer/queue. If I use std::vector, I have to do this:

if ( v.size() >= limit ) {
    std::vector<int> it = v.begin();
    v.insert( it, data );
    v.erase( it+1 );
}

Is there any simpler solution?

Solution 1

You want to maintain the size of the buffer, overwriting older items. Just overwrite the old ones as time goes on. If you want to deal with the case where nItems < limit, then you would need to deal with that, this is just a simple example of using modulo to insert into a fixed size buffer.

std::vector<int> data(10);

for (int i = 0 ; i < 100 ; ++i)
{
    data[i%10] = i;
}

for (std::vector<int>::const_iterator it = data.begin() ; it !=data.end(); ++it)
{
     std::cout << *it << std::endl;
}

That method of insertion will keep the last 10 elements in the buffer.

Solution 2

In c++11 for a fixed size alternative you should be using std::array:

const unsigned int BUFFER_SIZE = 10;
std::array<int, BUFFER_SIZE> buffer; // The buffer size is fixed at compile time.
for (i = 0; i < 100; ++i) {
    buffer[i % BUFFER_SIZE] = i;
}

Solution 3

A std::list might be an easier alternative to building a list than std::vector. There's also std::queue.

It's also funny that you're using a vector to implement a circular queue but ask a question on how to implement a circular list. Why not use a map?

Comments

[mahmood]

std::queue::push() also pushes at the end

[mahmood]

using std::list, I have to use push_front and pop_back to adjus the size. Right?

[mahmood]

how about fixed size? how it is possible with map?

[Luchian Grigore]

@mahmood what's the point of using dynamic structures if the size is fixed?