//  VC6.0 2008/5/20 #include "iostream"using namespace std; class SimpleCompareTrait { };class ComplexCompareTrait { }; template<class T> class ComplexCompare{public: typedef T ValueType; typedef ComplexCompareTrait CompareTrait;}; template<class T> class SimpleCompare{public: typedef T ValueType; typedef SimpleCompareTrait CompareTrait;}; template<class T, class Iterator, class Compare>Iterator __LowerBound(Iterator first, Iterator last, T val,       Compare comp, ComplexCompareTrait){ size_t len = 0; size_t half; Iterator middle;  len = last - first; while (len > 0) {  half = len >> 1;  middle = first;  middle += half;  if (comp(*middle, val) < 0)  {   first = middle;   ++first;   len = len - half - 1;  } else   len = half; } return first;} template<class T, class Iterator, class Compare>Iterator __LowerBound(Iterator first, Iterator last, T val,       Compare comp, SimpleCompareTrait){ size_t len = 0; size_t half; Iterator middle;  len = last - first; while (len > 0) {  half = len >> 1;  middle = first;  middle += half;  if (comp(*middle, val))  {   first = middle;   ++first;   len = len - half - 1;  } else   len = half; } return first;} template<class T, class Iterator, class Compare>Iterator LowerBound(Iterator first, Iterator last, T val, Compare comp){ return __LowerBound(first, last, val, comp, Compare::CompareTrait());} template<class T, class Iterator, class Compare>Iterator __BinSearch(Iterator first, Iterator last, T val,      Compare comp, ComplexCompareTrait){ size_t len = 0; size_t half; Iterator middle;  len = last - first; while (len > 0) {  half = len >> 1;  middle = first;  middle += half;  int iComp = comp(*middle, val);  if (iComp < 0)  {   first = middle;   ++first;   len = len - half - 1;  }  else if (iComp > 0)  {   len = half;  } else   return middle; } return last;} template<class T, class Iterator, class Compare>Iterator __BinSearch(Iterator first, Iterator last, T val,      Compare comp, SimpleCompareTrait){ size_t len = 0; size_t half; Iterator middle;  len = last - first; while (len > 0) {  half = len >> 1;  middle = first;  middle += half;  if (comp(*middle, val))  {   first = middle;   ++first;   len = len - half - 1;  }  else if (comp(val, *middle))  {   len = half;  } else   return middle; } return last;} template<class T, class Iterator, class Compare>Iterator BinSearch(Iterator first, Iterator last, T val, Compare comp){ return __BinSearch(first, last, val, comp, Compare::CompareTrait());} template<class T> class TheSimpleCompare : public SimpleCompare<T>{public: bool operator()(const T& lv, const T& rv) const { return lv < rv; }};template<class T> class TheComplexCompare : public ComplexCompare<T>{public: int operator()(const T& lv, const T& rv) const { return lv - rv; }}; typedef TheSimpleCompare<int> SimpleIntCompare;typedef TheComplexCompare<int> ComplexIntCompare;/*class SimpleIntCompare : public SimpleCompare<int>{public:bool operator()(int lv, int rv) const{ return lv < rv; } };class ComplexIntCompare : public ComplexCompare<int>{public:int operator()(int lv, int rv) const{ return lv - rv; } };*/ #define dimof(x) (sizeof(x)/sizeof(x[0])) int main(int argc, char* argv[]){ int  val = 8; int  tab[] = { 1, 2, 3, 4, 5, 6, 7, 9, 10, 10000};  int  *slow = LowerBound(tab, tab + dimof(tab) - 1, val, SimpleIntCompare()); int  *clow = LowerBound(tab, tab + dimof(tab) - 1, val, ComplexIntCompare());  int  *s = BinSearch(tab, tab + dimof(tab) - 1, val, SimpleIntCompare()); int  *c = BinSearch(tab, tab + dimof(tab) - 1, val, ComplexIntCompare());  cout << "*slow = " << *slow << ", *clow = " << *clow << endl; cout << "*s = " << *s << ", *c = " << *c << endl   << endl;  return 0;}

评论