Howard Hinnant escribió:
On Mar 17, 2010, at 5:29 PM, Joaquin M Lopez Munoz wrote:
Howard Hinnant <howard.hinnant <at> gmail.com> writes:
On Mar 16, 2010, at 2:27 PM, Brad Higgins wrote:
On Mar 15, 2010, at 4:11 PM, Howard Hinnant wrote:
I'm reviving an old thread with new information:
The LWG looked at this issue last week:
http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579
[...] Thanks for sharing your real-world experience Brad. I've passed your note on to the C++ committee. To answer your question, one vendor has already shipped these containers and with a design that reportedly does not suffer from this quadratic behavior, and is very reluctant to have this signature change.
Howard, I'm intrigued by the "reportedly" bit in the sentence above. Has any member of the committee had access to that code and assessed whether the quadratic behavior is *effectively* avoided?
I do not have access to the code. I have no reason to doubt the report. I have not seen actual timings from tests run.
I'm not getting this. N2023 (allegedly) *proves* that singly linked unordered containers *can't* implement iterator erase(iterator) with O(1) complexity. So N2023 can be right or wrong (if there's some flaw in the proof), but if a committee member votes for NAD I think it's only fair to demand some evidence from him as to why N2023 is wrong. Do you agree so far with me? Now, it's not that whatever technique they reportedly have applied is a trivial one, since at least three industry-level implementations of unordered containers have the problem predicted by N2023. Or, maybe that member is using *doubly linked* unordered containers: In that case N2023 does not apply and iterator erase(iterator) can indeed be implemented in O(1), but then if 579 is as a consequence closed as NAD this is tantamount to stating that singly linked hash tables are not valid implementations of C++ unordered containers. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo