Re: hashtable local iterator

[François Dumont <frs dot dumont at gmail dot com>]

On 12/14/2011 01:49 AM, Paolo Carlini wrote:
> Hi,
> > Hi
> >
> >     Since modification of hashtable implementation I was quite 
> > unhappy of the impact on local_iterator and especially on the 
> > end(size_type bkt) method that required to loop through all bucket 
> > nodes to access the past-the-end one. This is why I would like to 
> > propose, if it is still time, this new local iterator implementation 
> > that allow to implement begin(size_t)/end(size_t) in constant time. 
> > Note that:
> well, either we do this or, alternately, I'm afraid we have to revert 
> the whole thing because the current behavior makes the new 
> implementation non-conforming, right? Actually, in my opinion you 
> should have pointed out the issue much more explicitly much earlier. 
> If you are aware of similar issues, breaking the conformance of the 
> implementation, please say it now, I would hate large last minute 
> reversions.

    Sorry, I hadn't noticed that it was a non Standard conformity, I 
though that not being O(N) with N the number of elements in the 
container or even the number of bucket was enough but you are right the 
C++11 Standard is really clear on operation complexity and current 
implementation is wrong.

    I have one other point that do not make me happy, it is in the 
management of the iterator hint in insert and emplace_hint methods. 
libstdc++ do not make anything of it while the Standard say that 
insertion should be achieved as close as possible to this hint. This is 
not however a regression of the new implementation, former one was also 
ignoring this hint information.

> > - this new iterator type needs a pointer to its parent container to 
> > work which is quite unusual on normal iterators.
> On the spot, I cannot see anything wrong with this. Normally, when 
> such kinds of links are present one must be careful about what happens 
> when one of the two changes without telling the other. Are we risking, 
> I don't know, local iterators becoming invalid when they shouldn't?
> > - I had to make an overload of _M_bucket_index public to use it in 
> > local iterator implem', do you prefer to introduce a friend 
> > declaration ?
> I guess friendship is much better.
    I have done the modification to use friendship but with the issue 
raised by Christopher and you it is finally not so important. This swap 
issue in indeed rude. With current implementation I need at least the 
hash functor and bucket count to get the bucket index of the nodes on 
incrementation. I will study this problem but for the moment the only 
solution I see is to re-introduce the 2 nodes per bucket I had done in 
one of my propositions.

    I will try to do something as quick as possible.

François