Matthew Austern <austern@google.com>
N2256=07-0116
2007-04-18
Container insert/erase and iterator constness
Ten years ago, just before the standard was finished, Dave Abrahams pointed out
that the container requirements were too fussy about constness. Table 82,
sequence requirements, says that the expression for single-element
sequence insert is
a.insert(p, t), where
p stands for "a valid iterator to
a". The requirement tables say
similar things for sequence erase,
and for associative container erase
and insert. This is too strict,
because these requirements confuse iterator constness and container constness.
The container is being modified, but the iterator, which is used only for
positioning, is not. There is no reason to forbid it from being a const
iterator.
Making the iterator argument
const_iterator does raise another
question. Currently the return type for the single-element sequence
insert, both versions of sequence
erase, single-element associative
container insert, and both versions
of associative container erase, is
iterator. If we change the
arguments without making any other changes, then we will have functions with a
const_iterator argument type and an
iterator return type. Strictly
speaking, this is not a violation of const correctness. It doesn't turn a
const_iterator into an
iterator; all it does is generate
an iterator given a non-const
container, and of course there is nothing extraordinary about that. Still, this
member function made some committee members uncomfortable enough to look for an
alternative fix: overloading these member functions on
iterator and
const_iterator, so that the return
type matches the argument type.
This problem was never fixed for the sequence containers
(vector,
list, and
deque) or for the associative
containers (map,
set,
multimap, and
multiset). It was fixed for the
unordered associative containers
(unordered_map,
unordered_set,
unordered_multimap, and
unordered_multiset). Based on the
results of an LWG straw poll, the unordered associative containers use the
second alternative: two overloaded member functions.
We ought to fix this problem for the sequences containers and the associative
containers. It would be silly to release two standards with this known defect,
or to treat this issue differently in the unordered associative containers than
in the sequences and the associative containers.
We have two options for this fix: either apply the same fix to sequences and
associative containers as we already did for unordered associative containers,
or consistently change all of the containers to use a single member function
with a const_iterator argument and
an iterator return type. I present
wording for both options.
I prefer option B, because it's simpler: I believe that these overloads are
cumbersome and add no const correctness value. I am providing wording for both
options because option A is more consistent with the straw poll from the 2004
Redmond meeting.
Option A
In 2.3.1.1 [lib.sequence.reqmts] paragraph 3, replace
"p denotes a valid iterator to
a,
q denotes a valid dereferenceable
iterator to a,
[q1, q2) denotes a valid range in
a" with
"p denotes a valid iterator to
a,
pc denotes a valid const iterator
to a,
q denotes a valid dereferenceable
iterator to a,
qc denotes a valid dereferenceable
iterator to a,
[q1, q2) denotes a valid range in
a,
[qc1, qc2) denotes a valid
range of const iterators in a".
In Table 82 (sequence requirements):
-
Add another row after a.insert(p,
t): expression a.insert(pc,
t), return type
const_iterator, and description
"inserts a copy of t before
pc".
-
Change a.insert(p, n, t) to
a.insert(pc, n,
t), and make the corresponding change in the
description.
-
Change a.insert(p, i, j) to
a.insert(pc, i,
j),
and make the corresponding change in the description.
-
Add another row after
a.erase(q): expression
a.erase(qc), return type
const_iterator, and description
"erases the element pointed to by
qc".
-
Add another row after a.erase(q1,
q2): expression a.erase(qc1,
qc2), return type
const_iterator and description
"erases the elements in the range
[qc1, qc2)".
In 23.1.2 [lib.associative.reqmts] paragraph 7, replace
"p is a valid iterator to
a,
q is a valid dereferenceable
iterator to a,
[q1, q2) is a valid range in
a" with
"p is a valid iterator to
a,
pc is a valid const iterator to
a,
q is a valid
dereferenceable iterator to a,
qc is a valid dereferenceable const
iterator to a,
[q1, q2) is a valid range in
a, [qc1,
q2) is a valid range of const iterators in
a."
In table 84 (associative container requirements):
-
Add another row after a.insert(p,
t): expression a.insert(pc,
t), return type
const_iterator, description and
complexity "same as above".
-
Add another row following
a.erase(q): expression
a.erase(qc), return type
const_iterator, description and
complexity "same as above".
-
Add another row following a.erase(q1,
q2): expression a.erase(qc1,
qc2), return type
const_iterator, and description
and complexity "same as above".
In the class synopses of 23.2.1 [lib.deque], 23.2.2 [lib.list], 23.2.4
[lib.vector], and 23.2.5 [lib.vector.bool], and in the member function
descriptions in 23.2.1.3 [lib.deque.modifiers], 23.2.2.3 [lib.list.modifiers],
and 23.2.4.3 [lib.vector.modifiers], add the new signatures
const_iterator insert(const_iterator
position, const T& x);
const_iterator erase(const_iterator
position);
const_iterator erase(const_iterator
first, const_iterator last);
and change the signatures of the other two overloads of insert to
void insert(const_iterator position,
size_type n, const T& x);
template <class
InputIterator>
void insert(const_iterator
position, InputIterator first, InputIterator last);
In the class synopses in 23.3.1 [lib.map], 23.3.2 [lib.multimap], 23.3.3
[lib.set], and 23.3.4 [lib.multiset], change the
signatures
iterator insert(iterator position, const
value_type& x);
iterator erase(iterator position);
iterator erase(iterator first, iterator
last);
to
iterator insert(iterator position,
const value_type& x);
const_iterator
insert(const_iterator position, const value_type& x);
iterator
erase(iterator position);
const_iterator
erase(const_iterator position);
iterator erase(iterator first, iterator
last);
const_iterator
erase(const_iterator first, iterator last);
Option B
In 2.3.1.1 [lib.sequence.reqmts] paragraph 3, replace
"p denotes a valid iterator to
a,
q denotes a valid dereferenceable
iterator to a,
[q1, q2) denotes a valid range in
a" with
"p denotes a valid const iterator
to a,
q denotes a valid dereferenceable
const iterator to a,
[q1, q2) denotes a valid range of
const iterators in a"
In 23.1.2 [lib.associative.reqmts] paragraph 7, replace
"p is a valid iterator to
a,
q is a valid dereferenceable
iterator to a,
[q1, q2) is a valid range in
a" with
"p is a valid const iterator to
a,
q is a valid dereferenceable const
iterator to a,
[q1, q2) is a valid range of const
iterators in a".
In the class synopses of 23.2.1 [lib.deque], 23.2.2 [lib.list], and 23.2.4
[lib.vector],
and in the member function descriptions in 23.2.1.3 [lib.deque.modifiers],
23.2.2.3 [lib.list.modifiers], and 23.2.4.3 [lib.vector.modifiers], change the
signatures of insert and erase to
iterator insert(const_iterator position, const T& x);
void insert(const_iterator position,
size_type n, const T& x);
template <class
InputIterator>
void insert(const_iterator
position, InputIterator first, InputIterator last);
iterator erase(const_iterator
position);
iterator erase(const_iterator first,
const_iterator last);
In the class synopses in 23.3.1 [lib.map], 23.3.2 [lib.multimap], 23.3.3
[lib.set], and 23.3.4 [lib.multiset], change the signatures
iterator insert(iterator position,
const value_type& x);
iterator erase(iterator position);
iterator erase(iterator first, iterator
last);
to
iterator insert(const_iterator
position, const value_type& x);
iterator erase(const_iterator
position);
iterator erase(const_iterator first, iterator last);
In 23.1.3 [lib.unord.req] paragraph 9, change
"p and
q2 are valid iterators to
a,
q and
q1 are valid dereferenceable
iterators to a,
[q1, q2) is a valid range in
a,
r and
r1 are valid dereferenceable const
iterators to a,
r2 is a valid const iterator to
a,
[r1, r2) is a valid range in
a" to
"p and
q2 are valid const iterators to
a,
q and
q1 are valid dereferenceable const
iterators to a,
[q1, q2) is a valid range in
a".
In table 86 (unordered associative container requirements), delete the rows for
a.insert(r, t),
a.erase(r), and
a.erase(r1, r2).
In the class synopses in 23.4.1 [lib.unord.map], 23.4.2 [lib.unord.multimap],
23.4.3 [lib.unord.set], and 23.4.4 [lib.unord.multiset], replace the signatures
iterator insert(iterator hint, const
value_type& obj);
const_iterator insert(const_iterator
hint, const value_type& obj);
iterator erase(iterator position);
const_iterator erase(const_iterator
position);
iterator erase(iterator first, iterator
last);
const_iterator erase(const_iterator
first, const_iterator last);
with
iterator insert(const_iterator hint,
const value_type& obj);
iterator erase(const_iterator position);
iterator erase(const_iterator first,
iterator last);