focal (3) binarysearch.3bobcat.gz

NAME

       FBB::binary_search - Extensions to the STL binary_search function template

SYNOPSIS

       #include <bobcat/binarysearch>

DESCRIPTION

       The  FBB::binary_search  function  templates  extend the STL binary_search function template returning an
       iterator to the element found, instead of a bool value informing the caller whether or not  the  searched
       for element is present in a provided iterator range.

       The  bool  value returned by the STL binary_search function template is often not the kind of information
       the caller of the function is interested in. Rather, the caller will often want to use  binary_search  in
       the  way find_if is used: returning an iterator to the found element or returning the end-iterator if the
       element was not found. Whereas find_if does not require the elements in the iterator range to be  sorted,
       and  thus  will  use  a  linear  search  binary_search  may  use the sorted nature of the elements to its
       advantage, using a binary search algorithm requiring 2 log  N  iterations  to  locate  the  searched  for
       element  rather  than  (on  average)  N/2  iterations.  The FBB::binary_search algorithm uses this binary
       searching process while at the same time allowing its use like find_if.

       Since the FBB::binary_search function templates use the same  number  and  types  of  parameters  as  the
       stl::binary_search  function  templates  the  explicit use of the FBB namespace will often be required in
       situations where both function templates are made available to the compiler.

NAMESPACE

       FBB
       All constructors, members, operators and manipulators, mentioned in this man-page,  are  defined  in  the
       namespace FBB.

INHERITS FROM

       -

OVERLOADED FUNCTIONS

       In the following description several template type parameters are used. They are:

       o      Iterator represents an iterator type;

       o      Type represents a value of the type to which Iterator points.

       o      Comparator  represents  a  comparator  function  or  class  type object which was used to sort the
              elements to which the Iterator range refer;

       o      Iterator binary_search(Iterator begin, Iterator end, Type const &value):
              Using a binary search algorithm value is searched for in the range of elements referred to by  the
              provided  iterator  range.  If  the value is found an iterator pointing to this value is returned,
              otherwise  end  is  returned.  The  elements  in  the  range  must  have  been   sorted   by   the
              Type::operator<() function.

       o      Iterator binary_search(Iterator begin, Iterator end, Type const &value, Comparator comparator):
              Using  a binary search algorithm value is searched for in the range of elements referred to by the
              provided iterator range. If the value is found an iterator pointing to  this  value  is  returned,
              otherwise   end   is   returned.   The   elements  and  the  provided  value  are  compared  using
              comparator(*iterator, value) calls, where *iterator refers to an object in the  provided  iterator
              range.  The  elements  in  the  range must have been sorted by the Comparator function or function
              object.

EXAMPLES

       #include <iostream>
       #include <string>
       #include "../binarysearch"

       using namespace std;
       using namespace FBB;

       string words[] =
       {
           "eight",                // alphabetically sorted number-names
           "five",
           "four",
           "nine",
           "one",
           "seven",
           "six",
           "ten",
           "three",
           "two"
       };

       class Comparator
       {
           public:
               bool operator()(string const &left, string const &right) const;
       };

       inline bool Comparator::operator()(string const &left,
                                          string const &right) const
       {
           return left < right;
       }

       bool compFun(string const &left, string const &right)
       {
           return left < right;
       }

       int main()
       {
           string *ret = binary_search(words, words + 10, "five");
           if (ret != words + 10)
               cout << "five is at offset " << (ret - words) << endl;

           ret = binary_search(words, words + 10, "grandpa");
           if (ret == words + 10)
               cout << "grandpa is not the name of a number\n";

           ret = binary_search(words, words + 10, "five", Comparator());
           if (ret != words + 10)
               cout << "five is at offset " << (ret - words) << endl;

           ret = binary_search(words, words + 10, "grandpa", compFun);
                                                          // or use: Comparator()
           if (ret == words + 10)
               cout << "grandpa is not the name of a number\n";
       }

FILES

       bobcat/binarysearch - defines the template functions

SEE ALSO

       bobcat(7)

BUGS

       None reported.

DISTRIBUTION FILES

       o      bobcat_5.02.00-x.dsc: detached signature;

       o      bobcat_5.02.00-x.tar.gz: source archive;

       o      bobcat_5.02.00-x_i386.changes: change log;

       o      libbobcat1_5.02.00-x_*.deb: debian package holding the libraries;

       o      libbobcat1-dev_5.02.00-x_*.deb: debian package holding the libraries, headers and manual pages;

       o      http://sourceforge.net/projects/bobcat: public archive location;

BOBCAT

       Bobcat is an acronym of `Brokken’s Own Base Classes And Templates’.

COPYRIGHT

       This is free software, distributed under the terms of the GNU General Public License (GPL).

AUTHOR

       Frank B. Brokken (f.b.brokken@rug.nl).