Re: Customizing compare in bsearch()
On 24 Mrz., 12:44, Richard Smith <richardpaulsmith.0...@gmail.com>
wrote:
I have an array of addresses that contain integers ( these integers
are sorted in ascending order). They have duplicate values. Ex: 1,
2, 2, 3, 3, 3, 3, 4, 4......
I am trying to get hold of all the values that are greater than a
certain value(key). Currently trying to implement it using binary
search algo -
void *bsearch(
const void *key,
const void *base,
size_t num,
size_t width,
int ( __cdecl *compare ) ( const void *, const void *)
);
I am not able to achieve this completely, but for some of them.
Would there be any other way to get hold of all the values of the
array, with out changing the algorithm I am using?
It is unclear to me, which kind of advice you are looking
for, if one constraint is not to change the algorithm ;-)
So, the following might be a suggestion that breaks
your constraints: I recommend to use from <algorithm>
the function template equal_range with the signatures
template<class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The first one uses as ordering criterion operator< of
the corresponding type, the second one uses
a binary predicate, i.e. comp is similar to your
compare argument above, but you can use a
type-safe variant.
E.g. given
int data[] = { 1, 2, 2, 3, 3, 3, 3, 4, 4,...... };
const int thresh = ...; // This is you special value
you can use:
int* end = data + sizeof(data)/sizeof(data[0]);
int* p = std::upper_bound(data, end, thresh);
The range described by [p, end) is the range of all
values larger than thresh. You should use the
overload with a predicate comp, if your sorting
does not follow the same order as <.
HTH & Greetings from Bremen,
Daniel Kr?gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]