Enjoying Both Worlds: vector With insert/erase efficiency of list

Question

I need a container that gives me a fast indexer and can also be very efficiency in arbitrary insertion and deletion operations (meaning at any position of the container).

I remember reading about such container that uses buckets but I can't seem to find it or retrace the steps that lead me to it (I will start using the bookmarks, promise!)

Thank you kindly.

Answer 1

I need this kind of container for a sparse vector container that I wrote, I can't use map<> because it takes too much memory (the vector is not that sparse).

I ended up using a compressed bit vector. Each enum value has its own bit vector and this turn up rather well.

I still wish that I could find an efficient vector/list hybrid that is O(1) on random access and at least O(log N) in erase/insert.

Answer 2

You are looking for std::deque, which out-performs std::list under many (but not all) circumstances when insertion at places other than the ends is required. It uses "buckets" to do this, and supports random access. Really, for any standard library container, you need to test its performance against your application's use of it - we can't predict for you what will be best.

Answer 3

You may be looking for some sort of hash map, like boost::unordered_map (soon to be in the C++ standard). There are plenty of other hash implementations out there.