Customizing compare in bsearch()
in [C++]
|
Prev: Using std container to hold boost::shared_ptr with template parameter
Next: const is an overrated concept that is a source of extra typing and maintenance
From: Richard Smith on 23 Mar 2010 20:44 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? Thanks, Richard Smith -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Daniel Krügler on 24 Mar 2010 04:09 On 24 Mrz., 12:44, Richard Smith <richardpaulsmith.0...(a)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! ]
From: red floyd on 24 Mar 2010 04:25
On Mar 24, 4:44 am, Richard Smith <richardpaulsmith.0...(a)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? look at std::lower_bound -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |