Jump to content
  • Advertisement
Sign in to follow this  
Storyyeller

C++ maps and sets backed by array

This topic is 2480 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Has the profiler indicated that hash collisions are taking up a significant amount of your runtime?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!