带模板的二进制搜索功能，用于数组 - 编译问题

Question

首先说明我的问题：在我的项目中，由于各种原因我不能使用标准库函数，因此我必须手动实现一些函数。到目前为止，我对模板有初学者的经验，所以有些事情我还不清楚。

为此我想实现一个简单的二进制搜索功能：

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

我也希望能够搜索对象数组和对象指针数组，这就是我无意中遇到的问题，几天来我一直在努力解决这个问题。使用比较函数获取以下 class：

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)

Answer 1

您的模板需要 const T& 和 const TValue&。

当声明对指针的引用时，const 的位置很重要。

const TestClass *&ArrayElem 是对 const 指针的引用。

TestClass* const &ArrayElem 是对指针的常量引用。

只有后者会被您的模板接受。

带模板的二进制搜索功能，用于数组 - 编译问题

Binary search function with templates, for arrays - compilation problem

c++

templates

compiler-errors

class

binary-search