Ion Gaztañaga
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