C++ 11 ошибка компилятора функции constexpr с тернарным условным оператором (? :)

Question

Что не так с этим фрагментом кода?

#include <iostream> 

template<unsigned int N, unsigned int P=0> 
constexpr unsigned int Log2() { 
    return (N <= 1) ? P : Log2<N/2,P+1>(); 
} 

int main() 
{ 
    std::cout << "Log2(8) = " << Log2<8>() << std::endl; 
    return 0; 
} 

При компиляции с gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5), я получаю следующее сообщение об ошибке:

log2.cpp: In function ‘constexpr unsigned int Log2() [with unsigned int N = 0u, unsigned int P = 1023u]’: 
log2.cpp:5:38: error: template instantiation depth exceeds maximum of 1024 (use -ftemplate-depth= to increase the maximum) instantiating ‘constexpr unsigned int Log2() [with unsigned int N = 0u, unsigned int P = 1024u]’ 
log2.cpp:5:38: recursively instantiated from ‘constexpr unsigned int Log2() [with unsigned int N = 4u, unsigned int P = 1u]’ 
log2.cpp:5:38: instantiated from ‘constexpr unsigned int Log2() [with unsigned int N = 8u, unsigned int P = 0u]’ 
log2.cpp:10:37: instantiated from here 

Answer 1

Constexpr не работает таким образом.

Проще говоря, функции constexpr также должны быть доступны как функции выполнения. Представьте, что вы взяли constexpr из функции. Тогда подумайте, почему он не может работать.

Причина в том, что компилятор должен полностью создать тело функции; он не может решить на основании условия в ?: не создавать экземпляры с одной стороны. Поэтому он всегда должен создавать экземпляр рекурсивного вызова, приводя к бесконечной рекурсии.

В любом случае вы используете constexpr неправильно. Вы используете метод вычисления метапрограмм старого шаблона (передавая материал в качестве параметров шаблона), когда constexpr был предназначен для его замены. Просто используйте обычные параметры.

constexpr unsigned Log2(unsigned n, unsigned p = 0) { 
    return (n <= 1) ? p : Log2(n/2, p + 1); 
} 

std::cout << "Log2(8) = " << Log2(8) << std::endl; 

Edit: Я постараюсь уточнить, как это работает.

Когда компилятор встречает ваш код, он анализирует функцию шаблона и сохраняет его в форме шаблона. (Как это работает, отличается от компиляторов.) Пока все в порядке.

Далее, в main, компилятор видит вызов Log2<8>(). Он видит, что он должен создать экземпляр шаблона, поэтому он идет вперед и делает именно это: он создает экземпляр Log2<8, 0>. Тело шаблона функции заключается в следующем:

return (N <= 1) ? P : Log2<N/2,P+1>(); 

OK, компилятор видит это, но он не пытается оценить его. Почему? В настоящее время создается экземпляр шаблона, а не вычисляется значение. Он просто заменяет приведенные значения:

return (8 <= 1) ? 0 : Log2<8/2,0+1>(); 

Да, здесь есть еще один экземпляр шаблона. Не имеет значения, что это в условном выражении или что левая сторона может быть известна. Создание экземпляра шаблона должно быть полным. Таким образом, она идет вперед и вычисляет значения для нового экземпляра, а затем конкретизирует Log2<4, 1>:

return (4 <= 1) ? 1 : Log2<4/2,1+1>(); 

И игра начинается снова. Там в шаблон создания экземпляра там, и это Log2<2, 2>:

return (2 <= 1) ? 2 : Log2<2/2,2+1>(); 

И снова, Log2<1,3>():

return (1 <= 1) ? 3 : Log2<1/2,3+1>(); 

Я уже говорил о том, что компилятор не заботится о смысловом значении этого материала?Это просто еще один шаблон для создания экземпляра: Log2<0,4>:

return (0 <= 1) ? 4 : Log2<0/2,4+1>(); 

Log2<0,5> А потом:

return (0 <= 1) ? 5 : Log2<0/2,5+1>(); 

И так далее, и так далее. В какой-то момент компилятор понимает, что он никогда не останавливается и не сдаётся. Но ни в коем случае не говорит: «Подождите, условие этого тернарного оператора ложно, мне не нужно создавать экземпляр правой части». Это потому, что стандарт C++ не позволяет это делать. Тело функции должно создаваться полностью.

Теперь посмотрите на мое решение. Нет шаблона. Есть только функция. Компилятор видит это и говорит: «Эй, вот функция. Удивительно, позвольте мне поставить вызов этой функции здесь». И затем в какой-то момент (возможно, это может произойти значительно позже, в зависимости от компилятора), он может (но не вынужден в этом случае) сказать: «Эй, подожди, эта функция constexpr и я знайте значения параметров, позвольте мне оценить это ». Теперь он идет дальше и оценивает Log2(8, 0). Помните, тело:.

return (n <= 1) ? p : Log2(n/2, p + 1); 

«OK», компилятор говорит: «Я просто хочу знать, что эта функция возвращает Давайте посмотрим, 8 <= 1 является ложным, так что смотрите на правой стороне Log2(4, 1), да Впусти меня.? Посмотрите на это. OK, 4 <= 1 также неверно, поэтому он должен быть Log2(2, 2). Что это такое, 2 <= 1? Также неверно, так что это Log2(1, 3). Привет, 1 <= 1 правда, поэтому позвольте мне взять 3 и вернуть его. стек вызовов."

Итак, он приходит с ответом 3. Он не переходит в бесконечную рекурсию, потому что он оценивает функцию с полным знанием ценностей и семантики, а не просто тупо наращивает АСТ.

Я надеюсь, что это поможет.

Answer 2

Как уже говорилось, компилятор не оценивает условное выражение, такое как if/else или тройной оператор ?:. Тем не менее, есть еще способ сделать это условное время выражение компиляции:

#include <cstddef>  // size_t is shorter than unsigned int, it's a matter of taste in this case 
#include <iostream> // to show our results 
#include <type_traits> // needed for the mighty std::enable_if 

template<size_t N, size_t P = 0> 
constexpr typename std::enable_if<(N <= 1), size_t>::type Log2() 
{ 
    return P; 
} 

template<size_t N, size_t P = 0> 
constexpr typename std::enable_if<!(N <= 1), size_t>::type Log2() 
{ 
    return Log2<N/2, P + 1>(); 
} 

int main() 
{ 
    std::cout << Log2<1>() << "\n"; 
    std::cout << Log2<2>() << "\n"; 
    std::cout << Log2<4>() << "\n"; 
    std::cout << Log2<8>() << "\n"; 
    std::cout << Log2<16>() << "\n"; 
} 

Что это делает весьма очевидным: если N <= 1, первая ветвь должна быть оценена, таким образом Log2<0, P>() и Log2<1, P>() следует оценивать в P. Если N <= 1, верхний метод включен, так как этот заголовок функции действителен. Для всего остального, то есть N >= 2 или !(N <= 1), нам необходимо выполнить повтор, который выполняется вторым методом.