Proposed resolution:

In [unord.req], Table 98, change the following as indicated:

Table 98 — Unordered associative container requirements (in addition to container)

Expression	Return type	Assertion/note pre-/post-condition	Complexity
a.erase(q)	iterator	Erases the element pointed to by q. Return value is the iterator immediately following q prior to the erasure.	Average case O(1) O(max(1, 1/a.load_factor()), worst case O(a.size()) O(max(a.size(), a.bucket_count()).
a.erase(q1, q2)	iterator	Erases all elements in the range [q1, q2). Return value is the iterator immediately following the erased elements prior to the erasure.	Average case linear in distance(q1, q2) O(max(distance(q1,q2), 1/a.load_factor())), worst case O(a.size()) O(max(a.size(), a.bucket_count()).
a.quick_erase(q)	void	Erases the element pointed to by q.	Average case O(1), worst case O(a.size()).
a.quick_erase(q1, q2)	void	Erases all elements in the range [q1, q2).	Average case linear in distance(q1, q2), worst case O(a.size()).

Adjust the declarations accordingly in [unord.map], [unord.multimap], [unord.set], and [unord.multiset].

iterator erase(const_iterator position);
void quick_erase(const_iterator position);  
...
iterator erase(const_iterator first, const_iterator last);
void quick_erase(const_iterator first, const_iterator last);

[ Bellevue: ]

The Bellevue review of this issue reached consensus with the Portland consensus, in contravention of the Toronto non-consensus. Common implementations have the iterator readily available, and most common uses depend on the iterator being returned.

****

The rationale for the change in direction here is best summarized by Paolo's 2010-02-07 comment.

Pittsburgh: Issue is wrong because we believe the standard is consistent as written and the complexity is achievable.

Pittsburgh: We want to enable both existing unordred container implementations.

Rationale:

N2023 was discussed in Portland and the consensus was that there appears to be no need for either change proposed in the paper. 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.

Post Toronto: There does not at this time appear to be consensus with the Portland consensus.

[ 2010-03-27 Joaquín adds: ]

Signature of iterator erase(const_iterator) should be changed to void erase(const_iterator). If this is not viable an acceptable tradeoff could be to make the return type of erase(const_iterator) implementation defined.

The standard should allow implementations of unordered associative containers using either singly or doubly linked lists. N2023 proves that singly-linked lists implementations cannot provide the required complexity for iterator erase(const_iterator). Thus, some action is needed to allow both implementations.

Option 1: Changing the required complexity from O(1) to O(log n). This option merely masks a design flaw. Users are forcefully penalized for what they don't use (the returned iterator). Besides, they would have to learn about the pathological (yet very real) situations where using erase can lead to quadratic performance. Two out of these three objections remain even if some alternative member function like void quick_erase(const_iterator) is thrown in to the interface.

Some objections have been expressed to changing return type of erase to void, arguing that it would break current existing practice with standard library implementations based on doubly-linked lists, where the problem does not occur. However implementations based on drafts should not block the resolution of a serious design issue, more so when the issue will hurt future users of C++, as it's happening already.

Option 2: Make erase return type implementation defined. There's a possible tradeoff with the objectors above consisting in changing the signature to implementation defined erase(iterator), so that returning an iterator is indeed a valid extension. To this it can be argued that this would make implementantions returning an iterator look as somehow promoting proprietary extensions: this in my opinion is not a valid argument since those implementations are already extending the required interface by providing bidirectional iterators (just forward iterators are required).

[ 2010 Pittsburgh: ]

Reopened. There is some discussion as to whether there is an acceptable implementation of erase which returns iterator. Need more time to study it.

[ 2010 Pittsburgh: ]

Moved to Ready for Pittsburgh.

Rationale:

No consensus for a change.

[ 2010 Rapperswil: ]

The issue was lengthy discussed and implementation experience was demonstrated that a non-void return type is implementable for both single-linked and double-linked lists without loss of efficiency.

By a 12-1-1-0 poll voted to keep the return type of erase as iterator instead of void and a second 0-0-3-10 poll rejected the additional proposal to add a quick_erase returning void, thus LWG decided for NAD.

[ 2010-03-27 Joaquín adds: ]

Signature of iterator erase(const_iterator) should be changed to void erase(const_iterator). If this is not viable an acceptable tradeoff could be to make the return type of erase(const_iterator) implementation defined.

The standard should allow implementations of unordered associative containers using either singly or doubly linked lists. N2023 proves that singly-linked lists implementations cannot provide the required complexity for iterator erase(const_iterator). Thus, some action is needed to allow both implementations.

Option 1: Changing the required complexity from O(1) to O(log n). This option merely masks a design flaw. Users are forcefully penalized for what they don't use (the returned iterator). Besides, they would have to learn about the pathological (yet very real) situations where using erase can lead to quadratic performance. Two out of these three objections remain even if some alternative member function like void quick_erase(const_iterator) is thrown in to the interface.

Some objections have been expressed to changing return type of erase to void, arguing that it would break current existing practice with standard library implementations based on doubly-linked lists, where the problem does not occur. However implementations based on drafts should not block the resolution of a serious design issue, more so when the issue will hurt future users of C++, as it's happening already.

Option 2: Make erase return type implementation defined. There's a possible tradeoff with the objectors above consisting in changing the signature to implementation defined erase(iterator), so that returning an iterator is indeed a valid extension. To this it can be argued that this would make implementantions returning an iterator look as somehow promoting proprietary extensions: this in my opinion is not a valid argument since those implementations are already extending the required interface by providing bidirectional iterators (just forward iterators are required).

[ 2010-02-07 Original wording saved here: ]

Option 1:

The problem can be eliminated by omitting the requirement that a.erase(q) return an iterator. This is, however, in contrast with the equivalent requirements for other standard containers.

Option 2:

a.erase(q) can be made to compute the next iterator only when explicitly requested: the technique consists in returning a proxy object implicitly convertible to iterator, so that

iterator q1=a.erase(q);

works as expected, while

a.erase(q);

does not ever invoke the conversion-to-iterator operator, thus avoiding the associated computation. To allow this technique, some sections of TR1 along the line "return value is an iterator..." should be changed to "return value is an unspecified object implicitly convertible to an iterator..." Although this trick is expected to work transparently, it can have some collateral effects when the expression a.erase(q) is used inside generic code.

[ 2010-02-07 Paolo updates wording. ]

As pointed out by Chris in c++std-lib-26040, that an erase(unordered_container, iterator) returning an iterator can easily implemented in user code, if needed; that actually returning an iterator costs nothing for the overload taking two iterators, thus that proposed change is only for consistency; that forward_list::erase_after also returns void (for different reasons, granted, but isn't that any "erase" function in the containers uniformly returns an iterator); that, also in thread started by Chris' message, Alberto pointed out that the proxy idea isn't a good one; that users both of the GNU and Boost implementations are reporting serious performance problems with the current version returning an iterator.

[ 2009-12-11 Paolo opens: ]

I'm asking for DR 579 to be re-opened, basing on recent discussions on the library reflector, see Message c++std-lib-26040 and replies.

Addresses ES-2

See N2023 for full discussion.