From 4df6abc6b3e3899f2c619d27c4c873a8a8e25341 Mon Sep 17 00:00:00 2001 From: Phil Edwards Date: Sun, 16 Jun 2002 11:29:53 +0000 Subject: [PATCH] TODO: Update. 2002-06-16 Phil Edwards * docs/doxygen/TODO: Update. * docs/doxygen/tables.html: Uncomment magical middle column. * docs/doxygen/user.cfg.in: Kludge to ignore function-like macros. * include/bits/stl_queue.h: Doxygenate and reformat. * include/bits/ios_base.h, include/std/std_streambuf.h: Add comment for deprecated names required by the standard. From-SVN: r54666 --- libstdc++-v3/ChangeLog | 9 + libstdc++-v3/docs/doxygen/TODO | 3 +- libstdc++-v3/docs/doxygen/tables.html | 37 +- libstdc++-v3/docs/doxygen/user.cfg.in | 17 +- libstdc++-v3/include/bits/ios_base.h | 1 + libstdc++-v3/include/bits/stl_queue.h | 415 +++++++++++++++++------ libstdc++-v3/include/std/std_streambuf.h | 2 + 7 files changed, 358 insertions(+), 126 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 502a1002f06..94eff35ff09 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2002-06-16 Phil Edwards + + * docs/doxygen/TODO: Update. + * docs/doxygen/tables.html: Uncomment magical middle column. + * docs/doxygen/user.cfg.in: Kludge to ignore function-like macros. + * include/bits/stl_queue.h: Doxygenate and reformat. + * include/bits/ios_base.h, include/std/std_streambuf.h: Add comment + for deprecated names required by the standard. + 2002-06-14 J.T. Conklin * configure.in (target_alias): Fix. diff --git a/libstdc++-v3/docs/doxygen/TODO b/libstdc++-v3/docs/doxygen/TODO index b01dca9ff9c..50ddfe7f2d6 100644 --- a/libstdc++-v3/docs/doxygen/TODO +++ b/libstdc++-v3/docs/doxygen/TODO @@ -25,7 +25,8 @@ c20 Note A c21 Untouched, Note B c22 Untouched c23 See doxygroups.cc and Note B. Notes on what invalidates - iterators need to be added. + iterators need to be added. std::list-specific memfns need + to be filled out. c24 stl_iterator.h (__normal_iterator, other small TODO bits) stream iterators c25 stl_algo.h (lots of stuff) diff --git a/libstdc++-v3/docs/doxygen/tables.html b/libstdc++-v3/docs/doxygen/tables.html index 2382d25c70b..7c340529352 100644 --- a/libstdc++-v3/docs/doxygen/tables.html +++ b/libstdc++-v3/docs/doxygen/tables.html @@ -39,14 +39,15 @@ rendering is ugly. (Update: mozilla 0.9.9 looks MUCH better.)

