2009/11/23 Christopher Jefferson <chris@bubblescope.net>:

On 23 Nov 2009, at 23:23, Stefan Strasser wrote:

...

I can't think of a reason why it should be O(n) in this case (perfect hash, erase doesn't rehash). but even if it was, the results should be at worst quadratic.

I suspect the problem you are seeing is that erase returns an iterator to the next member of the unordered_set, which is a possibly O(n) search if the set is sparsely populated, and in particular if, as you get here, you erase the elements in a particularly bad order. I'm not sure why this doesn't occur with the intrusive containers.

That's right, I profiled it and it spends all the time searching for the next bucket.

One way to significantly reduce this problem is to use a different hash function, which shuffles the values more.

I could apply another hash function to the hash value to make this less likely, or perhaps store a pointer to the last non-empty bucket. I'll think about it. A workaround is to erase by key or iterator range if possible. Daniel

On Mon, Nov 23, 2009 at 6:40 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote: ...

Our very own Joaquín anticipated this problem very early:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf

"In pathological cases, h(n) can be as bad as ½ n(n + 1): this happens when the elements are erased in reverse order as they are arranged in the hash table."

It would be interesting to know

1) how intrusive containers avoid this, and

2) also if this is a real problem in real code.

At any rate, Joaquin shows that the *lower bound* complexity of erase is actually lg n, and not O(1).

Does anyone know how the WG21 LWG responded to his paper?

The Portland wiki says:

N2023 erase(iterator) for unordered containers should not return an iterator 6 votes NO, 4 votes to ask for better justification, no votes in favor of either proposed alternative. The consensus opinion was that since the iterator could serve as its own proxy, there appears to be no need for the change. In general, "converts to" is undesirable because it interferes with template matching. I'm guessing from the small number of votes that it was handled by a subgroup. It isn't clear they fully understood the problem, although it is often the case that wiki notes do not fully capture the discussion. Like you, I'm wondering how intrusive containers avoid the problem. Also, what do other implementations do, and how do they perform? --Beman

Beman Dawes wrote:

On Mon, Nov 23, 2009 at 6:40 PM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:

...

2) also if this is a real problem in real code.

Unfortunately (for me), it is. Literally the day after you asked, and without my having seen this thread, my teammate discovered this very issue in production code. The sequence of events which led to the poorly-performing program was: 1) Write program using std::map. 2) Switch to unordered_map, noting it reduced CPU utilization by ~30%. 3) Discover that performance suffered when large rehashes occurred. 4) Find the maximum bucket count (millions), and initialize with that. 5) Rehashing slowdowns go away, but then we discover something we failed to notice before due to profiling with fewer buckets: the application's user-space CPU utilization is dominated by erase()! We may end up switching to erase() by key, which is a shame since in our case we always have the victim iterator already when we want to erase (so now we must pay to find the key twice). Our application could benefit from reducing the number of buckets in some cases, but: 1) It's not supported by GCC, even if one writes a custom rehashing policy. 2) We would likely suffer from rehashing again, as given this issue with erase(), the optimum number of buckets varies throughout the program's lifetime (increasing then later decreasing).

what do other implementations do, and how do they perform?

We use GCC 4.2.4. It has code analogous to Boost's: _M_incr_bucket() { ++_M_cur_bucket; // This loop requires the bucket array to have a non-null sentinel. while (!*_M_cur_bucket) ++_M_cur_bucket; _M_cur_node = *_M_cur_bucket; } I haven't tried Boost, but I can tell you that GCC does not do well here. -JZ

On Tue, Nov 24, 2009 at 3:55 AM, Daniel James <daniel_james@fmail.co.uk>wrote:

...

2009/11/23 Christopher Jefferson <chris@bubblescope.net>:

...

One way to significantly reduce this problem is to use a different hash

function, which shuffles the values more.

That will improve things, but not by much as there'll still be a lot more buckets than elements. That would need to combined with regularly manually rehashing the container (ie. calling 's.rehash(0)') as elements are erased.

2009/11/23 Daniel James <daniel_james@fmail.co.uk>:

...

I could apply another hash function to the hash value to make this less likely, or perhaps store a pointer to the last non-empty bucket. I'll think about it.

Neither of those will work, there will still be other similar cases. With the current interface the only way to deal with this that I can think of is by changing the data structure, which will require more memory use. And there's been opposition to that. It could possibly use an iterator which only finds the next element when used, although that'll make a lot of other operations more expensive.

