This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Doxygen documentation for slist


Hi,

I wrote up some documentation for __gnu_cxx::slist, borrowing a lot from
what was there already for std::list.

I'm not an experienced writer for technical documentation, nor is
english my mother tongue, so comments and improvements are highly
welcome.

I also have some questions:

- Do I need copyright assignment forms for that kind of change? If so,
  who do I have to ask to get them?

- Should I wait until 4.0 is out to submit such changes? (It's not
  exactly a bug fix, but OTOH these changes are very low-risk, and they
  affect also the web pages.)

Yours,
--Lorenz

Index: include/ext/slist
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/ext/slist,v
retrieving revision 1.25
diff -u -r1.25 slist
--- include/ext/slist	24 Nov 2004 04:11:14 -0000	1.25
+++ include/ext/slist	25 Jan 2005 23:41:50 -0000
@@ -284,9 +284,35 @@
     }
 
   /**
+   *  @brief A container with linear time access to elements, and constant
+   *  time for for insertion and deletion @e after an iterator.
+   *
+   *  @ingroup Containers
+   *  @ingroup Sequences
+   *
    *  This is an SGI extension.
    *  @ingroup SGIextensions
-   *  @doctodo
+   *
+   *  Meets the requirements of a <a href="tables.html#65">container</a> and
+   *  a <a href="tables.html#67">sequence</a>.
+   *
+   *  An slist is a @e singly @e linked list, as opposed to the
+   *  std::list container, which is doubly linked. This means that it is
+   *  possible to iterate over an slist only in forward direction,
+   *  whereas lists allow for bidirectional iterators.
+   *
+   *  Note that insertion and deletion with the insert() and erase()
+   *  operations are slow for slists, since they require a linear
+   *  search. The insert_after() and erase_after() methods allow for
+   *  insertion and deletion in constant time anywhere in the list.
+   *  Slists don't have random access iterators, and elements can't be
+   *  accessed via subscripts ([]).
+   *
+   *  The advantage of %slist over %std::list is that per stored
+   *  element, one pointer can be saved, and it therefore uses less
+   *  memory. Usually, %std::list is more recommendable, since it is
+   *  standard and more portable.
+   *
    */
   template <class _Tp, class _Alloc = allocator<_Tp> >
     class slist : private _Slist_base<_Tp,_Alloc>
@@ -355,28 +381,64 @@
       }
 
     public:
+      /**
+       *  @brief  The default constructor creates an empty slist.
+       */
       explicit
       slist(const allocator_type& __a = allocator_type())
       : _Base(__a) {}
 
+      /**
+       *  @brief  Create an empty %slist with copies of an exemplar element.
+       *  @param  n  The number of elements to initially create.
+       *  @param  x  An element to copy.
+       *
+       *  This constructor fills the %slist with @a n copies of @a x.
+       */
       slist(size_type __n, const value_type& __x,
 	    const allocator_type& __a =  allocator_type())
       : _Base(__a)
       { _M_insert_after_fill(&this->_M_head, __n, __x); }
 
