Home / Questions / 306630
Accepted
Trauma
Asked: 2020-11-08 03:04:02 +0800 CST 2020-11-08 03:04:02 +0800 CST

template instantiation depth exceeds maximum

  • 772

Doing a recursion experiment with templates, I've come up with this:

#include <iostream>
#include <utility>

template< int INDEX = 0 >
void constexpr callInTuple( int index ) {
  if( INDEX == index ) {
    std::cout << INDEX << '\n';
  } else {
    std::cout << "Intentando con " << INDEX << ", fallido\n";
    callInTuple< INDEX + 1 >( index );
  }
}

int main( ) {
  callInTuple( 1 );

  return 0;
}

What I expect, when calling the function with the literal argument 1, is that something like this will be displayed on the screen:

Trying 0, failed
1

But it doesn't even compile, showing the error in the title:

template instantiation depth exceeds maximum ...

If I try it by calling the function like

callInTuple( 0 );

I would expect an even shorter output, like so:

0

However, I get the exact same error .

  • What am I doing wrong ?

  • How do I solve it ?

c++

1 Answers

  1. Best Answer

    Let's play at being the compiler.

    Templates are instantiated at compile time when they substitute received arguments. Let's do it: We know that callInTupleno parameter template is instantiated with 0, so we must replace all of them INDEXwith 0, so the generated function is:

    void constexpr callInTuple( int index ) {
  if( 0 == index ) {
    std::cout << 0 << '\n';
  } else {
    std::cout << "Intentando con " << 0 << ", fallido\n";
    callInTuple< 0 + 1 >( index );
  }
}

    The work is not finished, there is another call to callInTuplewith the expression 0 + 1that at compile time is translated to 1, so we must replace all the INDEXby 1, therefore the generated function is:

    void constexpr callInTuple( int index ) {
  if( 1 == index ) {
    std::cout << 1 << '\n';
  } else {
    std::cout << "Intentando con " << 1 << ", fallido\n";
    callInTuple< 1 + 1 >( index );
  }
}

    But we are not done, now it is instantiated callInTuplewith the expression 2, so we must replace all the INDEXby 2:

    void constexpr callInTuple( int index ) {
  if( 2 == index ) {
    std::cout << 2 << '\n';
  } else {
    std::cout << "Intentando con " << 2 << ", fallido\n";
    callInTuple< 2 + 1 >( index );
  }
}

    When you have repeated this about 65,535 times (this number can vary depending on the compiler or compiler parameters: -ftemplate-depth) the compiler will give up.

    This means that you've done the recursion wrong: it never reaches the base case . You get the same error because it indexis a variable at run time while it INDEXis known at compile time and the compiler has no choice but to keep generating instances of callInTuplebecause it has no means to break recursion at compile time.

    Your problems are:

    • If the base case is always less than the input variable, you should not be increasing the index but decreasing it.
    • Both indices must be known at compile time: so both must be non-type parameters.
    • In the base case, you should prevent the branch that continues the recursion from being generated: use if constexpr.

    Proposal .

    #include <iostream>
#include <utility>

template< int START, int INDEX = 0 >
void constexpr callInTuple( ) {
  if constexpr ( INDEX == START ) {
    std::cout << INDEX << '\n';
  } else {
    std::cout << "Intentando con " << START << ", fallido\n";
    callInTuple< START - 1, INDEX >( );
  }
}

int main( ) {
  callInTuple< 1 >( );

  return 0;
}

    But this solution uses the C++17 static conditional, since the question is tagged as C++11 you can't use it, so you should do a specialization of the template... but you can't partially specialize template functions:

    template< int START, int INDEX = 0 >
void constexpr callInTuple( ) {
  std::cout << "Intentando con " << START << ", fallido\n";
  callInTuple< START - 1, INDEX >( );
}
// ERROOOOOOR!!
template< int START >
void constexpr callInTuple< START, START >( ) {
  std::cout << START << '\n';
}

    So the solution will go through specializing classes:

    #include <iostream>
#include <utility>

template< int START, int INDEX = 0 >
struct callInTuple { 
  constexpr callInTuple( ) {
    std::cout << "Intentando con " << START << ", fallido\n";
    callInTuple< START - 1, INDEX >( );
  }
};

template< int START >
struct callInTuple< START, START > {
  constexpr callInTuple( ) {
    std::cout << START << '\n';
  }
};

int main( ) {
  callInTuple< 111, 99 >( );

  return 0;
}

    The above code produces the following output :

    Intentando con 111, fallido
Intentando con 110, fallido
Intentando con 109, fallido
Intentando con 108, fallido
Intentando con 107, fallido
Intentando con 106, fallido
Intentando con 105, fallido
Intentando con 104, fallido
Intentando con 103, fallido
Intentando con 102, fallido
Intentando con 101, fallido
Intentando con 100, fallido
99
    • 5