Recursion using template meta programming

Question

Can somebody explain to me, why the first call using the template function is falling into an infinite loop, while the second compile-time function runs correctly?

#include <iostream>
using namespace std;

template<int N, int M>
struct commondivs {                                              
  static const int val = (N<M) ? commondivs<N,(M-N)>::val : commondivs<(N-M),M>::val;
};

template<int N>
struct commondivs<N,N> {
  static const int val = N;
};


int commondiv(int N, int M){
    if(N==M){
        return N;
    }   
    return (N<M)?commondiv(N,(M-N)):commondiv((N-M),M);     
}

int main() {

    cout << commondivs<9,6>::val << endl;
    cout << commondiv(9,6) << endl;
    return 0;
}

Possible duplicate of Replacement for ternary operator in template metaprogramming — L. F.
– L. F., Commented Nov 25, 2019 at 15:11
The goal was to used template meta programming. constexpr is not an option. — Exxul
– Exxul, Commented Nov 25, 2019 at 15:26
Added c++98 tag to make explicit that constexpr is not an option. (It was introduced in C++11). That does invalidate existing answers. Exxul, please clarify which C++ version you're limited to. — MSalters
– MSalters, Commented Nov 26, 2019 at 16:55

HolyBlackCat · Accepted Answer · 2019-11-25 15:27:05Z

45

(N<M) ? commondivs<N,(M-N)>::val : commondivs<(N-M),M>::val

This line causes instantiation of both commondivs<N,(M-N)>::val and commondivs<(N-M),M>::val, even if the condition is known at compile time and one of the branches will never be taken.

Replace ? : with std::conditional_t, which doesn't have this limitation:

static const int val = std::conditional_t<N < M, commondivs<N,(M-N)>, commondivs<(N-M),M>>::val;

answered Nov 25, 2019 at 15:27

HolyBlackCat

102k13 gold badges182 silver badges306 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

songyuanyao · Accepted Answer · 2019-11-26 13:59:29Z

16

The problem is all the operands of conditional operator will be evaluated, so both commondivs<N,(M-N)> and commondivs<(N-M),M> get instantiated and their val get evaluated and then leads to recursive template instantiation.

You can apply constexpr if and put it in a constexpr static member function.

If the value is true, then statement-false is discarded (if present), otherwise, statement-true is discarded.

template<int N, int M>
struct commondivs {                                              
  constexpr static int get_val() {
    if constexpr (N<M) return commondivs<N,(M-N)>::val; // if true, the else part won't be evaluated
    else return commondivs<(N-M),M>::val;               // vice versa
  }
  static const int val = get_val();
};

LIVE

edited Nov 26, 2019 at 13:59

answered Nov 25, 2019 at 15:20

songyuanyao

174k16 gold badges327 silver badges432 bronze badges

3 Comments

Daniel McLaury Over a year ago

Evaluated or just instantiated?

songyuanyao Over a year ago

@DanielMcLaury Evaluated; not just instantiated.

Useless Over a year ago

The value of ::val has to be generated on both branches sure, but this is still instantiation (of a template with a static const member). Evaluation at run time does not happen ... well, it obviously can't since it never compiles ...

Evg · Accepted Answer · 2019-11-25 15:50:05Z

The ternary operator is not like if constexpr: when a compiler sees it, it has to generate code for both branches. In other words, to instantiate a template commondivs<M, N>, a compiler instantiates both templates commondivs<N, M - N> and commondivs<N - M, M>.

In contrast to that, commondiv(N, M - N) and commondiv(N - M, M) are translated into two function calls. Which one is taken, will be decided when the function is actually called.

Addition.

HolyBlackCat gave a solution with std::conditional_t. Here is another one:

template<int N, int M>
struct commondivs {                                              
    static constexpr int min = (N < M) ? N : M;
    static constexpr int max = (N < M) ? M : N;
    static constexpr int val = commondivs<min, max - min>::val;
};

template<int N>
struct commondivs<N, N> {
    static constexpr int val = N;
};

Paul Evans · Accepted Answer · 2019-11-25 15:27:12Z

0

You get infinite recursion because:

static const int val = (N<M) ? commondivs<N,(M-N)>::val : commondivs<(N-M),M>::val;

isn't metatemplate programming at all because ?:, as @Eng says, isn't constexpr.

You want to look at @HolyBlackCat's answer.

edited Nov 25, 2019 at 15:27

answered Nov 25, 2019 at 15:16

Paul Evans

27.7k3 gold badges41 silver badges56 bronze badges

2 Comments

Evg Over a year ago

It won't help. ?: is not constexpr.

Exxul Over a year ago

No I try it. The same infinite loop.

Collectives™ on Stack Overflow

Recursion using template meta programming

4 Answers 4

Comments

3 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related