+      /**
+       *  @brief  Create an %slist with default elements.
+       *  @param  n  The number of elements to initially create.
+       *
+       *  This constructor fills the %slist with @a n copies of a
+       *  default-constructed element.
+       */
       explicit
       slist(size_type __n)
       : _Base(allocator_type())
       { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
 
-      // We don't need any dispatching tricks here, because
-      // _M_insert_after_range already does them.
+      /**
+       *  @brief  Builds a %list from a range.
+       *  @param  first  An input iterator.
+       *  @param  last  An input iterator.
+       *
+       *  Create an %slist consisting of copies of the elements from
+       *  [@a first, @a last).  This is linear in N (where N is
+       *  distance(@a first, @a last)).
+       *
+       *  @if maint
+       *  We don't need any dispatching tricks here, because
+       *  _M_insert_after_range already does them.
+       *  @endif
+       */
       template <class _InputIterator>
         slist(_InputIterator __first, _InputIterator __last,
 	      const allocator_type& __a =  allocator_type())
 	: _Base(__a)
         { _M_insert_after_range(&this->_M_head, __first, __last); }
 
+      /**
+       *  @brief  %slist copy constructor.
+       *  @param  x  An %slist of identical element and allocator types.
+       *
+       *  The newly-created %slist uses a copy of the allocation object used
+       *  by @a x.
+       */
       slist(const slist& __x)
       : _Base(__x.get_allocator())
       { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
@@ -392,6 +454,16 @@
       // The range version is a member template, so we dispatch on whether
       // or not the type is an integer.
       
+      /**
+       *  @brief  Assigns a given value to an %slist.
+       *  @param  n  Number of elements to be assigned.
+       *  @param  val  Value to be assigned.
+       *
+       *  This function fills an %slist with @a n copies of the given
+       *  value.  Note that the assignment completely changes the %slist
+       *  and that the resulting %slist's size is the same as the number
+       *  of elements assigned.  Old data may be lost.
+       */
       void
       assign(size_type __n, const _Tp& __val)
       { _M_fill_assign(__n, __val); }
@@ -399,6 +471,18 @@
       void
       _M_fill_assign(size_type __n, const _Tp& __val);
 
+      /**
+       *  @brief  Assigns a range to an %slist.
+       *  @param  first  An input iterator.
+       *  @param  last   An input iterator.
+       *
+       *  This function fills a %slist with copies of the elements in the
+       *  range [@a first,@a last).
+       *
+       *  Note that the assignment completely changes the %slist and
+       *  that the resulting %slist's size is the same as the number of
+       *  elements assigned.  Old data may be lost.
+       */
       template <class _InputIterator>
         void
         assign(_InputIterator __first, _InputIterator __last)
@@ -419,71 +503,161 @@
 
     public:
 
+      /**
+       *  Returns a read/write iterator that points to the first element
+       *  in the %slist.  Iteration is done in ordinary element order.
+       */
       iterator
       begin()
       { return iterator((_Node*)this->_M_head._M_next); }
 
+      /**
+       *  Returns a read-only (constant) iterator that points to the
+       *  first element in the %slist.  Iteration is done in ordinary
+       *  element order.
+       */
       const_iterator
       begin() const
       { return const_iterator((_Node*)this->_M_head._M_next);}
 
+      /**
+       *  Returns a read/write iterator that points one past the last
+       *  element in the %slist.  Iteration is done in ordinary element
+       *  order.
+       */
       iterator
       end()
       { return iterator(0); }
 
+      /**
+       *  Returns a read-only (constant) iterator that points one past
+       *  the last element in the %slist.  Iteration is done in ordinary
+       *  element order.
+       */
       const_iterator
       end() const
       { return const_iterator(0); }
 
-      // Experimental new feature: before_begin() returns a
-      // non-dereferenceable iterator that, when incremented, yields
-      // begin().  This iterator may be used as the argument to
-      // insert_after, erase_after, etc.  Note that even for an empty
-      // slist, before_begin() is not the same iterator as end().  It
-      // is always necessary to increment before_begin() at least once to
-      // obtain end().
+      /**
+       *  (Experimental, new). before_begin() returns a
+       *  non-dereferenceable iterator that, when incremented, yields
+       *  begin().  This iterator may be used as the argument to
+       *  insert_after(), erase_after(), etc.
+       *
+       *  Note that even for an empty %slist, before_begin() is not the
+       *  same iterator as end().  It is always necessary to increment
+       *  before_begin() at least once to obtain end().
+       */
       iterator
       before_begin()
       { return iterator((_Node*) &this->_M_head); }
 
+      /**
+       *  (Experimental, new). Returns a read-only non-dereferencable
+       *  iterator that, when incremented, yields begin(). 
+       *
+       *  Note that even for an empty %slist, before_begin() is not the
+       *  same iterator as end().  It is always necessary to increment
+       *  before_begin() at least once to obtain end().
+       */
       const_iterator
       before_begin() const
       { return const_iterator((_Node*) &this->_M_head); }
 
+      /**
+       *  Returns the number of elements in the %slist.
+       *
+       *  Note that this operation is slow for %slists: it takes linear
+       *  time. In particular, empty() should be used to check
+       *  whether an %slist is empty instead of slist::size() == 0.
+       */
       size_type
       size() const
       { return __slist_size(this->_M_head._M_next); }
 
+      /**  Returns the size() of the largest possible %slist.  */
       size_type
       max_size() const
       { return size_type(-1); }
 
+      /**
+       *  Returns true if the %slist is empty.  (Thus begin() would equal
+       *  end().) Constant time.
+       */
       bool
       empty() const
       { return this->_M_head._M_next == 0; }
 
+      /**
+       *  @brief  Swaps data with another %slist.
+       *  @param  x  An %slist of the same element and allocator types.
+       *
+       *  This exchanges the elements between two lists in constant
+       *  time.  Note that the global std::swap() function is
+       *  specialized such that std::swap(l1,l2) will feed to this
+       *  function.
+       */
       void
       swap(slist& __x)
       { std::swap(this->_M_head._M_next, __x._M_head._M_next); }
 
     public:
 
+      /**
+       *  Returns a read/write reference to the data at the first
+       *  element of the %slist.
+       */
       reference
       front()
       { return ((_Node*) this->_M_head._M_next)->_M_data; }
 
+      /**
+       *  Returns a read-only (constant) reference to the data at the first
+       *  element of the %slist.
+       */
       const_reference
       front() const
       { return ((_Node*) this->_M_head._M_next)->_M_data; }
 
+      /**
+       *  @brief  Add data to the front of the %slist.
+       *  @param  x  Data to be added.
+       *
+       *  This is a typical stack operation.  The function creates an
+       *  element at the front of the %slist and assigns the given data
+       *  to it.  Due to the nature of a %slist this operation can be
+       *  done in constant time, and does not invalidate iterators and
+       *  references.
+       */
       void
       push_front(const value_type& __x)
       { __slist_make_link(&this->_M_head, _M_create_node(__x)); }
 
+      /**
+       *  @brief  Add a default initialized element to the front of
+       *  the %slist.
+       *
+       *  This is a typical stack operation.  The function creates an
+       *  element at the front of the %slist.  Due to the nature of a
+       *  %slist this operation can be done in constant time, and does
+       *  not invalidate iterators and references.
+       */
       void
       push_front()
       { __slist_make_link(&this->_M_head, _M_create_node()); }
 
+      /**
+       *  @brief  Removes first element.
+       *
+       *  This is a typical stack operation.  It shrinks the %slist by
+       *  one.  Due to the nature of a %slist this operation can be done
+       *  in constant time, and only invalidates iterators/references to
+       *  the element being removed.
+       *
+       *  Note that no data is returned, and if the first element's data
+       *  is needed, it should be retrieved before pop_front() is
+       *  called.
+       */
       void
       pop_front()
       {
@@ -493,11 +667,22 @@
 	this->_M_put_node(__node);
       }
 
+      /**
+       *  Returns an iterator pointing to the predecessor of @a pos.
+       *
+       *  This operation is slow for an %slist: It's linear time.
+       */
       iterator
       previous(const_iterator __pos)
       { return iterator((_Node*) __slist_previous(&this->_M_head,
 						  __pos._M_node)); }
 
+      /**
+       *  Returns a read-only iterator pointing to the predecessor of @a
+       *  pos.
+       *
+       *  This operation is slow for an %slist: It's linear time.
+       */
       const_iterator
       previous(const_iterator __pos) const
       { return const_iterator((_Node*) __slist_previous(&this->_M_head,
@@ -550,44 +735,158 @@
 	}
 
     public:
+      /**
+       *  @brief  Inserts given value into %slist after specified
+       *  iterator.
+       *  @param  pos  An iterator into the %slist.
+       *  @param  x  Data to be inserted.
+       *
+       *  This function will insert a copy of the given value after
+       *  the specified location.  Due to the nature of an %slist this
+       *  operation can be done in constant time, and does not
+       *  invalidate iterators and references.
+       */
       iterator
       insert_after(iterator __pos, const value_type& __x)
       { return iterator(_M_insert_after(__pos._M_node, __x)); }
 
+      /**
+       *  @brief  Inserts a default-constructed value into the %slist
+       *  after the specified iterator.
+       *  @param  pos  An iterator into the %slist.
+       *
+       *  This function will insert a default-constructed value after
+       *  the specified location.  Due to the nature of an %slist this
+       *  operation can be done in constant time, and does not
+       *  invalidate iterators and references.
+       */
       iterator
       insert_after(iterator __pos)
       { return insert_after(__pos, value_type()); }
 
+      /**
+       *  @brief  Inserts a number of copies of given data into the %slist.
+       *  after the specified iterator.
+       *  @param  pos  An iterator into the %slist.
+       *  @param  n  Number of elements to be inserted.
+       *  @param  x  Data to be inserted.
+       *
+       *  This function will insert a specified number of copies of the
+       *  given data before the location specified by @a pos.
+       *
+       *  Due to the nature of an %slist this operation can be done in
+       *  constant time, and does not invalidate iterators and
+       *  references.
+       */
       void
       insert_after(iterator __pos, size_type __n, const value_type& __x)
       { _M_insert_after_fill(__pos._M_node, __n, __x); }
 
-      // We don't need any dispatching tricks here, because
-      // _M_insert_after_range already does them.
+      /**
+       *  @brief  Inserts a range into the %slist after iterator pos.
+       *  @param  pos  An iterator into the %slist.
+       *  @param  first  An input iterator.
+       *  @param  last   An input iterator.
+       *
+       *  This function will insert copies of the data in the range [@a
+       *  first,@a last) into the %slist after the location specified by
+       *  @a pos.
+       *
+       *  This operator does not invalidate iterators and references.
+       *
+       *  Complexity: Linear in distance(@a first, @a last).
+       *
+       *  @if maint
+       *  We don't need any dispatching tricks here, because
+       *  _M_insert_after_range already does them.
+       *  @endif
+       */
       template <class _InIterator>
         void
         insert_after(iterator __pos, _InIterator __first, _InIterator __last)
         { _M_insert_after_range(__pos._M_node, __first, __last); }
 
+      /**
+       *  @brief  Inserts given value into %slist before specified iterator.
+       *  @param  pos  An iterator into the %slist.
+       *  @param  x  Data to be inserted.
+       *  @return  An iterator that points to the inserted data.
+       *
+       *  This function inserts a copy of the given value before
+       *  the specified location.
+       *
+       *  This operation does not invalidate iterators and references.
+       *
+       *  Note that insert() is slow for an %slist: It requires a linear
+       *  search through the list. Use insert_after() instead wherever
+       *  possible.
+       */
       iterator
       insert(iterator __pos, const value_type& __x)
       { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
 							 __pos._M_node),
 					__x)); }
 
+      /**
+       *  @brief  Inserts a default constructed value into %slist before
+       *          the specified iterator.
+       *  @param  pos  An iterator into the %slist.
+       *  @return  An iterator that points to the inserted data.
+       *
+       *  This function will insert a default-constructed value before
+       *  the specified location.
+       *
+       *  This operation does not invalidate iterators and references.
+       *
+       *  Note that this operation is slow for an %slist: It requires a
+       *  linear search through the list. Use insert_after() instead
+       *  wherever possible.
+       *
+       */
       iterator
       insert(iterator __pos)
       { return iterator(_M_insert_after(__slist_previous(&this->_M_head,
 							 __pos._M_node),
 					value_type())); }
 
+      /**
+       *  @brief  Inserts a number of copies of given data into the %list.
+       *  @param  pos  An iterator into the %slist.
+       *  @param  n  Number of elements to be inserted.
+       *  @param  x  Data to be inserted.
+       *
+       *  This function will insert a specified number of copies of the
+       *  given data before the location specified by @a position.
+       *
+       *  This operation does not invalidate iterators and references.
+       *
+       *  Note that this insert() is slow for an %slist: It requires a
+       *  linear search through the list. Use insert_after() instead
+       *  wherever possible.
+       */
       void
       insert(iterator __pos, size_type __n, const value_type& __x)
       { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
 			     __n, __x); }
 