IMO, the right way to fix this is for the LWG to fix the problem they created when they changed the interface to no longer return void. --Beman

Stefan Strasser escribió:

"void" return type: http://www.boost.org/doc/libs/1_38_0/doc/html/boost/intrusive/unordered_set....

This was changed to std::unordered-like interface: http://www.boost.org/doc/libs/1_41_0/doc/html/boost/intrusive/unordered_set.... The implementation is just the same: template<class Disposer> iterator erase_and_dispose(const_iterator i, Disposer disposer ) { iterator ret(i.unconst()); ++ret; priv_erase(i, disposer, ...); //... return ret; } So I guess, latest intrusive version suffers from the same problem. Ion

Am Wednesday 25 November 2009 18:12:32 schrieb Thorsten Ottosen:

...

it happened in real code.

Ok. Can we see that code snippet, or is it impossible for you to post it?

I can post the snippet doing the actual access, the code that results in the elements being removed in reverse order is quite large, so I'll write a short description: I have to be able to access some objects by an object id as long as they're in memory, so there is a unordered_map<object_id,weak_ptr<object> > objects; the reverse order is the result of an object caching algorithm. when a cache sweep finds that a couple of thousand objects need to be disposed, those objects happen to be in reverse order. they must still be removed from the unordered_map one-by-one, because some objects may have been accessed at a later time and re-inserted, so they're not disposed in this sweep. the order could probably be changed but I didn't expect it to make a difference.

Was there any reason that you could not erase by key instead of by iterator, or did it just feel more natural to erase by iterator?

here's the (simplified) code: unordered_map<object_id,weak_ptr<object> > objects; iterator it=objects.find(id); if(it != objects.end() && it->second.expired()){   objects.erase(it); } so I already had the iterator around because the element value is used before erasing. once you discovered the problem it is easy to fix (erase by key), but you certainly wouldn't expect that 2 lookups are faster than 1. with ordered containers you'd want to make sure that you only use 1 lookup, and that extends to unordered containers to some degree as well, if there are bucket sizes > 1 in the table. this is just an idea off the top of my head, I haven't thought this through, but has the committee ever considered making functions overloadable by their return type? void f(); // 1 int f(); // 2 int main(){   f(); //resolves to 1   int b=f(); //resolves to 2 }

Am Wednesday 25 November 2009 21:54:54 schrieb Jeffrey Bosboom:

Stefan Strasser wrote:

...

this is just an idea off the top of my head, I haven't thought this through, but has the committee ever considered making functions overloadable by their return type?

void f(); // 1 int f(); // 2

