为了解决我的问题,在我的项目中,我不得不手动实现一些功能,因为由于种种原因我无法使用标准库功能。
到目前为止,我对模板还是有初学者的经验,因此对我来说有些事情仍然不清楚。
为此,我想实现一个简单的二进制搜索功能:
template<class T, class TValue, ptrdiff_t compare(const T &elem, const TValue &value)>
bool binary_search(T const array[], size_t n, const TValue &value, size_t &index) {
size_t indexLow = 0;
size_t indexHigh = n;
while (indexLow < indexHigh) {
size_t indexMid = indexLow + ((indexHigh - indexLow) / 2);
if (0 > compare(array[indexMid], value)) {
indexLow = indexMid + 1;
continue; //search right
}
indexHigh = indexMid; //search left
}
if ((n > indexLow) && (0 == compare(array[indexLow], value))) {
index = indexLow;
return true;
}
return false;
}
我知道不使用迭代器或重载运算符进行比较有点不合常规,但是我想使算法本身尽可能简单。对我来说也很重要,我可以使用简单的数组(它不需要在 vector 等容器上工作)。
仅用于size_t,它与以下比较功能完美配合:
ptrdiff_t cmp_size_t(const size_t &elem, const size_t &value) {
if (elem > value)
{
return 1;
}
if (elem < value)
{
return -1;
}
return 0;
}
用法示例:size_t test_array0[] = { 1,2,3,4,5,6,7,8 };
size_t n_array0 = sizeof(test_array0) / sizeof(test_array0[0]);
size_t index;
for (size_t search_val = 0; 13 > search_val; ++search_val) {
if (binary_search<size_t, size_t, cmp_size_t>(test_array0, n_array0, search_val, index)) {
std::cout << search_val << " found at index: " << index << std::endl;
}
else {
std::cout << search_val << " not found" << std::endl;
}
}
我还希望能够搜索对象数组和对象指针数组,而这正是我偶然遇到了一个问题,而该问题我已经尝试了好几天了。使用带有比较功能的以下类:
struct TestClass {
const void *const value;
TestClass(const void *Value) :value(Value) {}
static ptrdiff_t cmp(const TestClass *&ArrayElem, const void *&SearchValue) {
if (ArrayElem->value > SearchValue) {
return 1;
}
if (ArrayElem->value < SearchValue) {
return -1;
}
return 0;
}
};
如果我尝试使用相同的代码进行搜索和排列:TestClass testElem0((void *)1);
TestClass testElem1((void *)2);
TestClass testElem2((void *)3);
TestClass *test_array1[] = {
&testElem0,
&testElem1,
&testElem2,
};
size_t n_array1 = sizeof(test_array1) / sizeof(test_array1[0]);
for (size_t search_val = 0; 13 > search_val; ++search_val) {
if (binary_search<TestClass *, void *, TestClass::cmp>(test_array1, n_array1, (void *)search_val, index)) {
std::cout << search_val << " found at index: " << index << std::endl;
}
else {
std::cout << search_val << " not found" << std::endl;
}
}
我收到以下编译错误:1>d:\temp\count_test\count_test\main.cpp(78): error C2672: 'bynary_search': no matching overloaded function found
1>d:\temp\count_test\count_test\main.cpp(78): error C2893: Failed to specialize function template 'bool bynary_search(const T [],std::size_t,const TValue &,size_t &)'
1> d:\temp\count_test\count_test\main.cpp(78): note: With the following template arguments:
1> d:\temp\count_test\count_test\main.cpp(78): note: 'T=TestClass *'
1> d:\temp\count_test\count_test\main.cpp(78): note: 'TValue=void *'
1> d:\temp\count_test\count_test\main.cpp(78): note: 'compare=ptrdiff_t TestClass::cmp(const TestClass *&,const void *&)'
我通过引用传递的原因是因为有时我想在对象数组或对象指针数组中进行搜索,并且我想确保无法编写调用复制构造函数的代码。我知道,对于像size_t,int,void *这样的原子类型,通过引用传递不是做到这一点的最佳方法,但是由于我还通过const传递元素,因此编译器将知道对其进行优化。我还不确定的另一件事是,是否有可能从函数参数中推断出一些模板参数,所以我可以这样写:
binary_search<cmp_size_t>(test_array0, n_array0, search_val, index)
代替binary_search<size_t, size_t, cmp_size_t>(test_array0, n_array0, search_val, index)
最佳答案
您的模板需要const T&
和const TValue&
。
在声明对指针的引用时,const
的位置很重要。const TestClass *&ArrayElem
是对const指针的引用。TestClass* const &ArrayElem
是对指针的const引用。
您的模板仅接受后者。
关于c++ - 带模板的二进制搜索功能,用于数组-编译问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63039603/