-      // We don't need any dispatching tricks here, because
-      // _M_insert_after_range already does them.
+      /**
+       *  @brief  Inserts a range into the %slist.
+       *  @param  pos  An iterator into the %slist.
+       *  @param  first  An input iterator.
+       *  @param  last   An input iterator.
+       *
+       *  This function inserts copies of the data in the range [@a
+       *  first,@a last) into the %slist before the location specified by
+       *  @a pos.
+       *
+       *  Complexity: Linear in distance(begin(), @a pos) and
+       *  distance(@a first, @a last).
+       *
+       *  @if maint
+       *  We don't need any dispatching tricks here, because
+       *  _M_insert_after_range already does them.
+       *  @endif
+       */
       template <class _InIterator>
         void
         insert(iterator __pos, _InIterator __first, _InIterator __last)
@@ -595,40 +894,132 @@
 				__first, __last); }
 
     public:
+      /**
+       *  @brief Erase the element following the given iterator
+       *
+       *  Complexity: Constant time.
+       */
       iterator
       erase_after(iterator __pos)
       { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); }
 
+      /**
+       *  @brief Erase elements in a range
+       *  @param before_first  An iterator pointing to the node before
+       *                       the first element to be erased.
+       *  @param last          An iterator pointing to the first element
+       *                       after the range to be removed.
+       *
+       *  Remove elements in the range (@a before_first, @a last).
+       *
+       *  Complexity: Linear in distance(@a before_first, @a last).
+       */
       iterator
       erase_after(iterator __before_first, iterator __last)
       { return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
 						      __last._M_node)); }
 
