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?

Tardif

I don't understand your question... You want to implement a circular list using std:vector? – Upton

no. this is my implementation with std::vector. However it not a good looking idea. insert and then delete to keep the size fixed... – Tardif

boost.org/doc/libs/1_49_0/libs/circular_buffer/doc/… perhaps? – Motherhood

First thing the removal of the element would not use delete but probably erase, and I fail to see how replacing the element in one position (that is the net effect of the code above interpreted as pseudo code, I.e. ignoring the undefined behavior of using the iterator after the insertion) would help I building a circular buffer. You probably meant to remove from the head and insert at the tail? – Smalt

BTW you have a bug: insert could potentially invalidate the iterator it, so erase could crash or corrupt the memory. – Utile

I edited the post. I use erase. Also this is not pseudo code. it is part of the code – Tardif

@Bart. using boost is also good. However I want to see if it is possible with stl or not. – Tardif

Answer 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.

Blinnie

Answer 2

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?

Micrometry

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

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

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

@Tardif what's the point of using dynamic structures if the size is fixed? – Micrometry

Answer 3

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

Volunteer

Answer 4

Try std::deque. The interface is like using a std::vector but insert and removal at beginning and end are more efficient.

Molybdenous

Answer 5

You can use your vectors as usual, and then create a get_element(index) function to make it feel circular. It's pretty fast and straight-forward, since it's just integer manipulation.

template<typename T>
T get_element(std::vector<T> vec, int index) {
    int vector_size = vec.size();
    int vector_max = vector_size - 1;
    int vector_min = 0;
    int index_diff = 0;
    int refined_index = 0;

    // index_diff is the amount of index-out-of-range. Positive means index was
    // bigger than the vector size, negative means index was smaller than 0
    if (index > vector_max) {
        index_diff = index - vector_max;
    } else if (index < vector_min) {
        index_diff = index;
    } else {
        index_diff = 0;
    }

    // Make the indexing feel circular
    // index mod 16 yields a number from 0 to 15
    if (index_diff > 0) {
        refined_index = index % vector_size;
    } else if (index_diff < 0) {
        int temp_index = index % vector_size;

        if (temp_index != 0) {
            refined_index = vector_size - std::abs(temp_index);
            // if the negative mod equals to 0, we can't have 16 - 0 = 16 index,
            // so we set it to 0 manually
        } else {
            refined_index = 0;
        }
    } else {
        refined_index = index;
    }

    return vec[refined_index];
}

Then use it like:

int result = get_element<int>(myvec, 256);

Note that any index smaller than 0 starts rotating from the last element of your vector, which is of course intended.

Ronel