STL Hash_Map question

[Axel Gallus]

I want to search the key which is lower or equal than
a given key in a hash_map.

I am using the MS Visual C++ hash_map, which is not included in the STL
http://msdn2.microsoft.com/en-us/library/h80zf4bx(VS.71).aspx
and in my opinion there is no method which
could do this directly (There are only a upper_bound() and lower_bound()
function
which deliver the first key equal or greater than the given key).

How would you search for the key which is lower or equal to the given
exploiting the
const time characteristics of a hash_map efficiently?

Greetings

A.Galllus

 

[Gianni Mariani]

I want to search the key which is lower or equal than
a given key in a hash_map.

I am using the MS Visual C++ hash_map, which is not included in the STL
http://msdn2.microsoft.com/en-us/library/h80zf4bx(VS.71).aspx
and in my opinion there is no method which
could do this directly (There are only a upper_bound() and lower_bound()
function
which deliver the first key equal or greater than the given key).

How would you search for the key which is lower or equal to the given
exploiting the
const time characteristics of a hash_map efficiently?

You can't. By definition, a hash map hashes the key - randomizes it so
to speak so that exact matches are statistically O(1). You would need
to do an exhaustive search or alternatively place the keys in both a
hash map and a regular map and search the most appropriate map. There
are all kinds of strategies for lazy indexing strategies that perform
the indexing operations just before you need them and cache the results.

I once had a situation where I would keep an ordered list of keys, once
a new key was inserted I placed the key in an unordered section of the
list. When the unordered section of the list became larger than some
threshold, it was resorted (merged back into the rest of the ordered
list). Naturally searches required a binary search on the ordered part
of the list and a sequential search on the un-ordered part.

This was almost 20 years ago. Now I would use std::map<> and only
bother looking at new strategies once it was determined that this was a
performance issue.