c++ - وظيفة قالب مضروب دون التخصص قالب




templates recursion (2)

المشكلة هنا هي أن عبارة if هي عبارة عن بناء لوقت التشغيل. عندما يكون لديك 

int f() {
  if (N == 1) return 1; // we exit the recursion at 1 instead of 0
  return N*f<N-1>();
}

يتم إنشاء مثيل لـ f<N-1> حيث يمكن استدعاؤه. على الرغم من أن شرط if سيوقفه عن استدعاء f<0> ، لا يزال على المحول البرمجي إنشاء مثيل له لأنه جزء من الوظيفة. هذا يعني أنه يشبه f<4> ، والذي يشبه f<3> ، والذي يشبه f<2> ، وسيستمر تشغيله إلى الأبد.

تتمثل طريقة Pre C ++ 17 لإيقاف هذا في استخدام تخصص لـ 0 الذي يكسر هذه السلسلة. بدءًا من C ++ 17 باستخدام constexpr if ، لم تعد هناك حاجة لذلك. عن طريق 

int f() {
  if constexpr (N == 1) return 1; // we exit the recursion at 1 instead of 0
  else return N*f<N-1>();
}

يضمن return N*f<N-1>(); لن يوجد حتى في الحالة 1 ، لذلك لا تستمر في النزول في فتحة أرانب مثيل.

أنا لا أفهم السلوك التالي.

التعليمات البرمجية التالية ، التي تهدف إلى حساب العامل في وقت الترجمة ، لا يتم تجميعها حتى: 

#include <iostream>
using namespace std;
template<int N>
int f() {
  if (N == 1) return 1; // we exit the recursion at 1 instead of 0
  return N*f<N-1>();
}
int main() {
  cout << f<5>() << endl;
  return 0;
}

ويلقي الخطأ التالي: 

...$ g++ factorial.cpp && ./a.out 
factorial.cpp: In instantiation of ‘int f() [with int N = -894]’:
factorial.cpp:7:18:   recursively required from ‘int f() [with int N = 4]’
factorial.cpp:7:18:   required from ‘int f() [with int N = 5]’
factorial.cpp:15:16:   required from here
factorial.cpp:7:18: fatal error: template instantiation depth exceeds maximum of 900 (use ‘-ftemplate-depth=’ to increase the maximum)
    7 |   return N*f<N-1>();
      |            ~~~~~~^~
compilation terminated.

بينما ، عند إضافة التخصص لـ N == 0 (الذي لا يصل القالب أعلاه) ، 

template<>
int f<0>() {
  cout << "Hello, I'm the specialization.\n";
  return 1;
}

يتم تجميع الشفرة وإعطاء الإخراج الصحيح لـ ، حتى إذا لم يتم استخدام التخصص: 

...$ g++ factorial.cpp && ./a.out 
120

المشكلة هي أن f<N>() دائمًا ما ينشأ عن f<N-1>() ما إذا كان ذلك إذا تم أخذ الفرع أم لا. ما لم يتم إنهاؤها بشكل صحيح ، سيؤدي ذلك إلى إنشاء تكرار غير محدود في وقت التحويل البرمجي (أي أنه سيحاول إنشاء مثيل لـ F<0> ، ثم f<-1> ، ثم f<-2> وهكذا). من الواضح أنه يجب عليك إنهاء تلك العودية بطريقة أو بأخرى.

بصرف النظر عن حل constexpr والتخصص الذي اقترحه NathanOliver ، يمكنك إنهاء العودية بشكل صريح: 

template <int N>
inline int f()
{
    if (N <= 1)
        return 1;
    return N * f<(N <= 1) ? N : N - 1>();
}

ضع في اعتبارك أن هذا الحل ضعيف إلى حد ما (يجب تكرار نفس الحالة الطرفية مرتين) ، أكتب هذه الإجابة فقط لإظهار أن هناك دائمًا طرق أكثر لحل المشكلة: -)




c++   templates   recursion   template-specialization   factorial  


factorial