diff options
| author | Phil Edwards <pme@gcc.gnu.org> | 2002-04-18 02:55:50 +0000 |
|---|---|---|
| committer | Phil Edwards <pme@gcc.gnu.org> | 2002-04-18 02:55:50 +0000 |
| commit | bf551f96b1722b7310c29f3a00feecea8454c962 (patch) | |
| tree | f86fda1c73b68c5da6c930d161c1bd88fb7020d3 /libstdc++-v3/docs/doxygen | |
| parent | d4c6e01f81bd51ed7dbac060086f9a97ba19eb50 (diff) | |
| download | gcc-bf551f96b1722b7310c29f3a00feecea8454c962.zip gcc-bf551f96b1722b7310c29f3a00feecea8454c962.tar.gz gcc-bf551f96b1722b7310c29f3a00feecea8454c962.tar.bz2 | |
doxygroups.cc: New group on binary searching.
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.
From-SVN: r52453
Diffstat (limited to 'libstdc++-v3/docs/doxygen')
| -rw-r--r-- | libstdc++-v3/docs/doxygen/doxygroups.cc | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/libstdc++-v3/docs/doxygen/doxygroups.cc b/libstdc++-v3/docs/doxygen/doxygroups.cc index da71879..ccf7204 100644 --- a/libstdc++-v3/docs/doxygen/doxygroups.cc +++ b/libstdc++-v3/docs/doxygen/doxygroups.cc @@ -179,6 +179,36 @@ char* __cxa_demangle (const char* mangled_name, char* output_buffer, } // 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: |