This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.
map::erase
Section: 24.4.4 [map] Status: C++17 Submitter: Christopher Jefferson Opened: 2011-05-18 Last modified: 2017-07-30
Priority: 3
View all other issues in [map].
View all issues with C++17 status.
Discussion:
map::erase
(and several related methods) took an iterator in C++03, but take a const_iterator
in C++0x. This breaks code where the map's key_type
has a constructor which accepts an iterator
(for example a template constructor), as the compiler cannot choose between erase(const key_type&)
and erase(const_iterator)
.
#include <map> struct X { template<typename T> X(T&) {} }; bool operator<(const X&, const X&) { return false; } void erasor(std::map<X,int>& s, X x) { std::map<X,int>::iterator it = s.find(x); if (it != s.end()) s.erase(it); }
[ 2011 Bloomington ]
This issue affects only associative container erase
calls, and is not more general, as these are the
only functions that are also overloaded on another single arguement that might cause confusion - the erase
by key method. The complete resolution should simply restore the iterator
overload in addition to the
const_iterator
overload for all eight associative containers.
Proposed wording supplied by Alan Talbot, and moved to Review.
[2012, Kona]
Moved back to Open by post-meeting issues processing group.
Pablo very unhappy about case of breaking code with ambiguous conversion between both iterator types.
Alisdair strongly in favor of proposed resolution, this change from C++11 bit Chris in real code, and it took a while to track down the cause.
Move to open, bring in front of a larger group
Proposed wording from Jeremiah:
erase(key)
shall not participate in overload resolution if iterator
is
convertible to key
.
Note that this means making erase(key)
a template-method
Poll Chris to find out if he already fixed his code, or fixed his library
Jeremiah - allow both overloads, but enable_if
the const_iterator
form as
a template, requiring is_same
to match only const_iterator
.
Poll PJ to see if he has already applied this fix?
[2015-02 Cologne]
AM: To summarize, we changed a signature and code broke. At what point do we stop and accept breakage in increasingly obscure code? VV: libc++ is still broken, but libstdc++ works, so they've fixed this — perhaps using this PR? [Checks] Yes, libstdc++ uses this solution, and has a comment pointing to LWG 2059. AM: This issue hasn't been looked at since Kona. In any case, we already have implementation experience now.
AM: I'd say let's ship it. We already have implementation experience (libstdc++ and MSVS). MC: And "tentatively ready" lets me try to implement this and see how it works.Proposed resolution:
Editorial note: The following things are different between 24.2.7 [associative.reqmts] p.8 and 24.2.8 [unord.req] p.10. These should probably be reconciled.
- First uses the convention "denotes"; second uses the convention "is".
- First redundantly says: "If no such element exists, returns a.end()." in erase table entry, second does not.
24.2.7 [associative.reqmts] Associative containers
8 In Table 102, X
denotes an associative container class, a
denotes a value of X
, a_uniq
denotes a value of X
when X
supports unique keys, a_eq
denotes a value of X
when
X
supports multiple keys, u
denotes an identifier, i
and j
satisfy input iterator
requirements and refer to elements implicitly convertible to value_type
, [i,j)
denotes a valid range,
p
denotes a valid const iterator to a
, q
denotes a valid dereferenceable const iterator to a
,
r
denotes a valid dereferenceable iterator to a, [q1, q2)
denotes a valid range of const iterators
in a
, il
designates an object of type initializer_list<value_type>
, t
denotes a value of
X::value_type
, k
denotes a value of X::key_type
and c
denotes a value of type
X::key_compare
. A
denotes the storage allocator used by X
, if any, or
std::allocator<X::value_type>
otherwise, and m
denotes an allocator of a type convertible to A
.
24.2.7 [associative.reqmts] Associative containers Table 102
Add row:
a.erase(r) |
iterator |
erases the element pointed to by r . Returns an iterator pointing to the element immediately following r
prior to the element being erased. If no such element exists, returns a.end() .
|
amortized constant |
24.2.8 [unord.req] Unordered associative containers
10 In table 103: X
is an unordered associative container class, a
is an object of type X
,
b
is a possibly const object of type X
, a_uniq
is an object of type X
when
X
supports unique keys, a_eq
is an object of type X
when X
supports equivalent keys,
i
and j
are input iterators that refer to value_type
, [i, j)
is a valid range,
p
and q2
are valid const iterators to a
, q
and q1
are valid dereferenceable
const iterators to a
, r
is a valid dereferenceable iterator to a, [q1,q2)
is a
valid range in a
, il
designates an object of type initializer_list<value_type>
,
t
is a value of type X::value_type
, k
is a value of type key_type
, hf
is a
possibly const value of type hasher
, eq
is a possibly const value of type key_equal
,
n
is a value of type size_type
, and z
is a value of type float
.
24.2.8 [unord.req] Unordered associative containers Table 103
Add row:
a.erase(r) |
iterator |
Erases the element pointed to by r . Returns the iterator immediately following r prior to the erasure.
|
Average case O(1), worst case O(a.size() ). |
24.4.4.1 [map.overview] Class template map overview p. 2
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.4.5.1 [multimap.overview] Class template multimap overview p. 2
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.4.6.1 [set.overview] Class template set overview p. 2
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.4.7.1 [multiset.overview] Class template multiset overview
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.5.4.1 [unord.map.overview] Class template unordered_map overview p. 3
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.5.5.1 [unord.multimap.overview] Class template unordered_multimap overview p. 3
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.5.6.1 [unord.set.overview] Class template unordered_set overview p. 3
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
24.5.7.1 [unord.multiset.overview] Class template unordered_multiset overview p. 3
iterator erase(iterator position); iterator erase(const_iterator position); size_type erase(const key_type& x); iterator erase(const_iterator first, const_iterator last);
C.6.12 [diff.cpp03.containers] C.2.12 Clause 23: containers library
23.2.3, 23.2.4
Change: Signature changes: from iterator to const_iterator parameters
Rationale: Overspecification. Effects: The signatures of the following member functions changed from taking an iterator to taking a const_iterator:
Valid C++ 2003 code that uses these functions may fail to compile with this International Standard.