+      /**
+       *  @brief  Remove element at given position.
+       *  @param  pos  Iterator pointing to element to be erased.
+       *  @return  An iterator pointing to the next element (or end()).
+       *
+       *  This function will erase the element at the given position and thus
+       *  shorten the %slist by one.
+       *  
+       *  It only invalidates iterators/references to the element being
+       *  removed.  The user is also cautioned 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.
+       *
+       *  On an %slist, this operation is slow: It requires linear time.
+       */
       iterator
       erase(iterator __pos)
       { return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head,
 							      __pos._M_node)); }
 
+      /**
+       *  @brief  Remove a range of elements.
+       *  @param  first  Iterator pointing to the first element to be erased.
+       *  @param  last  Iterator pointing to one past the last element to be
+       *                erased.
+       *  @return  An iterator pointing to the element pointed to by @a last
+       *           prior to erasing (or end()).
+       *
+       *  This function erases the elements in the range [@a first, @a
+       *  last) and shortens the %slist accordingly.
+       *
+       *  It only invalidates iterators/references to the element being
+       *  removed.  The user is also cautioned 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.
+       *
+       *  For an %slist, this operation is linear time.
+       */
       iterator
       erase(iterator __first, iterator __last)
       { return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head,
 							      __first._M_node),
 					     __last._M_node); }
 
