Discussion :

[plieuse]

Bonjour,
J'essaie d'écrire un programme qui calcule les indices de la suite de Fibonacci avec des templates. Ca marche d'ailleurs :

fibo.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
#ifndef __FIBO_H__
#define __FIBO_H__
template <int i>
int fibo (void);
template <>
int fibo<0> ();
template <>
int fibo<1> ();
#include "fibo.impl.h"
#endif /* __FIBO_H__ */

fibo.impl.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef __FIBO_IMPL_H__
#define __FIBO_IMPL_H__
template <int i>
int fibo ()
{
    return fibo<i-1>() + fibo<i-2>();
}
#endif /* __FIBO_IMPL_H__ */
 
fibo.cpp : 
#include "fibo.h"
template <>
int fibo <0> ()
{
    return 1;
}
template <>
int fibo <1> ()
{
    return 1;
}

main.cpp :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <iostream>
#include "fibo.h"
int main (int /* argc */, char* /* argv */[]) 
{
    const int i = 5;
    std::cout << "l'indice " << i 
              << " de la suite de Fibonacci est " << fibo<5>() 
              << std::endl;
}

Là où ça coince, c'est que j'essaie d'écrire un programme qui calcule les indices de la suite de Fibonacci à partir d'un nombre passé à l'exécution. Je garde les mêmes fibo.h, fibo.impl.h et fibo.cpp et j'ajoute les fichiers suivants :

printFibo.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
#ifndef __PRINTFIBO_H__
#define __PRINTFIBO_H__
template <int j>
void printFibo (const int i);
#include "printFibo.impl.h"
#endif /* __PRINTFIBO_H__ */

printFibo.impl.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifndef __PRINTFIBO_IMPL_H__
#define __PRINTFIBO_IMPL_H__
#include <stdio.h>
#include <iostream>
#include "fibo.h"
template <int j>
void printFibo (const int i) 
{
    std::cout << "l'indice " << j 
              << " de la suite de Fibonacci est " 
              << fibo<j>()
              << std::endl;
    if (j < i) {
        printFibo<j+1> (i);
    }
}
#endif /* __PRINTFIBO_IMPL_H__ */

main.cpp:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <iostream>
#include "fibo.h"
#include "printFibo.h"
int main (int /* argc */, char* /* argv */[]) 
{
    printFibo<0> (5);
}

