ISO/ IEC 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)