Как сохранить промежуточные результаты рекурсивной функции с использованием шаблонов C++ во время компиляции?

Question

Я спросил How do I capture the results of a recursive function at compile-time?, но я думаю, что мой подход был неправильным.

У меня есть программа, как так:

#include <iostream> 
#include <list> 

std::list<unsigned int> recursive_case(std::list<unsigned int>& result, unsigned int& i) { 
    result.push_front(1 + (i % 10)); 
    i /= 10; 
    return i != 0 ? recursive_case(result, i) : result; 
} 

std::list<unsigned int> initial_case(unsigned int i) { 
    std::list<unsigned int> result; 
    result.push_back(i % 10); 
    i /= 10; 
    return i != 0 ? recursive_case(result, i) : result; 
} 

int main() { 
    auto list = initial_case(123); 
    bool first = true; 
    for (auto i: list) { 
     if (first) { 
      first = false; 
     } else { 
      std::cout << ", "; 
     } 
     std::cout << i; 
    } 
    std::cout << std::endl; 
} 

Выход является 2, 3, 3.

Я хочу выполнить вышеуказанное вычисление и получить тот же результат, но в компиляции-времени (итерация цикла и печать на выходе будут во время выполнения, то есть все, начиная с цикла for). Шаблоны кажутся возможными (вот почему я пометил этот вопрос как таковой), но я открыт для всего, что выполняет работу во время компиляции.

Answer 1

Вот одно из решений.

#include <iostream> 

// Print one digit. 
template <unsigned int N, bool Initial> struct AtomicPrinter 
{ 
    static void print() 
    { 
     std::cout << N%10; 
    } 
}; 

template <unsigned int N> struct AtomicPrinter<N, false> 
{ 
    static void print() 
    { 
     std::cout << 1 + N%10 << ", "; 
    } 
}; 

// Recursive printer for a number 
template <unsigned int N, bool Initial> struct Printer 
{ 
    static void print() 
    { 
     Printer<N/10, false>::print(); 
     AtomicPrinter<N, Initial>::print(); 
    } 
}; 

// Specialization to end recursion. 
template <bool TF> struct Printer<0, TF> 
{ 
    static void print() 
    { 
    } 
}; 

void printList() 
{ 
    Printer<123, true>::print(); 
    std::cout << std::endl; 
} 

int main() { 
    printList(); 
} 

Если есть необходимость отделить печать цифры от построения списка цифр, вы можете использовать:

#include <iostream> 
#include <list> 

template <unsigned int N, bool Initial> struct Digit 
{ 
    static void get(std::list<int>& l) 
    { 
     l.push_back(N%10); 
    } 
}; 

template <unsigned int N> struct Digit<N, false> 
{ 
    static void get(std::list<int>& l) 
    { 
     l.push_back(1 + N%10); 
    } 
}; 

template <unsigned int N, bool Initial> struct Digits 
{ 
    static void get(std::list<int>& l) 
    { 
     Digits<N/10, false>::get(l); 
     Digit<N, Initial>::get(l); 
    } 
}; 

template <bool TF> struct Digits<0, TF> 
{ 
    static void get(std::list<int>& l) 
    { 
    } 
}; 

void printList() 
{ 
    std::list<int> l; 
    Digits<123, true>::get(l); 
    bool first = true; 
    for (auto i: l) { 
     if (first) { 
     first = false; 
     } else { 
     std::cout << ", "; 
     } 
     std::cout << i; 
    } 
    std::cout << std::endl; 
} 

int main() { 
    printList(); 
} 

Answer 2

Вы можете использовать constexpr вычислить список во время компиляции. Я преобразовал рекурсию в итерацию и использовал indices trick для вызова calculate столько раз, сколько необходимо.

#include <iostream> 
#include <array> 
#include <iterator> 
#include <utility> 

constexpr std::size_t count_digits(std::size_t N, std::size_t Count = 0) 
{ 
    return (N > 0) ? count_digits(N/10, Count+1) : Count; 
} 

constexpr std::size_t ipow(std::size_t N, std::size_t Base) 
{ 
    return (N > 0) ? Base*ipow(N-1,Base) : 1; 
} 

constexpr std::size_t calculate(std::size_t n, std::size_t i) 
{ 
    std::size_t p = ipow(i,10); 
    std::size_t t = (n/p) % 10; 
    return i > 0 ? (t+1) : t; 
} 

template<std::size_t Num, std::size_t C, std::size_t... Is> 
constexpr std::array<std::size_t, C> build_list(std::index_sequence<Is...>) 
{ 
    return {{ calculate(Num, C-Is-1)... }}; 
} 

template <std::size_t Num, std::size_t C = count_digits(Num)> 
constexpr auto build_list() 
{ 
    return build_list<Num, C>(std::make_index_sequence<C>{}); 
} 


int main() 
{ 
    constexpr auto list = build_list<123>(); 

    for(auto e : list) 
    { 
     std::cout << e << " "; 
    } 

    return 0; 
} 

выход:

2 3 3 

live example

Answer 3

Вы можете использовать что-то вроде следующего, чтобы разделить число во время компиляции:

#include <utility> 
#include <iostream> 

template <char... Cs> 
std::integer_sequence<char, Cs...> operator "" _seq() { return {}; } 

template <char...Cs> 
void print(std::integer_sequence<char, Cs...>) 
{ 
    const char* sep = ""; 
    for (const auto& c : {Cs...}) { 
     std::cout << sep << c; 
     sep = ", "; 
    } 
} 

int main() { 
    auto seq = 123_seq; 
    print(seq); 
} 

Demo