+      /**
+       *  @brief  Resizes the %slist to the specified number of elements.
+       *  @param  new_size  Number of elements the %slist should contain.
+       *  @param  x         Data with which new elements should be populated.
+       *
+       *  This function will %resize the %slist to the specified number
+       *  of elements.  If the number is smaller than the %slist's
+       *  current size the %slist is truncated, otherwise the %slist is
+       *  extended and new elements are populated with given data.
+       */
       void
       resize(size_type new_size, const _Tp& __x);
 
+      /**
+       *  @brief  Resizes the %slist to the specified number of elements.
+       *  @param  new_size  Number of elements the %slist should contain.
+       *
+       *  This function will resize the %slist to the specified number of
+       *  elements.  If the number is smaller than the %slist's current
+       *  size the %slist is truncated, otherwise the %slist is extended
+       *  and new elements are default-constructed.
+       */
       void
       resize(size_type new_size)
       { resize(new_size, _Tp()); }
 
+      /**
+       *  @brief  Erases all the elements.
+       *
+       *  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()
       { this->_M_erase_after(&this->_M_head, 0); }
 
     public:
-      // Moves the range [__before_first + 1, __before_last + 1) to *this,
-      //  inserting it immediately after __pos.  This is constant time.
+
+      /**
+       *  @brief  Insert a range after @a pos.
+       *  @param  pos           Where to insert the range
+       *  @param  before_first  Iterator pointing to the position before
+       *                        the beginning of the range to be moved.
+       *  @param  before_last   Iterator pointing to the position before
+       *                        the end of the range to be moved.
+       *
+       *  Moves the range [@a before_first + 1, @a before_last + 1) to
+       *  *this, inserting it immediately after @a pos.  This is constant
+       *  time.
+       *
+       *  The iterators @a before_first and @a before_last are required
+       *  to be iterators from an %slist.
+       */
       void
       splice_after(iterator __pos,
 		   iterator __before_first, iterator __before_last)
