This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[libstdc++] reformat and doxygenate stack, map, multimap
- From: Phil Edwards <phil at jaj dot com>
- To: libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Fri, 21 Jun 2002 23:04:07 -0400
- Subject: [libstdc++] reformat and doxygenate stack, map, multimap
map and multimap were already mostly doc'd by Stephan Buys; this just
finishes off the work and does the same reformatting that everything else
is slowly getting. Only set and multiset now remain from the standard
containers.
The only code change is a concept-check for a default constructor in
map's operator[]. The default ctor isn't required in map by default, but
is specifically used in op[], so it's nice to give a good error message
at compile time if the user hasn't met the requirments. Tested on
i686-pc-linux-gnu.
Applied to trunk.
2002-06-21 Phil Edwards <pme@gcc.gnu.org>
* include/bits/stl_map.h, include/bits/stl_multimap.h,
include/bits/stl_queue.h, include/bits/stl_stack.h: Reformat and
complete doxygenation.
* include/bits/boost_concept_check.h: Minor comment.
Index: include/bits/stl_map.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_map.h,v
retrieving revision 1.11
diff -u -3 -p -r1.11 stl_map.h
--- include/bits/stl_map.h 8 Feb 2002 02:19:06 -0000 1.11
+++ include/bits/stl_map.h 22 Jun 2002 03:01:59 -0000
@@ -58,302 +58,442 @@
* You should not attempt to use it directly.
*/
-#ifndef _CPP_BITS_STL_MAP_H
-#define _CPP_BITS_STL_MAP_H 1
+#ifndef __GLIBCPP_INTERNAL_MAP_H
+#define __GLIBCPP_INTERNAL_MAP_H
#include <bits/concept_check.h>
+// Since this entire file is within namespace std, there's no reason to
+// waste two spaces along the left column. Thus the leading indentation is
+// slightly violated from here on.
namespace std
{
/**
- * @brief A standard container made up of pairs (see std::pair in <utility>)
- * which can be retrieved based on a key.
+ * @brief A standard container made up of (key,value) pairs, which can be
+ * retrieved based on a key, in logarithmic time.
*
- * This is an associative container. Values contained within it can be
- * quickly retrieved through a key element. Example: MyMap["First"] would
- * return the data associated with the key "First".
+ * @ingroup Containers
+ * @ingroup Assoc_containers
+ *
+ * Meets the requirements of a <a href="tables.html#65">container</a>, a
+ * <a href="tables.html#66">reversible container</a>, and an
+ * <a href="tables.html#69">associative container</a> (using unique keys).
+ * For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
+ * value_type is std::pair<const Key,T>.
+ *
+ * Maps support bidirectional iterators.
+ *
+ * @if maint
+ * The private tree data is declared exactly the same way for map and
+ * multimap; the distinction is made entirely in how the tree functions are
+ * called (*_unique versus *_equal, same as the standard).
+ * @endif
*/
-template <class _Key, class _Tp, class _Compare = less<_Key>,
- class _Alloc = allocator<pair<const _Key, _Tp> > >
-class map
+template <typename _Key, typename _Tp, typename _Compare = less<_Key>,
+ typename _Alloc = allocator<pair<const _Key, _Tp> > >
+ class map
{
// concept requirements
__glibcpp_class_requires(_Tp, _SGIAssignableConcept)
- __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
+ __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept)
public:
- // typedefs:
- typedef _Key key_type;
- typedef _Tp data_type;
- typedef _Tp mapped_type;
- typedef pair<const _Key, _Tp> value_type;
- typedef _Compare key_compare;
+ typedef _Key key_type;
+ typedef _Tp mapped_type;
+ typedef pair<const _Key, _Tp> value_type;
+ typedef _Compare key_compare;
class value_compare
- : public binary_function<value_type, value_type, bool> {
- friend class map<_Key,_Tp,_Compare,_Alloc>;
- protected :
- _Compare comp;
- value_compare(_Compare __c) : comp(__c) {}
- public:
- bool operator()(const value_type& __x, const value_type& __y) const {
- return comp(__x.first, __y.first);
- }
- };
+ : public binary_function<value_type, value_type, bool>
+ {
+ friend class map<_Key,_Tp,_Compare,_Alloc>;
+ protected:
+ _Compare comp;
+ value_compare(_Compare __c) : comp(__c) {}
+ public:
+ bool operator()(const value_type& __x, const value_type& __y) const
+ { return comp(__x.first, __y.first); }
+ };
private:
+ /// @if maint This turns a red-black tree into a [multi]map. @endif
typedef _Rb_tree<key_type, value_type,
_Select1st<value_type>, key_compare, _Alloc> _Rep_type;
- _Rep_type _M_t; // red-black tree representing map
+ /// @if maint The actual tree structure. @endif
+ _Rep_type _M_t;
+
public:
- typedef typename _Rep_type::pointer pointer;
- typedef typename _Rep_type::const_pointer const_pointer;
- typedef typename _Rep_type::reference reference;
- typedef typename _Rep_type::const_reference const_reference;
- typedef typename _Rep_type::iterator iterator;
- typedef typename _Rep_type::const_iterator const_iterator;
- typedef typename _Rep_type::reverse_iterator reverse_iterator;
- typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
- typedef typename _Rep_type::size_type size_type;
- typedef typename _Rep_type::difference_type difference_type;
- typedef typename _Rep_type::allocator_type allocator_type;
-
- // allocation/deallocation
-
- map() : _M_t(_Compare(), allocator_type()) {}
- explicit map(const _Compare& __comp,
- const allocator_type& __a = allocator_type())
- : _M_t(__comp, __a) {}
+ // many of these are specified differently in ISO, but the following are
+ // "functionally equivalent"
+ typedef typename _Rep_type::allocator_type allocator_type;
+ typedef typename _Rep_type::reference reference;
+ typedef typename _Rep_type::const_reference const_reference;
+ typedef typename _Rep_type::iterator iterator;
+ typedef typename _Rep_type::const_iterator const_iterator;
+ typedef typename _Rep_type::size_type size_type;
+ typedef typename _Rep_type::difference_type difference_type;
+ typedef typename _Rep_type::pointer pointer;
+ typedef typename _Rep_type::const_pointer const_pointer;
+ typedef typename _Rep_type::reverse_iterator reverse_iterator;
+ typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
+
- template <class _InputIterator>
- map(_InputIterator __first, _InputIterator __last)
+ // [23.3.1.1] construct/copy/destroy
+ // (get_allocator() is normally listed in this section, but seems to have
+ // been accidentally omitted in the printed standard)
+ /**
+ * @brief Default constructor creates no elements.
+ */
+ map() : _M_t(_Compare(), allocator_type()) { }
+
+ // for some reason this was made a separate function
+ /**
+ * @brief Default constructor creates no elements.
+ */
+ explicit
+ map(const _Compare& __comp, const allocator_type& __a = allocator_type())
+ : _M_t(__comp, __a) { }
+
+ /**
+ * @brief Map copy constructor.
+ * @param x A %map of identical element and allocator types.
+ *
+ * The newly-created %map uses a copy of the allocation object used
+ * by @a x.
+ */
+ map(const map& __x)
+ : _M_t(__x._M_t) { }
+
+ /**
+ * @brief Builds a %map from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * Creats a %map consisting of copies of the elements from [first,last).
+ * This is linear in N if the range is already sorted, and NlogN
+ * otherwise (where N is distance(first,last)).
+ */
+ template <typename _InputIterator>
+ map(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }
- template <class _InputIterator>
- map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
- const allocator_type& __a = allocator_type())
- : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
- map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
+ /**
+ * @brief Builds a %map from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param comp A comparison functor.
+ * @param a An allocator object.
+ *
+ * Creats a %map consisting of copies of the elements from [first,last).
+ * This is linear in N if the range is already sorted, and NlogN
+ * otherwise (where N is distance(first,last)).
+ */
+ template <typename _InputIterator>
+ map(_InputIterator __first, _InputIterator __last,
+ const _Compare& __comp, const allocator_type& __a = allocator_type())
+ : _M_t(__comp, __a)
+ { _M_t.insert_unique(__first, __last); }
- map<_Key,_Tp,_Compare,_Alloc>&
- operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
+ // FIXME There is no dtor declared, but we should have something generated
+ // by Doxygen. I don't know what tags to add to this paragraph to make
+ // that happen:
+ /**
+ * The dtor only erases the elements, and note that if the elements
+ * themselves are pointers, the pointed-to memory is not touched in any
+ * way. Managing the pointer is the user's responsibilty.
+ */
+
+ /**
+ * @brief Map assignment operator.
+ * @param x A %map of identical element and allocator types.
+ *
+ * All the elements of @a x are copied, but unlike the copy constructor, the
+ * allocator object is not copied.
+ */
+ map&
+ operator=(const map& __x)
{
_M_t = __x._M_t;
return *this;
}
- // accessors:
-
- key_compare key_comp() const { return _M_t.key_comp(); }
- value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
- allocator_type get_allocator() const { return _M_t.get_allocator(); }
+ /// Get a copy of the memory allocation object.
+ allocator_type
+ get_allocator() const { return _M_t.get_allocator(); }
+ // iterators
/**
- * Returns a read/write iterator that points to the first pair in the map.
+ * Returns a read/write iterator that points to the first pair in the %map.
* Iteration is done in ascending order according to the keys.
*/
- iterator begin() { return _M_t.begin(); }
+ iterator
+ begin() { return _M_t.begin(); }
/**
* Returns a read-only (constant) iterator that points to the first pair
- * in the map. Iteration is done in ascending order according to the keys.
+ * in the %map. Iteration is done in ascending order according to the keys.
*/
- const_iterator begin() const { return _M_t.begin(); }
+ const_iterator
+ begin() const { return _M_t.begin(); }
/**
* Returns a read/write iterator that points one past the last pair in the
- * map. Iteration is done in ascending order according to the keys.
+ * %map. Iteration is done in ascending order according to the keys.
*/
- iterator end() { return _M_t.end(); }
+ iterator
+ end() { return _M_t.end(); }
/**
* Returns a read-only (constant) iterator that points one past the last
- * pair in the map. Iteration is done in ascending order according to the
+ * pair in the %map. Iteration is done in ascending order according to the
* keys.
*/
- const_iterator end() const { return _M_t.end(); }
+ const_iterator
+ end() const { return _M_t.end(); }
/**
* Returns a read/write reverse iterator that points to the last pair in
- * the map. Iteration is done in descending order according to the keys.
+ * the %map. Iteration is done in descending order according to the keys.
*/
- reverse_iterator rbegin() { return _M_t.rbegin(); }
+ reverse_iterator
+ rbegin() { return _M_t.rbegin(); }
/**
* Returns a read-only (constant) reverse iterator that points to the last
- * pair in the map. Iteration is done in descending order according to
+ * pair in the %map. Iteration is done in descending order according to
* the keys.
*/
- const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
+ const_reverse_iterator
+ rbegin() const { return _M_t.rbegin(); }
/**
* Returns a read/write reverse iterator that points to one before the
- * first pair in the map. Iteration is done in descending order according
+ * first pair in the %map. Iteration is done in descending order according
* to the keys.
*/
- reverse_iterator rend() { return _M_t.rend(); }
+ reverse_iterator
+ rend() { return _M_t.rend(); }
/**
* Returns a read-only (constant) reverse iterator that points to one
- * before the first pair in the map. Iteration is done in descending order
+ * before the first pair in the %map. Iteration is done in descending order
* according to the keys.
*/
- const_reverse_iterator rend() const { return _M_t.rend(); }
+ const_reverse_iterator
+ rend() const { return _M_t.rend(); }
+
+ // capacity
+ /** Returns true if the %map is empty. (Thus begin() would equal end().) */
+ bool
+ empty() const { return _M_t.empty(); }
- /** Returns true if the map is empty. (Thus begin() would equal end().) */
- bool empty() const { return _M_t.empty(); }
- /** Returns the size of the map. */
- size_type size() const { return _M_t.size(); }
- /** Returns the maximum size of the map. */
- size_type max_size() const { return _M_t.max_size(); }
+ /** Returns the size of the %map. */
+ size_type
+ size() const { return _M_t.size(); }
+ /** Returns the maximum size of the %map. */
+ size_type
+ max_size() const { return _M_t.max_size(); }
+
+ // [23.3.1.2] element access
/**
- * @brief Subscript ( [] ) access to map data.
+ * @brief Subscript ( @c [] ) access to %map data.
* @param k The key for which data should be retrieved.
- *
- * Allows for easy lookup with the subscript ( [] ) operator. Returns the
+ * @return A reference to the data of the (key,data) %pair.
+ *
+ * Allows for easy lookup with the subscript ( @c [] ) operator. Returns
* data associated with the key specified in subscript. If the key does
- * not exist a pair with that key is created with a default value, which
+ * not exist, a pair with that key is created using default values, which
* is then returned.
+ *
+ * Lookup requires logarithmic time.
*/
- _Tp& operator[](const key_type& __k) {
+ mapped_type&
+ operator[](const key_type& __k)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_DefaultConstructibleConcept<mapped_type>)
+
iterator __i = lower_bound(__k);
// __i->first is greater than or equivalent to __k.
if (__i == end() || key_comp()(__k, (*__i).first))
- __i = insert(__i, value_type(__k, _Tp()));
+ __i = insert(__i, value_type(__k, mapped_type()));
return (*__i).second;
}
- void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
-
- // insert/erase
+ // modifiers
/**
- * @brief Attempts to insert a std::pair into the map.
+ * @brief Attempts to insert a std::pair into the %map.
* @param x Pair to be inserted (see std::make_pair for easy creation of
* pairs).
- * @return A pair of which the first element is an iterator that points
- * to the possibly inserted pair, a second element of type bool
- * to show if the pair was actually inserted.
- *
- * This function attempts to insert a (key, value) pair into the map. A
- * map relies on unique keys and thus a pair is only inserted if its first
- * element (the key) is not already present in the map.
+ * @return A pair, of which the first element is an iterator that points
+ * to the possibly inserted pair, and the second is a bool that
+ * is true if the pair was actually inserted.
+ *
+ * This function attempts to insert a (key, value) %pair into the %map. A
+ * %map relies on unique keys and thus a %pair is only inserted if its first
+ * element (the key) is not already present in the %map.
+ *
+ * Insertion requires logarithmic time.
*/
- pair<iterator,bool> insert(const value_type& __x)
+ pair<iterator,bool>
+ insert(const value_type& __x)
{ return _M_t.insert_unique(__x); }
/**
- * @brief Attempts to insert a std::pair into the map.
+ * @brief Attempts to insert a std::pair into the %map.
* @param position An iterator that serves as a hint as to where the
* pair should be inserted.
* @param x Pair to be inserted (see std::make_pair for easy creation of
* pairs).
- * @return An iterator that points to the inserted (key,value) pair.
+ * @return An iterator that points to the element with key of @a x (may
+ * or may not be the %pair passed in).
*
- * This function is not concerned about whether the insertion took place
- * or not and thus does not return a boolean like the single-argument
+ * This function is not concerned about whether the insertion took place,
+ * and thus does not return a boolean like the single-argument
* insert() does. Note that the first parameter is only a hint and can
* potentially improve the performance of the insertion process. A bad
* hint would cause no gains in efficiency.
+ *
+ * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
+ * for more on "hinting".
+ *
+ * Insertion requires logarithmic time (if the hint is not taken).
*/
- iterator insert(iterator position, const value_type& __x)
+ iterator
+ insert(iterator position, const value_type& __x)
{ return _M_t.insert_unique(position, __x); }
/**
- * @brief A template function that attemps to insert elements from
- * another range (possibly another map).
+ * @brief A template function that attemps to insert a range of elements.
* @param first Iterator pointing to the start of the range to be inserted.
* @param last Iterator pointing to the end of the range.
+ *
+ * Complexity similar to that of the range constructor.
*/
- template <class _InputIterator>
- void insert(_InputIterator __first, _InputIterator __last) {
- _M_t.insert_unique(__first, __last);
- }
+ template <typename _InputIterator>
+ void
+ insert(_InputIterator __first, _InputIterator __last)
+ { _M_t.insert_unique(__first, __last); }
/**
- * @brief Erases an element from a map.
+ * @brief Erases an element from a %map.
* @param position An iterator pointing to the element to be erased.
*
* This function erases an element, pointed to by the given iterator, from
- * a map. Note that this function only erases the element, and that if
+ * a %map. Note that this function only erases the element, and that if
* the element is itself a pointer, the pointed-to memory is not touched
* in any way. Managing the pointer is the user's responsibilty.
*/
- void erase(iterator __position) { _M_t.erase(__position); }
+ void
+ erase(iterator __position) { _M_t.erase(__position); }
/**
- * @brief Erases an element according to the provided key.
+ * @brief Erases elements according to the provided key.
* @param x Key of element to be erased.
- * @return Doc me! (Number of elements that match key? Only makes sense
- * with multimap)
+ * @return The number of elements erased.
*
- * This function erases an element, located by the given key, from a map.
+ * This function erases all the elements located by the given key from
+ * a %map.
* Note that this function only erases the element, and that if
* the element is itself a pointer, the pointed-to memory is not touched
* in any way. Managing the pointer is the user's responsibilty.
*/
- size_type erase(const key_type& __x) { return _M_t.erase(__x); }
+ size_type
+ erase(const key_type& __x) { return _M_t.erase(__x); }
/**
- * @brief Erases a [first,last) range of elements from a map.
+ * @brief Erases a [first,last) range of elements from a %map.
* @param first Iterator pointing to the start of the range to be erased.
* @param last Iterator pointing to the end of the range to be erased.
*
- * This function erases a sequence of elements from a map.
+ * This function erases a sequence of elements from a %map.
* Note that this function only erases the element, and that if
* the element is itself a pointer, the pointed-to memory is not touched
* in any way. Managing the pointer is the user's responsibilty.
*/
- void erase(iterator __first, iterator __last)
- { _M_t.erase(__first, __last); }
+ void
+ erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
+
+ /**
+ * @brief Swaps data with another %map.
+ * @param x A %map of the same element and allocator types.
+ *
+ * This exchanges the elements between two maps in constant time.
+ * (It is only swapping a pointer, an integer, and an instance of
+ * the @c Compare type (which itself is often stateless and empty), so it
+ * should be quite fast.)
+ * Note that the global std::swap() function is specialized such that
+ * std::swap(m1,m2) will feed to this function.
+ */
+ void
+ swap(map& __x) { _M_t.swap(__x._M_t); }
- /** Erases all elements in a map. Note that this function only erases
+ /**
+ * Erases all elements in a %map. Note that this function only erases
* the elements, and that if the elements themselves are pointers, the
* pointed-to memory is not touched in any way. Managing the pointer is
* the user's responsibilty.
*/
- void clear() { _M_t.clear(); }
+ void
+ clear() { _M_t.clear(); }
- // map operations:
+ // observers
+ /**
+ * Returns the key comparison object out of which the %map was constructed.
+ */
+ key_compare
+ key_comp() const { return _M_t.key_comp(); }
/**
- * @brief Tries to locate an element in a map.
- * @param x Key of (key, value) pair to be located.
+ * Returns a value comparison object, built from the key comparison
+ * object out of which the %map was constructed.
+ */
+ value_compare
+ value_comp() const { return value_compare(_M_t.key_comp()); }
+
+ // [23.3.1.3] map operations
+ /**
+ * @brief Tries to locate an element in a %map.
+ * @param x Key of (key, value) %pair to be located.
* @return Iterator pointing to sought-after element, or end() if not
* found.
*
* This function takes a key and tries to locate the element with which
* the key matches. If successful the function returns an iterator
- * pointing to the sought after pair. If unsuccessful it returns the
- * one past the end ( end() ) iterator.
+ * pointing to the sought after %pair. If unsuccessful it returns the
+ * past-the-end ( @c end() ) iterator.
*/
- iterator find(const key_type& __x) { return _M_t.find(__x); }
+ iterator
+ find(const key_type& __x) { return _M_t.find(__x); }
/**
- * @brief Tries to locate an element in a map.
- * @param x Key of (key, value) pair to be located.
+ * @brief Tries to locate an element in a %map.
+ * @param x Key of (key, value) %pair to be located.
* @return Read-only (constant) iterator pointing to sought-after
* element, or end() if not found.
*
* This function takes a key and tries to locate the element with which
* the key matches. If successful the function returns a constant iterator
- * pointing to the sought after pair. If unsuccessful it returns the
- * one past the end ( end() ) iterator.
+ * pointing to the sought after %pair. If unsuccessful it returns the
+ * past-the-end ( @c end() ) iterator.
*/
- const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
+ const_iterator
+ find(const key_type& __x) const { return _M_t.find(__x); }
/**
- * @brief Finds the number of elements with given key.
+ * @brief Finds the number of elements with given key.
* @param x Key of (key, value) pairs to be located.
- * @return Number of elements with specified key.
+ * @return Number of elements with specified key.
*
- * This function only makes sense for multimaps.
+ * This function only makes sense for multimaps; for map the result will
+ * either be 0 (not present) or 1 (present).
*/
- size_type count(const key_type& __x) const {
- return _M_t.find(__x) == _M_t.end() ? 0 : 1;
- }
+ size_type
+ count(const key_type& __x) const
+ { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
/**
* @brief Finds the beginning of a subsequence matching given key.
@@ -361,12 +501,13 @@ public:
* @return Iterator pointing to first element matching given key, or
* end() if not found.
*
- * This function is useful only with std::multimap. It returns the first
+ * This function is useful only with multimaps. It returns the first
* element of a subsequence of elements that matches the given key. If
* unsuccessful it returns an iterator pointing to the first element that
* has a greater value than given key or end() if no such element exists.
*/
- iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
+ iterator
+ lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); }
/**
* @brief Finds the beginning of a subsequence matching given key.
@@ -374,14 +515,13 @@ public:
* @return Read-only (constant) iterator pointing to first element
* matching given key, or end() if not found.
*
- * This function is useful only with std::multimap. It returns the first
+ * This function is useful only with multimaps. It returns the first
* element of a subsequence of elements that matches the given key. If
* unsuccessful the iterator will point to the next greatest element or,
* if no such greater element exists, to end().
*/
- const_iterator lower_bound(const key_type& __x) const {
- return _M_t.lower_bound(__x);
- }
+ const_iterator
+ lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); }
/**
* @brief Finds the end of a subsequence matching given key.
@@ -390,7 +530,8 @@ public:
*
* This function only makes sense with multimaps.
*/
- iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
+ iterator
+ upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); }
/**
* @brief Finds the end of a subsequence matching given key.
@@ -400,9 +541,9 @@ public:
*
* This function only makes sense with multimaps.
*/
- const_iterator upper_bound(const key_type& __x) const {
- return _M_t.upper_bound(__x);
- }
+ const_iterator
+ upper_bound(const key_type& __x) const
+ { return _M_t.upper_bound(__x); }
/**
* @brief Finds a subsequence matching given key.
@@ -410,8 +551,7 @@ public:
* @return Pair of iterators that possibly points to the subsequence
* matching given key.
*
- * This function improves on lower_bound() and upper_bound() by giving a more
- * elegant and efficient solution. It returns a pair of which the first
+ * This function returns a pair of which the first
* element possibly points to the first element matching the given key
* and the second element possibly points to the last element matching the
* given key. If unsuccessful the first element of the returned pair will
@@ -420,9 +560,9 @@ public:
*
* This function only makes sense for multimaps.
*/
- pair<iterator,iterator> equal_range(const key_type& __x) {
- return _M_t.equal_range(__x);
- }
+ pair<iterator,iterator>
+ equal_range(const key_type& __x)
+ { return _M_t.equal_range(__x); }
/**
* @brief Finds a subsequence matching given key.
@@ -430,8 +570,7 @@ public:
* @return Pair of read-only (constant) iterators that possibly points to
* the subsequence matching given key.
*
- * This function improves on lower_bound() and upper_bound() by giving a more
- * elegant and efficient solution. It returns a pair of which the first
+ * This function returns a pair of which the first
* element possibly points to the first element matching the given key
* and the second element possibly points to the last element matching the
* given key. If unsuccessful the first element of the returned pair will
@@ -440,64 +579,87 @@ public:
*
* This function only makes sense for multimaps.
*/
- pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
- return _M_t.equal_range(__x);
- }
-
- template <class _K1, class _T1, class _C1, class _A1>
- friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
- const map<_K1, _T1, _C1, _A1>&);
- template <class _K1, class _T1, class _C1, class _A1>
- friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
- const map<_K1, _T1, _C1, _A1>&);
+ pair<const_iterator,const_iterator>
+ equal_range(const key_type& __x) const
+ { return _M_t.equal_range(__x); }
+
+ template <typename _K1, typename _T1, typename _C1, typename _A1>
+ friend bool operator== (const map<_K1,_T1,_C1,_A1>&,
+ const map<_K1,_T1,_C1,_A1>&);
+ template <typename _K1, typename _T1, typename _C1, typename _A1>
+ friend bool operator< (const map<_K1,_T1,_C1,_A1>&,
+ const map<_K1,_T1,_C1,_A1>&);
};
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
- const map<_Key,_Tp,_Compare,_Alloc>& __y) {
- return __x._M_t == __y._M_t;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
- const map<_Key,_Tp,_Compare,_Alloc>& __y) {
- return __x._M_t < __y._M_t;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
- const map<_Key,_Tp,_Compare,_Alloc>& __y) {
- return !(__x == __y);
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
- const map<_Key,_Tp,_Compare,_Alloc>& __y) {
- return __y < __x;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
- const map<_Key,_Tp,_Compare,_Alloc>& __y) {
- return !(__y < __x);
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
- const map<_Key,_Tp,_Compare,_Alloc>& __y) {
- return !(__x < __y);
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
- map<_Key,_Tp,_Compare,_Alloc>& __y) {
- __x.swap(__y);
-}
+
+/**
+ * @brief Map equality comparison.
+ * @param x A %map.
+ * @param y A %map of the same type as @a x.
+ * @return True iff the size and elements of the maps are equal.
+ *
+ * This is an equivalence relation. It is linear in the size of the
+ * maps. Maps are considered equivalent if their sizes are equal,
+ * and if corresponding elements compare equal.
+*/
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
+ const map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return __x._M_t == __y._M_t; }
+
+/**
+ * @brief Map ordering relation.
+ * @param x A %map.
+ * @param y A %map of the same type as @a x.
+ * @return True iff @a x is lexographically less than @a y.
+ *
+ * This is a total ordering relation. It is linear in the size of the
+ * maps. The elements must be comparable with @c <.
+ *
+ * See std::lexographical_compare() for how the determination is made.
+*/
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
+ const map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return __x._M_t < __y._M_t; }
+
+/// Based on operator==
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
+ const map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return !(__x == __y); }
+
+/// Based on operator<
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
+ const map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return __y < __x; }
+
+/// Based on operator<
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
+ const map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return !(__y < __x); }
+
+/// Based on operator<
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
+ const map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return !(__x < __y); }
+
+/// See std::map::swap().
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline void
+ swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y)
+ { __x.swap(__y); }
} // namespace std
-#endif /* _CPP_BITS_STL_MAP_H */
+#endif /* __GLIBCPP_INTERNAL_MAP_H */
-// Local Variables:
-// mode:C++
-// End:
Index: include/bits/stl_multimap.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_multimap.h,v
retrieving revision 1.11
diff -u -3 -p -r1.11 stl_multimap.h
--- include/bits/stl_multimap.h 8 Feb 2002 02:19:06 -0000 1.11
+++ include/bits/stl_multimap.h 22 Jun 2002 03:01:59 -0000
@@ -1,6 +1,6 @@
// Multimap implementation -*- C++ -*-
-// Copyright (C) 2001 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
@@ -63,293 +63,421 @@
#include <bits/concept_check.h>
+// Since this entire file is within namespace std, there's no reason to
+// waste two spaces along the left column. Thus the leading indentation is
+// slightly violated from here on.
namespace std
{
+
// Forward declaration of operators < and ==, needed for friend declaration.
-template <class _Key, class _Tp,
- class _Compare = less<_Key>,
- class _Alloc = allocator<pair<const _Key, _Tp> > >
+
+template <typename _Key, typename _Tp,
+ typename _Compare = less<_Key>,
+ typename _Alloc = allocator<pair<const _Key, _Tp> > >
class multimap;
-template <class _Key, class _Tp, class _Compare, class _Alloc>
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
-template <class _Key, class _Tp, class _Compare, class _Alloc>
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
/**
- * @brief A standard container made up of pairs (see std::pair in <utility>)
- * which can be retrieved based on a key.
+ * @brief A standard container made up of (key,value) pairs, which can be
+ * retrieved based on a key, in logarithmic time.
+ *
+ * @ingroup Containers
+ * @ingroup Assoc_containers
+ *
+ * Meets the requirements of a <a href="tables.html#65">container</a>, a
+ * <a href="tables.html#66">reversible container</a>, and an
+ * <a href="tables.html#69">associative container</a> (using equivalent keys).
+ * For a @c multimap<Key,T> the key_type is Key, the mapped_type is T, and
+ * the value_type is std::pair<const Key,T>.
*
- * This is an associative container. Values contained within it can be
- * quickly retrieved through a key element. In contrast with a map a
- * multimap can have multiple duplicate keys.
+ * Multimaps support bidirectional iterators.
+ *
+ * @if maint
+ * The private tree data is declared exactly the same way for map and
+ * multimap; the distinction is made entirely in how the tree functions are
+ * called (*_unique versus *_equal, same as the standard).
+ * @endif
*/
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-class multimap
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ class multimap
{
// concept requirements
__glibcpp_class_requires(_Tp, _SGIAssignableConcept)
- __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
+ __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept)
public:
-
-// typedefs:
-
- typedef _Key key_type;
- typedef _Tp data_type;
- typedef _Tp mapped_type;
- typedef pair<const _Key, _Tp> value_type;
- typedef _Compare key_compare;
-
- class value_compare : public binary_function<value_type, value_type, bool> {
- friend class multimap<_Key,_Tp,_Compare,_Alloc>;
- protected:
- _Compare comp;
- value_compare(_Compare __c) : comp(__c) {}
- public:
- bool operator()(const value_type& __x, const value_type& __y) const {
- return comp(__x.first, __y.first);
- }
+ typedef _Key key_type;
+ typedef _Tp mapped_type;
+ typedef pair<const _Key, _Tp> value_type;
+ typedef _Compare key_compare;
+
+ class value_compare
+ : public binary_function<value_type, value_type, bool>
+ {
+ friend class multimap<_Key,_Tp,_Compare,_Alloc>;
+ protected:
+ _Compare comp;
+ value_compare(_Compare __c) : comp(__c) {}
+ public:
+ bool operator()(const value_type& __x, const value_type& __y) const
+ { return comp(__x.first, __y.first); }
};
private:
+ /// @if maint This turns a red-black tree into a [multi]map. @endif
typedef _Rb_tree<key_type, value_type,
_Select1st<value_type>, key_compare, _Alloc> _Rep_type;
- _Rep_type _M_t; // red-black tree representing multimap
+ /// @if maint The actual tree structure. @endif
+ _Rep_type _M_t;
+
public:
- typedef typename _Rep_type::pointer pointer;
- typedef typename _Rep_type::const_pointer const_pointer;
- typedef typename _Rep_type::reference reference;
- typedef typename _Rep_type::const_reference const_reference;
- typedef typename _Rep_type::iterator iterator;
- typedef typename _Rep_type::const_iterator const_iterator;
- typedef typename _Rep_type::reverse_iterator reverse_iterator;
- typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
- typedef typename _Rep_type::size_type size_type;
- typedef typename _Rep_type::difference_type difference_type;
- typedef typename _Rep_type::allocator_type allocator_type;
+ // many of these are specified differently in ISO, but the following are
+ // "functionally equivalent"
+ typedef typename _Rep_type::allocator_type allocator_type;
+ typedef typename _Rep_type::reference reference;
+ typedef typename _Rep_type::const_reference const_reference;
+ typedef typename _Rep_type::iterator iterator;
+ typedef typename _Rep_type::const_iterator const_iterator;
+ typedef typename _Rep_type::size_type size_type;
+ typedef typename _Rep_type::difference_type difference_type;
+ typedef typename _Rep_type::pointer pointer;
+ typedef typename _Rep_type::const_pointer const_pointer;
+ typedef typename _Rep_type::reverse_iterator reverse_iterator;
+ typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
-// allocation/deallocation
+ // [23.3.2] construct/copy/destroy
+ // (get_allocator() is also listed in this section)
+ /**
+ * @brief Default constructor creates no elements.
+ */
multimap() : _M_t(_Compare(), allocator_type()) { }
- explicit multimap(const _Compare& __comp,
- const allocator_type& __a = allocator_type())
+
+ // for some reason this was made a separate function
+ /**
+ * @brief Default constructor creates no elements.
+ */
+ explicit
+ multimap(const _Compare& __comp, const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { }
- template <class _InputIterator>
- multimap(_InputIterator __first, _InputIterator __last)
- : _M_t(_Compare(), allocator_type())
- { _M_t.insert_equal(__first, __last); }
-
- template <class _InputIterator>
- multimap(_InputIterator __first, _InputIterator __last,
- const _Compare& __comp,
- const allocator_type& __a = allocator_type())
- : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
- multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { }
+ /**
+ * @brief %Multimap copy constructor.
+ * @param x A %multimap of identical element and allocator types.
+ *
+ * The newly-created %multimap uses a copy of the allocation object used
+ * by @a x.
+ */
+ multimap(const multimap& __x)
+ : _M_t(__x._M_t) { }
+
+ /**
+ * @brief Builds a %multimap from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * Creats a %multimap consisting of copies of the elements from
+ * [first,last). This is linear in N if the range is already sorted,
+ * and NlogN otherwise (where N is distance(first,last)).
+ */
+ template <typename _InputIterator>
+ multimap(_InputIterator __first, _InputIterator __last)
+ : _M_t(_Compare(), allocator_type())
+ { _M_t.insert_equal(__first, __last); }
+
+ /**
+ * @brief Builds a %multimap from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param comp A comparison functor.
+ * @param a An allocator object.
+ *
+ * Creats a %multimap consisting of copies of the elements from [first,last).
+ * This is linear in N if the range is already sorted, and NlogN
+ * otherwise (where N is distance(first,last)).
+ */
+ template <typename _InputIterator>
+ multimap(_InputIterator __first, _InputIterator __last,
+ const _Compare& __comp,
+ const allocator_type& __a = allocator_type())
+ : _M_t(__comp, __a)
+ { _M_t.insert_equal(__first, __last); }
+
+ // FIXME There is no dtor declared, but we should have something generated
+ // by Doxygen. I don't know what tags to add to this paragraph to make
+ // that happen:
+ /**
+ * The dtor only erases the elements, and note that if the elements
+ * themselves are pointers, the pointed-to memory is not touched in any
+ * way. Managing the pointer is the user's responsibilty.
+ */
- multimap<_Key,_Tp,_Compare,_Alloc>&
- operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {
+ /**
+ * @brief %Multimap assignment operator.
+ * @param x A %multimap of identical element and allocator types.
+ *
+ * All the elements of @a x are copied, but unlike the copy constructor, the
+ * allocator object is not copied.
+ */
+ multimap&
+ operator=(const multimap& __x)
+ {
_M_t = __x._M_t;
- return *this;
+ return *this;
}
- // accessors:
-
- key_compare key_comp() const { return _M_t.key_comp(); }
- value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
- allocator_type get_allocator() const { return _M_t.get_allocator(); }
+ /// Get a copy of the memory allocation object.
+ allocator_type
+ get_allocator() const { return _M_t.get_allocator(); }
+ // iterators
/**
* Returns a read/write iterator that points to the first pair in the
- * multimap. Iteration is done in ascending order according to the keys.
+ * %multimap. Iteration is done in ascending order according to the keys.
*/
- iterator begin() { return _M_t.begin(); }
+ iterator
+ begin() { return _M_t.begin(); }
/**
* Returns a read-only (constant) iterator that points to the first pair
- * in the multimap. Iteration is done in ascending order according to the
+ * in the %multimap. Iteration is done in ascending order according to the
* keys.
*/
- const_iterator begin() const { return _M_t.begin(); }
+ const_iterator
+ begin() const { return _M_t.begin(); }
/**
* Returns a read/write iterator that points one past the last pair in the
- * multimap. Iteration is done in ascending order according to the keys.
+ * %multimap. Iteration is done in ascending order according to the keys.
*/
- iterator end() { return _M_t.end(); }
+ iterator
+ end() { return _M_t.end(); }
/**
* Returns a read-only (constant) iterator that points one past the last
- * pair in the multimap. Iteration is done in ascending order according
+ * pair in the %multimap. Iteration is done in ascending order according
* to the keys.
*/
- const_iterator end() const { return _M_t.end(); }
+ const_iterator
+ end() const { return _M_t.end(); }
/**
* Returns a read/write reverse iterator that points to the last pair in
- * the multimap. Iteration is done in descending order according to the
+ * the %multimap. Iteration is done in descending order according to the
* keys.
*/
- reverse_iterator rbegin() { return _M_t.rbegin(); }
+ reverse_iterator
+ rbegin() { return _M_t.rbegin(); }
/**
* Returns a read-only (constant) reverse iterator that points to the last
- * pair in the multimap. Iteration is done in descending order according
+ * pair in the %multimap. Iteration is done in descending order according
* to the keys.
*/
- const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
+ const_reverse_iterator
+ rbegin() const { return _M_t.rbegin(); }
/**
* Returns a read/write reverse iterator that points to one before the
- * first pair in the multimap. Iteration is done in descending order
+ * first pair in the %multimap. Iteration is done in descending order
* according to the keys.
*/
- reverse_iterator rend() { return _M_t.rend(); }
+ reverse_iterator
+ rend() { return _M_t.rend(); }
/**
* Returns a read-only (constant) reverse iterator that points to one
- * before the first pair in the multimap. Iteration is done in descending
+ * before the first pair in the %multimap. Iteration is done in descending
* order according to the keys.
*/
- const_reverse_iterator rend() const { return _M_t.rend(); }
-
- /** Returns true if the map is empty. (Thus begin() would equal end().) */
- bool empty() const { return _M_t.empty(); }
+ const_reverse_iterator
+ rend() const { return _M_t.rend(); }
- /** Returns the size of the map. */
- size_type size() const { return _M_t.size(); }
+ // capacity
+ /** Returns true if the %multimap is empty. */
+ bool
+ empty() const { return _M_t.empty(); }
- /** Returns the maximum size of the map. */
- size_type max_size() const { return _M_t.max_size(); }
+ /** Returns the size of the %multimap. */
+ size_type
+ size() const { return _M_t.size(); }
- void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
+ /** Returns the maximum size of the %multimap. */
+ size_type
+ max_size() const { return _M_t.max_size(); }
- // insert/erase
+ // modifiers
/**
- * @brief Inserts a std::pair into the multimap.
+ * @brief Inserts a std::pair into the %multimap.
* @param x Pair to be inserted (see std::make_pair for easy creation of
* pairs).
* @return An iterator that points to the inserted (key,value) pair.
*
- * This function inserts a (key, value) pair into the multimap. Contrary
- * to a std::map the multimap does not rely on unique keys and thus a
+ * This function inserts a (key, value) pair into the %multimap. Contrary
+ * to a std::map the %multimap does not rely on unique keys and thus
* multiple pairs with the same key can be inserted.
+ *
+ * Insertion requires logarithmic time.
*/
- iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
+ iterator
+ insert(const value_type& __x) { return _M_t.insert_equal(__x); }
/**
- * @brief Inserts a std::pair into the multimap.
+ * @brief Inserts a std::pair into the %multimap.
* @param position An iterator that serves as a hint as to where the
* pair should be inserted.
* @param x Pair to be inserted (see std::make_pair for easy creation of
* pairs).
* @return An iterator that points to the inserted (key,value) pair.
*
- * This function inserts a (key, value) pair into the multimap. Contrary
- * to a std::map the multimap does not rely on unique keys and thus a
+ * This function inserts a (key, value) pair into the %multimap. Contrary
+ * to a std::map the %multimap does not rely on unique keys and thus
* multiple pairs with the same key can be inserted.
* Note that the first parameter is only a hint and can potentially
* improve the performance of the insertion process. A bad hint would
* cause no gains in efficiency.
+ *
+ * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
+ * for more on "hinting".
+ *
+ * Insertion requires logarithmic time (if the hint is not taken).
*/
- iterator insert(iterator __position, const value_type& __x) {
- return _M_t.insert_equal(__position, __x);
- }
+ iterator
+ insert(iterator __position, const value_type& __x)
+ { return _M_t.insert_equal(__position, __x); }
/**
- * @brief A template function that attemps to insert elements from
- * another range (possibly another multimap or standard container).
- * @param first Iterator pointing to the start of the range to be
- * inserted.
- * @param last Iterator pointing to the end of the range to be inserted.
- */
- template <class _InputIterator>
- void insert(_InputIterator __first, _InputIterator __last) {
- _M_t.insert_equal(__first, __last);
- }
+ * @brief A template function that attemps to insert a range of elements.
+ * @param first Iterator pointing to the start of the range to be inserted.
+ * @param last Iterator pointing to the end of the range.
+ *
+ * Complexity similar to that of the range constructor.
+ */
+ template <typename _InputIterator>
+ void
+ insert(_InputIterator __first, _InputIterator __last)
+ { _M_t.insert_equal(__first, __last); }
/**
- * @brief Erases an element from a multimap.
+ * @brief Erases an element from a %multimap.
* @param position An iterator pointing to the element to be erased.
*
* This function erases an element, pointed to by the given iterator, from
- * a mutlimap. Note that this function only erases the element, and that
+ * a %multimap. Note that this function only erases the element, and that
* if the element is itself a pointer, the pointed-to memory is not
* touched in any way. Managing the pointer is the user's responsibilty.
*/
- void erase(iterator __position) { _M_t.erase(__position); }
+ void
+ erase(iterator __position) { _M_t.erase(__position); }
/**
- * @brief Erases an element according to the provided key.
+ * @brief Erases elements according to the provided key.
* @param x Key of element to be erased.
- * @return Doc me! (Number of elements erased?)
+ * @return The number of elements erased.
*
- * This function erases all elements, located by the given key, from a
- * multimap.
+ * This function erases all elements located by the given key from a
+ * %multimap.
* Note that this function only erases the element, and that if
* the element is itself a pointer, the pointed-to memory is not touched
* in any way. Managing the pointer is the user's responsibilty.
*/
- size_type erase(const key_type& __x) { return _M_t.erase(__x); }
+ size_type
+ erase(const key_type& __x) { return _M_t.erase(__x); }
/**
- * @brief Erases a [first,last) range of elements from a multimap.
+ * @brief Erases a [first,last) range of elements from a %multimap.
* @param first Iterator pointing to the start of the range to be erased.
* @param last Iterator pointing to the end of the range to be erased.
*
- * This function erases a sequence of elements from a multimap.
+ * This function erases a sequence of elements from a %multimap.
* Note that this function only erases the elements, and that if
* the elements themselves are pointers, the pointed-to memory is not
* touched in any way. Managing the pointer is the user's responsibilty.
*/
- void erase(iterator __first, iterator __last)
- { _M_t.erase(__first, __last); }
+ void
+ erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
+
+ /**
+ * @brief Swaps data with another %multimap.
+ * @param x A %multimap of the same element and allocator types.
+ *
+ * This exchanges the elements between two multimaps in constant time.
+ * (It is only swapping a pointer, an integer, and an instance of
+ * the @c Compare type (which itself is often stateless and empty), so it
+ * should be quite fast.)
+ * Note that the global std::swap() function is specialized such that
+ * std::swap(m1,m2) will feed to this function.
+ */
+ void
+ swap(multimap& __x) { _M_t.swap(__x._M_t); }
- /** Erases all elements in a multimap. Note that this function only erases
+ /**
+ * Erases all elements in a %multimap. Note that this function only erases
* the elements, and that if the elements themselves are pointers, the
* pointed-to memory is not touched in any way. Managing the pointer is
* the user's responsibilty.
*/
- void clear() { _M_t.clear(); }
+ void
+ clear() { _M_t.clear(); }
- // multimap operations:
+ // observers
+ /**
+ * Returns the key comparison object out of which the %multimap
+ * was constructed.
+ */
+ key_compare
+ key_comp() const { return _M_t.key_comp(); }
+
+ /**
+ * Returns a value comparison object, built from the key comparison
+ * object out of which the %multimap was constructed.
+ */
+ value_compare
+ value_comp() const { return value_compare(_M_t.key_comp()); }
+ // multimap operations
/**
- * @brief Tries to locate an element in a multimap.
+ * @brief Tries to locate an element in a %multimap.
* @param x Key of (key, value) pair to be located.
- * @return Iterator pointing to sought-after (first matching?) element,
+ * @return Iterator pointing to sought-after element,
* or end() if not found.
*
* This function takes a key and tries to locate the element with which
* the key matches. If successful the function returns an iterator
- * pointing to the sought after pair. If unsuccessful it returns the
- * one past the end ( end() ) iterator.
+ * pointing to the sought after %pair. If unsuccessful it returns the
+ * past-the-end ( @c end() ) iterator.
*/
- iterator find(const key_type& __x) { return _M_t.find(__x); }
+ iterator
+ find(const key_type& __x) { return _M_t.find(__x); }
/**
- * @brief Tries to locate an element in a multimap.
+ * @brief Tries to locate an element in a %multimap.
* @param x Key of (key, value) pair to be located.
- * @return Read-only (constant) iterator pointing to sought-after (first
- * matching?) element, or end() if not found.
+ * @return Read-only (constant) iterator pointing to sought-after
+ * element, or end() if not found.
*
* This function takes a key and tries to locate the element with which
* the key matches. If successful the function returns a constant iterator
- * pointing to the sought after pair. If unsuccessful it returns the
- * one past the end ( end() ) iterator.
+ * pointing to the sought after %pair. If unsuccessful it returns the
+ * past-the-end ( @c end() ) iterator.
*/
- const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
+ const_iterator
+ find(const key_type& __x) const { return _M_t.find(__x); }
/**
* @brief Finds the number of elements with given key.
* @param x Key of (key, value) pairs to be located.
* @return Number of elements with specified key.
*/
- size_type count(const key_type& __x) const { return _M_t.count(__x); }
+ size_type
+ count(const key_type& __x) const { return _M_t.count(__x); }
/**
* @brief Finds the beginning of a subsequence matching given key.
@@ -362,7 +490,8 @@ public:
* pointing to the first element that has a greater value than given key
* or end() if no such element exists.
*/
- iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
+ iterator
+ lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); }
/**
* @brief Finds the beginning of a subsequence matching given key.
@@ -375,16 +504,16 @@ public:
* to the next greatest element or, if no such greater element exists, to
* end().
*/
- const_iterator lower_bound(const key_type& __x) const {
- return _M_t.lower_bound(__x);
- }
+ const_iterator
+ lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); }
/**
* @brief Finds the end of a subsequence matching given key.
* @param x Key of (key, value) pair to be located.
* @return Iterator pointing to last element matching given key.
*/
- iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
+ iterator
+ upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); }
/**
* @brief Finds the end of a subsequence matching given key.
@@ -392,9 +521,8 @@ public:
* @return Read-only (constant) iterator pointing to last element matching
* given key.
*/
- const_iterator upper_bound(const key_type& __x) const {
- return _M_t.upper_bound(__x);
- }
+ const_iterator
+ upper_bound(const key_type& __x) const { return _M_t.upper_bound(__x); }
/**
* @brief Finds a subsequence matching given key.
@@ -402,17 +530,15 @@ public:
* @return Pair of iterators that possibly points to the subsequence
* matching given key.
*
- * This function improves on lower_bound() and upper_bound() by giving a more
- * elegant and efficient solution. It returns a pair of which the first
+ * This function returns a pair of which the first
* element possibly points to the first element matching the given key
* and the second element possibly points to the last element matching the
* given key. If unsuccessful the first element of the returned pair will
* contain an iterator pointing to the next greatest element or, if no such
* greater element exists, to end().
*/
- pair<iterator,iterator> equal_range(const key_type& __x) {
- return _M_t.equal_range(__x);
- }
+ pair<iterator,iterator>
+ equal_range(const key_type& __x) { return _M_t.equal_range(__x); }
/**
* @brief Finds a subsequence matching given key.
@@ -420,72 +546,96 @@ public:
* @return Pair of read-only (constant) iterators that possibly points to
* the subsequence matching given key.
*
- * This function improves on lower_bound() and upper_bound() by giving a more
- * elegant and efficient solution. It returns a pair of which the first
+ * This function returns a pair of which the first
* element possibly points to the first element matching the given key
* and the second element possibly points to the last element matching the
* given key. If unsuccessful the first element of the returned pair will
* contain an iterator pointing to the next greatest element or, if no such
* a greater element exists, to end().
*/
- pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
- return _M_t.equal_range(__x);
- }
+ pair<const_iterator,const_iterator>
+ equal_range(const key_type& __x) const { return _M_t.equal_range(__x); }
- template <class _K1, class _T1, class _C1, class _A1>
- friend bool operator== (const multimap<_K1, _T1, _C1, _A1>&,
- const multimap<_K1, _T1, _C1, _A1>&);
- template <class _K1, class _T1, class _C1, class _A1>
- friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&,
- const multimap<_K1, _T1, _C1, _A1>&);
+ template <typename _K1, typename _T1, typename _C1, typename _A1>
+ friend bool operator== (const multimap<_K1,_T1,_C1,_A1>&,
+ const multimap<_K1,_T1,_C1,_A1>&);
+ template <typename _K1, typename _T1, typename _C1, typename _A1>
+ friend bool operator< (const multimap<_K1,_T1,_C1,_A1>&,
+ const multimap<_K1,_T1,_C1,_A1>&);
};
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- return __x._M_t == __y._M_t;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- return __x._M_t < __y._M_t;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- return !(__x == __y);
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- return __y < __x;
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- return !(__y < __x);
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline bool operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- return !(__x < __y);
-}
-
-template <class _Key, class _Tp, class _Compare, class _Alloc>
-inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
- multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
- __x.swap(__y);
-}
+
+/**
+ * @brief Multimap equality comparison.
+ * @param x A %multimap.
+ * @param y A %multimap of the same type as @a x.
+ * @return True iff the size and elements of the maps are equal.
+ *
+ * This is an equivalence relation. It is linear in the size of the
+ * multimaps. Multimaps are considered equivalent if their sizes are equal,
+ * and if corresponding elements compare equal.
+*/
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ {
+ return __x._M_t == __y._M_t;
+ }
+
+/**
+ * @brief Multimap ordering relation.
+ * @param x A %multimap.
+ * @param y A %multimap of the same type as @a x.
+ * @return True iff @a x is lexographically less than @a y.
+ *
+ * This is a total ordering relation. It is linear in the size of the
+ * multimaps. The elements must be comparable with @c <.
+ *
+ * See std::lexographical_compare() for how the determination is made.
+*/
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return __x._M_t < __y._M_t; }
+
+/// Based on operator==
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return !(__x == __y); }
+
+/// Based on operator<
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return __y < __x; }
+
+/// Based on operator<
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return !(__y < __x); }
+
+/// Based on operator<
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline bool
+ operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ { return !(__x < __y); }
+
+/// See std::multimap::swap().
+template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
+ inline void
+ swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
+ multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+ { __x.swap(__y); }
} // namespace std
#endif /* __GLIBCPP_INTERNAL_MULTIMAP_H */
-// Local Variables:
-// mode:C++
-// End:
Index: include/bits/stl_queue.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_queue.h,v
retrieving revision 1.13
diff -u -3 -p -r1.13 stl_queue.h
--- include/bits/stl_queue.h 16 Jun 2002 11:29:52 -0000 1.13
+++ include/bits/stl_queue.h 22 Jun 2002 03:01:59 -0000
@@ -75,10 +75,10 @@ template <typename _Tp, typename _Sequen
class queue;
template <typename _Tp, typename _Seq>
-inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
+inline bool operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
template <typename _Tp, typename _Seq>
-inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
+inline bool operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
/**
@@ -291,8 +291,8 @@ template <typename _Tp, typename _Sequen
* defining a strict weak ordering.
*
* Members not found in "normal" containers are @c container_type,
- * which is a typedef for the second Sequence parameter, and @c push and
- * @c pop, which are standard %queue/FIFO operations.
+ * which is a typedef for the second Sequence parameter, and @c push,
+ * @c pop, and @c top, which are standard %queue/FIFO operations.
*
* @note No equality/comparison operators are provided for %priority_queue.
*
Index: include/bits/stl_stack.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_stack.h,v
retrieving revision 1.10
diff -u -3 -p -r1.10 stl_stack.h
--- include/bits/stl_stack.h 6 Dec 2001 20:29:31 -0000 1.10
+++ include/bits/stl_stack.h 22 Jun 2002 03:01:59 -0000
@@ -1,6 +1,6 @@
// Stack implementation -*- C++ -*-
-// Copyright (C) 2001 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
@@ -63,98 +63,192 @@
#include <bits/concept_check.h>
+// Since this entire file is within namespace std, there's no reason to
+// waste two spaces along the left column. Thus the leading indentation is
+// slightly violated from here on.
namespace std
{
// Forward declarations of operators == and <, needed for friend declaration.
-template <class _Tp,
- class _Sequence = deque<_Tp> >
+template <typename _Tp, typename _Sequence = deque<_Tp> >
class stack;
-template <class _Tp, class _Seq>
-bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
+template <typename _Tp, typename _Seq>
+inline bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
-template <class _Tp, class _Seq>
-bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
+template <typename _Tp, typename _Seq>
+inline bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y);
-template <class _Tp, class _Sequence>
-class stack
+/**
+ * @brief A standard container giving FILO behavior.
+ *
+ * @ingroup Containers
+ * @ingroup Sequences
+ *
+ * Meets many of the requirements of a <a href="tables.html#65">container</a>,
+ * but does not define anything to do with iterators. Very few of the
+ * other standard container interfaces are defined.
+ *
+ * This is not a true container, but an @e adaptor. It holds another
+ * container, and provides a wrapper interface to that container. The
+ * wrapper is what enforces strict first-in-last-out %stack behavior.
+ *
+ * The second template parameter defines the type of the underlying
+ * sequence/container. It defaults to std::deque, but it can be any type
+ * that supports @c back, @c push_back, and @c pop_front, such as
+ * std::list, std::vector, or an appropriate user-defined type.
+ *
+ * Members not found in "normal" containers are @c container_type,
+ * which is a typedef for the second Sequence parameter, and @c push,
+ * @c pop, and @c top, which are standard %stack/FILO operations.
+*/
+template <typename _Tp, typename _Sequence>
+ class stack
{
// concept requirements
+ typedef typename _Sequence::value_type _Sequence_value_type;
__glibcpp_class_requires(_Tp, _SGIAssignableConcept)
__glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept)
- typedef typename _Sequence::value_type _Sequence_value_type;
- __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
+ __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
- template <class _Tp1, class _Seq1>
+ template <typename _Tp1, typename _Seq1>
friend bool operator== (const stack<_Tp1, _Seq1>&,
const stack<_Tp1, _Seq1>&);
- template <class _Tp1, class _Seq1>
+ template <typename _Tp1, typename _Seq1>
friend bool operator< (const stack<_Tp1, _Seq1>&,
const stack<_Tp1, _Seq1>&);
+
public:
- typedef typename _Sequence::value_type value_type;
- typedef typename _Sequence::size_type size_type;
- typedef _Sequence container_type;
+ typedef typename _Sequence::value_type value_type;
+ typedef typename _Sequence::reference reference;
+ typedef typename _Sequence::const_reference const_reference;
+ typedef typename _Sequence::size_type size_type;
+ typedef _Sequence container_type;
- typedef typename _Sequence::reference reference;
- typedef typename _Sequence::const_reference const_reference;
protected:
+ // See queue::c for notes on this name.
_Sequence c;
-public:
- stack() : c() {}
- explicit stack(const _Sequence& __s) : c(__s) {}
- bool empty() const { return c.empty(); }
- size_type size() const { return c.size(); }
- reference top() { return c.back(); }
- const_reference top() const { return c.back(); }
- void push(const value_type& __x) { c.push_back(__x); }
- void pop() { c.pop_back(); }
+public:
+ // XXX removed old def ctor, added def arg to this one to match 14882
+ /**
+ * @brief Default constructor creates no elements.
+ */
+ explicit
+ stack(const _Sequence& __c = _Sequence())
+ : c(__c) {}
+
+ /**
+ * Returns true if the %stack is empty.
+ */
+ bool
+ empty() const { return c.empty(); }
+
+ /** Returns the number of elements in the %stack. */
+ size_type
+ size() const { return c.size(); }
+
+ /**
+ * Returns a read/write reference to the data at the first element of the
+ * %stack.
+ */
+ reference
+ top() { return c.back(); }
+
+ /**
+ * Returns a read-only (constant) reference to the data at the first
+ * element of the %stack.
+ */
+ const_reference
+ top() const { return c.back(); }
+
+ /**
+ * @brief Add data to the top of the %stack.
+ * @param x Data to be added.
+ *
+ * This is a typical %stack operation. The function creates an element at
+ * the top of the %stack and assigns the given data to it.
+ * The time complexity of the operation depends on the underlying
+ * sequence.
+ */
+ void
+ push(const value_type& __x) { c.push_back(__x); }
+
+ /**
+ * @brief Removes first element.
+ *
+ * This is a typical %stack operation. It shrinks the %stack by one.
+ * The time complexity of the operation depends on the underlying
+ * sequence.
+ *
+ * Note that no data is returned, and if the first element's data is
+ * needed, it should be retrieved before pop() is called.
+ */
+ void
+ pop() { c.pop_back(); }
};
-template <class _Tp, class _Seq>
-bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
-{
- return __x.c == __y.c;
-}
-
-template <class _Tp, class _Seq>
-bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
-{
- return __x.c < __y.c;
-}
-
-template <class _Tp, class _Seq>
-bool operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
-{
- return !(__x == __y);
-}
-
-template <class _Tp, class _Seq>
-bool operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
-{
- return __y < __x;
-}
-template <class _Tp, class _Seq>
-bool operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
-{
- return !(__y < __x);
-}
-
-template <class _Tp, class _Seq>
-bool operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
-{
- return !(__x < __y);
-}
+/**
+ * @brief Stack equality comparison.
+ * @param x A %stack.
+ * @param y A %stack of the same type as @a x.
+ * @return True iff the size and elements of the stacks are equal.
+ *
+ * This is an equivalence relation. Complexity and semantics depend on the
+ * underlying sequence type, but the expected rules are: this relation is
+ * linear in the size of the sequences, and stacks are considered equivalent
+ * if their sequences compare equal.
+*/
+template <typename _Tp, typename _Seq>
+ inline bool
+ operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
+ { return __x.c == __y.c; }
+
+/**
+ * @brief Stack ordering relation.
+ * @param x A %stack.
+ * @param y A %stack of the same type as @a x.
+ * @return True iff @a x is lexographically less than @a y.
+ *
+ * This is an total ordering relation. Complexity and semantics depend on the
+ * underlying sequence type, but the expected rules are: this relation is
+ * linear in the size of the sequences, the elements must be comparable
+ * with @c <, and std::lexographical_compare() is usually used to make the
+ * determination.
+*/
+template <typename _Tp, typename _Seq>
+ inline bool
+ operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
+ { return __x.c < __y.c; }
+
+/// Based on operator==
+template <typename _Tp, typename _Seq>
+ inline bool
+ operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
+ { return !(__x == __y); }
+
+/// Based on operator<
+template <typename _Tp, typename _Seq>
+ inline bool
+ operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
+ { return __y < __x; }
+
+/// Based on operator<
+template <typename _Tp, typename _Seq>
+ inline bool
+ operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
+ { return !(__y < __x); }
+
+/// Based on operator<
+template <typename _Tp, typename _Seq>
+ inline bool
+ operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
+ { return !(__x < __y); }
} // namespace std
#endif /* __GLIBCPP_INTERNAL_STACK_H */
-// Local Variables:
-// mode:C++
-// End:
Index: include/bits/boost_concept_check.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/boost_concept_check.h,v
retrieving revision 1.8
diff -u -3 -p -r1.8 boost_concept_check.h
--- include/bits/boost_concept_check.h 4 Jan 2002 21:27:31 -0000 1.8
+++ include/bits/boost_concept_check.h 22 Jun 2002 03:01:59 -0000
@@ -149,6 +149,8 @@ struct _Aux_require_same<_Tp,_Tp> { type
__a = __b; // const required for argument to assignment
}
_Tp __a;
+ // possibly should be "Tp* a;" and then dereference "a" in constraint
+ // functions? present way would require a default ctor, i think...
};
template <class _Tp>