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

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.

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.

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.

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.