@@ -638,21 +1029,47 @@
 			       __before_last._M_node);
       }
 
-      // Moves the element that follows __prev to *this, inserting it
-      // immediately after __pos.  This is constant time.
+      /**
+       *  @brief  Move an element in an %slist.
+       *  @param  prev  Iterator pointing to the predecessor of the
+       *                element to move.
+       *  @param  pos   Where to insert the element.
+       *
+       *  Moves the element that follows @a prev to *this, inserting it
+       *  immediately after @a pos.  This is constant time.
+       *
+       *  @a prev must be an iterator from an %slist.
+       */
       void
       splice_after(iterator __pos, iterator __prev)
       { __slist_splice_after(__pos._M_node,
 			     __prev._M_node, __prev._M_node->_M_next); }
 
-      // Removes all of the elements from the list __x to *this, inserting
-      // them immediately after __pos.  __x must not be *this.  Complexity:
-      // linear in __x.size().
+      /**
+       *  @brief  Move another %slist into this %slist.
+       *  @param  pos  Where to insert the values.
+       *  @param  x    %slist containing the elements to be moved.
+       *
+       *  Moves all of the elements from the list x to *this, inserting
+       *  them immediately after @a pos.  @a x must not be *this. @a x
+       *  is empty after the move.
+       *
+       *  Complexity: linear in @a x.size().
+       */
       void
       splice_after(iterator __pos, slist& __x)
       { __slist_splice_after(__pos._M_node, &__x._M_head); }
 
-      // Linear in distance(begin(), __pos), and linear in __x.size().
+      /**
+       *  @brief  Move another %slist into this %slist
+       *  @param  pos  Position before which the %slist should be inserted.
+       *  @param  x    The %slist to insert.
+       *
+       *  This moves the %slist @a x to the point before @a pos. The
+       *  list @a x is empty after this operation.
+       *
+       *  Linear in distance(begin(), @a pos) and @a x.size().
+       */
       void
       splice(iterator __pos, slist& __x)
       {
@@ -661,15 +1078,34 @@
 			       &__x._M_head,
 			       __slist_previous(&__x._M_head, 0)); }
 
-      // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
+      /**
+       *  @brief  Insert element from another %slist.
+       *  @param  pos  Iterator referencing the element to insert before.
+       *  @param  x  Source %slist.
+       *  @param  i  Iterator referencing the element to move.
+       *
+       *  Removes the element in @a x referenced by @a i and inserts it
+       *  into the current list before @a pos.
+       *
+       *  Complexity: Linear in distance(begin(), @a pos), and in
+       *  distance(@a x.begin(), @a i).
+       */
       void
       splice(iterator __pos, slist& __x, iterator __i)
       { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
 			     __slist_previous(&__x._M_head, __i._M_node),
 			     __i._M_node); }
 
