Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
FBB::binary_search(3bobcat) Binary search function FBB::binary_search(3bobcat)

NAME
       FBB::binary_search  - Extensions	to the STL binary_search function tem-
       plate

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	inter-
       ested  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 ele-
       ment rather than	(on average) N/2  iterations.  The  FBB::binary_search
       algorithm uses this binary searching process while at the same time al-
       lowing 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  re-
	      turned,  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 re-
	      turned, 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";

	   return 0;
       }

FILES
       bobcat/binarysearch - defines the template functions

SEE ALSO
       bobcat(7)

BUGS
       None reported.

DISTRIBUTION FILES
       o      bobcat_3.25.01-x.dsc: detached signature;

       o      bobcat_3.25.01-x.tar.gz: source archive;

       o      bobcat_3.25.01-x_i386.changes: change log;

       o      libbobcat1_3.25.01-x_*.deb:  debian  package  holding  the   li-
	      braries;

       o      libbobcat1-dev_3.25.01-x_*.deb:  debian  package holding the li-
	      braries, 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).

libbobcat-dev_3.25.01-x.tar.gz	   2005-2015	   FBB::binary_search(3bobcat)

NAME | SYNOPSIS | DESCRIPTION | NAMESPACE | INHERITS FROM | OVERLOADED FUNCTIONS | EXAMPLES | FILES | SEE ALSO | BUGS | DISTRIBUTION FILES | BOBCAT | COPYRIGHT | AUTHOR

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=binarysearch&sektion=3bobcat&manpath=FreeBSD+12.1-RELEASE+and+Ports>

home | help