Type Traits 实例,提高效率

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

#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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航