CODEWITHSUNDEEP
c++arraysperformancelistvector
user2955554
user2955554

Reputation: 309

C++ vector, list or array for fixed size and predefined type data

I'm trying to select the appropriate data type for a new project to fit the following requirements:

ex. let's say 1,2,3,4,5,6 inserted into the container. After some time 6 will be deleted and 7 will be inserted so the list would be 7,1,2,3,4,5 and then 5 will deleted etc... but the size must be same.

I was wondering which data structure will be the most efficient and suitable one for my situtation from performance and memory point of view.

Thanks...

edit: by the way its a little bit different froö the basic FIFO logic because lets say we create 10 elements (size) data container but inserted only 3 elements even it has not reach the end of the container(limit of the size), if the specified time passed it would be deleted.

By the way i was thinking about to use boost:array but a little bit confused about std:vector and std:deque. Is there any specific advantage in this situtaion?

Upvotes: 2

Views: 1635

Answers (5)

Grimm The Opiner
Grimm The Opiner

Reputation: 1806

We all know from our data structures and algorithm classes that where inserts and deletes are likely we should use a linked list of some sort. It might be that what we know is wrong though.

Modern memory is blisteringly fast copying huge chunks of data around (so you shouldn't worry as much as you think about copying data around) and uses caching for linear searches (which a linked list structure will effectively defeat). These two factors combined may well mean you should use a good old vector or boost::array.

But don't take my word for it, here's Bjarn Stroustrup explaining it all.

Upvotes: 0

6502
6502

Reputation: 114481

The fastest solution for this is a statically-allocated array where you handle the queue yourself using head/tail/count; for example

#define MAX_NUMBER_OF_ELEMENTS 10

// Use statically-allocated memory
unsigned char raw_buf[MAX_NUMBER_OF_ELEMENTS * sizeof(X)];
X * const buf = (X *)&raw_buf[0];
int head, tail, count;

// Returns the address for a new element on the queue
inline void *add_element_address() {
    void *p = &buf[head];
    if (++head == MAX_NUMBER_OF_ELEMENTS) head = 0;
    count++;
    return p;
}

// Removes oldest element from the queue
inline void remove_element() {
    buf[tail].~X();
    if (++tail == MAX_NUMBER_OF_ELEMENTS) tail = 0;
    count--;
}

// Get the n-th element from the queue where 0 is the
// last added element and count-1 is the oldest one.
X& element(int index) {
    index = head - index - 1;
    if (index < 0) index += MAX_NUMBER_OF_ELEMENTS;
    return buf[index];
}

void add_element(... constructor arguments ...) {
    new (add_element_address()) X(... constructor arguments ...);
}

With this approach the buffer will be at a fixed address in memory (thus also freeing a register) and no copy of any kind is needed on the objects (they're constructed directly in place using placement new). Adding, removing and indexed access operations are all O(1).

Upvotes: 0

Evgeny Lazin
Evgeny Lazin

Reputation: 9413

You need std::queue backed by std::vector with some fixed capacity:

std::vector<YourType> underlying_storage(capacity);
std::queue<YourType, std::vector<YourType>> queue(std::move(underlying_storage));

// Now your queue is backed up by vector with predefined capacity

Upvotes: 0

Michal
Michal

Reputation: 2228

What you need is a cyclic buffer build on fixed-size array, this is very simple and the fastest data structure.

You can write your own cyclic buffer class or try to use boost implementation of cyclic buffer http://www.boost.org/doc/libs/1_54_0/libs/circular_buffer/doc/circular_buffer.html

Upvotes: 6

ice-phoenix
ice-phoenix

Reputation: 361

Looks like you need a queue, probably backed up by some optimized fixed-size container with FIFO support.

Upvotes: 1

Related Questions