[Boost-users] unordered_map has no lower_bound?

[Martin Wartens]

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?
The use case is an efficient insert when I have to take special actions when
the key is already in the container. For a map this would work like:
iter = lower_bound(key); which gets the first element greater or equal to key
Now I can check if the key is already in the map and execute some action to
handle this case.
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?
Thanks,
Martin

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;

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Daniel James]

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

[Daniel James]

> Martin Wartens wrote:
>> 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;

Ah, I just found out why I didn't do this before - prev_ptr might be a
pointer object (depending on the allocator), so the correct line is:

return (*prev_ptr) != link_ptr();

Which can potentially be inefficient. I think the best thing to do is to
use a pragma to disable the warning, or maybe:

return static_cast<bool>(*prev_ptr);

or:

return boost::implicit_cast<bool>(*prev_ptr);

would work.

[Ben Hutchings]

Daniel James wrote:
>> Martin Wartens wrote:
>>
>>> 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;
>
>
> Ah, I just found out why I didn't do this before - prev_ptr might be a
> pointer object (depending on the allocator), so the correct line is:
>
> return (*prev_ptr) != link_ptr();
>
> Which can potentially be inefficient. I think the best thing to do is to
> use a pragma to disable the warning,

If it's the warning I'm thinking of (C4800: "forcing value to bool
'true' or 'false'" - well, *duh*) then this is the right approach.

> or maybe:
>
> return static_cast<bool>(*prev_ptr);
>
> or:
>
> return boost::implicit_cast<bool>(*prev_ptr);
>
> would work.

Neither of those prevents the warning.

Ben.

[Peter Dimov]

Ben Hutchings wrote:

> Daniel James wrote:
>> Ah, I just found out why I didn't do this before - prev_ptr might be
>> a pointer object (depending on the allocator), so the correct line
>> is: return (*prev_ptr) != link_ptr();
>>
>> Which can potentially be inefficient. I think the best thing to do
>> is to use a pragma to disable the warning,
>
> If it's the warning I'm thinking of (C4800: "forcing value to bool
> 'true' or 'false'" - well, *duh*) then this is the right approach.
>
>> or maybe:
>>
>> return static_cast<bool>(*prev_ptr);
>>
>> or:
>>
>> return boost::implicit_cast<bool>(*prev_ptr);
>>
>> would work.
>
> Neither of those prevents the warning.

return *prev_ptr? true: false;

is what I use. The compiler is right, by the way, forcing the value to bool
does indeed produce suboptimal code, whereas the above workaround does not
:-)

[Gottlob Frege]

> Date: Mon, 04 Apr 2005 16:39:34 +0100
> From: Ben Hutchings <ben.hu...@businesswebsoftware.com>
> Subject: Re: [Boost-users] Re: unordered_map has no lower_bound?
> To: boost...@lists.boost.org
> Message-ID: <42515FB6...@businesswebsoftware.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed

>
> Daniel James wrote:
> >> Martin Wartens wrote:
> >>
> >>> 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;
> >
> >

> > Ah, I just found out why I didn't do this before - prev_ptr might be a
> > pointer object (depending on the allocator), so the correct line is:
> >
> > return (*prev_ptr) != link_ptr();
> >
> > Which can potentially be inefficient. I think the best thing to do is to
> > use a pragma to disable the warning,
>
> If it's the warning I'm thinking of (C4800: "forcing value to bool
> 'true' or 'false'" - well, *duh*) then this is the right approach.
>
> > or maybe:
> >
> > return static_cast<bool>(*prev_ptr);
> >
> > or:
> >
> > return boost::implicit_cast<bool>(*prev_ptr);
> >
> > would work.
>
> Neither of those prevents the warning.
>

> Ben.
>

I always use !! to prevent that warning. like

return !!*prev_ptr;

YMMV.

[Martin Wartens]

Hi,
I can confirm that the cast-variants don't prevent the warning. "return !!
*prev_ptr;" and "return *prev_ptr? true: false;" both seem to work.
Back to the main topic: I find it quite unsatisfiying that there is seems to be
no way to avoid searching for the same position twice
("get_bucket", "find_iterator"). I don't see where the hint-version of insert
could be of any use, especially since the standard says "Implementations are
permitted to ignore the hint". I would need a function like "insert_if" taking
a predicate that decides whether to insert when an object with the same key
already exists.

Martin

[Daniel James]

Martin Wartens wrote:
> Back to the main topic: I find it quite unsatisfiying that there is seems to be
> no way to avoid searching for the same position twice
> ("get_bucket", "find_iterator").

The only thing I can think of within TR1 would be to cache the result of
the previous search - but that would be very wasteful for any other
situation.

> I don't see where the hint-version of insert
> could be of any use

I think its main use is inserting from a range - if equivalent values
are adjacent there will be a slight speed up (depends on the hash
function and equality functions).

> especially since the standard says "Implementations are
> permitted to ignore the hint". I would need a function like "insert_if" taking
> a predicate that decides whether to insert when an object with the same key
> already exists.

If you have a problem with TR1, you be better of posting to comp.std.c++
or similar. I'm not going to implement any extensions without a very
good reason. Sorry.

Are you sure that searching twice is really hurting performance? With a
good hash function it shouldn't take long at all.

Daniel

[Martin Wartens]

> I think its main use is inserting from a range - if equivalent values
> are adjacent there will be a slight speed up (depends on the hash
> function and equality functions).

Aha!

> If you have a problem with TR1, you be better of posting to comp.std.c++
> or similar. I'm not going to implement any extensions without a very
> good reason. Sorry.

No, I didn't meant that :-) I was just having visions.

Thanks for your answers and of course for the implementation,
Martin