Prototype functions in C / C++
What kinds of functions are these? What can these prototypes do?
/*1*/int func ( int (*x)(int,int) )
/*2*/int func ( int x(int,int) )
/*3*/int func1 ( int(fn)() )
/*4*/int func2 ( int(*fn)() )
Is this type of function called a function pointer? How it is used and why it should be used.
typedef int cellulae_func(int, int);
void tabula(cellulae_func *cell, int lat, int alt);
2 answers
This is pointer to function, so in this way, just as a parameter can receive a reference to an object, the parameter can receive a reference to a function.
Therefore C has what is called high-order function or first class. We treat functions as if they were data.
A function is of course already a reference, after all access to it is given by the address of the beginning of the code written in this function, so analogous to a vector that has a pointer to its first element. This goes for static functions even, but in this case the address is associated with an existing identifier in the code and if it is called directly, it does not have much to do with it.
But it is possible to store this address in a variable, or even pass as an argument to a function that precisely expects a type that is a function. Is, the function itself, is not calling a function in the argument and passing the result from her, you pass her. Of course you talk about passing the function without copying your code from one place to another, you copy only the address.
So just like a vector of integers you can have a parameter more or less like int * x when it is a function that receives an integer and returns another integer it would be something like int (*x)(int), being that the first int indicates that the function to be received should return a int, it will be stored in a variable called x int, as demonstrated by the last int.
I found out now that I could that I could use the syntax without the pointer, when I learned I could only use it like that and I still need to research if this is standard, but I believe it is by the source.
typedef
Obviously a function signature is a type of the parameter variable, being a type it is possible to create a typedef for it and make the syntax more pleasant.
Does not need to be only in parameter, but is where it fits best. It could be a member of a struct, has interesting cases for this, and is a way to simulate dynamic polymorphism.
Examples:
#include <stdio.h>
int func( int (*x)(int,int) ) { return x(20, 5); }
int func2( int x(int,int) ) { return x(20, 5); }
int func3( int(fn)() ) { return fn(); }
int func4( int(*fn)() ) { return fn(); }
typedef int cellulae_func(int, int);
int tabula(cellulae_func *cell, int lat, int alt) { return cell(lat, alt); }
int soma(int x, int y) { return x + y; }
int sub(int x, int y) { return x - y; }
int teste() { return 42; }
int main(void) {
printf("%d\n", tabula(soma, 20, 5));
printf("%d\n", tabula(sub, 20, 5));
printf("%d\n", func(soma));
printf("%d\n", func2(soma));
printf("%d\n", func3(teste));
printf("%d\n", func4(teste));
printf("%d\n", func4(soma)); //funciona, mas está errado
int (*funcs[2])(int x, int y);
funcs[0] = soma;
funcs[1] = sub;
printf("%d\n", func(funcs[0]));
}
See working on ideone. E no repl.it. also I put on GitHub for future reference .
Note that I pass the static names of functions, and since these names are actually pointers, I am passing their address. On the other side the variable that receives this pointer is used to call the function using the syntax of the parentheses. It cannot be used correctly otherwise, although old compilers or with wild settings allow to do havoc, and of course, with a cast everything is allowed, even if the result is bad.
The ideal is to use functions with compatible signatures, it is undefined behavior to use an inappropriate one, as demonstrated in one of the lines.
Both functions named x have the same signature, which is compatible with both soma and sub defined below. typedef is compatible with the same signature. The names could be different, because deep down this is just the name of the variable. Those with name fn have another signature.
Use
The advantage of having this is that they can dynamically configure what to perform in a given context. Which is the such of the polymorphism (at least one form of it). And is a substitute for if in many cases, since functions can be placed in a vector or other data structure, as I demonstrated above in the example. So whenever some action needs to be configured on demand, according to the need of the moment, this type of function is interesting.
Is widely used as callback, where you call an algorithm that at a certain point needs to run something that it doesn't yet know what it is, or that is, it responds to something configurable by the caller. So think of handlers, events .
C itself has algorithms that expect a callback , for example the qsort() where you say how it should perform the comparison of data to sort the way you want, so taking the specific data, deciding whether it will do something extra operation with the data, such as giving a upper , whether it will be ascending or descending.
A creativity allows you to make diverse compositions, could for example create a dictionary with (pointers to) the functions as values of it and according to something typed by the user or getting the information otherwise at run time call the appropriate function, which is very similar to what a language with quite dynamism and having a different function.eval() lets do.
If it is static this can be a jump table.
An application what is the flame likelazy evaluation, where you define what you want to do, but don't want it to be done at that moment, then you "pass the code" somewhere and at the appropriate time the code is called.
Limitation
C has no syntax of lambda that could declare the function in the location it needs. Something like this:
printf("%d\n", tabula((int x, int y) => x + y, 20, 5));
C also does not have its own mechanism of capturing several of the current scope to load along with the function passed as a parameter, something that other languages have, but nothing prevents you from manually creating this capability, it's just not convenient.
Example
The most obvious example of use is with sorting algorithms where you need to tell what the criterion of what is less than the other, even to decide the exact key or whether the order should be ascending or descending. So the function qsort() default C already receives a function as a parameter. In C++ this is much more efficient.
#include <stdio.h>
#include <stdlib.h>
int compare(const void* left, const void* right) { return (*(int*)right - *(int*)left); }
int main() {
int (*cmp) (const void* , const void*) = &compare;
int array[] = {1, 8, 0, 4, 6, 5, 1, 6, 9, 7};
qsort(array, 10, sizeof(int), cmp);
for (int i = 0; i < 10; i++) printf("%d ", array[i]);
}
See working on ideone. E no repl.it. also I put on GitHub for future reference .
Exercise: does this generate a stable rating? The question is a catch.
C++
This should not be used in C++, except for compatibility, it has long had libraries that handle this better, and since 2011 it has lambdas and closures. And even some specific uses C++ has better solution.
Assembly
See how it looks after compiled by GCC (other compilers are theoretically less efficient):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov DWORD PTR [rbp-8], esi
mov edx, DWORD PTR [rbp-4]
mov eax, DWORD PTR [rbp-8]
add eax, edx
pop rbp
ret
func:
push rbp
mov rbp, rsp
mov esi, 5
mov edi, 20
call soma
pop rbp
ret
func2:
push rbp
mov rbp, rsp
sub rsp, 16
mov QWORD PTR [rbp-8], rdi
mov rax, QWORD PTR [rbp-8]
mov esi, 5
mov edi, 20
call rax
leave
ret
tabula:
push rbp
mov rbp, rsp
sub rsp, 16
mov QWORD PTR [rbp-8], rdi
mov DWORD PTR [rbp-12], esi
mov DWORD PTR [rbp-16], edx
mov ecx, DWORD PTR [rbp-16]
mov edx, DWORD PTR [rbp-12]
mov rax, QWORD PTR [rbp-8]
mov esi, ecx
mov edi, edx
call rax
leave
ret
main:
push rbp
mov rbp, rsp
mov edx, 5
mov esi, 20
mov edi, OFFSET FLAT:soma
call tabula
mov eax, 0
call func
mov edi, OFFSET FLAT:soma
call func2
mov eax, 0
pop rbp
ret
Better visually see in Compiler Explorer.
You can notice that the call is indirect and has more complex instructions. What is perhaps not so obvious is the extra memory access and this yes it can be slower and makes more difference than a few more instructions. And you can see that everything that is definition of types and contracts is thrown away.
Meanwhile I remembered a common situation where this is used and which probably also helps to contextualize, which is in an ordering.
As @Maniero has already explained, These are pointers to functions, and the name can both be with or without pointer notation that the compiler will treat equally.
So these two are equal:
/*1*/int func ( int (*x)(int,int) )
// ^--
/*2*/int func ( int x(int,int) )
// ^--
Imagine you have a bubble sort to sort an array of integers:
void bubble_sort(int arr[], int tamanho) {
int i, j;
for (i = 0; i < tamanho - 1; i++) {
for (j = 0; j < tamanho - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
More now I would like to be able to use other types without being just whole. How will you compare ? The comparison depends intrinsically on type and even becomes worse when we consider types that the programmer can create with struct. Soon it is impossible for you to be able to know in advance how to compare.
Instead you get a function that knows how to compare two elements and returns:
-
< 0when the first element is smaller -
0when are equal -
> 0when the first element is greater
Himself qsort that exists in the standard library also gets a function to compare. See an example of an integer comparison function for qsort:
int compare (const void * a, const void * b){
return ( *(int*)a - *(int*)b );
}
And now when you call qsort you pass the function as argument:
qsort (values, 6, sizeof(int), compare);
// ^--- aqui
Thus qsort calls its function whenever it has to compare two elements in the array and sort them.
So in this example of Bubble sort we can do the same, receive a function to compare each element. This has some implications for the parameters of this bubble_sort:
-
The array must become a
void*to point to any type in memory -
It is also necessary to know how many bytes a type occupies in memory to know how many bytes we walk forward whenever we want to go to the next element
-
It is also necessary receive the function that knows how to compare two elements
With this the new signature of the function can be:
void bubble_sort_generico(void *arr, int tamanho, int bytes_elem, int comparador(void*, void*) );
// ponteiro de função identico ao que tem na pergunta ----^
Now the implementation becomes more complex because it handles void* and each advance in the array has to be made in x bytes which corresponds to the amount of bytes each element has:
void bubble_sort_generico(void *arr, int tamanho, int bytes_elem, int comparador(void*, void*) ){
int i, j, tamanho_bytes = tamanho * bytes_elem;
for (i = 0; i < tamanho_bytes - bytes_elem; i += bytes_elem) {
for (j = 0; j < tamanho_bytes - i - bytes_elem; j += bytes_elem) {
void *ptr_elem1 = arr + j;
void *ptr_elem2 = arr + j + bytes_elem;
if (comparador(ptr_elem1, ptr_elem2) > 0){ //chamar o comparador
char temp[1024];
memcpy(temp, ptr_elem1, bytes_elem);
memcpy(ptr_elem1, ptr_elem2, bytes_elem);
memcpy(ptr_elem2, temp, bytes_elem);
}
}
}
}
Each of the memcpys corresponds to the simple assignment that was previously done with int temp = arr[j];. Since each element can have several bytes there is no way to make a simple assignment and so the solution is to copy byte by byte until it perfects all the bytes that make an element. For simplicity I used the memcpy but it could also be done manually with a for.
The statement comparador(ptr_elem1, ptr_elem2) that is inside the if is the one that calls the received function as a parameter to make the comparison, passing two pointers as arguments.
The comparator can be a copy of what I showed for the qsort but adjusted to the types that the function wait:
int comparador (void *a, void *b){
return ( *(int*)a - *(int*)b );
}
Note that I did not use const void* for simplicity but it would make more clear sense, since the comparison function is not supposed to change anything.
It is worth remembering that this implementation may be better in some respects, but I tried to keep it simple since the very concept of working for everything with void* already tends to be complex enough. That was also why I opted for one of the simplest sort algorithms.
The call in main would look like this:
int main() {
int nums[] = {37, 2, 59, 1, 19, 3, 14};
int tamanho = sizeof(nums) / sizeof(nums[0]);
bubble_sort_generico(nums, tamanho, sizeof(int), comparador);
Now the difference is that you can also sort strings for example if you pass a function that can compare two strings:
int comparador_nomes(void * a, void* b){
char **nome1 = (char**)a;
char **nome2 = (char**)b;
return strcmp(*nome1, *nome2);
}
int main() {
char *nomes[] = {"joao", "filipa", "rita", "ana", "marcos"};
int tamanho2 = sizeof(nomes) / sizeof(nomes[0]);
bubble_sort_generico(nomes, tamanho2, sizeof(char*) , comparador_nomes);
Note that I compared the names based on the strcmp.
See these two examples in Ideone
As a final note, If you look at the signature of qsort in some of the implementations, you see something similar to the examples you put:
typedef int (*__compar_d_fn_t) (const void *, const void *, void *);
void _quicksort (void *const pbase, size_t total_elems, size_t size, __compar_d_fn_t cmp, void *arg) {
// ^-- função aqui
A difference is that they made a typedef to be syntactically simpler to write the function.