Binary search function with templates, for arrays - compilation problem

Question

To preface my problem: in my project, i have to implement a few functions manually, since i can't use the standard library functions for various reasons. I have beginner experience with templates so far so some things are still not clear to me.

For this i wanted to implement a simple binary search function:

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

I know it is a bit unorthodox to NOT use iterators or overloaded operators to compare, but i wanted to keep the algorithm itself as simple as possible. Also it is important for me, that i works with simple arrays (it does not need to work on containers like vector and such).

Using only for size_t, it works perfectly with the following compare function:

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

Example of usage:

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

I would also like to be able to search array of object and array of object pointers too, and this is where i have stumbled into a problem which i have been trying to solve for days now. Take the following class with a compare function:

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

If i try to use the same code to search and array:

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

i get the following compilation error:

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 *&)'

The reason i`m passing by reference is because sometimes i want to search in array of objects, or array of object pointers, and i want to make sure it is not possible to write code, that invokes the copy constructor. I know, that for atomic types like size_t, int, void *, passing by reference is not the best way to do it, but since i'm also passing elements with const, the compiler will know to optimize it.

Also another thing i'm not sure, is if is it possible to deduce some of the template arguments from the function arguments, so i can write:

binary_search<cmp_size_t>(test_array0, n_array0, search_val, index)

instead of

binary_search<size_t, size_t, cmp_size_t>(test_array0, n_array0, search_val, index)

Answer 1

Your template expects a const T& and const TValue&.

When declaring references to pointers the placement of the const matters.

const TestClass *&ArrayElem is a reference to a const pointer.

TestClass* const &ArrayElem is a const-reference to a pointer.

Only the latter will be accepted by your template.