1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
includefile(include/header)
COMMENT(manpage, section, releasedate, archive, short name)
manpage(FBB::binary_search)(3bobcat)(_CurYrs_)
(libbobcat-dev__CurVers_)
(Binary search function)
manpagename(FBB::binary_search)(Extensions to the STL binary_search function
template)
manpagesynopsis()
bf(#include <bobcat/binarysearch>)nl()
manpagedescription()
The bf(FBB::binary_search) function templates extend the STL tt(binary_search)
function templates by returning an iterator to the found element, instead of a
bf(bool) value informing the caller whether or not the searched for element is
present in a provided iterator range.
The bf(bool) value returned by the STL tt(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 tt(binary_search) in the way
tt(find_if) is used: returning an iterator to an element or returning
the end-iterator if the element was not found.
Whereas tt(find_if) does not require the elements in the iterator range to be
sorted, and therefore uses a linear search, tt(binary_search) benefits from
the sorted nature of the elements using a binary search algorithm requiring
tt(2 log N) iterations to locate the searched for element rather than (on
average) tt(N/2) iterations. The tt(FBB::binary_search) algorithm uses this
binary searching process while at the same time allowing it to be used like
tt(find_if).
Since the tt(FBB::binary_search) function templates use the same number and
types of parameters as the tt(stl::binary_search) function templates and
because they are implemented using the tt(stl::lower_bound) algorithms the
tt(FBB) namespace must explicitly be specified when calling tt(binary_search).
includefile(include/namespace)
manpagesection(INHERITS FROM)
-
manpagesection(OVERLOADED FUNCTIONS)
In the following description several template type parameters are
used. They are:
itemization(
it() bf(Iterator) represents an iterator type;
it() bf(Type) represents a value of the type to which tt(Iterator)
points.
it() bf(Comparator) represents a comparator function or class type object
which was used to sort the elements to which the tt(Iterator) range refer;
)
itemization(
itb(Iterator binary_search(Iterator begin, Iterator end, Type const
&value))
Using a binary search algorithm tt(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 tt(end) is
returned. The elements in the range must have been sorted by the
tt(Type's operator<) function.
itb(Iterator binary_search(Iterator begin, Iterator end, Type const
&value, Comparator comparator))
Using a binary search algorithm tt(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 tt(end) is
returned. The elements and the provided value are compared using
tt(comparator(*iterator, value)) calls, where tt(*iterator) refers to an
object in the provided iterator range. The elements in the range must have
been sorted by the tt(Comparator) function or function object.
The tt(comparator) function is called with two arguments. The first
argument refers to an element in the tt(begin..end) range, the second argument
refers to tt(value).
Usually the types of these arguments are identical, but they may
differ. Assuming that tt(Iterator) refers to elements of a type tt(Data), then
comparison operators tt(bool operator<(Data const &lhs, Type const &rhs)) and
tt(bool operator<(Type const &rhs, Data const &lhs)) must both be available.
)
manpagesection(EXAMPLES)
verbinclude(../../binarysearch/driver/driver.cc)
and an example showing the use of different types:
verbinclude(../../binarysearch/driver/driver2.cc)
manpagefiles()
em(bobcat/binarysearch) - defines the template functions
manpageseealso()
bf(bobcat)(7)
manpagebugs()
None reported.
includefile(include/trailer)
|