int main(){ f(); //resolves to 1 int b=f(); //resolves to 2 }

That's a pretty drastic language change to solve an issue that is really a library problem.

I don't want to argue for it because as I've said, I haven't really thought this through. but this isn't a library specific problem, it applies to unnecessary evaluation of discarded return values in general. it's just exacerbated in this case because you can't just add a parameter or create a second function like you normally would because the function signature is specified.

(Besides, what if I want to call function 2 for its side effects and ignore its return type? Even the ugly "(void)f()" doesn't seem to do what I want.)

I can't think of a reason why you'd want that, but (int) f(); should do the trick.

2009/11/26 Jeffrey Bosboom <jbosboom@uci.edu>

Stefan Strasser wrote:

...

I don't want to argue for it because as I've said, I haven't really thought this through. but this isn't a library specific problem, it applies to unnecessary evaluation of discarded return values in general. it's just exacerbated in this case because you can't just add a parameter or create a second function like you normally would because the function signature is specified.

Well, C++ is an eagerly-evaluated language, and the construction of a return value is part of the effects of a function. So simply not creating return values when they aren't used isn't possible now, as that could break existing code; I'm also not sure how this interacts with the separate compilation model. (On the other hand, compilers are allowed to perform copy elision, and the consequences of this are more surprising when elision isn't performed (leading to performance loss) than when it is performed. Perhaps allowing this optimization wouldn't be a problem in practice?)

Allowing overloading on return type wouldn't work well with the type inference already performed by compilers, and would create a new way to add ambiguity to valid code. For example, the following code works just fine:

int f(); auto i = f(); std::cout << std::make_pair(f(), f());

But add an overload on return type:

int f(); Foo* f(); //added later auto i = f(); //what's the type of i? //what are the template args for make_pair? std::cout << std::make_pair(f(), f());

It's certainly possible for adding an overload on parameter types to create an ambiguity when there wasn't one, so perhaps this is acceptable, but I find it surprising.

Getting back to this specific case, I think the two versions of erase() are different enough in performance to warrant providing both. Unfortunately, I don't know of a good alternate name for whichever one isn't named erase().

Would it be possible to implement lazy evaluation of the iterator?

template<typename UnorderedSet> class lazy_iterator_evaluator { public: lazy_iterator_evaluator(...) typedef typename UnorderedSet::iterator iterator; operator iterator() {//Do the heavy calculations here} }; an let erase return this instead? lazy_iterator_evaluator<unordered_set<T> > unordered_set<T>::erase(...); Regards Peder Holt --Jeffrey Bosboom

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Jeffrey Bosboom wrote:

Getting back to this specific case, I think the two versions of erase() are different enough in performance to warrant providing both. Unfortunately, I don't know of a good alternate name for whichever one isn't named erase().

I'd suggest "remove" but that name is tainted by the behavior of the remove algorithm. "Discard?" _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

2009/11/26 John Zwinck <jzwinck@athenacr.com>:

I suggest augmenting the existing name: something like "erase_fast" or even "erase_void" would be fine (at least until someone else comes up with something better, for which there will no doubt be plenty of time).

'erase' would be better. But as a temporary measure I'll add something like that, you might want to file a ticket to make sure I don't forget and track what I do. Daniel

On Sat, Nov 28, 2009 at 3:52 PM, John Zwinck <jzwinck@athenacr.com> wrote:

Daniel James wrote:

...

'erase' would be better. But as a temporary measure I'll add something like that, you might want to file a ticket to make sure I don't forget and track what I do.

I have created a ticket: https://svn.boost.org/trac/boost/ticket/3693

Instead of making a new function name, why not a function overload: iterator erase(iterator it); // original void erase(iterator it, no_return); // no_return is an empty global created struct so you can just call m.erase(it, no_return);

On Sun, Nov 29, 2009 at 4:48 PM, John Zwinck <jzwinck@athenacr.com> wrote:

OvermindDL1 wrote:

...

Instead of making a new function name, why not a function overload:

iterator erase(iterator it); // original void erase(iterator it, no_return); // no_return is an empty global created struct so you can just call m.erase(it, no_return);

Is "m.erase(it, no_return)" better than "m.erase_no_return(it)"?

Is there a precedent (in C++, not Boost) for this, other than the (IMO confusing) pre- vs. post-increment operator declarations?

operator new(std::nothrow_t) -- gpd

On Sun, Nov 29, 2009 at 8:48 AM, John Zwinck <jzwinck@athenacr.com> wrote:

OvermindDL1 wrote:

...

Instead of making a new function name, why not a function overload:

iterator erase(iterator it); // original void erase(iterator it, no_return); // no_return is an empty global created struct so you can just call m.erase(it, no_return);

Is "m.erase(it, no_return)" better than "m.erase_no_return(it)"?

Is there a precedent (in C++, not Boost) for this, other than the (IMO confusing) pre- vs. post-increment operator declarations?

I'm also concerned that people who bind C++ with dynamic languages may end up writing wrappers to make it a unary function again.  This is a special case of the fact that a binary function may be a little more difficult to integrate into code which uses pointers to member functions.

I'm open to other opinions, but offhand I prefer a unary function.

As another post showed there is precedent. I find the no_return cleaner to read personally, and I would not be abject to having it as a template parameter either as a policy (m.erase<no_return>(it)) either, just seems and reads cleaner to me.

Daniel James wrote:

This is meant to be a short lived workaround, we shouldn't over-engineer it. A new type and a template method is pretty gratuitous. I prefer the simplest, least disruptive solution - adding a new method with a different name. In the future when the method is removed (it'll go through a deprecation process first) the resulting error messages will be simpler and the name of the function will be easily searched (both in code and for an explanation on the web).

I agree. John Zwinck

On Mar 15, 2010, at 4:33 PM, Daniel James wrote:

On 15 March 2010 20:11, Howard Hinnant <howard.hinnant@gmail.com> wrote:

...

I'm reviving an old thread with new information:

Thank you, that's very useful. I think I'll add quick_erase in this release and deprecate the function I added in the last release (sigh).

Ok, note that the committee didn't decide on quick_erase. The issue is still open.

...

where node_ptr is a nested typedef in the container to unique_ptr<__node, __node_deleter<__node_allocator>>. With this tool one can remove a node from a container, change its value, and insert it back into the container (or another which has an equal allocator). E.g.:

You probably know better than me, but I don't think you can use unique_ptr like that with the new allocator requirements.

Just for clarity's sake, the unique_ptr should hold a reference to the container's deleter, not a copy. So users of the node_ptr would need to watch out for lifetime issues (the node_ptr should not outlive the container which produced it). I consider that a small price to pay for the functionality/performance gained. But it /is/ inventive. -Howard

On Mar 15, 2010, at 4:59 PM, Daniel James wrote:

On 15 March 2010 20:44, Howard Hinnant <howard.hinnant@gmail.com> wrote:

...

On Mar 15, 2010, at 4:33 PM, Daniel James wrote:

...

...

where node_ptr is a nested typedef in the container to unique_ptr<__node, __node_deleter<__node_allocator>>. With this tool one can remove a node from a container, change its value, and insert it back into the container (or another which has an equal allocator). E.g.:

You probably know better than me, but I don't think you can use unique_ptr like that with the new allocator requirements.

Just for clarity's sake, the unique_ptr should hold a reference to the container's deleter, not a copy. So users of the node_ptr would need to watch out for lifetime issues (the node_ptr should not outlive the container which produced it). I consider that a small price to pay for the functionality/performance gained. But it /is/ inventive.

Sorry, I should have been clearer, I was worried about the node pointer. I don't think you can use a '__node*' with the new allocator requirements. You can obviously get a pointer by from a reference, but there doesn't seem to be a way to get 'allocator_type::pointer' back later, since there's no longer a requirement for 'allocator::address'.

Ah! Excellent point. If I'm missing your point just let me know. But the way to handle this is to have your custom deleter make its node_pointer type the same as the node_allocator's node_pointer type. unique_ptr will then use it for the storage. template <class _Alloc> class __hash_node_destructor { typedef _Alloc allocator_type; typedef allocator_traits<allocator_type> __alloc_traits; public: typedef typename __alloc_traits::pointer pointer; // unique_ptr<T, __hash_node_destructor<A>> uses this for its pointer type ... }; The container will want to rebind its user-supplied allocator into a node allocator and then instantiate its node_destructor with that. Now when the node_destructor calls __alloc_traits::deallocate, it is passing the same pointer type that the allocator expects. It helps if you already have allocator_traits implemented for all of this. hth, Howard

Zitat von Howard Hinnant <howard.hinnant@gmail.com>:

At each remove() the node_ptr is ignored/destructed, thus deallocating the node. There is no iterator increment.

This is a performance-tested solution with your test program:

20000: 0m0.012s // your time is 0m0.244s 40000: 0m0.017s // your time is 0m0.940s 60000: 0m0.024s // your time is 0m5.584s 80000: 0m0.028s // your time is 0m4.232s 100000: 0m0.037s // your time is 0m34.814s 120000: 0m0.041s // your time is 0m33.486s

The bad news is that the LWG will consider this much too inventive at this late date. That being said, I believe it solves several real world performance problems (this one and others listed in LWG 839). I offer it here in case someone wants to implement it for boost containers.

In case you don't like the "too inventive" response from the C++ committee, I'm the one to yell at. I will happily forward your response to the committee.

I think none of the solutions are perfect, with Option 1(void result) being the one that makes the most sense to me. as others have noted it wouldn't be the first time a container violates that requirement, and a returned iterator is of very limited use in an unordered container anyway. but while we're being inventive, I would like to see the following considered, for the long-term. if I am not mistaken we're dealing with a function overloading problem here. overloading by return type. template<class T,...> class unordered_set{ ... void erase(iterator); // (1) iterator erase(iterator); // (2) ... }; s.erase(it); //calls (1) it=s.erase(it); //calls (2) this obviously requires language support, but it would solve the problem beyond this specific case. problems like this are quite common, and are usually (when you're not bound to a Container concept) solved like this: void erase(iterator in,iterator *out=0); or void erase(iterator in); void erase(iterator in,iterator &out); you can find signatures like this in several boost libraries. more examples of overloading by return type: int f(); // (1) float f(); // (2) void f(); // (3) int a=f(); //calls (1) f(); //calls (3) (float)f(); //calls (2) void g(int); void g(float); g(f()); //ambiguous Regards, Stefan

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

We were all over the map on it. We finally left it in Open status in hopes of learning more in the next few months.

One solution I've been thinking of is a variant of what is currently proposed in the issue:

void quick_erase(const_iterator);

I have also run into this issue in production code, but in the multi_index implementation of the hash_table (which seems to adhere to the unordered_map standard). In my case, I seem to have hit the absolute worst-case, which results in the erase of about 600,000 elements (in a hash with 5 million buckets) to take hours. When updated to return void, the same routine runs in seconds. Here is a simplified example which closely replicates my use case, using the unordered_map:

-------------------------- #include <iostream> #include <boost/unordered_map.hpp>

int main(int argc, char* argv[]) { typedef boost::unordered_map<int, int> hash_map; hash_map hm; hm.rehash(1000000);

int x = 500000; std::cout << "Add " << x << " elements...";

for (int i=0; i<x; i++) { hm[i] = i*2; } std::cout << "done!\n";

std::cout << "\nremove the elements..."; for (int i=x-1; i>=0; i--) { hash_map::iterator itr = hm.find(i); if (itr != hm.end()) { hm.erase(itr); } } std::cout << "done!\n";

return 0; } ----------------------------

I don't understand why the erase(iterator) routine needs to return anything other than void. In the case of a hash table, the next node ought to be some random node, which makes it somewhat useless. However, if a client really wants an iterator to the next valid element, they can post-increment the argument iterator themselves. This idiom would suffice for other containers, as well.

With the worst-case erase(iterator) performance being O(bucket_count), this effectively makes erase(iterator) unusable. Seeing the performance of the above program, it's clear to me that the implementation of erase(iterator) is broken, and it seems to me that it is broken due to this return-type requirement. A differently-named erase(iterator) routine would solve the problem, but I don't understand why the standard would leave the erase() booby-trap to ensnare others. Howard, what is the rationale for keeping the return type of the erase routine as iterator?

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

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. Just a few minutes ago I changed my implementation of unordered_map to use a "lazy increment" for the iterator and ran it against Brad's test: $ time a.out Add 500000 elements...done! remove the elements...done! real 0m0.153s user 0m0.127s sys 0m0.020s This time is about the same as I got using an erase() that did not increment the iterator. The "lazy increment" allows the iterator to walk off of the end of bucket, and does not try to find the next bucket until dereference, another increment, or comparison. I do not claim this is "the solution" it is one of several I'm exploring. I mention it here in case others want to try it and report their experience. -Howard

Daniel James escribió:

On 17 March 2010 22:06, Howard Hinnant <howard.hinnant@gmail.com> wrote:

...

Just a few minutes ago I changed my implementation of unordered_map to use a "lazy increment" for the iterator and ran it against Brad's test:

$ time a.out Add 500000 elements...done!

remove the elements...done!

real 0m0.153s user 0m0.127s sys 0m0.020s

This time is about the same as I got using an erase() that did not increment the iterator. The "lazy increment" allows the iterator to walk off of the end of bucket, and does not try to find the next bucket until dereference, another increment, or comparison. I do not claim this is "the solution" it is one of several I'm exploring. I mention it here in case others want to try it and report their experience.

I've attached a patch to do something similar for Boost.Unordered. I got a similar result, although I think it will make some other things slower. And I'm not keen on mutable variables.

There's an additional problem, I think. Your patch does not check_increment() on hash_iterator copy ctor, so that the following pathological situation can happen: auto it1=cont.erase(it),it2=it1; // it1 and it2 unchecked yet (void)(it1==it1); // it1 checked cont.insert(x); // x gets inserted between it and it1 (void)(it2==it2); // it2 gets checked and points to the position of x. assert(it1==it2); // fails! Now, if you add check_increment() to the copy ctor you get the quadratic behavior back in compilers without RVO. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

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

On Mar 18, 2010, at 3:35 AM, joaquin@tid.es wrote:

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.

This is a good summary of the situation with the following added information: It is not sufficient to just have the nodes connected by a doubly linked list. This alone introduces linear behavior (in terms of adjacent empty buckets) in insert and erase. The data structure also has two pointers per bucket to mark the beginning and end of each bucket. -Howard

On Mar 18, 2010, at 10:21 AM, joaquin@tid.es wrote:

Howard Hinnant escribió:

...

On Mar 18, 2010, at 3:35 AM, joaquin@tid.es wrote:

...

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.

This is a good summary of the situation with the following added information: [...]

I sincerely hope that 579 is then reopened so that singly linked implementations of unordered associative containers are accepted back into the standard.

Issue 579 is still open: http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579 How it will be closed is very much in debate.

I participate in the Spanish C++ committee and will route my opinion through our representative in JTC1/SC22/WG21.

Thank you, please do. Your participation through your national body representative is very important! -Howard