Re: How to get an insertion hint for an unordered associated
container?
On Nov 24, 5:24 am, Pavel
<pauldontspamt...@removeyourself.dontspam.yahoo> wrote:
James Kanze wrote:
On Nov 21, 8:34 pm, Pavel
[...]
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.
That is actually avoidable in tr1/unordered map (you can
access bucket(const key_type &) etc). However, O(1) (on
average, worst case is linear), is not 1. In my domain area,
spending 2*O(1) instead of O(1) often means "you won, I lost".
So, I am trying to get to O(1) from 2 * O(1). If one assumes
that the lookup algorithm in hash is always like this:
1. Identify the bucket.
2. Linearly search in the bucket for the equal key or free spot or
end-of-bucket.
I'm not sure that the (upcoming) standard requires linear search
in the bucket, but it does require buckets, which are accessible
for some things (but I'm not sure what) from the user interface.
I think that the available functionality is only sufficient for
instrumentation---determining how effective your hash function
actually is.
(which it is in my version of GNU implementation of tr1
unordered_map). I could even say my problem if solved (if
only they used the hint, which they don't as you correctly
suggested). But it is not guaranteed.
The "hint" is in the form of an iterator. I'm not sure how they
could use it.
It might be useful if they provided functions for looking up and
inserting into a given bucket (at your own risk, of course);
you could then call c.bucket(key) (which calculates the hash
code), and do all further operations on the returned bucket.
Probably a bit too dangerous, however.
(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.
Just noticed that.. Don't understand why they don't use it:
Because it's an iterator, and an iterator doesn't contain any
useful information to use in the case of an unordered container.
they have to re-compute same information in insert() again (at
least bucket index and hash code). I hope they will use it in
the future though and that API is there to allow optimization,
not just for compatibility..
Explain how? The iterator doesn't contain the hash code in any
way.
Most of the hash maps I've written in the past would cache the
last element found, in order to support things like:
if ( m.contains(x) ) {
m[x] = 2*m[x] ; // or whatever...
}
efficiently. It still required a comparison for each access, in
order to know whether I could use the cached value, but it did
avoid multiple calculations of the hash code when accessing the
same element several times in succession.
But the equal_range() definition to return two end() iterators
on "not found" condition is a hog -- I can't understand why
this could not be defined as "return an empty range" so either
of two identical iterators that could be used as a hint for
insertion, consistent with how it's defined for ordered ass.
containers.
What does "consistent with how it's defined for ordered
containers" mean here? The value returned from lower_range
defines where any new element should be inserted, according to
the ordering relationship. In an unordered container, there is
no specific place where the new element should be inserted.
What you're asking for really isn't possible.
What is the benefit of requiring them both be end()? Checking
for "not found" condition costs one iterator comparison either
way.. seems like waste to me.
No benefit, perhaps, but no real harm either. Ordered and
unordered containers are fundamentally different beasts.
If you're concerned about the time necessary to calculate the
hash function, you could use a wrapper for the key, which caches
the hash function once it has been calculated, and uses the
cached value if it is present. Most of the time, I suspect that
it won't make a difference (although for strings, if the keys
can be fairly long, maybe). So you end up with something like:
class CachedHashString : private std::string
{
bool isHashed;
unsigned hashValue;
public:
// Duplicate any needed constructors, setting isHashed
// to false.
// using declarations for whatever functions you want
// to expose (only const!)
unsigned hash() const
{
if ( ! isHashed ) {
hashValue = ... ;
isHashed = true;
}
return hashValue;
}
};
and the hash function you use with the container uses the member
hash function.
--
James Kanze