Menu
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.
353
Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. Vector of Maps in STL: Vector of maps can be used to design complex and efficient data structures.
std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare . Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.
Here is a rule of thumb: If you want to add elements to your container or remove elements from your container, use a std::vector; if not, use a std::array.
Vector is implemented as a dynamically allocated array. The memory for this array is allocated in the constructor. As more elements are inserted the array is dynamically increased in size. A constructor without parameter creates an array with a default size.
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, called AssocVector.
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.
107
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
