[C++] HashMap - Near Exact Mapping

brianon

Guys,

I need to store ranges of numbers that will relate to an ID in a hashmap (hashmap being the choice for now).

So up to 120,000 entries. I will then be supplied with a number and must find the range it falls into and thus the corresponding ID.

So say I have 1-10=ID1, 11-20=ID12, 50-5000=ID44, 6000-10000=ID54

I would have a class OtherInfo with Int EndRange and ID
Then a hash_map <int, OtherInfo>

I fill the map with ...

1, (10:1) // this means 1 to 10 is ID 1
11, (20:12) // this means 11 to 20 is ID 12
50, (5000:44) // this means 50 to 5000 is ID 44
6000, (10000:54) // this means 6000 to 10000 is ID 54

Grand

Now I have to find the ID for 11. I map.find(11) on the map and get "11, (20:12)" which tells me ID=12. Lovely.

Now I want to find the ID for 15. I know it is the same map entry that I want to get BUT map.find(15) would not find anything because 15 is not one of the key values.

Is there anything I can do to get the nearest match ? Do I need to overload the == or >/< operators ?

Any help appreciated. Just not sure that a hash_map is suitable for range finding ... BUT good performance is a BIG requirement

Cheers,
Brian.

Tobias Greeshman

If you were using Java this would be so much easier, get the set of keys back, sort them and find the right key you need.

Anyways, one thing I would consider is subclassing the hash_map container and add a method that returns a collection of keys as a list maybe. Since the keys are all int's you could easily compare them. Now be warned you're gonna have to be comfortable with complex templated class definitions.

There's also the hash_map::key_comp() and hash_map::value_comp() which may be of use to you.

brianon

Cheers. Quick question ...

When you populate a hash_map, is it auto sorted ?

As in if I was to iterate through a hash_map would the keys (being ints) be in numerical order ?

Cheers.

brianon

Thinking about this...if hash_maps are not sorted then maybe I should use map and do a binary search ? Would that make more sense ?