c++templatestemplate-argument-deduction

How to pass an element of type T and an array of that T type as reference to a function in C++?


I have the following two functions, but I always get this compiler error:

deduced conflicting types for parameter 'T'

I figure that the problem is that T refers to an array and int at the same time, but how could I resolve this issue? If I remember correctly, I have seen similar done with adding some more code to the template part, but I couldn't find that now.

template<typename T>
int binSearch(const T& A, int u, int v, T x) {
    if (u > v) return 0;
    int m = (u + v) / 2;

    if(A[m] > x) return binSearch(A, u, m-1, x);
    if(A[m] < x) return binSearch(A, m+1, v, x);
    else return m;
}

template<typename T>
int logSearch(const T& A, T x) {
    return binSearch(A, 0, sizeof(A) / sizeof(A[0]), x);
}

example of how I want to use this function:

#include <iostream>

#include "..\binSearch.hh"

int main() {
    int asd[] = {0,1,2,3,4,5,6,7,8,9};

    std::cout << logSearch(asd, 3);

    return 0;
}

When compiling this file with g++, I get the following:

g++ .\Algorithms\tests\example.cpp
.\Algorithms\tests\example.cpp: In function 'int main()':
.\Algorithms\tests\example.cpp:8:27: error: no matching function for call to 'logSearch(int [10], int)'
    8 |     std::cout << logSearch(asd, 3);
      |                  ~~~~~~~~~^~~~~~~~
In file included from .\Algorithms\tests\example.cpp:3:
.\Algorithms\tests\..\binSearch.hh:15:5: note: candidate: 'template<class T> int logSearch(const T&, T)'
   15 | int logSearch(const T& A, T x) {
      |     ^~~~~~~~~
.\Algorithms\tests\..\binSearch.hh:15:5: note:   template argument deduction/substitution failed:
.\Algorithms\tests\example.cpp:8:27: note:   deduced conflicting types for parameter 'T' ('int [10]' and 'int')
    8 |     std::cout << logSearch(asd, 3);
      |                  ~~~~~~~~~^~~~~~~~

Solution

  • To answer your immediate question, in order to create a function template that accepts an array of Ts and a T element, you need to use the following syntax:

    template<typename T, int N>
    int f(const T (&A)[N], T const & x) {
       // ...
    }
    

    Notes:

    1. The template now has an additional non-type template parameter for the array's size.
    2. The element to search can be passed by const & (i.e. T const & x) to avoid copy (which is not singinifcant for ints but might be for other Ts).

    Live demo

    However - in C++ is it generally not recommended to use plain C arrays.

    Instead you can use use std::vector (or std::array for static size arrays):

    template<typename T>
    int f(std::vector<T> const & A, T const & x) {
       // ...
    }
    

    Or in this case, as @Useless commented, use std::ranges::random_access_range which is more general and can be used with std::vector, std::array etc.