Is there already some std::vector based set/map implementation?

Question

For small sets or maps, it's usually much faster to just use a sorted vector, instead of the tree-based set/map - especially for something like 5-10 elements. LLVM has some classes in that spirit, but no real adapter that would provide a std::map like interface backed up with a std::vector.

Any (free) implementation of this out there?

Edit: Thanks for all the alternative ideas, but I'm really interested in a vector based set/map. I do have specific cases where I tend to create huge amounts of sets/maps which contain usually less than 10 elements, and I do really want to have less memory pressure. Think about for example neighbor edges for a vertex in a triangle mesh, you easily wind up with 100k sets of 3-4 elements each.

Answer 1

I don't know any such implementation, but there are some functions that help working with sorted vectors already in STL, such as lower_bound and upper_bound.

Answer 2

If the set or map truly is small, the performance gained by micro-optimizing the data structure will have little to no noticeable effects. You'll save maybe one or two memory (read: cache) lookups when searching a tiny tree vs tiny vector, which in the big picture is insignificant.

Having said that, you could give hash_map a try. Lookups by key are guaranteed to run in constant time.

Answer 3

Maybe you're looking for unordered map's and unordered set's. Try taking a look at the TR1 unordered containers that rely on hashing, or the Boost.Unordered container library. Underneath the interface, I'm not sure if they really do use std::vector, but I'd wager it's worth taking a look at.

Answer 4

If you can't find anything suitable, I would just wrap a std::vector to do sort() on insert, and implement find() using lower_bound(). It should be straight forward, and just as efficient as a custom solution.

Answer 5

I just stumbled upon your question, hope its not too late.

I recommend a great (open source) library named Loki. It has a vector based implementation of an associative container that is a drop-in replacement for std::map.

It offers better performance for accessing elements (and worst performance for insertions/deletions).

The library was written by Andrei Alexandrescu author of Modern C++ Design.

It also contains some other really nifty stuff.