CODEWITHSUNDEEP
c++data-structures
mgr
mgr

Reputation: 157

Proper data structure to store last n elements in C++

I need to store last n time values and I'm using a vector for this. I can do this and it works, but my question is, at long run, the vector would fill up and I might run out of memory right?. I'm using a stl vector of floats.

To be more clear : I'm pushing back time values from another process and i ONLY need the last 5 time values.

How can I do this efficiently, without letting the vector fill up and eventually run out of memory?

Upvotes: 5

Views: 4342

Answers (6)

codenumb
codenumb

Reputation: 61

I think the data should shift to the next place whenever a new data comes,
ie:
4->5->6->7 //old data
when a new data comes, the expected array must be
5->6->7->8 //updated
for that 

int arr[4]={0};
int count=0;
int head=0;

void insert(int data)
{

    arr[count%4]=data;
    count++;
    if(count > 4)
        head=count%4;
    printf("count=%d head=%d\n",count,head);
}

void display()
{
    int i;
    for(i=0;i<4;i++)
    {
        printf("%d->",arr[(head+i)%4]);
    }
    printf("\n");
}

int item_at(int i)
{
    return arr[(head+i)%4];
}

int main ()
{
    int opt,data;
    while(1)
    {
        printf("0. Exit\n1. Insert\n2. Display\n3. Item at\n");
        scanf("%d",&opt);
        if(opt == 0)
            return 0;
        else if(opt == 1)
        {
            scanf("%d",&data);
            insert(data);
        }
        else if(opt == 2)
        {
            display();
        }
        else if(opt == 3)
        {
            scanf("%d",&data);
            printf("arr[%d]=%d\n",data, item_at(data));
        }
    }
return 0;
}

Upvotes: 0

Gaminic
Gaminic

Reputation: 581

To my knowledge, a queue (or deque) isn't circular in its memory usage. It will, instead, grow when needed and occassionally copy to fit.

I'd suggest making your own structure. All you need is an array of size 5, and a pointer (or index) for the 'last' item, which is going to be overwritten with the next new one. Each time a new value is added, the 'last' item is overwritten and the 'last' pointer is moved up:

last = (last+1)%5;

Make sure to find a good way to handle the start, where there are less than 5 items in the array. If you just fill the array with error/neutral values at the start, you should be okay.

Upvotes: 4

Adri&#225;n P&#233;rez
Adri&#225;n P&#233;rez

Reputation: 2216

Didnt remember the container name :) I would use a std::queue container. So you can delete from the other end without worrying about positions within the sequence. About the threading thing... I think I cannot help but afaik vectors and list are not thread safe.

Upvotes: 0

forrestchen
forrestchen

Reputation: 1

I think the STL queue is what you want.

Upvotes: 0

mkaes
mkaes

Reputation: 14119

Sounds as if you want a circular buffer that overrides the values.
Take a look at boost for an example.

Upvotes: 6

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

Use a queue - it is perfect in that case. You push in the queue until it's size is 5 and then when adding a new value, you first pop from the queue and then push into it.

EDIT: if you need to be able to have direct access to all 5 elements probably a deque is a better option. I also believe the default queue implementation is based on deque.

Upvotes: 3

Related Questions