[Boost-users] Re: unordered_map has no lower_bound?

From: Daniel James (daniel_at_[hidden])
Date: 2005-03-28 11:44:31

Martin Wartens wrote:
> Hi,
> I am already using the unordered_map implementation from the file vault. I have 
> got some problems with unordered_map, because it offers no "lower_bound" (it is 
> not a problem of the implementation, it is simply not in the specs). My 
> question is, why is that so and what can I do about it?

Because the container isn't ordered, so there is no concept of 'greater 
than' or 'less than' here. Just equality.

> Then I can insert the new element in the map with the "hint"-version of insert:
> mymap.insert(iter, newelement);
> The hint-version starts searching at the hint for the correct insertion point, 
> so we don't have to search through the map twice. It is strange that such a 
> hint-insert also exists for the unordered_map. But what hint could I give it, 
> if I don't have lower_bound?

The standard doesn't specify this, and it's not really that useful. My 
implementation will make use of a hint that's pointing to a value with 
an equal key, which, I think, is just about all you can do. But as long 
as you don't have many collisions, insert is pretty fast without a hint.

> PS: there is a small problem in hash_table.hpp causing a warning in VC7.1
> line 278 should be:
> return (*prev_ptr)!=0;
> instead of
> return *prev_ptr;

Thanks, someone else pointed that out, and I forgot about it. It's an 
annoying warning but I'll change the code.

Daniel