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

views:

141

answers:

+2 Q:

[STL] 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.

+3 A:

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.

David Thornley 2010-08-02 21:37:19

all variants of map take too much memory

Shay Erlichmen 2010-08-03 09:44:27

+1 A:

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.

anon 2010-08-02 22:50:20

Just to be clear, deque's buckets aren't useful in insertion/deletion from the middle - according to the documentation, it's still an O(n) operation. I suppose it's possible that some implementations grow them independently.

Stephen 2010-08-03 00:22:17

@Stephen O(N) does not mean that overall performance is slow - tests I (and others) have done show that deque is faster, in real terms, than list in many circumstances. For example, to erase from a list or deque you have to find the erasure point, which is O(N) for lists. The one advantage of lists is that iterators are not invalifdated by erase or insert, but at least in my code this is very rarely a requirement.

anon 2010-08-03 07:15:56

@Neil I tested it with std::deque but the results are still too slow for my needs.

Shay Erlichmen 2010-08-03 09:43:21

@Neil : agreed. I just wanted to point out that it's not O(bucket size) to insert in a middle bucket.

Stephen 2010-08-03 13:21:45

@Shay : you could probably implement your own container, based off deque or vector, which grows the buckets independently. But it'll be slower on random access, because it'll need to compute the index. I'm confused why you need this array-like behavior but don't iterate the array. Perhaps a hash set/map is best?

Stephen 2010-08-03 13:26:57

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.

Shay Erlichmen 2010-08-03 09:53:12

@Shay: There is no one true data structure. All commonly used ones have strengths and weaknesses. Fortunately for you, a bit vector was possible, because you seemed to be asking for something with the strengths of a vector, a list, and a map with the disadvantages of none of those.

David Thornley 2010-08-03 13:54:10

ansaurus

tags:

views:

answers:

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

related questions