FBB::binary_search(3bobcat) | Binary search function | FBB::binary_search(3bobcat) |
FBB::binary_search - Extensions to the STL binary_search function template
#include <bobcat/binarysearch>
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.
FBB
All constructors, members, operators and manipulators, mentioned in this
man-page, are defined in the namespace FBB.
-
In the following description several template type parameters are used. They are:
#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"; }
bobcat/binarysearch - defines the template functions
None reported.
Bobcat is an acronym of `Brokken’s Own Base Classes And Templates’.
This is free software, distributed under the terms of the GNU General Public License (GPL).
Frank B. Brokken (f.b.brokken@rug.nl).
2005-2018 | libbobcat-dev_4.08.06-x.tar.gz |