JTC1/SC22/WG21
N0822
Doc. No.: X3J16/95-0222
WG21/N0822
Date: December 3, 1995
Project: Programming Language C++
Reply To: J. Lawrence Podmolik
STR
podmolik@str.com
Clause 23 (Containers Library) Issues List
Revision 7
Revision History
----------------
Revision 1 - January 31, 1995. Distributed in pre-Austin mailing.
Revision 2 - March 2, 1995. Distributed at the Austin meeting.
Revision 3 - May 28, 1995. Distributed in pre-Monterey mailing.
Notes: some discussion was condensed or elided for closed
issues to keep the list to a reasonable size. Also, some
compound issues were split into several separate issues
and some problems with issue numbering were corrected.
Revision 4 - July 11, 1995. Updated and distributed at the Monterey
meeting.
Includes several issues generated from the first round of
X3J16 public review comments, as well as issues resulting
from editorial boxes in the April 28, 1995 version of the WP.
Revision 5 - July 31, 1995. Distributed in post-Monterey mailing.
Updated to reflect issues closed at the Monterey meeting,
Also includes several new issues resulting from the X3J16
public review comments and from discussions at Monterey.
Revision 6 - October 29, 1995. Distributed at the Tokyo meeting.
Includes issues that remained open following the Monterey
meeting, plus a significant number of new issues. For
brevity, this revision lists the full text only of ongoing
and new issues; issues closed up to and including the
Monterey meeting are summarized below.
Note: Working Paper references in this revision are to the
pre-Tokyo draft dated 26 September 1995.
Revision 7 - November ??, 1995. Distributed in the post-Tokyo mailing.
Updated to reflect issues closed at the Tokyo meeting. Also
includes new issues raised (but not addressed) at the Tokyo
meeting and any issues identified since that meeting.
Introduction
------------
This document is a summary of the issues identified in Clause 23. For
each issue the status, a short description, and pointers to relevant
reflector messages and papers are given. This evolving document will
serve as a basis of discussion and historical for Containers issues and
as a foundation of proposals for resolving specific issues.
Summary of Open Issues
----------------------
23-028 Clean up empty sections in Clause 23
23-041 Possible solutions for map::insert()
23-043 Fix container ambiguities when T == size_type
23-044 Inconsistent insert() return types for assoc. containers
23-045 Remove <stdexcept> from <bitset> synopsis
23-046 Clean up bitset element access methods
23-047 Clarify complexity for deque::erase()
23-048 Improve description of list::sort()
23-049 Clarify complexity for vector::insert(p,i,j)
23-050 Add additional constructors to Container requirements
23-051 Fix description of list::unique()
23-052 Fix description of list::merge()
23-053 vector<bool>::const_reference should be bool
23-054 Define vector<bool>::reference::operator==()
23-055 Fix return type of map::operator[]()
23-056 Remove const version of map::operator[]()
23-057 Need semantics for associative containers
23-058 Fix reverse iterator typedef arguments
23-059 Wrong reverse iterator type for associative containers
23-060 Fix postcondition for (&a)->~X() in requirements table
23-061 Reorganize Clause 23 sections
23-062 Remove() algorithm doesn't work on map/multimap
Summary of Closed Issues
------------------------
23-001 Add convenience functions to STL containers
23-002 Should some STL members return an iterator?
23-003 Nomenclature problems in STL classes
23-004 Should STL classes have fixed comparator semantics?
23-005 Should some STL members return a size_type?
23-006 Naming inconsistencies in bits<T>
23-007 Adding vector<bool>::flip that toggles all bits
23-008 Add a nested reference class to bits<T>
23-009 Add "default value" arg to map/multimap constructors
23-010 * Requirements for type T in template containers
23-011 Bitset inserters/extractors need updating
23-012 Templatize bits members for basic_string
23-013 Return values from library class member functions
23-014 Add hash tables to standard library
23-015 Reference counted strings and begin()/end()
23-016 Adding constructors to nested reference types
23-017 Add clear() to all containers
23-018 Add additional pop() functions to containers
23-019 Make Allocator argument in containers const refs
23-020 Change container adapter interfaces
23-021 Modify complexity of swap() due to allocators
23-022 Add typedef, member to retrieve allocator type
23-023 Specify container iterators as opaque types
23-024 * Fix copy constructors w.r.t. allocators
23-025 Remove bitset exposition implementation
23-026 Update vector<bool> with partial specialization
23-027 Make vector<bool> bit ref swap a static member
23-029 Fix vector constructor signatures in description
23-030 * Update descriptions of deque operations
23-031 * Specialize swap() algorithm for containers
23-032 * Non-const top() missing in priority_queue?
23-033 * Clean up resize() effects for deque, list and vector
23-034 * Reverse iterator types for list
23-035 * Correct argument list to vector<bool>::insert
23-036 * Need semantics for at() member deque/vector
23-037 * Semantics for a.back() in sequence requirements
23-038 * Specify iterator properties for Clauses 21 & 23
23-039 * Reconsider return type of erase(iterator)
23-040 * Need typedefs for map/multimap T type
23-042 * Fix default container for priority_queue
Note: Issues marked with a '*' indicate issues closed at the most
recent meeting (Tokyo, November 1995)
Issues
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-010
Title: Requirements for type T in template containers
Sections: 23 [lib.containers]
Status: Closed
Description:
The current WP does not place explicit requirements (that I
could find) on class T (the value_type) for container classes.
It appears that for (most? many? all?) containers, T must
either have an accessible default constructor, copy
constructor, operator=, and destructor, or the compiler must be
able to generate them.
Where present, similar requirements probably apply to class Key
and other template arguments throughout the library clauses.
Implementors need to know the requirements so that they can
avoid use of class member functions not required to be present
(or compiler generatable) and accessible.
Resolution:
Discussed by the LWG in Tokyo.
This issue was addressed by Beman Dawes' paper N0700 =
95-0100, "Requirements for STL Template Arguments". The
Working Paper now contains the necessary requirements in
subclauses 20.1 [lib.utility.requirements] and 23.1
[lib.container.requirements].
Therefore: close this issue with no further action required.
Requestor: Beman Dawes <beman@dawes.win.net>
Owner:
Emails: (none)
Papers: WG21/N0700 = X3J16/95-0100
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-024
Title: Fix copy constructors w.r.t. allocators
Sections: 23.2.2 [lib.deque], 23.2.3 [lib.list],
23.2.5 [lib.vector], 23.2.6 [lib.vector.bool],
23.3.1 [lib.map], 23.3.2 [lib.multimap],
23.3.3 [lib.set], 23.3.4 [lib.multiset]
Status: Closed
Description:
The copy constructors for each of the containers listed
above takes a second Allocator argument. However, this
argument defaults to Allocator(), meaning that the
new container is by default created with the default
allocator, rather than the allocator used in the original
initializer container. The default should be to use the
same allocator as the initializing object.
This issue was originally discussed by the LWG at Monterey.
It was generally agreed that by default the copy should use
the same allocator as the original object.
One suggested resolution was to provide an overloaded copy
constructor for each container, allowing the user to specify
the allocator used for the copy, e.g.
vector(const vector<T,Allocator>& x);
vector(const vector<T,Allocator>& x, const Allocator& a);
However, some people preferred simply removing this feature
altogether, i.e.
- remove the allocator argument from all container copy
constructors in Clause 23 (and Clause 21).
- specify that the behavior of the copy constructor is
to copy the container using the allocator of the original
(source) container.
- if a user wants to copy a container using a different
allocator, then this can be done either by constructing a
new container with the desired allocator and then doing an
assignment, or using explicit iteration over the original
container.
Once this issue is resolved all the appropriate declarations
and descriptions must be cleaned up, not only in Clause 23,
but in Clause 21 as well.
Resolution:
Discussed by the LWG in Tokyo. It was decided that removing
the allocator argument from all container copy constructors
in Clause 23 was the best solution.
Therefore:
o In each of the subclauses listed above, remove the
last argument ("const Allocator& = Allocator()")
from each of the container copy constructors.
o In subclause 23.1 [lib.container.requirements], replace
paragraph 7 with the following:
"Copy constructors for all container types defined
in this clause copy the allocator argument from
their respective first parameters. All other
constructors for container types take an Allocator&
argument (20.1.4)."
Requestor: Library Working Group
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-028
Title: Clean up empty sections in Clause 23
Sections: 23 (Containers library)
Status: Active
Description:
Clause 23 contains a large number of empty sections with
no text, especially in the descriptions of the associative
containers. These sections must be reviewed in detail.
Either the appropriate text must be added to these sections
or the sections should be deleted.
[Note: this problem applies to other library clauses as well,
e.g. Clause 24 (Iterators library).]
Proposed Resolution:
Discussed in Monterey but no action was taken. Discussed
again by the LWG in Tokyo.
Since most of the empty sections are simply placeholders,
they can be removed easily after it is determined that they
serve no purpose.
Therefore, leave the empty sections intact for now.
Requestor: Library Working Group
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-030
Title: Update descriptions of deque operations
Sections: 23.2.2.6 [lib.deque.modifiers]
Status: Closed
Description:
Update the effects sections for deque operations to provide
additional guarantees about iterator and reference validity.
In particular, change the following two descriptions in
[lib.deque.modifiers]:
> insert and push invalidate all the iterators and references
> to the deque.
insert in the middle of a deque invalidates all the iterators
and references to the deque. insert and push at either end of
a deque invalidate all the iterators to the deque, but have no
effect on the validity of all the references to the deque.
> erase and pop invalidate all the iterators and references to
> the deque.
erase in the middle of a deque invalidates all the iterators
and references to the deque. erase and pop at either end of a
deque invalidate only the iterators and the references to the
erased element.
Resolution:
Discussed by the LWG in Tokyo.
Change the Effects section for the deque insert() members in
23.2.2.6 [lib.deque.modifiers] to read as follows:
"An insert in the middle of the deque invalidates all
the iterators and references to the deque. An insert
at either end of the deque invalidates all the
iterators to the deque, but has no effect on the
validity of the references to the deque."
Change the Effects section for the deque erase() members in
23.2.2.6 [lib.deque.modifiers] to read as follows:
"An erase in the middle of the deque invalidates all
the iterators and references to the deque. An erase
at either end of the deque invalidates only the
iterators and the references to the erased element."
Note: the deque push and pop members are defined in terms of
insert() and erase() in Table 64 (Optional Sequence Operations),
therefore need not be addressed separately.
Requestor: Meng Lee (lee@hpl.hp.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-031
Title: Specialize swap() algorithm for containers
Sections: 23 [lib.containers]
Status: Closed
Description:
The containers in Clause 23 provide a member swap() function
that under certain conditions is more efficient than the
generic swap() algorithm that requires a temporary.
The library should provide partial specializations for
the swap() algorithm when it is applied to containers.
The specialization simply translates the call into a
call to the corresponding member function.
For example, for vector we would add
template <class T, class A>
void swap(vector<T,A>& a, vector<T,A>& b)
{
a.swap(b);
}
and similarly for the other containers.
Resolution:
Discussed by the LWG in Tokyo.
Add partial specializations for the swap() function to
the following sections: 23.2.2 [lib.deque], 23.2.3 [lib.list],
23.2.5 [lib.vector], 23.2.6 [lib.vector.bool], 23.3.1
[lib.map], 23.3.2 [lib.multimap], 23.3.3 [lib.set] and
23.3.4 [lib.multiset].
These specializations should be declared as follows:
template <class T, class Allocator>
void swap(deque<T,Allocator>& a, deque<T,Allocator>& b);
template <class T, class Allocator>
void swap(list<T,Allocator>& a, list<T,Allocator>& b);
template <class T, class Allocator>
void swap(vector<T,Allocator>& a, vector<T,Allocator>& b);
template <class Allocator>
void swap(vector<bool,Allocator>& a, vector<bool,Allocator>& b);
template <class Key, class T, class Compare, class Allocator>
void swap(map<Key,T,Compare,Allocator>& a,
map<Key,T,Compare,Allocator>& b);
template <class Key, class T, class Compare, class Allocator>
void swap(multimap<Key,T,Compare,Allocator>& a,
multimap<Key,T,Compare,Allocator>& b);
template <class Key, class Compare, class Allocator>
void swap(set<Key,Compare,Allocator>& a,
set<Key,Compare,Allocator>& b);
template <class Key, class Compare, class Allocator>
void swap(multiset<Key,Compare,Allocator>& a,
multiset<Key,Compare,Allocator>& b);
In each case, the Effects section should be written as:
Effects: a.swap(b)
Requestor: Alex Stepanov
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-032
Title: Non-const top() missing in priority_queue?
Sections: 23.2.4.2 [lib.priority.queue]
Status: Closed
Description:
Template class priority_queue, has a const version of top()
but no non-const version.
Should it also have a non-const version, like the HP
implementation does? We didn't see a proposal explicitly
removing this routine, so maybe it was inadvertently missed?
Resolution:
Discussed by the LWG in Tokyo. Recommend that the issue
be closed with no change to the working paper.
Requestor: Judy Ward (j_ward@zko.dec.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-033
Title: Clean up resize() effects for deque, list and vector
Sections: 23.2.2.4 [lib.deque.capacity],
23.2.3.4 [lib.list.capacity],
23.2.5.4 [lib.vector.capacity]
Status: Closed
Description:
The Effects sections for the resize() members of deque,
list and vector need work:
- all "s." should be removed
- the "v" argument should be replaced by "c"
- "size()-sz" should be switched to "sz-size()"
Resolution:
Discussed by the LWG in Tokyo.
Recommend that the changes listed in the above Description
be applied to the three relevant sections.
Requestor: Judy Ward (j_ward@zko.dec.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-034
Title: Reverse iterator types for list
Sections: 23.2.3 [lib.list]
Status: Closed
Description:
Template class list shows the reverse_iterator and
const_reverse_iterator typedefs based on reverse_iterator.
Shouldn't these typedefs instead be based on
reverse_bidirectional_iterator, as specified in the HP
implementation and because lists support bidirectional
iterators?
Resolution:
Discussed by the LWG in Tokyo. Recommend modifying the
reverse_iterator and const_reverse_iterator typedefs in
section 23.2.3 [lib.list] with:
typedef reverse_bidirectional_iterator<
iterator, value_type, reference,
difference_type> reverse_iterator;
typedef reverse_bidirectional_iterator<
const_iterator, value_type, const_reference,
difference_type> const_reverse_iterator;
NOTE: In addition to the naming problem described here,
all the reverse_iterator and const_reverse_iterator typedefs
in Clause 23 also omit the fourth (Pointer) template argument
required by for the reverse iterator adapters defined in
24.3.1 [lib.reverse.iterators]. The class basic_string in
Clause 21 also has this problem.
Requestor: Judy Ward (j_ward@zko.dec.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-035
Title: Correct argument list to vector<bool>::insert
Sections: 23.2.6 [lib.vector.bool]
Status: Closed
Description:
Class vector<bool>, shows the second insert function:
void insert (iterator position, size_type n,
const bool& x = bool());
At the Austin meeting, proposal 95-0014R1, section 1.2.7,
removed the default value for the third parameter. This
change was made to the template class vector, but was missed
for the vector<bool> specialization.
Resolution:
Discussed by the LWG in Tokyo. Recommend changing the
declaration of the second version of insert() in 23.2.6
[lib.vector.bool] to:
void insert(iterator position, size_type n,
const bool& x);
Requestor: Judy Ward (j_ward@zko.dec.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-036
Title: Need semantics for at() member deque/vector
Sections: 23.2.6 [lib.vector.bool]
Status: Closed
Description:
Template class list is missing a description for the new at()
function, i.e. at() does range checking whereas operator[]
does not.
(The proposal to add at() was passed at Valley Forge, 94-0155,
section 3.)
Resolution:
Discussed by the LWG in Tokyo. List does not support the at()
or operator[] members. However, semantics for at() are
missing from the descriptions of vector and deque.
Add an entry to Table 64 (Optional Sequence Operations)
in section 23.1.1 [lib.sequence.reqmts] that describes the
at() member. The table entry should read:
a.at(n) T&; const T& *(a.begin()+n) vector,deque
for constant a
Also, add a new paragraph immediately after Table 64 that
reads as follows:
"The member function at() provides bounds-checked
access to container elements. at() throws
out_of_range if n >= a.size()."
Note: basic_string already includes verbiage for at() in
21.1.1.7 [lib.string.access].
Requestor: Judy Ward (j_ward@zko.dec.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-037
Title: Semantics for a.back() in sequence requirements
Sections: 23.1.1 [lib.sequence.reqmts]
Status: Closed
Description:
In subclause 23.1.1 [lib.sequence.reqmts], Table 64
(Optional sequence requirements), the operation semantics
for a.back() are given as *a.end().
It is supposed to be *(a.end()-1); that is how it is
implemented by HP.
Resolution:
Discussed by the LWG in Tokyo.
The current revision of the WP gives the semantics as
*--a.end(). Therefore, close this issue with no changes
to the WP.
Requestor: Beman Dawes (beman@dawes.win.net)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-038
Title: Specify iterator properties for Clauses 21 & 23
Sections: 21 [lib.strings], 23 [lib.containers]
Status: Closed
Description:
This is a Clause 23 (Containers) and a Clause 21 (Strings)
issue.
Clause 24 explains iterator categories in detail, but
elsewhere in the WP it doesn't say what the results of
iterator_category(), value_type(), and distance_type()
applied to the various iterator types are.
The following table defines the iterator information for
each of the iterators in Clauses 21 and 23 (in addition
to the stream iterator types):
Type Category value_type distance_type
-------------------------- ------------- ---------- -------------
istream_iterator<V,T> Input V T::off_type
istreambuf_iterator<C,T> Input C T::off_type
ostream_iterator<V,T> Output V T::off_type
ostreambuf_iterator<C,T> Output C T::off_type
basic_string<C,T,A> RandomAccess C difference_type
deque<T,A> RandomAccess T difference_type
list<T,A> Bidirectional T difference_type
vector<T,A> RandomAccess T difference_type
map<K,V,Comp,A> Bidirectional value_type difference_type
multimap<K,V,Comp,A> Bidirectional value_type difference_type
set<K,V,Comp,A> Bidirectional value_type difference_type
multiset<K,V,Comp,A> Bidirectional value_type difference_type
(For container X<>, "xxx_type" refers to X<>::xxx_type.)
Resolution:
Discussed by the LWG in Tokyo. The WP explicitly states the
iterator types for deque, list and vector, but not for the
associative containers.
Therefore, add the following sentence to the first paragraph
of sections 23.3.1 [lib.map], 23.3.2 [lib.multimap], 23.3.3
[lib.set] and 23.3.4 [lib.multiset], respectively:
"XXX supports bidirectional iterators."
where XXX is replaced by map, multimap, set and multiset,
respectively.
Requestor: Nathan Myers (myersn@roguewave.com)
Owner:
Emails: c++std-lib-4173, c++std-lib-4175
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-039
Title: Reconsider return type of erase(iterator)
Sections: 23.1.1 [lib.container.reqmts]
Status: Closed
Description:
NOTE: An earlier proposal by Frank Griswold (issue 23-002)
recommended the following:
The method listed below should return an iterator
providing the location of the change called for by
the method. These changes should be made in parallel
on all the containers mentioned in the WP:
iterator Container<T>::erase(iterator);
The rationale was that certain algorithms would be difficult
or impossible to write unless the erase() member returned
the iterator (the current return type is void).
The original proposal did not generate enough support in the
LWG to be brought for a vote and the issue was closed.
However, Nathan Myers now provides the following example to
illustrate why this decision should be reconsidered:
--------
Here is the sample code illustrating why erase really should
return an iterator.
template <class Sequence, InputIterator>
void extract(Sequence& box, InputIterator first,
InputIterator last)
{
typename Sequence::iterator_type hit = box1.begin();
while (first != last &&
(hit = find(hit, box.end(), *first)) != box.end()) {
hit = box.erase(hit); // [1]
++first;
}
}
I don't see how to do this without line [1] as it is.
But this is illegal with sequence::erase defined as it is now.
Here's another example:
template <class T, class Sequence, UnaryFunction>
void extract(Sequence& box, const UnaryFunction& f, const T& t)
{
typename Sequence::iterator_type hit = box1.begin();
while (first != last &&
(hit = find(hit, box.end(), t)) != box.end()) {
hit = box.erase(hit); // [1]
t = f(t);
}
}
Resolution:
Discussed by the LWG in Tokyo. It was decided to add an
iterator return value not only to the single-argument
version of erase() but also the two-argument version that
erases all the elements in a range. Therefore:
Modify the two entries for erase() in Table 63 (Sequence
requirements) to read as follows:
a.erase(q) iterator erases the element pointed
to by q
a.erase(q1,q2) iterator erases the elements in the
range [q1,q2).
Also, add the following two paragraphs immediately after
the table:
"The iterator returned from a.erase(q) points to
the element immediately following q prior the
element being erased. If no such element exists,
a.end() is returned."
"The iterator returned by a.erase(q1,q2) points
to the element pointed to by q2 prior to any
elements being erased. If no such element exists,
then a.end() is returned."
Finally, make the corresponding changes to basic_string
(section 21.1.1.8.5 [lib.string.erase]) once the "remove"
member of basic_string is renamed "erase".
NOTE: Also need to provide semantics for the iterator that
is returned from insert().
Requestor: Nathan Myers (myersn@roguewave.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-040
Title: Need typedefs for map/multimap T type
Sections: 23 [lib.containers]
Status: Closed
Description:
Neither map nor multimap currently provide a typedef
corresponding to the type T. Such a typedef should be
added to both map and multimap.
The following are some suggested names for this typedef:
typedef T mapped_type;
typedef T elem_type;
typedef T assoc_type;
typedef T associated_type;
typedef T contained_type;
Resolution:
Discussed by the LWG in Tokyo. Recommend adding the
following typedef to the declarations of map (section
23.3.1 [lib.map]) and multimap (section 23.3.2
[lib.multimap]):
typedef T mapped_type;
Also replace the use of T as the return type of operator[]
with mapped_type in the declaration of map.
Requestor: Beman Dawes (beman@dawes.win.net)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-041
Title: Possible solutions for map::insert()
Sections: 23 [lib.containers]
Status: Active
Description:
--> Nathan Myers writes in c++std-lib-4239:
The problem with map<>::insert has been kicking around
on comp.std.c++ for some time, and has come up here as
well. The issue is that (given a map<> instance m and
a map insert iterator i) there is no concise way to
construct a value to pass:
m.insert(pair<const int,string>(3,"hi"));
*i = pair<const int,string>(3,"hi");
make_pair<>(), whatever its merits, is little help.
The problem is twofold: first, because the required "const"
cannot be deduced, the full type must be specified in the
call -- this repetition of type names is a general nuisance;
second, type deduction may deduce the wrong type anyway.
Any solution offered should solve both.
One approach to the problem would be to provide
a template converting constructor for pair<>:
template <class T1, class T2>
struct pair {
template <class U, class V>
pair(const pair<U,V>& p) : first(p.first), second(p.second) {}
...
};
One could then rewrite the above example as
m.insert(make_pair(3,"hi"));
*i = make_pair(3,"hi");
relying on the implicit conversion (e.g.)
pair<int,char*> --> pair<const int,string>.
A more conservative solution would be to provide a static
member function of map<>:
static value_type
value(const K& k, const T& t) { return pair<const K,T>(k,t); }
One could then rewrite the above example as
m.insert(m.value(3,"hi"));
*i = m.value(3,"hi");
I would consider either of these a satisfactory solution.
--> Sean Corfield replied in c++std-lib-4241:
Of the two solutions, I suspect the converting constructor
will be more useful: it will help people using pair<> in
non-map code (and I have been bitten by this).
For the map-specific solution, what about a two-argument
version of 'insert' that simply constructs the correct
pair<> type and invokes the one-argument version?
Something like:
... insert(const T t, U u)
{ return insert(pair<const T, U>(t, u)); }
[I'd be quite happy with the static member value() -- this is
just another possible alternative]
Proposed Resolution:
Discussed by the LWG in Tokyo. No clear consensus was
reached. The LWG preferred adding a two-argument overload
for insert(), but unfortunately this creates ambiguities
with the existing template version of insert() that takes
two Iterator arguments.
Requestor: Nathan Myers (myersn@roguewave.com)
Owner:
Emails: c++std-lib-4239, c++std-lib-4241
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-042
Title: Fix default container for priority_queue
Sections: 23.2.4.2 [lib.priority.queue]
Status: Closed
Description:
The resolution to issue 23-020, closed at the Monterey
meeting, contained an error compared to the original
proposed resolution. The default container for a
priority_queue should be vector, not deque.
Proposed Resolution:
Change the declaration of priority_queue in 23.2.4.2
[lib.priority.queue] from:
template<class T, class Container = deque<T>,
class Compare = less<Container::value_type>,
class Allocator = allocator>
class priority_queue {
...
};
to:
template<class T, class Container = vector<T>,
class Compare = less<Container::value_type>,
class Allocator = allocator>
class priority_queue {
...
};
Requestor: Nathan Myers (myersn@roguewave.com)
Owner:
Emails: (none)
Papers: X3J16/95-0160 = WG21/N0760 (Clause 23 issues Rev. 5)
------------------------------------------------------------------------
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! NEW !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-043
Title: Fix container ambiguities when T == size_type
Sections: 23 [lib.containers]
Status: Active
Description:
Various types of calls to constructors & member functions
are ambiguous for the case that the element of the container
is a size_type: as long as C++ does not have constraints,
the templates on InputIterator may conflict with the
size/value methods.
A note should be added to explain how to disambiguate the
constructors (do not default the allocator argument). A
solution (possibly involving a defaultable dummy argument?)
should be found for assign() and insert().
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-044
Title: Inconsistent insert() return types for assoc. containers
Sections: 23.1.2 [lib.associative.reqmts]
Status: Active
Description:
The table in 23.1.2 [lib.associative.reqmts] gives the
following signatures:
pair<iterator, bool> a_uniq.insert(t);
iterator a_eq.insert(t);
iterator a.insert(p,t);
Why is the case with the extra "hint" parameter p treated
differently? In other words, in the latter case when
inserting into a container with unique keys, there is no
way to determine if an insertion actually takes place.
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-045
Title: Remove <stdexcept> from <bitset> synopsis
Sections: 23.2 [lib.sequences]
Status: Active
Description:
Remove the header <stdexcept> from the <bitset> header
synopsis. It is not needed.
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-046
Title: Clean up bitset element access methods
Sections: 23.2.1 [lib.template.bitset],
23.2.1.2 [lib.bitset.members]
23.2.1.3 [lib.bitset.operators]
Status: Active
Description:
Make the following changes to class bitset:
o Add a const version of operator[](size_t) that
returns bool.
o Add both const and non-const versions of at()
to provide checked access (as is done for the
other containers in clause 23).
o Provide semantics for operator[] and at() in
23.2.1.2 [lib.bitset.members] and
23.2.1.3 [lib.bitset.operators].
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-047
Title: Clarify complexity for deque::erase()
Sections: 23.2.2.6 [lib.deque.modifiers]
Status: Active
Description:
The complexity given for erase should be labelled as a worst
case complexity.
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-048
Title: Improve description of list::sort()
Sections: 23.2.3.7 [lib.list.ops]
Status: Active
Description:
Need a more precise specification of the semantics for the
list sort() functions.
Note: refer to 25.3 [lib.alg.sorting.] for possible wording
to use.
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-049
Title: Clarify complexity for vector::insert(p,i,j)
Sections: 23.2.5.6 [lib.vector.modifiers]
Status: Active
Description:
The promise about the complexity if insert(p,i,j) is not
compatible with the last sentence of the associated footnote.
Change that last sentence to allow for copying the elements
of the range before insertion.
In X3J16/95-0195 = WG21/N0795, P.J. Plauger adds:
The vector::insert template cannot meet the stated
complexity requirements (originally intended for a
random_access_iterator) when the template class parameter
InputIterator is truly an input_iterator. They need to be
*carefully* rethought. (See 23.2.5.2 for the handling of
vector::vector template.)
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-050
Title: Add additional constructors to Container requirements
Sections: 23.1 [lib.container.requirements]
Status: Active
Description:
In section 23.1 [lib.container.requirements], the Container
requirements table should also list the required constructors
X(al) and X(a, al), for al an object of type Allocator.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-051
Title: Fix description of list::unique()
Sections: 23.2.3.7 [lib.list.ops]
Status: Active
Description:
The Effects section for list::unique() doesn't say what
happens with binary_pred in the template form. Should say
that the predicate for removal is either operator= or
binary_pred.
Also, list::unique() does not apply the binary predicate
``Exactly size() - 1'' times if size() is zero. Should
qualify the statement for non-empty lists only.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-052
Title: Fix description of list::merge()
Sections: 23.2.3.7 [lib.list.ops]
Status: Active
Description:
list::merge doesn't state the ordering criteria for either
version of the two functions, at least not with sufficient
completeness.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-053
Title: vector<bool>::const_reference should be bool
Sections: 23.2.6 [lib.vector.bool]
Status: Active
Description:
The definition for vector<bool, allocator>::const_reference
should be bool, not const reference.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-054
Title: Define vector<bool>::reference::operator==()
Sections: 23.2.6 [lib.vector.bool]
Status: Active
Description:
vector<bool>::reference should define operator=(const
reference& x) as returning ``*this = bool(x)''. The default
assignment operator is not adequate for this class.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-055
Title: Fix return type of map::operator[]()
Sections: 23.3.1 [lib.map]
Status: Active
Description:
The return type of map::operator[] should be
Allocator::types<T>.reference, not T&.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-056
Title: Remove const version of map::operator[]()
Sections: 23.3.1 [lib.map]
Status: Active
Description:
map::operator[](const key_type&) const is an unapproved (and
nonsensical) addition. It should be struck.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-057
Title: Need semantics for associative containers
Sections: 23.3.1.1 [lib.map.types] and others
Status: Active
Description:
Much of the description of template classes map, multimap,
set, and multiset have no semantics. These must be
supplied.
Proposed Resolution:
Requestor: P. J. Plauger
Owner:
Emails: (none)
Papers: X3J16/95-0195 = WG21/N0795
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-058
Title: Fix reverse iterator typedef arguments
Sections: 23.2.2 [lib.deque], 23.2.3 [lib.list]
23.2.5 [lib.vector], 23.2.6 [lib.vector.bool],
23.3.1 [lib.map], 23.3.2 [lib.multimap],
23.3.3 [lib.set], 23.3.4 [lib.multiset]
Status: Active
Description:
The following reverse iterator typedefs are incorrect:
deque::reverse_iterator 23.2.2 [lib.deque]
list::reverse_bidirectional_iterator 23.2.3 [lib.list]
vector::reverse_iterator 23.2.5 [lib.vector]
vector<bool>::reverse_iterator 23.2.6 [lib.vector.bool]
map::reverse_iterator 23.3.1 [lib.map]
multimap::reverse_iterator 23.3.2 [lib.multimap]
set::reverse_iterator 23.3.3 [lib.set]
multiset::reverse_iterator 23.3.4 [lib.multiset]
In each case, the typedefs only specify four template
arguments, e.g.
typedef reverse_iterator<iterator, value_type,
const_reference, difference_type> reverse_iterator
However, the definitions of reverse_iterator and
reverse_bidirectional_iterator require *five* template
arguments. Each of the above typedefs is missing a
"pointer" template argument in the fourth position,
after the reference argument but before the difference
type.
Each typedefs should be written to read:
typedef reverse_iterator<iterator, value_type,
reference, pointer, difference_type> reverse_iterator;
A complicating factor is that none of the containers in
Clause 23 currently have a "pointer" typedef. Such a
typedef must be introduced for each container, e.g.
typedef typename Allocator::types<T>::pointer pointer;
Proposed Resolution:
Requestor: Larry Podmolik (podmolik@str.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-059
Title: Wrong reverse iterator type for associative containers
Sections: 23.3.1 [lib.map], 23.3.2 [lib.multimap],
23.3.3 [lib.set], 23.3.4 [lib.multiset]
Status: Active
Description:
Each of the associative containers (map, multimap, set
and multiset) supports only bidirectional iterators, but
their reverse_iterator typedefs currently use the regular
reverse_iterator adapter, which requires random access
iterators. These typedefs should be specified using
reverse_bidirectional_iterator instead.
Note: this issue is identical to issue 23-034, which dealt
with list only. It was an oversight not to make the same
fixes to the associative containers.
Proposed Resolution:
Requestor: Larry Podmolik (podmolik@str.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-060
Title: Fix postcondition for (&a)->~X() in requirements table
Sections: 23.1 [lib.container.requirements]
Status: Active
Description:
In the Container requirements table, the postcondition for
the expression (&a)->~X() refers to a.size(). This doesn't
make any sense, as the destructor call deletes the container
object.
Proposed Resolution:
Requestor: German delegation comments
Owner:
Emails: c++std-edit-579
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-061
Title: Reorganize Clause 23 sections
Sections: 23 [lib.containers]
Status: Active
Description:
The current overall structure of Clause 23 needs some work.
In particular, bitset is not a Sequence (in the STL sense)
and shuld be moved to its own section. Also, the container
adapters belong in a separate section for the same reason
(they are currently stuck in between list and vector).
I suggest the following organization for Clause 23:
Introduction
Fixed-size containers
<bitset>
Variable-size containers
Requirements
Sequences
<deque>
<list>
<vector>
Associative Containers
<map>
<set>
Container adapters
<queue>
<stack>
Proposed Resolution:
Requestor: Larry Podmolik (podmolik@str.com)
Owner:
Emails: (none)
Papers: (none)
-------------------------------------------------------------------------
Work Group: Library
Issue Number: 23-062
Title: Remove() algorithm doesn't work on map/multimap
Sections: 23 [lib.containers]
Status: Active
Description:
The remove() algorithm doesn't work on map or multimap.
Although remove() is specified to require only forward
iterators, and map supports bidirectional iterators,
the HP implementation required that the value_type of
the collection be assignable. Map::value_type is a
typedef for a pair<const Key, value>, therefore the
compiler cannot generate asignment to the first member.
John Skaller responds in c++std-lib-4305:
>If the algorithm requires iterators with an mutable/
>assignable value type, then this can simply be added to the
>requirements of the algorithm(s) affected. Almost ALL other
>algorithms are affected -- for example you can't sort a
>constant container, the iterators need to have mutable value
>types.
Skaller further suggests that the iterator tags should be
related by an inheritance structure.
Angelica Langer sums up in c++std-lib-4312:
:: We think there are two separate issues here:
:: The one is relating the iterator tags by means of
:: inheritance in order to prevent code duplication.
:: The other is to add new tags to express the difference
:: between constant and mutable iterators.
Proposed Resolution:
Requestor: Angelika Langer (langer@roguewave.com)
Owner:
Emails: c++std-lib-4305, c++std-lib-4308,
c++std-lib-4312, c++std-lib-4314
Papers: (none)