As I understand it, C++ STL maps are usually implemented as balanced binary trees, because this meets the requirements of efficient insertion and iterator invalidation. However, sometimes you don't need that functionality.
What if you have a set/map that will be queried a lot but where insertions and removals are rare? It seems like it would make sense to have a map type that is backed by a sorted array. Although lookups are still log time, they are presumably much faster due to the lack of multiple pointer dereferences while traversing the tree. Likewise, iteration is much faster.
So is this something that is commonly done? What is the easiest way to do it? It seems like the kind of thing that would be in Boost somewhere.
C++ maps and sets backed by array
It should be easy to implement yourself. The standard library provides std::vector, std::sort, std::upper_bound and std::lower_bound. I'm not aware of any de-facto standard implementation of this.
Author
I figured it would be easy to implement as long as you don't care about wrapping every single STL feature. But I was wondering about opinions of the usefulness of this and whether any standard implementations already exist.
In which case you would use vector, with std::binary_search and std::lower_bound.
EDIT: Epic ninja'd!
EDIT: Epic ninja'd!
If iteration order is not important you can use std::unordered_set and std::unordered_map instead. If your compiler doesn't have them yet, you can find them in boost. These containers are implemented as a hash table which often gives faster lookups.
Author
Thanks, I forgot about hashtables. I guess that makes the most sense in cases where you don't care about iteration order and can known enough about the problem to choose a good hash, which is a common case.
This has already been created. It's in the Loki library and is called AssocVector and is a drop-in replacement for map.
It has slight changes to the iterator invalidation rules, item relocation allowances, and the runtime complexity of a couple of operations.
I've reviewed it before and the only issue I spotted with it was that bulk inserts could be improved in terms of Big-Oh notation, which they may well have fixed now.
It has slight changes to the iterator invalidation rules, item relocation allowances, and the runtime complexity of a couple of operations.
I've reviewed it before and the only issue I spotted with it was that bulk inserts could be improved in terms of Big-Oh notation, which they may well have fixed now.
Author
Where can I find documentation for the GCC unordered_set and map implementations? I need to know the details in order to design a perfect hash function.
Has the profiler indicated that hash collisions are taking up a significant amount of your runtime?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