+ cols="5" title="Table 65"> - + @@ -54,6 +55,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -62,6 +64,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -69,12 +72,14 @@ Anything calling itself a container must meet these minimum requirements. + + @@ -83,6 +88,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -90,6 +96,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -97,6 +104,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -104,6 +112,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -111,6 +120,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -118,6 +128,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -125,6 +136,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -132,6 +144,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -140,6 +153,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -147,12 +161,14 @@ Anything calling itself a container must meet these minimum requirements. + + @@ -161,6 +177,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -168,6 +185,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -175,6 +193,7 @@ Anything calling itself a container must meet these minimum requirements. + @@ -184,7 +203,7 @@ Anything calling itself a container must meet these minimum requirements. - + @@ -192,7 +211,7 @@ Anything calling itself a container must meet these minimum requirements. - + @@ -200,7 +219,7 @@ Anything calling itself a container must meet these minimum requirements. - + @@ -208,7 +227,7 @@ Anything calling itself a container must meet these minimum requirements. - + @@ -216,7 +235,7 @@ Anything calling itself a container must meet these minimum requirements. - + @@ -224,7 +243,7 @@ Anything calling itself a container must meet these minimum requirements. - + @@ -232,7 +251,7 @@ Anything calling itself a container must meet these minimum requirements. - + diff --git a/libstdc++-v3/docs/doxygen/user.cfg.in b/libstdc++-v3/docs/doxygen/user.cfg.in index 776ddba2b48..dff2f3f9d11 100644 --- a/libstdc++-v3/docs/doxygen/user.cfg.in +++ b/libstdc++-v3/docs/doxygen/user.cfg.in @@ -669,13 +669,13 @@ ENABLE_PREPROCESSING = YES # compilation will be performed. Macro expansion can be done in a controlled # way by setting EXPAND_ONLY_PREDEF to YES. -MACRO_EXPANSION = NO +MACRO_EXPANSION = YES # If the EXPAND_ONLY_PREDEF and MACRO_EXPANSION tags are both set to YES # then the macro expansion is limited to the macros specified with the # PREDEFINED and EXPAND_AS_PREDEFINED tags. -EXPAND_ONLY_PREDEF = NO +EXPAND_ONLY_PREDEF = YES # If the SEARCH_INCLUDES tag is set to YES (the default) the includes files # in the INCLUDE_PATH (see below) will be search if a #include is found. @@ -701,10 +701,19 @@ INCLUDE_FILE_PATTERNS = # or name=definition (no spaces). If the definition and the = are # omitted =1 is assumed. -PREDEFINED = _GLIBCPP_DEPRECATED +### The deprecated functions are clearly marked as such in the code, but +### the DEPRECATED macro must be defined for that code to be seen by doxygen. +### The class_requires macros are kludges because SKIP_FUNCTION_MACROS is +### completely broken, and the presence of the macros confuses the parser. + +PREDEFINED = _GLIBCPP_DEPRECATED \ + __glibcpp_class_requires="//" \ + __glibcpp_class_requires2="//" \ + __glibcpp_class_requires3="//" \ + __glibcpp_class_requires4="//" # If the MACRO_EXPANSION and EXPAND_PREDEF_ONLY tags are set to YES then -# this tag can be used to specify a list of macro names that should be expanded. +# this tag can be used to specify a list of macro names that should be expanded. # The macro definition that is found in the sources will be used. # Use the PREDEFINED tag if you want to use a different macro definition. diff --git a/libstdc++-v3/include/bits/ios_base.h b/libstdc++-v3/include/bits/ios_base.h index f5b026900f6..83037047f6f 100644 --- a/libstdc++-v3/include/bits/ios_base.h +++ b/libstdc++-v3/include/bits/ios_base.h @@ -217,6 +217,7 @@ namespace std static const seekdir end = seekdir(SEEK_END); #ifdef _GLIBCPP_DEPRECATED + // Annex D.6 typedef int io_state; typedef int open_mode; typedef int seek_dir; diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h index 5503640187a..bcfb2304e9b 100644 --- a/libstdc++-v3/include/bits/stl_queue.h +++ b/libstdc++-v3/include/bits/stl_queue.h @@ -1,6 +1,6 @@ // Queue 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,182 +63,373 @@ #include +// 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 > +template > class queue; -template +template inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); -template +template inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); -template -class queue +/** + * @brief A standard container giving FIFO behavior. + * + * @ingroup Containers + * @ingroup Sequences + * + * Meets many of the requirements of a container, + * 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-first-out %queue 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 front, @c back, @c push_back, and @c pop_front, + * such as std::list 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 and + * @c pop, which are standard %queue/FIFO operations. +*/ +template + class queue { // concept requirements + typedef typename _Sequence::value_type _Sequence_value_type; __glibcpp_class_requires(_Tp, _SGIAssignableConcept) __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept) __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 + template friend bool operator== (const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); - template + template friend bool operator< (const queue<_Tp1, _Seq1>&, const queue<_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: + /** + * 'c' is the underlying container. Maintainers wondering why this isn't + * uglified as per style guidelines should note that this name is + * specified in the standard, [23.2.3.1]. (Why? Presumably for the same + * reason that it's protected instead of private: to allow derivation. + * But none of the other containers allow for derivation. Odd.) + */ _Sequence c; + public: - explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {} - - bool empty() const { return c.empty(); } - size_type size() const { return c.size(); } - reference front() { return c.front(); } - const_reference front() const { return c.front(); } - reference back() { return c.back(); } - const_reference back() const { return c.back(); } - void push(const value_type& __x) { c.push_back(__x); } - void pop() { c.pop_front(); } + /** + * @brief Default constructor creates no elements. + */ + explicit + queue(const _Sequence& __c = _Sequence()) + : c(__c) {} + + /** + * Returns true if the %queue is empty. + */ + bool + empty() const { return c.empty(); } + + /** Returns the number of elements in the %queue. */ + size_type + size() const { return c.size(); } + + /** + * Returns a read/write reference to the data at the first element of the + * %queue. + */ + reference + front() { return c.front(); } + + /** + * Returns a read-only (constant) reference to the data at the first + * element of the %queue. + */ + const_reference + front() const { return c.front(); } + + /** + * Returns a read/write reference to the data at the last element of the + * %queue. + */ + reference + back() { return c.back(); } + + /** + * Returns a read-only (constant) reference to the data at the last + * element of the %queue. + */ + const_reference + back() const { return c.back(); } + + /** + * @brief Add data to the end of the %queue. + * @param x Data to be added. + * + * This is a typical %queue operation. The function creates an element at + * the end of the %queue 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 %queue operation. It shrinks the %queue 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_front(); } }; -template -bool -operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) -{ - return __x.c == __y.c; -} - -template -bool -operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) -{ - return __x.c < __y.c; -} - -template -bool -operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) -{ - return !(__x == __y); -} - -template -bool -operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) -{ - return __y < __x; -} - -template -bool -operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) -{ - return !(__y < __x); -} - -template -bool -operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) -{ - return !(__x < __y); -} -template , - class _Compare = less > -class priority_queue +/** + * @brief Queue equality comparison. + * @param x A %queue. + * @param y A %queue of the same type as @a x. + * @return True iff the size and elements of the queues 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 queues are considered equivalent + * if their sequences compare equal. +*/ +template + inline bool + operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) + { return __x.c == __y.c; } + +/** + * @brief Queue ordering relation. + * @param x A %queue. + * @param y A %queue 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 + inline bool + operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) + { return __x.c < __y.c; } + +/// Based on operator== +template + inline bool + operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) + { return !(__x == __y); } + +/// Based on operator< +template + inline bool + operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) + { return __y < __x; } + +/// Based on operator< +template + inline bool + operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) + { return !(__y < __x); } + +/// Based on operator< +template + inline bool + operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) + { return !(__x < __y); } + + +/** + * @brief A standard container automatically sorting its contents. + * + * @ingroup Containers + * @ingroup Sequences + * + * 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 sorting and first-in-first-out %queue behavior. + * Very few of the standard container/sequence interface requirements are + * met (e.g., iterators). + * + * The second template parameter defines the type of the underlying + * sequence/container. It defaults to std::vector, but it can be any type + * that supports @c front(), @c push_back, @c pop_back, and random-access + * iterators, such as std::deque or an appropriate user-defined type. + * + * The third template parameter supplies the means of making priority + * comparisons. It defaults to @c less but can be anything + * 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. + * + * @note No equality/comparison operators are provided for %priority_queue. + * + * @note Sorting of the elements takes place as they are added to, and + * removed from, the %priority_queue using the %priority_queue's + * member functions. If you access the elements by other means, and + * change their data such that the sorting order would be different, + * the %priority_queue will not re-sort the elements for you. (How + * could it know to do so?) +*/ +template , + typename _Compare = less > + class priority_queue { // concept requirements + typedef typename _Sequence::value_type _Sequence_value_type; __glibcpp_class_requires(_Tp, _SGIAssignableConcept) __glibcpp_class_requires(_Sequence, _SequenceConcept) __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept) - typedef typename _Sequence::value_type _Sequence_value_type; - __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept); - __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept); + __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) + __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept) 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: - _Sequence c; - _Compare comp; -public: - explicit priority_queue(const _Compare& __x = _Compare(), - const _Sequence& __s = _Sequence()) - : c(__s), comp(__x) - { make_heap(c.begin(), c.end(), comp); } - - template - priority_queue(_InputIterator __first, _InputIterator __last, - const _Compare& __x = _Compare(), - const _Sequence& __s = _Sequence()) - : c(__s), comp(__x) - { - c.insert(c.end(), __first, __last); - make_heap(c.begin(), c.end(), comp); - } - - bool empty() const { return c.empty(); } - size_type size() const { return c.size(); } - const_reference top() const { return c.front(); } + // See queue::c for notes on these names. + _Sequence c; + _Compare comp; +public: + /** + * @brief Default constructor creates no elements. + */ + explicit + priority_queue(const _Compare& __x = _Compare(), + const _Sequence& __s = _Sequence()) + : c(__s), comp(__x) + { make_heap(c.begin(), c.end(), comp); } + + /** + * @brief Builds a %queue from a range. + * @param first An input iterator. + * @param last An input iterator. + * @param x A comparison functor describing a strict weak ordering. + * @param s An initial sequence with which to start. + * + * Begins by copying @a s, inserting a copy of the elements from + * @a [first,last) into the copy of @a s, then ordering the copy + * according to @a x. + * + * For more information on function objects, see the documentation on + * @link s20_3_1_base functor base classes@endlink. + */ + template + priority_queue(_InputIterator __first, _InputIterator __last, + const _Compare& __x = _Compare(), + const _Sequence& __s = _Sequence()) + : c(__s), comp(__x) + { + c.insert(c.end(), __first, __last); + make_heap(c.begin(), c.end(), comp); + } + + /** + * Returns true if the %queue is empty. + */ + bool + empty() const { return c.empty(); } + + /** Returns the number of elements in the %queue. */ + size_type + size() const { return c.size(); } + + /** + * Returns a read-only (constant) reference to the data at the first + * element of the %queue. + */ + const_reference + top() const { return c.front(); } + + /** + * @brief Add data to the %queue. + * @param x Data to be added. + * + * This is a typical %queue operation. + * The time complexity of the operation depends on the underlying + * sequence. + */ void push(const value_type& __x) { try { - c.push_back(__x); - push_heap(c.begin(), c.end(), comp); + c.push_back(__x); + push_heap(c.begin(), c.end(), comp); } catch(...) { - c.clear(); - __throw_exception_again; + c.clear(); + __throw_exception_again; } } + /** + * @brief Removes first element. + * + * This is a typical %queue operation. It shrinks the %queue 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() { try { - pop_heap(c.begin(), c.end(), comp); - c.pop_back(); + pop_heap(c.begin(), c.end(), comp); + c.pop_back(); } catch(...) { - c.clear(); - __throw_exception_again; + c.clear(); + __throw_exception_again; } } }; -// no equality is provided +// No equality/comparison operators are provided for priority_queue. } // namespace std #endif /* __GLIBCPP_INTERNAL_QUEUE_H */ -// Local Variables: -// mode:C++ -// End: diff --git a/libstdc++-v3/include/std/std_streambuf.h b/libstdc++-v3/include/std/std_streambuf.h index 012bf4e6cf6..a319b89e2e9 100644 --- a/libstdc++-v3/include/std/std_streambuf.h +++ b/libstdc++-v3/include/std/std_streambuf.h @@ -464,6 +464,8 @@ namespace std { return traits_type::eof(); } #ifdef _GLIBCPP_DEPRECATED + // http://gcc.gnu.org/ml/libstdc++/2002-05/msg00168.html + // Annex D.6 public: void stossc() -- 2.30.2

