Which container should I use for random access, cheap addition and removal (without de/allocation), with a known maximum size?

Question

I need the lighter container that must store till 128 unsigned int. It must add, edit and remove each element accessing it quickly, without allocating new memory every time (I already know it will be max 128).

Such as:

add int 40 at index 4 (1/128 item used)
add int 36 at index 90 (2/128 item used)
edit to value 42 the element at index 4
add int 36 at index 54 (3/128 item used)
remove element with index 90 (2/128 item used)
remove element with index 4 (1/128 item used)

... and so on. So every time I can iterate trought only the real number of elements added to the container, not all and check if NULL or not.

During this process, as I said, it must not allocating/reallocating new memory, since I'm using an app that manage "audio" data and this means a glitch every time I touch the memory.

Which container would be the right candidate? It sounds like a "indexes" queue.

Answer 1

As I understand the question, you have two operations

Insert/replace element value at cell index
Delete element at cell index

and one predicate

Is cell index currently occupied?

This is an array and a bitmap. When you insert/replace, you stick the value in the array cell and set the bitmap bit. When you delete, you clear the bitmap bit. When you ask, you query the bitmap bit.

Answer 2

You can just use std::vector<int> and do vector.reserve(128); to keep the vector from allocating memory. This doesn't allow you to keep track of particular indices though.

If you need to keep track of an 'index' you could use std::vector<std::pair<int, int>>. This doesn't allow random access though.

Answer 3

If you only need cheap setting and erasing values, just use an array. You can keep track of what cells are used by marking them in another array (or bitmap). Or by just defining one value (e.g. 0 or -1) as an "unused" value.

Of course, if you need to iterate over all used cells, you need to scan the whole array. But that's a tradeoff you need to make: either do more work during adding and erasing, or do more work during a search. (Note that an .insert() in the middle of a vector<> will move data around.)

In any case, 128 elements is so few, that a scan through the whole array will be negligible work. And frankly, I think anything more complex than a vector will be total overkill. :)

Roughly:

unsigned data[128] = {0}; // initialize
unsigned used[128] = {0};
data[index] = newvalue; used[index] = 1; // set value
data[index] = used[index] = 0;           // unset value
// check if a cell is used and do something 
if (used[index]) { do something } else { do something else }