Provided by: libbobcat-dev_5.11.01-1_amd64 
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 templates
by returning an iterator to the found element, 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 an 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
therefore uses a linear search, binary_search benefits from the sorted nature of the
elements 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 it to be used
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 and because they are implemented
using the stl::lower_bound algorithms the FBB namespace must explicitly be specified when
calling binary_search.
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’s 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.
The comparator function is called with two arguments. The first argument refers to
an element in the begin..end range, the second argument refers to value.
Usually the types of these arguments are identical, but they may differ. Assuming
that Iterator refers to elements of a type Data, then comparison operators bool
operator<(Data const &lhs, Type const &rhs) and bool operator<(Type const &rhs,
Data const &lhs) must both be available.
EXAMPLES
#include <iostream>
#include <string>
#include "../binarysearch"
using namespace std;
string words[] =
{
"eight", // alphabetically sorted number-names
"five",
"four",
"nine",
"one",
"seven",
"six",
"ten",
"three",
"two"
};
bool compFun(string const &left, string const &right)
{
return left < right;
}
int main()
{
string *ret = FBB::binary_search(words, words + 10, "five");
if (ret != words + 10)
cout << "five is at offset " << (ret - words) << endl;
ret = FBB::binary_search(words, words + 10, "grandpa");
if (ret == words + 10)
cout << "grandpa is not the name of a number\n";
ret = FBB::binary_search(words, words + 10, "five",
[&](string const &element, string const &value)
{
return element < value;
}
);
if (ret != words + 10)
cout << "five is at offset " << (ret - words) << endl;
ret = FBB::binary_search(words, words + 10, "grandpa", compFun);
// or use: Comparator()
if (ret == words + 10)
cout << "grandpa is not the name of a number\n";
}
and an example showing the use of different types:
#include <iostream>
#include <string>
#include "../binarysearch"
using namespace std;
struct Words
{
string str;
int value;
};
bool operator<(Words const &word, string const &str)
{
return word.str < str;
}
bool operator<(string const &str, Words const &word)
{
return str < word.str;
}
Words words[] =
{
{ "eight", 0 }, // alphabetically sorted number-names
{ "five", 0 },
{ "four", 0 },
{ "nine", 0 },
{ "one", 0 },
{ "seven", 0 },
{ "six", 0 },
{ "ten", 0 },
{ "three", 0 },
{ "two", 0 }
};
int main()
{
auto ret = FBB::binary_search(words, words + 10, "five",
[&](Words const &element, string const &value)
{
return element < value;
}
);
cout << (ret != words + 10 ? "found it" : "not present") << ’\n’;
}
FILES
bobcat/binarysearch - defines the template functions
SEE ALSO
bobcat(7)
BUGS
None reported.
BOBCAT PROJECT FILES
o https://fbb-git.gitlab.io/bobcat/: gitlab project page;
o bobcat_5.11.01-x.dsc: detached signature;
o bobcat_5.11.01-x.tar.gz: source archive;
o bobcat_5.11.01-x_i386.changes: change log;
o libbobcat1_5.11.01-x_*.deb: debian package containing the libraries;
o libbobcat1-dev_5.11.01-x_*.deb: debian package containing the libraries, headers
and manual pages;
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).