| 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 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.
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;
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’;
}
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-2020 | libbobcat-dev_5.07.00 |