Associative container with predictable keys: which one to use?

Question

A simple question, but the answer is not obvious to me: For performance reasons, which map-type (or maybe non map-type?) container should I, from a performance perspective, best use in the following scenario:

• keys are unsigned integer numbers,
• insertions are frequent,
• read access is even more frequent and random access,
• items are inserted with ascending key values (first inserted item has key 0, next one key 1 and so on),
• items are removed randomly (so sooner or later the list of keys will have "holes", as the corresponding items have been deleted). Removal is almost as frequent as insertion.

I hesitate to use std::map, as ascending key order and frequent removal seem to imply continuous re-balancing of the search tree, which to me seems to be a waste of performance.

In other words: Can I gain performance from the fact that I know in advance what the keys of the items will be and even the order in which the keys will appear for insertion? (I do not know the total number of items, though.)

Answer 1

If you do use an stl::map -- even if just for profiling to compare with a hash -- you can use your knowledge that "items are inserted with ascending key values" to greatly increase the efficiency of the stl::map insertion operation by giving a hint to the insert call:

iterator insert ( iterator position_hint, const value_type& x );

... where the position_hint will be, for example, an iterator to the previous item inserted.

Answer 2

If memory is not a problem, why not use a std::vector of some custom type? You could have the fastest access times, since all elements are in order, and just save a flag if an element is removed. Consider this proxy class:

template<typename RealType>
class MyProxy {
public:
    RealType instance;
    bool isused;


    MyProxy(RealType) { /* TODO */ }
};

Which is then used within your std::vector:

std::vector<MyProxy<MyRealType> > vec;

For a lookup, you just have to check whether the index is within the bounds of the std::vector and that the isused flag is true. For removal just get the element of index i and set the flag to false. For insertion you have to push_back a new instance of MyProxy<MyType> instead of MyType.

The drawback of this approach is of course, that the std::vector is constantly growing, so you have to keep an eye on memory consumption and eventually freeing the vector, but this is possibly the fastest method for lookup, insertion and removal.