unordered_map has no lower_bound?
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;
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
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. Daniel
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.
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 :-)
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
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
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
participants (4)
-
Ben Hutchings -
Daniel James -
Martin Wartens -
Peter Dimov