579. erase(iterator) for unordered containers should not return an iterator

Section: 23.2.8 [unord.req] Status: NAD Submitter: Joaquín M López Muñoz Opened: 2006-06-13 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with NAD status.

Discussion:

Addresses ES-2

See N2023 for full discussion.

[ 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.

[ 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.

[ 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-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 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.

Rationale:

No consensus for a change.

Proposed resolution: