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 } 

Answer 4

I'd suggest a tandem of vectors, one to hold the active indices, the other to hold the data:

class Container
{
  std::vector<size_t> indices;
  std::vector<int> data;

  size_t index_worldToData(size_t worldIndex) const
  {
    auto it = std::lower_bound(begin(indices), end(indices), worldIndex);
    return it - begin(indices);
  }

public:
  Container()
  {
    indices.reserve(128);
    data.reserve(128);
  }

  int& operator[] (size_t worldIndex)
  {
    return data[index_worldToData(worldIndex)];
  }

  void addElement(size_t worldIndex, int element)
  {
    auto dataIndex = index_worldToData(worldIndex);
    indices.insert(it, worldIndex);
    data.insert(begin(data) + dataIndex, element);
  }

  void removeElement(size_t worldIndex)
  {
    auto dataIndex = index_worldToData(worldIndex);
    indices.erase(begin(indices) + dataIndex);
    data.erase(begin(indices) + dataIndex);
  }

  class iterator
  {
    Container *cnt;
    size_t dataIndex;

  public:
    int& operator* () const { return cnt.data[dataIndex]; }
    iterator& operator++ () { ++dataIndex; }
  };

  iterator begin() { return iterator{ this, 0 }; }
  iterator end() { return iterator{ this, indices.size() }; }
};

(Disclaimer: code not touched by compiler, preconditions checks omitted)

This one has logarithmic time element access, linear time insertion and removal, and allows iterating over non-empty elements.

Answer 5

You could use a doubly-linked list and an array of node pointers. Preallocate 128 list nodes and keep them on freelist. Create a empty itemlist. Allocate an array of 128 node pointers called items

• To insert at i: Pop the head node from freelist, add it to itemlist, set items[i] to point at it.
• To access/change a value, use items[i]->value
• To delete at i, remove the node pointed to by items[i], reinsert it in 'freelist'
• To iterate, just walk itemlist

Everything is O(1) except iteration, which is O(N_{active_items}). Only caveat is that iteration is not in index order.

Freelist can be singly-linked, or even an array of nodes, as all you need is pop and push.

Answer 6

class Container {
  private:
    set<size_t> indices;
    unsigned int buffer[128];
  public:
    void set_elem(const size_t index, const unsigned int element) {
      buffer[index] = element;
      indices.insert(index);
    }
    // and so on -- iterate over the indices if necessary
};

Answer 7

There are multiple approaches that you can use, I will cite them in order of effort expended.

---

The most affordable solution is to use the Boost non-standard containers, of particular interest is flat_map. Essentially, a flat_map offers the interface of a map over the storage provided by a dynamic array.

You can call its reserve member at the start to avoid memory allocation afterward.

---

A slightly more involved solution is to code your own memory allocator.

The interface of an allocator is relatively easy to deal with, so that coding an allocator is quite simple. Create a pool-allocator which will never release any element, warm it up (allocate 128 elements) and you are ready to go: it can be plugged in any collection to make it memory-allocation-free.

Of particular interest, here, is of course std::map.

---

Finally, there is the do-it-yourself road. Much more involved, quite obviously: the number of operations supported by standard containers is just... huge.

Still, if you have the time or can live with only a subset of those operations, then this road has one undeniable advantage: you can tailor the container specifically to your needs.

Of particular interest here is the idea of having a std::vector<boost::optional<int>> of 128 elements... except that since this representation is quite space inefficient, we use the Data-Oriented Design to instead make it two vectors: std::vector<int> and std::vector<bool>, which is much more compact, or even...

struct Container {
    size_t const Size = 128;

    int array[Size];
    std::bitset<Size> marker;
}

which is both compact and allocation-free.

Now, iterating requires iterating the bitset for present elements, which might seem wasteful at first, but said bitset is only 16 bytes long so it's a breeze! (because at such scale memory locality trumps big-O complexity)

Answer 8

Why not use std::map<int, int>, it provides random access and is sparse.

Answer 9

If a vector (pre-reserved) is not handy enough, look into Boost.Container for various “flat” varieties of indexed collections. This will store everything in a vector and not need memory manipulation, but adds a layer on top to make it a set or map, indexable by which elements are present and able to tell which are not.