Re: [boost] [multi_index][ann] Boost.MultiIndex 1.56 preview: major update with new hashed index implementation

Subject: Re: [boost] [multi_index][ann] Boost.MultiIndex 1.56 preview: major update with new hashed index implementation
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2013-12-26 08:01:43

Ion Gaztañaga <igaztanaga <at> gmail.com> writes:

> 
> El 26/12/2013 0:46, Joaquin M Lopez Munoz escribió:
> 
> > http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#579
> >
> > was a NAD, so I had to comply, even though I take it as proven that
> > complying incurs an extra pointer per element that the original
> > proponents of unordered associative containers didn't see coming.
> 
> I agree. Quoting 
> "http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html"
> 
> "my goal is neither to require nor to forbid stored hash codes. I don't 
> know of an implementation that currently stores hash codes, but I also 
> don't know of anything in this proposal that would forbid it."
> 
> and
> 
> "Singly linked lists have slower iterators, because an iterator first 
> steps within a bucket and then, upon reaching the end of a bucket, steps 
> to the next"

Just for the fun of it, I did some archaealogoy, and it turns out that
the first TR1 drafts had erase(it) return void up to N1745. Then
on http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf
Matt Austern himself raised the issue 6.19 "Unordered associative
container erase shouldn't return void" where the rationale was that
returning an iterator to the following element is more useful than
not returning anything. And version N1836 of TR1 already took this
change in :-/

Now it is too late to fix this and we'll have to live with bloated
data structures for this type of containers, at least until someone
proposes a new category of lightweight unordered associative containers
or something.
 
> [...] I started thinking about your proxy-returning proposal and 
> how it could be implemented. I think that could be a good solution for 
> Boost.Intrusive using singly linked lists with no stored hash allowing the
> 
> while(it != itend)
>    it = cont.erase(it)
> 
> pattern, which is what STL users are used to. But I guess conversions to 
> const_iterator and related would be a problem for the proxy.

Yep, more so in the presence of C++11 auto (until we have operator auto
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3748.pdf )

> [...]
> Just another comment in case you'd like to improve your benchmarks: I 
> think "erase(iterator)" is much less used than "erase(key)", and in that 
> case I don't think Dinkumware data structure would be better (maybe 
> power of two bucket arrays can still help, but you need to traverse the 
> linked list to find the element)

Good observation, I'll give a try and post results in the blog.

Thank you,

Joaquín M López Muñoz
Telefónica Digital