How to write a lower_bound_if function modification to STL

[Dorwin C. Black]

Do any gurus out there know what the source code for the STL binary
search algorithm "lower_bound" would look like? I want to make a slight
modification called "lower_bound_if" which would take a predicate as the
third argument similar to "find_if" and "copy_if". Is there some reasom
why the STL does not provide such an algorithm already?

template<class For, class Pred>
For lower_bound_if(For first, For last, Pred p);

Thanks in advance for any help.

-DCB

 

[David Fisher]

Do any gurus out there know what the source code for the STL binary
search algorithm "lower_bound" would look like?

Being a template, the source code should be visible in the <algorithm>
header file ...

David F

 

[Jeff Schwab]

Do any gurus out there know what the source code for the STL binary
search algorithm "lower_bound" would look like? I want to make a slight
modification called "lower_bound_if" which would take a predicate as the
third argument similar to "find_if" and "copy_if". Is there some reasom
why the STL does not provide such an algorithm already?

template<class For, class Pred>
For lower_bound_if(For first, For last, Pred p);

Thanks in advance for any help.

-DCB

What would the predicate do? The lower_bound algorithm compares two
elements at a time, so it needs a comparison function, not a
find_if-style unary predicate. Here's the implementation that came with
g++:

/**
* @brief Finds the first position in which @a val could be inserted
* without changing the ordering.
* @param first An iterator.
* @param last Another iterator.
* @param val The search term.
* @return An iterator pointing to the first element "not less than"
* @a val.
* @ingroup binarysearch
*/
template<typename _ForwardIter, typename _Tp>
_ForwardIter
lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
typedef typename
iterator_traits<_ForwardIter>::difference_type _DistanceType;

// concept requirements
// Note that these are slightly stricter than those of the 4-argument
// version, defined next. The difference is in the strictness of the
// comparison operations... so for looser checking, define your own
// comparison function, as was intended.

__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
__glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
__glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
_DistanceType __len = distance(__first, __last);
_DistanceType __half;
_ForwardIter __middle;
while (__len > 0) {
__half = __len >> 1;
__middle = __first;
advance(__middle, __half);
if (*__middle < __val) {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}

 

[Donovan Rebbechi]

What would the predicate do? The lower_bound algorithm compares two
elements at a time, so it needs a comparison function, not a
find_if-style unary predicate. Here's the implementation that came with
g++:

About their conventions for _naming __identifiers: I've always wondered why
they do this. Is it to avoid possible collision with user macro definitions ?

Cheers,

 

[Martijn Lievaart]

About their conventions for _naming __identifiers: I've always wondered why
they do this. Is it to avoid possible collision with user macro definitions ?

Yes, and for the globally visible symbols to avoid collision with user
defined symbols. These identifiers are reserved for implementors, so a
user is not allowed to use them.

HTH,
M4

 

[Dorwin C. Black]

What would the predicate do? The lower_bound algorithm compares two
elements at a time, so it needs a comparison function, not a
find_if-style unary predicate.

You are correct. I will need another argument in my algorithm. What I am
trying to do is find a way to perform a binary search on a collection of
objects that are sorted based on a member variable. For example, say I have a
class called CBaseballPlayer with member variable to represent their age
(m_usAge - unsigned short), and I set up a collection of pointers to CBaseball
player objects sorted by age. Now I want to find the first player in the list
whose age is equal to some value. I could use find_if( ), but if I have a
very large list, that may be slow. So what I want is an algorithm that can do
a binary search like the following:

template<class For, class T, class Op>
For lower_bound_using(For first, For last, const T& value, Op op)

The operator will be a functional object ( say for the above example the
operator takes a pointer to CBaseballPlayer and returns m_usAge )

Here's the implementation that came with
g++:

Thanks, I think this will help me figure out how to do what I want to do.

-DCB