-      // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
-      // and in distance(__first, __last).
+      /**
+       *  @brief  Insert range from another %slist.
+       *  @param  pos    Iterator referencing the element to insert before.
+       *  @param  x      Source %slist.
+       *  @param  first  Iterator referencing the start of range in @a x.
+       *  @param  last   Iterator referencing the end of range in @a x.
+       *
+       *  Complexity: Linear in distance(begin(), @a pos), in
+       *  distance(@a x.begin(), @a first), and in distance(@a first, @a last).
+       */
       void
       splice(iterator __pos, slist& __x, iterator __first, iterator __last)
       {
@@ -681,6 +1117,13 @@
       }
 
     public:
+      /**
+       *  @brief Reverse the order of the elements stored in the %slist.
+       *
+       *  Reverse the order of elements in the list. This operation
+       *  is linear time and in-place (i.e. requires no additional
+       *  memory).
+       */
       void
       reverse()
       {
@@ -688,30 +1131,112 @@
 	  this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
       }
 
+      /**
+       *  @brief  Remove all elements equal to a given value.
+       *  @param  val  The value to remove.
+       *
+       *  Removes every element in the list equal to @a val.
+       *  Remaining elements stay in list order.  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
       remove(const _Tp& __val);
 
+      /**
+       *  @brief  Remove consecutive duplicate elements.
+       *
+       *  For each consecutive set of elements with the same value,
+       *  remove all but the first one.  Remaining elements stay in
+       *  list order.  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.
+       *
+       *  This operation is linear time.
+       */
       void
       unique();
       
+      /**
+       *  @brief  Merge sorted lists.
+       *  @param  x  Sorted list to merge.
+       *
+       *  Assumes that both @a x and this list are sorted according to
+       *  operator<().  Merges elements of @a x into this list in
+       *  sorted order, leaving @a x empty when complete.  Elements in
+       *  this list precede elements in @a x that are equal.
+       *
+       *  This operation is linear in the size of the two lists.
+       */
       void
       merge(slist& __x);
       
+      /**
+       *  @brief  Sort the elements.
+       *
+       *  Sorts the elements of this list in NlogN time.  Equivalent
+       *  elements remain in list order.
+       *
+       */
       void
       sort();
 
+      /**
+       *  @brief  Remove all elements satisfying a predicate.
+       *  @param  pred  Unary predicate function or object.
+       *
+       *  Removes every element in the list for which the predicate
+       *  returns true.  Remaining elements stay in list order.  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.
+       */
       template <class _Predicate>
         void
         remove_if(_Predicate __pred);
 
+      /**
+       *  @brief  Remove consecutive elements satisfying a predicate.
+       *  @param  pred  Binary predicate function or object.
+       *
+       *  For each consecutive set of elements [first,last) that
+       *  satisfy predicate(first,i) where i is an iterator in
+       *  [first,last), remove all but the first one.  Remaining
+       *  elements stay in list order.  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.
+       */
       template <class _BinaryPredicate>
         void
         unique(_BinaryPredicate __pred);
 
+      /**
+       *  @brief  Merge sorted lists according to comparison function.
+       *  @param  x  Sorted %slist to merge.
+       *  @param  StrictWeakOrdering Comparison function definining
+       *                             sort order.
+       *
+       *  Assumes that both @a x and this %slist are sorted according to
+       *  StrictWeakOrdering.  Merges elements of @a x into this list
+       *  in sorted order, leaving @a x empty when complete.  Elements
+       *  in this list precede elements in @a x that are equivalent
+       *  according to StrictWeakOrdering().
+       */
       template <class _StrictWeakOrdering>
         void
         merge(slist&, _StrictWeakOrdering);
 
+      /**
+       *  @brief  Sort the elements according to comparison function.
+       *
+       *  Sorts the elements of this %slist in NlogN time.  Equivalent
+       *  elements remain in list order.
+       */
       template <class _StrictWeakOrdering>
         void
         sort(_StrictWeakOrdering __comp);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]