Re: tr1::hashtable::operator[]

[Joe Buck <Joe dot Buck at synopsys dot COM>]

Peter's proposed patch:
> 
> >       operator[](const K& k)
> >       {
> >        Hashtable* h = static_cast<Hashtable*>(this);
> >-       typename Hashtable::iterator it =
> >-         h->insert(std::make_pair(k, mapped_type())).first;
> >+
> >+        typename Hashtable::iterator it = h->find(k);
> >+        if (it == h->end())
> >+          it = h->insert(std::make_pair(k, mapped_type())).first;
> >        return it->second;
> >       }
> >     };

On Sat, May 13, 2006 at 08:23:22PM +0200, Paolo Carlini wrote:
> Frankly, I'm not fully convinced, I think we should work on this a 
> little more. For one, ext/hash_map  (the closest relative) also doesn't 
> use find. Moreover, map, which indeed do use find (lower_bound) then 
> calls *insert with hint*. It seems to me that in our case we are not 
> talking about "a bit of extra overhead", because we are essentially 
> doing an additional completely redundant lookup (in case the element is 
> not present).

However, if the element *is* present, then we do a redundant call
to the constructor of mapped_type as well as to std::make_pair
(I don't know if eliding constructors is done in such a way that
the mapped_type is constructed in place in the pair, if it isn't it
is even worse).

This can be quite expensive if mapped_type has a constructor
that allocates heap storage: we have a wasted new and delete call.

There is wasted work because of the two lookups, but perhaps there's
a way to further improve the situation by exposing the common part
of find() and insert(), namely the hash computation.  If there were
a way to do the find(), and somehow reuse the hash computed by the
find() to do the insert() more quickly, then I think Peter's approach
would be an even bigger win.