[libstdc++] More doxygen markup
Phil Edwards
phil@jaj.com
Wed Apr 17 19:57:00 GMT 2002
Doxygenates [25.3.3] and [25.3.4] and corrects a small markup bug in the
comments for std::deque. Documentation change only, applied to trunk
and branch.
2002-04-17 Phil Edwards <pme@gcc.gnu.org>
* docs/doxygen/doxygroups.cc: New group on binary searching.
* include/bits/stl_algo.h: Document binary searches and merges.
* include/bits/stl_deque.h: The 'map' member is not the 'map' class.
Index: docs/doxygen/doxygroups.cc
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/docs/doxygen/doxygroups.cc,v
retrieving revision 1.9
diff -u -3 -p -r1.9 doxygroups.cc
--- docs/doxygen/doxygroups.cc 2 Apr 2002 02:07:19 -0000 1.9
+++ docs/doxygen/doxygroups.cc 18 Apr 2002 02:54:15 -0000
@@ -179,6 +179,36 @@ char* __cxa_demangle (const char* mangle
} // namespace abi
// // // // // // // // // // // // // // // // // // // // // // // //
+/** @addtogroup binarysearch Binary search algorithms
+These algorithms are variations of a classic binary search. They all assume
+that the sequence being searched is already sorted.
+
+The number of comparisons will be logarithmic (and as few as possible).
+The number of steps through the sequence will be logarithmic for
+random-access iterators (e.g., pointers), and linear otherwise.
+
+The LWG has passed Defect Report 270, which notes: <em>The proposed
+resolution reinterprets binary search. Instead of thinking about searching
+for a value in a sorted range, we view that as an important special
+case of a more general algorithm: searching for the partition point in a
+partitioned range. We also add a guarantee that the old wording did not:
+we ensure that the upper bound is no earlier than the lower bound, that
+the pair returned by equal_range is a valid range, and that the first part
+of that pair is the lower bound.</em>
+
+The actual effect of the first sentence is that a comparison functor
+passed by the user doesn't necessarily need to induce a strict weak ordering
+relation. Rather, it partitions the range.
+*/
+
+// // // // // // // // // // // // // // // // // // // // // // // //
+
+// // // // // // // // // // // // // // // // // // // // // // // //
+/* * @addtogroup groupname description of group
+placeholder text
+*/
+
+// // // // // // // // // // // // // // // // // // // // // // // //
// vim:et:noai:
Index: include/bits/stl_algo.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.26
diff -u -3 -p -r1.26 stl_algo.h
--- include/bits/stl_algo.h 5 Apr 2002 17:58:41 -0000 1.26
+++ include/bits/stl_algo.h 18 Apr 2002 02:54:15 -0000
@@ -2756,8 +2756,15 @@ __result, __binary_pred, _IterType());
}
- // Binary search (lower_bound, upper_bound, equal_range, binary_search).
-
+ /**
+ * @brief Finds the first position in which @a val could be inserted
+ * without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return An iterator pointing to the first element "not less than" @a val.
+ * @ingroup binarysearch
+ */
template<typename _ForwardIter, typename _Tp>
_ForwardIter
lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
@@ -2793,6 +2800,19 @@ __result, __binary_pred, _IterType());
return __first;
}
+ /**
+ * @brief Finds the first position in which @a val could be inserted
+ * without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @param comp A functor to use for comparisons.
+ * @return An iterator pointing to the first element "not less than" @a val.
+ * @ingroup binarysearch
+ *
+ * The comparison function should have the same effects on ordering as
+ * the function used for the initial sort.
+ */
template<typename _ForwardIter, typename _Tp, typename _Compare>
_ForwardIter
lower_bound(_ForwardIter __first, _ForwardIter __last,
@@ -2824,6 +2844,15 @@ __result, __binary_pred, _IterType());
return __first;
}
+ /**
+ * @brief Finds the last position in which @a val could be inserted
+ * without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return An iterator pointing to the first element greater than @a val.
+ * @ingroup binarysearch
+ */
template<typename _ForwardIter, typename _Tp>
_ForwardIter
upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
@@ -2856,6 +2885,19 @@ __result, __binary_pred, _IterType());
return __first;
}
+ /**
+ * @brief Finds the last position in which @a val could be inserted
+ * without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @param comp A functor to use for comparisons.
+ * @return An iterator pointing to the first element greater than @a val.
+ * @ingroup binarysearch
+ *
+ * The comparison function should have the same effects on ordering as
+ * the function used for the initial sort.
+ */
template<typename _ForwardIter, typename _Tp, typename _Compare>
_ForwardIter
upper_bound(_ForwardIter __first, _ForwardIter __last,
@@ -2887,6 +2929,22 @@ __result, __binary_pred, _IterType());
return __first;
}
+ /**
+ * @brief Finds the largest subrange in which @a val could be inserted
+ * at any place in it without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return An pair of iterators defining the subrange.
+ * @ingroup binarysearch
+ *
+ * This is equivalent to
+ * @code
+ * std::make_pair(lower_bound(first, last, val),
+ * upper_bound(first, last, val))
+ * @endcode
+ * but does not actually call those functions.
+ */
template<typename _ForwardIter, typename _Tp>
pair<_ForwardIter, _ForwardIter>
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
@@ -2925,6 +2983,23 @@ __result, __binary_pred, _IterType());
return pair<_ForwardIter, _ForwardIter>(__first, __first);
}
+ /**
+ * @brief Finds the largest subrange in which @a val could be inserted
+ * at any place in it without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @param comp A functor to use for comparisons.
+ * @return An pair of iterators defining the subrange.
+ * @ingroup binarysearch
+ *
+ * This is equivalent to
+ * @code
+ * std::make_pair(lower_bound(first, last, val, comp),
+ * upper_bound(first, last, val, comp))
+ * @endcode
+ * but does not actually call those functions.
+ */
template<typename _ForwardIter, typename _Tp, typename _Compare>
pair<_ForwardIter, _ForwardIter>
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
@@ -2963,6 +3038,17 @@ __result, __binary_pred, _IterType());
return pair<_ForwardIter, _ForwardIter>(__first, __first);
}
+ /**
+ * @brief Determines whether an element exists in a range.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return True if @a val (or its equivelent) is in [@a first,@a last ].
+ * @ingroup binarysearch
+ *
+ * Note that this does not actually return an iterator to @a val. For
+ * that, use std::find or a container's specialized find member functions.
+ */
template<typename _ForwardIter, typename _Tp>
bool
binary_search(_ForwardIter __first, _ForwardIter __last,
@@ -2979,6 +3065,21 @@ __result, __binary_pred, _IterType());
return __i != __last && !(__val < *__i);
}
+ /**
+ * @brief Determines whether an element exists in a range.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @param comp A functor to use for comparisons.
+ * @return True if @a val (or its equivelent) is in [@a first,@a last ].
+ * @ingroup binarysearch
+ *
+ * Note that this does not actually return an iterator to @a val. For
+ * that, use std::find or a container's specialized find member functions.
+ *
+ * The comparison function should have the same effects on ordering as
+ * the function used for the initial sort.
+ */
template<typename _ForwardIter, typename _Tp, typename _Compare>
bool
binary_search(_ForwardIter __first, _ForwardIter __last,
@@ -2995,8 +3096,22 @@ __result, __binary_pred, _IterType());
return __i != __last && !__comp(__val, *__i);
}
- // merge, with and without an explicitly supplied comparison function.
-
+ /**
+ * @brief Merges two sorted ranges.
+ * @param first1 An iterator.
+ * @param first2 Another iterator.
+ * @param last1 Another iterator.
+ * @param last2 Another iterator.
+ * @param result An iterator pointing to the end of the merged range.
+ * @return An iterator pointing to the first element "not less than" @a val.
+ *
+ * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
+ * [result, result + (last1-first1) + (last2-first2)). Both input ranges
+ * must be sorted, and the output range must not overlap with either of
+ * the input ranges. The sort is @e stable, that is, for equivalent
+ * elements in the two ranges, elements from the first range will always
+ * come before elements from the second.
+ */
template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
_OutputIter
merge(_InputIter1 __first1, _InputIter1 __last1,
@@ -3028,6 +3143,26 @@ __result, __binary_pred, _IterType());
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
+ /**
+ * @brief Merges two sorted ranges.
+ * @param first1 An iterator.
+ * @param first2 Another iterator.
+ * @param last1 Another iterator.
+ * @param last2 Another iterator.
+ * @param result An iterator pointing to the end of the merged range.
+ * @param comp A functor to use for comparisons.
+ * @return An iterator pointing to the first element "not less than" @a val.
+ *
+ * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
+ * [result, result + (last1-first1) + (last2-first2)). Both input ranges
+ * must be sorted, and the output range must not overlap with either of
+ * the input ranges. The sort is @e stable, that is, for equivalent
+ * elements in the two ranges, elements from the first range will always
+ * come before elements from the second.
+ *
+ * The comparison function should have the same effects on ordering as
+ * the function used for the initial sort.
+ */
template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
typename _Compare>
_OutputIter
@@ -3061,8 +3196,11 @@ __result, __binary_pred, _IterType());
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
- // inplace_merge and its auxiliary functions.
-
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter, typename _Distance>
void
__merge_without_buffer(_BidirectionalIter __first,
@@ -3102,6 +3240,11 @@ __result, __binary_pred, _IterType());
__len1 - __len11, __len2 - __len22);
}
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter, typename _Distance, typename _Compare>
void
__merge_without_buffer(_BidirectionalIter __first,
@@ -3142,6 +3285,11 @@ __result, __binary_pred, _IterType());
__len1 - __len11, __len2 - __len22, __comp);
}
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter1, typename _BidirectionalIter2,
typename _Distance>
_BidirectionalIter1
@@ -3170,6 +3318,11 @@ __result, __binary_pred, _IterType());
}
}
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter1, typename _BidirectionalIter2,
typename _BidirectionalIter3>
_BidirectionalIter3
@@ -3199,6 +3352,11 @@ __result, __binary_pred, _IterType());
}
}
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter1, typename _BidirectionalIter2,
typename _BidirectionalIter3, typename _Compare>
_BidirectionalIter3
@@ -3229,6 +3387,11 @@ __result, __binary_pred, _IterType());
}
}
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter, typename _Distance, typename _Pointer>
void
__merge_adaptive(_BidirectionalIter __first,
@@ -3273,6 +3436,11 @@ __result, __binary_pred, _IterType());
}
}
+ /**
+ * @if maint
+ * This is a helper function for the merge routines.
+ * @endif
+ */
template<typename _BidirectionalIter, typename _Distance, typename _Pointer,
typename _Compare>
void
@@ -3320,6 +3488,23 @@ __result, __binary_pred, _IterType());
}
}
+ /**
+ * @brief Merges two sorted ranges in place.
+ * @param first An iterator.
+ * @param middle Another iterator.
+ * @param last Another iterator.
+ * @return Nothing.
+ *
+ * Merges two sorted and consecutive ranges, [first,middle) and
+ * [middle,last), and puts the result in [first,last). The output will
+ * be sorted. The sort is @e stable, that is, for equivalent
+ * elements in the two ranges, elements from the first range will always
+ * come before elements from the second.
+ *
+ * If enough additional memory is available, this takes (last-first)-1
+ * comparisons. Otherwise an NlogN algorithm is used, where N is
+ * distance(first,last).
+ */
template<typename _BidirectionalIter>
void
inplace_merge(_BidirectionalIter __first,
@@ -3350,6 +3535,27 @@ __result, __binary_pred, _IterType());
__buf.begin(), _DistanceType(__buf.size()));
}
+ /**
+ * @brief Merges two sorted ranges in place.
+ * @param first An iterator.
+ * @param middle Another iterator.
+ * @param last Another iterator.
+ * @param comp A functor to use for comparisons.
+ * @return Nothing.
+ *
+ * Merges two sorted and consecutive ranges, [first,middle) and
+ * [middle,last), and puts the result in [first,last). The output will
+ * be sorted. The sort is @e stable, that is, for equivalent
+ * elements in the two ranges, elements from the first range will always
+ * come before elements from the second.
+ *
+ * If enough additional memory is available, this takes (last-first)-1
+ * comparisons. Otherwise an NlogN algorithm is used, where N is
+ * distance(first,last).
+ *
+ * The comparison function should have the same effects on ordering as
+ * the function used for the initial sort.
+ */
template<typename _BidirectionalIter, typename _Compare>
void
inplace_merge(_BidirectionalIter __first,
Index: include/bits/stl_deque.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_deque.h,v
retrieving revision 1.18
diff -u -3 -p -r1.18 stl_deque.h
--- include/bits/stl_deque.h 27 Mar 2002 21:41:33 -0000 1.18
+++ include/bits/stl_deque.h 18 Apr 2002 02:54:15 -0000
@@ -437,7 +437,8 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* - size_t _M_map_size
* - iterator _M_start, _M_finish
*
- * map_size is at least 8. map is an array of map_size pointers-to-"nodes".
+ * map_size is at least 8. %map is an array of map_size pointers-to-"nodes".
+ * (The name has nothing to do with the std::map class.)
*
* A "node" has no specific type name as such, but it is referred to as
* "node" in this file. It is a simple array-of-Tp. If Tp is very large,
@@ -451,18 +452,18 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* memory pool. There are 20 hours left in the year; perhaps I can fix
* this before 2002.
*
- * Not every pointer in the map array will point to a node. If the initial
- * number of elements in the deque is small, the /middle/ map pointers will
+ * Not every pointer in the %map array will point to a node. If the initial
+ * number of elements in the deque is small, the /middle/ %map pointers will
* be valid, and the ones at the edges will be unused. This same situation
- * will arise as the map grows: available map pointers, if any, will be on
- * the ends. As new nodes are created, only a subset of the map's pointers
+ * will arise as the %map grows: available %map pointers, if any, will be on
+ * the ends. As new nodes are created, only a subset of the %map's pointers
* need to be copied "outward".
*
* Class invariants:
* - For any nonsingular iterator i:
- * - i.node points to a member of the map array. (Yes, you read that
+ * - i.node points to a member of the %map array. (Yes, you read that
* correctly: i.node does not actually point to a node.) The member of
- * the map array is what actually points to the node.
+ * the %map array is what actually points to the node.
* - i.first == *(i.node) (This points to the node (first Tp element).)
* - i.last == i.first + node_size
* - i.cur is a pointer in the range [i.first, i.last). NOTE:
@@ -478,10 +479,10 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* that range are uninitialized storage. Otherwise, [start.cur, start.last)
* and [finish.first, finish.cur) are initialized objects, and [start.first,
* start.cur) and [finish.cur, finish.last) are uninitialized storage.
- * - [map, map + map_size) is a valid, non-empty range.
+ * - [%map, %map + map_size) is a valid, non-empty range.
* - [start.node, finish.node] is a valid range contained within
- * [map, map + map_size).
- * - A pointer in the range [map, map + map_size) points to an allocated node
+ * [%map, %map + map_size).
+ * - A pointer in the range [%map, %map + map_size) points to an allocated node
* if and only if the pointer is in the range [start.node, finish.node].
*
* Here's the magic: nothing in deque is "aware" of the discontiguous storage!
More information about the Gcc-patches
mailing list