Re: How to get an insertion hint for an unordered associated
container?
On Nov 21, 8:34 pm, Pavel
<pauldontspamt...@removeyourself.dontspam.yahoo> wrote:
I am trying to figure out if I can use tr1/C++0x
std::unordered_map to speed-up an algorithm I did before using
an ordered map.
The problem is quite common:
BEGIN
Given a key 'k', if no equivalent of 'k' is on the container,
create value and insert it; otherwise, update part of the
value that is already on the container in a specific way.
Creating the value (even a "default" one) comes at cost so I
do not want to create it if I do not need to insert.
END
With ordered ass. containers I solved it via equal_range() or
lower_bound() depending on the nature of the key and
subsequent insert() with "hint" iterator returned by one of
these functions if 'k' was not found. With unordered,
lower_bound() is not there for me and equal_range() is useless
as it returns a couple of end iterators if 'k' is not found as
opposed to a useful insertion point so I would have to lookup
again to insert.
Am I missing any known pattern of use of unordered associative
containers that would help to avoid an extra value-creation?
Any help would be appreciated.
One "standard" solution even with ordered containers is
something like:
MapType::iterator entry = myMap.find(key);
if ( entry != myMap.end() ) {
// insert...
}
This avoids the extra construction, at the cost of two look-ups,
when inserting. The cost of the second look-up can be
attenuated with ordered containers by using lower_bound, rather
than find, and using the return value as a hint---this does cost
an extra comparison in your code, however. The cost of the
second look-up in an unordered container cannot easily be
avoided, but it is O(1), and not O(lg n). The main potentially
avoidable cost would be calculating the hash code twice, but I
don't think that the interfaces currently available have any
provision to support this. (Basically, it would mean
calculating the hash value in user code, and having additional
variants of functions like find and insert which take a
pre-calculated hash value.)
IIRC, the unordered containers do have variants of insert which
take a "hint", but this is only present for compatibility with
the existing ordered containers; the hint is not used.
--
James Kanze