EDIT 1
Based on the comments below, I have now tried to implement using the functors. I am still stuck, so any kind of help would be appreciated. Here is my implementation:
mysorting.h
................
#include<myutils.h>
// =================================
// the actual class
class Sorting {
public:
template <typename T, typename Func> static void mergeSort(T *, int, Func);
};
template static void Sorting::mergeSort<int, CompareInt>(int *, int, CompareInt);
......................
So, I am passing the third argument as a functor which I have defined in my myutils.h. Also, I have instantiated the template for mergeSort to work for int.
Also, I have instantiated the template for the merge function that I am using to merge the arrays in myutils.h. Here is a snippet from my myutils.h:
................
template <typename T, typename Func> void merge(T[], T[], int, T[], int, Func);
// functor for comparing he integers
struct CompareInt {
int operator() (int a, int b) {
return a-b;
}
};
template void merge<int, CompareInt>(int[], int[], int, int[], int, CompareInt);
........................
The snippet from myutils.cpp is as follows:
.......................
template <typename T, typename Func> void merge(T t[], T first[], int fL, T sec[], int sL, Func compar) {
int i = 0;
int j = 0;
int k = 0;
// while both the arrays have the elements left ..
while (j < fL && k < sL) {
if (compar(first[j], sec[k]) < 0) {
memcpy(t + i, sec + j, sizeof(T));
i++; j++;
} else {
memcpy(t + i, sec + k, sizeof(T));
i++; k++;
}
}
...........
}
}
.......................
And the snippet from mysorting.cpp is as follows:
...............................
class Sorting {
public:
template <typename T, typename Func> static void mergeSort(T *, int, Func);
};
template <typename T, typename Func> void Sorting::mergeSort(T *arr, int l, Func compar) { ...}
..........................
I am simply calling :
CompareInt c;
Sorting::mergeSort(arr, 5, c);
to run the sort function. When I try to compile my code using my Makefile, I get the following error:
g++ -c -g -Wall -I./include -c src/mysorting.cpp -o src/mysorting.o
In file included from src/mysorting.cpp:2:0:
./include/myutils.h: In instantiation of ‘void merge(T*, T*, int, T*, int, Func) [with T = int; Func = CompareInt]’:
./include/myutils.h:19:79: required from here
./include/myutils.h:19:79: error: explicit instantiation of ‘void merge(T*, T*, int, T*, int, Func) [with T = int; Func = CompareInt]’ but no definition available [-fpermissive]
template void merge<int, CompareInt>(int[], int[], int, int[], int, CompareInt);
^
./include/myutils.h: In instantiation of ‘void merge(T*, T*, int, T*, int, Func) [with T = int; Func = CompareInt]’:
./include/myutils.h:19:79: required from here
./include/myutils.h:19:79: error: explicit instantiation of ‘void merge(T*, T*, int, T*, int, Func) [with T = int; Func = CompareInt]’ but no definition available [-fpermissive]
./include/myutils.h: In instantiation of ‘void merge(T*, T*, int, T*, int, Func) [with T = int; Func = CompareInt]’:
./include/myutils.h:19:79: required from here
./include/myutils.h:19:79: error: explicit instantiation of ‘void merge(T*, T*, int, T*, int, Func) [with T = int; Func = CompareInt]’ but no definition available [-fpermissive]
make: *** [src/mysorting.o] Error 1
Can you please give me some hints on this?
ORIGINAL
I am trying to write a static function in my class Sorting in cpp for implementing merge sort. I have already implemented it the merge sort for sorting an integer array. Now, I am trying to implement the merge sort using Templates to sort the arrays of any datatype. For that, I am trying to pass an additional argument as a compar function in the mergeSort function. Here is the implementation:
The header file is as follows:
................
class Sorting {
public:
template <typename T> static void mergeSort(T *,int, int (*)(const void*,const void*));
};
................
The cpp file is as follows:
class Sorting {
public:
template <typename T> static void mergeSort(T *,int, int (*)(const void*,const void*));
};
.......
template <typename T> void Sorting::mergeSort(T *arr, int l, int (*compar)(const void*,const void*)) {
// if the lengh of the array is 1, it is already sorted. Case, when the array is
// empty
if (l <= 1) {
return;
}
// else, we divide the arrays and recurse..
T *left = new T[l/2];
T *right = new T[l - l/2];
// copying the values into the left and the right arrays..
memcpy(left, arr, l/2 * sizeof(T));
memcpy(right, arr + l/2, (l - l/2) * sizeof(T));
// running merge sort on the lef tand the right arrays separately ..
mergeSort(left, l/2, compar);
mergeSort(right, l - l/2, compar);
merge(arr, left, l/2, right, l - l/2, compar);
}
Implementation of the merge function is as follows:
template <typename T> void merge(T t[], T first[], int fL, T sec[], int sL, int (*compar)(const void*,const void*)) {
int i = 0;
int j = 0;
int k = 0;
// while both the arrays have the elements left ..
while (j < fL && k < sL) {
if ((*compar)(first + j, sec + k) < 0) {
memcpy(t + i, sec + j, sizeof(T));
i++; j++;
} else {
memcpy(t + i, sec + k, sizeof(T));
i++; k++;
}
}
// while only the first array has the elements left
while(j < fL) {
memcpy(t + i, sec + j, sizeof(T));
i++; j++;
}
// while only the second array has the elements left
while(k < fL) {
memcpy(t + i, sec + k, sizeof(T));
i++; k++;
}
}
And finally, my main.cpp is as follows:
................
int compare(const void *a, const void *b) {
return ( *(int*)a - *(int*)b );
}
int main() {
int arr[5] = {5,4,3,2,1};
Sorting::mergeSort(arr, 5, compare);
}
...............
When I am trying to compile the code with the Makefile, it gives me the following error:
Undefined symbols for architecture x86_64:
"void Sorting::mergeSort<int>(int*, int, int (*)(void const*, void const*))", referenced from:
_main in main.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [a.out] Error 1
The code got successfully compiled when I ran my function specifically for the integers, but now I have some troubles. Any idea?