Makefile :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
CC=g++
CFLAGS=-W -Wall -ansi -pedantic
LDFLAGS=
EXECDIR=exec
EXEC=$(addprefix $(EXECDIR)/, fibo)
INCDIR=include
INCFLAGS=$(foreach d, $(INCDIR), -I$d)
SRCDIR=source
SRC=$(wildcard $(SRCDIR)/*.cpp)
OBJDIR=obj
OBJ=$(addprefix $(OBJDIR)/, $(notdir $(SRC:.cpp=.o)))
all: $(EXEC)
.PHONY: clean mrproper doc
clean:
        @rm -rf $(OBJ)
mrproper: clean
        @rm -rf $(EXEC)
doc:
        @doxygen Doxyfile
$(OBJDIR)/%.o: $(SRCDIR)/%.cpp
        @$(CC) -o $@ -c $< $(CFLAGS) $(INCFLAGS)
$(EXEC): $(OBJ) 
        @$(CC) -o $@ $^ $(LDFLAGS)

message d'erreur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
In file included from include/fibo.h:13:0,
                 from source/main.cpp:4:
include/fibo.impl.h:7:36: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<int i> int fibo() [with int i = 896]’
include/fibo.impl.h:7:36:   required from ‘int fibo() [with int i = 898]’
include/printFibo.impl.h:17:9:   recursively required from ‘void printFibo(int) [with int j = 1]’
include/printFibo.impl.h:17:9:   required from ‘void printFibo(int) [with int j = 0]’
source/main.cpp:15:20:   required from here
 
include/fibo.impl.h:7:36: error: no matching function for call to ‘fibo()’
include/fibo.impl.h:7:36: note: candidate is:
include/fibo.impl.h:5:5: note: template<int i> int fibo()
include/fibo.impl.h:5:5: note:   substitution of deduced template arguments resulted in errors seen above
include/fibo.impl.h:7:36: error: no matching function for call to ‘fibo()’
include/fibo.impl.h:7:36: note: candidate is:
include/fibo.impl.h:5:5: note: template<int i> int fibo()
include/fibo.impl.h:5:5: note:   template argument deduction/substitution failed:
In file included from include/printFibo.h:7:0,
                 from source/main.cpp:5:
include/printFibo.impl.h: In instantiation of ‘void printFibo(int) [with int j = 899]’:
include/printFibo.impl.h:17:9:   recursively required from ‘void printFibo(int) [with int j = 1]’
include/printFibo.impl.h:17:9:   required from ‘void printFibo(int) [with int j = 0]’
source/main.cpp:15:20:   required from here
include/printFibo.impl.h:12:5: error: no matching function for call to ‘fibo()’
include/printFibo.impl.h:12:5: note: candidate is:
In file included from include/fibo.h:13:0,
                 from source/main.cpp:4:
include/fibo.impl.h:5:5: note: template<int i> int fibo()
include/fibo.impl.h:5:5: note:   template argument deduction/substitution failed:
In file included from include/printFibo.h:7:0,
                 from source/main.cpp:5:
include/printFibo.impl.h:12:5: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(const void*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]’
include/printFibo.impl.h:17:9:   recursively required from ‘void printFibo(int) [with int j = 1]’
include/printFibo.impl.h:17:9:   required from ‘void printFibo(int) [with int j = 0]’
source/main.cpp:15:20:   required from here
 
include/printFibo.impl.h:17:9: error: no matching function for call to ‘printFibo(const int&)’
include/printFibo.impl.h:17:9: note: candidate is:
include/printFibo.impl.h:10:6: note: template<int j> void printFibo(int)
include/printFibo.impl.h:10:6: note:   template argument deduction/substitution failed:
In file included from include/fibo.h:13:0,
                 from source/main.cpp:4:
include/fibo.impl.h: In function ‘int fibo() [with int i = 898]’:
include/fibo.impl.h:8:1: warning: control reaches end of non-void function [-Wreturn-type]
make: *** [obj/main.o] Erreur 1

Voilà. Si quelqu'un a une idée... Merci.
Marie

[Zenol]

La réponse est dans le message d'éreur de ton compilateur.

Quand tu travail avec des templates, tu dois garder à l'esprit que les templates sont résolues à la compilation. Cela signifit que si tu a dans ton code des apelles à fibo<1>(), fibo<2>, .... ,fibo<42>(), alors le compilateur vas écrire 42 fonctions différentes, correspondant à ces 42 fonctions. Les paramètres des templates doivent être connus à la compilation. Tu ne peux pas utiliser des valeurs connues seulement à l'éxécution.

Malheureusement, d'une façon détourné, tu essaye d'utiliser des valeurs connues à l'é×écution. Dans ta fonction printFibo, tu apelle printFibo<j+1>. Contrairement à une fonction apellée à l'execution, lors de la compilation, l'expression est toujours évalué. Le compilateur entre donc dans une sorte de récurtion infinie, et arrivé au 900ième apelle récursif, il te dis qu'il laisse tomber :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 error: template instantiation depth exceeds maximum of 900

Alors oui tu pourais lui dire de continuer plus profond "use -ftemplate-depth= to increase the maximum". Seulement, est-ce ce que tu veux faire? Déjà, je ne saurais meme pas te dire si la récursion vas terminer (je suppose que oui, quand le int/long feras un overflow, et donc tu instancie probablement autant de fonctions qu'un int peut prendre de valeur... Beurk!).

Les templates sont là pour résoudre des problèmes "à la compilation". Si tu veux une valeur particulière de la suite de fibonnaci, alors tu peux grace au template demander au compilateur de le calculer pour toi, via des templates. Si tu veux disposer de plusieurs vertion d'une meme fonction pour différents types, là aussi les templates te permetrons de n'écrire qu'une unique fonction, et le compilateur génèreras les autres. Pareille pour les "types générique". Tu défini une famille de types et le compilateur te construiras tous ces types.

Il faut bien distinguer les problèmes qui peuvent être résolu à la compilation (demander fibonnaci d'un indice écrit dans le code) de ceux résolu à l'éxécution (calculer la n-ième valeur de la suite de fibonacci où n est entré par l'utilisateur). Avec des templates, tu ne peux que "près calculer" des valeurs de ta suite.


Si tu veux lister à la compilation, tu peux faire quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
printFibo<int indice_max> {printFibo<indice_max -1>(); // affichage de fibo pour la valeur de indice_max}
printFibo<0>{//Juste un affichage}

De cette façon, printfFibo<42> n'auras besoin que de printFibo<0>, ..., printFibo<42>.


Si tu veux vraiment faire croitre une valeur avec des appels récursifs, le tout "en template", il faut que tu regarde du coté de la méta-programmation en C++ comment faire des structures logiques (pour avoir un if résolu à la compilation, et non un if résolu à l'éxécution).