3. [C++11] Templates/constexpr und Rekursion.

[C++11] Templates/constexpr und Rekursion.

  • S

    Hallo,

    es ist ja hinlänglich bekannt wie man mittels Templates Schleifen durch Rekursion realisiert. Fast jeder kennt sicherlich das Beispiel der Berechnung der Fakultät.
    Durch constexpr kann man sich nun ein haufen Tipparbeit sparen und einfach schreiben

    constexpr int fak (int N)
{
  return N < 2 ? 1 : N * fak(N-1);
}

    Leider kann man solche Funktion nur durch integrale Konstanten parametrisieren, während man Templates durch Typen und Templates parametrisieren kann. Also hab ich mir gedacht, warum nicht so:

    template <int N>
constexpr int fak ()
{
  return N < 2 ? 1 : N * fak<N-1> ();
}

int main()
{
  fak<10> ();
  return 0;
}

    Mein Compiler (gcc-4.8, gcc-4.7) scheint das aber nicht zu verstehen, zumindest versucht er die Funktion für alle möglichen Werte von N zu instanzieren und schreit mich an mit

    Fehler: Instanziierungstiefe für Templates überschreitet Höchstwert ...

    Jetzt habe ich mich halt gefragt: Habe ich einen Denkfehler? Liegt es am Compiler? Was sagt der Standard dazu?
    Ich finde das jedenfalls sehr schade. Nur als kleines Bsp:

    template <typename Type, Type...> // meinetwegen auch tupel oder sonstwas
struct compiletime_vector
{
  typedef Type value_type;
};

template <typename Type, Type T0, Type... TN>
struct compiletime_vector <Type, T0, TN...>
{
  typedef Type value_type;

  static constexpr Type                   head = T0;
  typedef compiletime_vector<Type, TN...> tail;
};

template <typename Vec, int N>
constexpr typename Vec::value_type get_element ()
{
  return N == 0 ? Vec::head : get_element<typename Vec::tail, N-1> ();
}

int main()
{
    typedef compiletime_vector <int, 10, 20, 30, 40, 50> vector;

    get_element<vector, 2> (); // fails

    return 0;
}

    (mir ist klar das ich die get Methode auch in ein struct packen und durch Spezialisiereung die Rekursion beenden kann)

    Erbitte Diskussion 🙂

    0
  • C
    Mod

    ScottZhang schrieb:

    Habe ich einen Denkfehler?

    Das (ein wenig). Die Regeln sind im Grunde die Gleichen wie in C++03, und gerade weil jetzt auch constexpr-Funktionen zur Verfügung stehen, gibt es keinen Grund, an diesen Regeln etwas zu ändern.

    n3337 schrieb:

    14.7.1 Implicit instantiation [temp.inst]
    [...]
    3 Unless a function template specialization has been explicitly instantiated or explicitly specialized, the function
    template specialization is implicitly instantiated when the specialization is referenced in a context that
    requires a function definition to exist.     Unless a call is to a function template explicit specialization or to a
    member function of an explicitly specialized class template, a default argument for a function template or a
    member function of a class template is implicitly instantiated when the function is called in a context that
    requires the value of the default argument.

    3.2 One definition rule [basic.def.odr]
    [...]
    3 Every program shall contain exactly one definition of every non-inline function or variable that is odr-used
    in that program; no diagnostic required.     The definition can appear explicitly in the program, it can be found
    in the standard or a user-defined library, or (when appropriate) it is implicitly defined (see 12.1, 12.4 and
    12.8). An inline function shall be defined in every translation unit in which it is odr-used.

    2 An expression is potentially evaluated unless it is an unevaluated operand (Clause 5) or a subexpression
    thereof.     A variable whose name appears as a potentially-evaluated expression is odr-used unless it is an
    object that satisfies the requirements for appearing in a constant expression (5.19) and the lvalue-to-rvalue
    conversion (4.1) is immediately applied. this is odr-used if it appears as a potentially-evaluated expression
    (including as the result of the implicit transformation in the body of a non-static member function (9.3.1)).
    A virtual member function is odr-used if it is not pure. A non-overloaded function whose name appears
    as a potentially-evaluated expression or a member of a set of candidate functions, if selected by overload
    resolution when referred to from a potentially-evaluated expression, is odr-used, unless it is a pure virtual
    function and its name is not explicitly qualified.     [ Note: This covers calls to named functions (5.2.2), operator
    overloading (Clause 13), user-defined conversions (12.3.2), allocation function for placement new (5.3.4), as
    well as non-default initialization (8.5). A copy constructor or move constructor is odr-used even if the call
    is actually elided by the implementation. —end note ] An allocation or deallocation function for a class is
    odr-used by a new expression appearing in a potentially-evaluated expression as specified in 5.3.4 and 12.5.
    A deallocation function for a class is odr-used by a delete expression appearing in a potentially-evaluated
    expression as specified in 5.3.5 and 12.5. A non-placement allocation or deallocation function for a class is
    odr-used by the definition of a constructor of that class. A non-placement deallocation function for a class is
    odr-used by the definition of the destructor of that class, or by being selected by the lookup at the point of
    definition of a virtual destructor (12.4).26 A copy-assignment function for a class is odr-used by an implicitlydefined
    copy-assignment function for another class as specified in 12.8. A move-assignment function for a
    class is odr-used by an implicitly-defined move-assignment function for another class as specified in 12.8. A
    default constructor for a class is odr-used by default initialization or value initialization as specified in 8.5.
    A constructor for a class is odr-used as specified in 8.5. A destructor for a class is odr-used as specified
    in 12.4.

    5 Expressions [expr]
    [...]
    7 In some contexts, unevaluated operands appear (5.2.8, 5.3.3, 5.3.7, 7.1.6.2). An unevaluated operand is not
    evaluated. [ Note: In an unevaluated operand, a non-static class member may be named (5.1) and naming
    of objects or functions does not, by itself, require that a definition be provided (3.2). —end note ]

    5.2.8 Type identification [expr.typeid]
    5.3.3 Sizeof [expr.sizeof]
    5.3.7 noexcept operator [expr.unary.noexcept]
    7.1.6.2 Simple type specifiers [dcl.type.simple]     <-- hier geht es in diesem Zusammenhang um decltype

    Die Frage, ob ein bestimmter Teilausdruck ausgewertet wird oder nicht, hat erst einmal nichts damit zu tun, ob darin enthaltene Templatespezialisierungen auch instantiiert werden müssen, es sei denn, es handelt sich um eine der o.g. Ausnahmen (typeid,sizeof,noexcept,decltype).

    0
  • S

    Erstmal danke camper für die Mühe, das rauszusuchen. Ich gebs zu ich war einfach zu faul dazu :). Aber ich bin kein Programmierer, bei mir hätte das Tage oder Wochen in anspruch genommen ...

    Dann bleibt die Frage warum das Template instanziiert werden muss (für N<2).
    Denn das der Ausdruck

    N < 2 ? die : das;

    nicht immer vollständig ausgewertet wird ist offensichtlich.

    0
  • S
     

    template <unsigned short N> //