Table 65 --- Container Requirements

+
Anything calling itself a container must meet these minimum requirements.
expression result typeoperational semantics notes, pre-/post-conditions, assertions complexity
X::value_type T  T is Assignable compile time
X::reference lvalue of T    compile time
X::const_reference const lvalue of T    compile time
X::iterator iterator type pointing to T  Any iterator category except output iterator. Convertible to X::const_iterator. compile time
X::const_iterator iterator type pointing to const T  Any iterator category except output iterator. compile time
X::difference_type signed integral type  identical to the difference type of X::iterator and X::const_iterator compile time
X::size_type unsigned integral type  size_type can represent any non-negative value of difference_type compile time
X u;    post: u.size() == 0 constant
X();    X().size == 0 constant
X(a);    a == X(a) linear
X u(a);
X u = a;		    post: u == a. Equivalent to: X u; u = a; linear
(&a)->~X(); void  dtor is applied to every element of a; all the memory is deallocated linear
a.begin() iterator; const_iterator for constant a    constant
a.end() iterator; const_iterator for constant a    constant
a == b convertible to bool  == is an equivalence relation. a.size()==b.size() && equal(a.begin(),a.end(),b.begin()) linear
a != b convertible to bool  equivalent to !(a==b) linear
a.swap(b) void  swap(a,b) may or may not have constant complexity
r = a X&  r == a linear
a.size() size_typea.end() - a.begin()   may or may not have constant complexity
a.max_size() size_typesize() of the largest possible container   may or may not have constant complexity
a.empty() convertible to boola.size() == 0   constant
a < b convertible to boollexographical_compare( a.begin, a.end(), b.begin(), b.end()) pre: < is defined for T and is a total ordering relation linear
a > b convertible to boolb < a   linear
a <= b convertible to bool!(a > b)   linear
a >= b convertible to bool!(a < b)   linear