- binary_search accoring to its name - 1 Update
| Bonita Montero <Bonita.Montero@gmail.com>: Nov 27 03:38PM +0100 This is a somewhat more efficient binary_search, but it requires that all key in the array are unique. It's more efficient because it doesn't need two predicate compares to test for equality since it uses a predicate which returns a stong_ordering-object. If you're debugging it tests whether the object left and right from the result are less or greater to ensure uniqueness of the key-value. template<typename RandomIt, typename T, typename Pred> inline RandomIt xbinary_search( RandomIt begin, RandomIt end, T const &key, Pred pred ) requires std::random_access_iterator<RandomIt> && requires( Pred pred, typename std::iterator_traits<RandomIt>::value_type &elem, T const &key ) { { pred( elem, key ) } -> std::convertible_to<std::strong_ordering>; } { using namespace std; size_t lower = 0, upper = end - begin, mid; strong_ordering so; while( lower != upper ) { mid = (lower + upper) / 2; so = pred( begin[mid], key ); if( so == 0 ) { assert(!mid || pred( begin[mid - 1], key ) < 0); assert(begin + mid + 1 == end || pred( begin[mid + 1], key ) > 0); return begin + mid; } if( so > 0 ) upper = mid; else lower = mid + 1; } return end; } Another advantage is, that the supplied key can have a differnt type than the elements in the array; so you can f.e. check for an member of an element. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment