Effective container that keeps order and is fast at deleting elements from any position

Question

I am looking for a container in C++ that satisfies my following needs:

• I need to delete elements by index.
• Right after I delete one element, I will insert another on in the front (ALWAYS!!!!!)
• Besides that, there is not change in size.
• It NEEDS to be indexed.
• The values stored in the container are unique, as the index.
• One index should be assigned to one value. Unless i delete or add one values. Then the index should be adapted.

For another set of data, that is working kinda parallel to that container, I need one with these features and these additional:

• This one needs to work kinda in two directions: Since it stores a unique value, I need to be able to access the index through the actual value (which is 100% unique) very fast, since that will happen a lot of times.

I cannot grantee, that any of the value types support operators like <, <=, ... besides == and !=

If there are questions, go ahead an ask. If something is unclear, I will further explain it.

EDIT:

Since I've been requested, here comes the actual problem behind that:

I am writing a library made out of an template container class, which is able to store a certain amount of objects. All these Objects are the same type. (Well, of course...) Another very important property of these objects must be, that they can be recreated by a unique index. this index could be also anything. An example in this case would be a two dimensional space, where you can create objects, that are on the plane and all there properties can be recreated by giving the object class the coordinates (as a single object in this case). Now when the container reaches maximum capacity, it deletes the objects last used. My idea was here, that you give the container the unique index. If the desired object is still stored, the function return a pointer on the object and moves it inside the inner container to the front. If the desired object is NOT stored in the internal container, the last object in the internal container will be deleted and the new one will be generated and put to the front.

I need this, because I have a program which will easily use all my RAM and by far more. Well I could generated and destroy the object every time, but that just seems like a waste of computation power to me. So I came up with this container that only deletes the object, if it hasn't been used for quite a big time. Which is in my particularity case pretty useful (Path-finding on HUGE maps)

I hope that helps!

EDIT2:

Ok. I'm going to make this even more clear.

Let's start of with a simple data cache:

[0] d1  [1] d2  [2] d3  [3] d4

Now let's say I used d3. The structure should now look like this:

[0] d3  [1] d1  [2] d2  [3] d4

Now I add a completely new element to the container (d5).

[0] d5  [1] d3  [2] d1  [3] d2

That is the idea behind. Now instead of int-values as index, I allow to have a custom index class, which is able to restore every single object, that might possibly deleted (That is not a problem. Just a requirement in order for my class to work).

Let's begin with the beginning statement. That looks like this for the first case:

[0] i1  [1] i2  [2] i3  [3] i4
[i1] 0  [i2] 1  [i3] 2  [i4] 3

The second example looks like this:

[0] i3  [1] i1  [2] i2  [3] i4
[i1] 1  [i2] 2  [i3] 0  [i4] 3

And finally the last state looks like this:

[0] i5  [1] i3  [2] i1  [3] i2
[i1] 2  [i2] 3  [i3] 1  [i5] 0

I hope that makes it more clear. For the second one more than one container might be possible.

Answer 1

Just wanted to point out the multi_index_container solution has the same inefficiency as using a vector for random access support: deletion will have a cost linear in the size of the data structure. Internally, the random_access index uses a data structure similar to a vector of pointers.

There aren't that many data structures that allow both random access AND deletion of any element at better-than-linear time. AFAIK std::deque has linear time deletion, unless the item is close to one of the ends of the sequence.

This leaves us with balanced binary trees (and variants, like skip lists). A self balancing binary tree can maintain the size of the subtree below any node at a fixed overhead, and with this "augmentation" implement random access in O(log n). Unfortunately, the default implementations of std::map generally don't have this feature. So using std::map and std::advance gives you linear time random-access. You can't implement efficient random-access "on top" of std::map as your user code is not aware of the tree manipulations done internally by std::map.

You could roll your own (AVL trees are relatively easy to implement). Can't think of any easier way unless you're willing to accept poor performance on either the random access lookup or the delete+insert operation. The "least bad" solution that doesn't involve trees is probably using std::deque

EDIT: The augmented tree data structures I've mentioned are known as http://en.wikipedia.org/wiki/Order_statistic_tree.

Answer 2

Let's have a look at your requirements:

• Access by position
• Access by element
• Deletion at arbitrary position
• Unicity of elements

How to ?

• You need something with Random Access to support the "access by position", or at least close to Random Access O(log N) might be sufficient
• Given that elements may not support ordering, unicity would require the use of a hash-set

This can be easily achieved using Boost.MultiIndex I think. The examples section already gives a MRU cache implementation and you are close enough. I would suggest combining:

• a Random Access Index: yielding Access and Deletion by position
• with a Hashed Index: yielding Access by element and Unicity check

This means something like:

typedef multi_index_container<
  T,
  indexed_by<
    random_access<>,
    hashed_unique</*...*/>
  > 
> cache_type;

Note: that for a Hashed Index to work, you need both support for == (or a specialization of std::equal<T>) and a hash functor. The latter can be provided by the user at the point of declaration of the container if the type does not already support it.

Answer 3

If you are using boost c++ libraries, take a look at Multi-index containers.

http://www.boost.org/doc/libs/1_52_0/libs/multi_index/doc/index.html

Answer 4

Ok. Thank you everybody, but I found a very effective solution for this:

Since my problems requires the following data structure;

[0] d1  [1] d2  [2] d3  [3] d4
[0] i1  [1] i2  [2] i3  [3] i4
[i1] 0  [i2] 1  [i3] 2  [i4] 3

I decided, to use these Containers:

1. list
2. list
3. map

Through some research I found out about std::advance and std::next, which allow me to effectively access certain elements in the list. To update the map, I will just run a simple for loop, which should work quite efficient.

If you have better ideas, please post the here!

Thank you again!

Answer 5

Sorry - I find your question a bit vague - but I'll state what I think your requirement must be then discuss the data structure needs...

So, we have indexed data like - something like this (where indexes are in brackets):

[0] a  [1] h  [2] b  [3] q

Your main operation is the delete/insert - say we did delete element 2 and insert value x, we'd have:

[0] x  [1] a  [2] h  [3] q

So, if we call the element index being deleted n, given what we've effectively done is move [0..n-1] along one position, then overwrite [0] with the extra value.

Discussion

If you do this operation with a vector, then the move operation can be arbitrarily large and relatively slow. But if you use some other container such as an associative container (map, unordered map) you'd have to update the keys for all those "moved" elements anyway. Other common containers don't provide O(log2N) or better indexing, so aren't promising, so let's stick with vector and see how to minimise the pain. As well as the move being O(N), it involves shifting arbitrarily large objects: in the case when the objects are much larger than a pointer, you could have an array of points to objects and just move the array's pointers without moving the objects: that could be much faster (it's also useful for objects that don't like being moved, typical reason is the C++03 copy slowness for which C++11 introduced move operators).

I can't think of anything much better than this vector approach.

Returning to the vagueness of your question - if your confusing "index" with "key" and simply need a keyed container but don't need objects to shift their keys with each delete/insert operation, then a map or unordered map is a much better choice.