constexpr unsigned long long fak ()
{
  return N * fak<N-1> ();
}

template <> constexpr unsigned long long fak<1> () { return 1; }
template <> constexpr unsigned long long fak<0> () { return 1; }

#include <iostream>

int main()
{
  std::cout << fak<10> ();
}

    Wieso den Konditionsoperator? Man kann doch gleich spezialisieren...
    (Ich habe die Typen ein wenig angepasst)

    0
  • S

    Partielle spezialisierung geht aber nicht ...

    Es geht mir garnicht um alternetive Lösungen, die sind mir bekannt.

    0
  • S

    ScottZhang schrieb:

    Partielle spezialisierung geht aber nicht ...

    Wie meinst du das? Dass das funktioniert ist doch klar.

    ScottZhang schrieb:

    Es geht mir garnicht um alternetive Lösungen, die sind mir bekannt.

    Ach, ok ^^

    Hilft dir das weiter:

    template <unsigned char N>
constexpr unsigned long long fak ()
{
    return N < 2 ? 1 : N * fak<N-1> ();
}

int main()
{
      fak<10> ();
}

    Das funktioniert.

    0
  • S

    Ich meine sowas

    template <typename Dawas, size_t Lauf>
consexpr bla_type tu_was () 
{
  return mach_was_mit ( tu_was<Dawas, Lauf-1> () );
}

    In dem Falle bräuchtes du ne partielle Spezialisierung von Funktionen was nach meiner Kenntnis nicht erlaubt ist

    Sone schrieb:

    template <unsigned char N>
constexpr unsigned long long fak ()
{
    return N < 2 ? 1 : N * fak<N-1> ();
}

int main()
{
      fak<10> ();
}

    Das funktioniert.

    Ja das würde gehen, entspricht aber nicht dem Sachverhalt und ist getrickst 🙂

    0
  • C

    Seit C++11 ist das übrigens erlaubt wenn ich mich richtig erinnere, die ganz ganz neueste VS 2012 Beta sollte das sogar erlauben. 🙂 Falsch erinnert.
    Falls du das Feature noch nicht hast, geben structs + statische Methoden Abhilfe.

    0
Anmelden zum Antworten