Изучая C++, вы столкнулись с шаблонами, отличным способом создания общих функций и классов, но это C++, да ладно, вы можете сделать больше, чем просто это, шаблоны C++, мой друг, не останавливайтесь на простых классах и функциях, это другой мир, дикий мир метапрограммирования шаблонов. Но в любом случае вы просто хотите хорошо освоить шаблоны C++, не волнуйтесь, я представляю вам приличную задачу по шаблонам C++, она называется «Числа Пеано».
Вы можете решить ее здесь Числа Пеано.
Прежде всего, не гуглите, не переполняйте стек, не пишите gpt-это, не кодируйте лама-это в любом случае вы меня понимаете.
Попробуйте сами, потратьте время, пока не добьетесь успеха. или получите унижение, а затем проверьте решение.
Решение
Ты сдался? 😒
Не могли придумать обходной путь? Большой
Не стыдно пытаться, я тоже боролся с этой проблемой.
Итак, у нас есть отправная точка
struct Peano {}; struct Zero: Peano {}; template<class T> struct Succ: Peano {};
Это похоже на 0 и числа, большие или равные 1, поэтому мы можем представлять любое число.
Давайте разберем это и сосредоточимся на более мелких разделах, поскольку я делаю это по шаблону, сначала мне нужно иметь представление о том, что происходит. и как я собираюсь подойти к проблеме.
Реализация добавления
template <class T1, class T2> struct Add {};
Итак, как я могу это сделать? Я не могу использовать встроенные операторы и целые числа.
Мне приходится полагаться на магию шаблонов, которую может предложить C++.
Хорошо, мистер шаблоны C++:
- вы можете сделать специализацию шаблона
- вы можете вести себя как сопоставление с образцом, но для типов
- ты можешь сделать рекурсию
Поскольку я не могу использовать оператор, я очень ограничен, поэтому мне нужно подойти к этому творчески, я знаю, что мне нужна рекурсия для повторения операции и специализация шаблона для создания исключений того, как должен вести себя компилятор при удовлетворении определенных критериев.
Давайте посмотрим, как я могу использовать специализацию шаблона, согласно задаче 1 и 0 представлены как 'Succ‹Zero><' и 'Zero', мы можем обернуть столько же 'Succ', поскольку мы можем представить цифру, это простое сложение на 1, а как насчет вычитания на 1?
Думаю, я могу сделать наоборот и развернуть внутреннее число.
template <class T1, class T2> struct Add {}; template <class T1, class T2> struct Add<T1, Succ<T2>> {};
Теперь у нас есть T1 — число, и T2 — еще одно число — 1.
Я тут кое-что вижу. Если задуматься, я могу представить сложение как вычитание 1 из правого операнда и прибавление 1 к левому операнду.
Что, если я буду продолжать прибавлять 1 и вычитать 1, пока правый операнд не станет «Ноль». Думаю, у меня получилось. Поскольку шаблоны C++ являются рекурсивными, я могу снова и снова вызывать одну и ту же операцию, действуя как цикл.
Фантастика.
template <class T1, class T2> struct Add {}; template <class T1, class T2> struct Add<T1, Succ<T2>> { using type = typename Add<Succ<T1>, T2>::type; };
Какая-то рекурсия без точки остановки, да… давайте добавим, где она должна остановиться.
Поскольку мы не имеем дело с отрицательными числами, мы можем просто остановиться, когда второй операнд равен нулю.
template <class T1, class T2> struct Add {}; template <class T1, class T2> struct Add<T1, Succ<T2>> { using type = typename Add<Succ<T1>, T2>::type; }; template <class T1> struct Add<T1, Zero> { using type = T1; };
А теперь пришло время настоящего теста.
В C++ есть набор утилит для работы с шаблонами, определенными в заголовке '‹type_traits›'.
В заголовке type_traits мне нужно «std::is_same_v‹T1, T2>>», который проверяет, относятся ли T1 и T2 к одному и тому же типу, и возвращает true или false.
#include <type_traits> #include <iostream> template <class T1, class T2> struct Add {}; template <class T1, class T2> struct Add<T1, Succ<T2>> { using type = typename Add<Succ<T1>, T2>::type; }; template <class T1> struct Add<T1, Zero> { using type = T1; }; int main() { using One = Succ<Zero>; using Two = Succ<One>; using Three = Succ<Two>; std::cout << std::is_same_v<typename Add<One, One>::type, Two> << '\n'; // compare two types std::cout << std::is_same_v<typename Add<Two, One>::type, Three> << '\n'; std::cout << std::is_same_v<typename Add<One, Three>::type, Two> << '\n'; }
компиляция и запуск следующего кода дает нам:
1 1 1
1 для true и 0 для false (вместо этого мы можем использовать std::boolalpha для вывода логических значений)
Пока! круто все работает. Теперь, обладая этим умом, я могу заставить работать умножение и вычитание, а деление - это просто последовательность вычитания, а также оценивать нечетность и четность и доходить до реализации целых арифметических операций, исчисления, алгебры и квантовой механики.
Реализация вычитания
Хорошо, давайте попробуем вычитание. Проблемы предполагают, что мы проверим наличие ошибок в случае, если результаты будут отрицательными.
template <class T1, class T2> struct Sub {};
Что касается сложения, я продолжаю оборачивать левый операнд в Succ N раз, пока второй операнд не достигнет нуля.
Для вычитания я могу сделать то же самое, но с разворачиванием левого операнда N раз, пока второй операнд не достигнет нуля.
template <class T1, class T2> struct Sub {}; template <class T1, class T2> struct Sub<Succ<T1>, Succ<T2>> { using type = typename Sub<T1, T2>::type; }; template <class T1> struct Sub<T1, Zero> { using type = T1; };
Но мне приходится обрабатывать случай, когда первый операнд достигает нуля раньше правильного, добавляя тип ошибки и устанавливая для него значение «Отрицательный», когда первый операнд равен «Нулю», и «Нет ошибок», когда операция может быть завершена без ошибок.
template <class T1, class T2> struct Sub {}; template <class T1, class T2> struct Sub<Succ<T1>, Succ<T2>>: Sub<T1, T2> {}; template <class T1> struct Sub<T1, Zero> { using error = NoError; using type = T1; }; template <class T2> struct Sub<Zero, Succ<T2>> { using error = Negative; };
На этот раз я использовал подкласс и не указал явно `тип`, потому что я не хочу предоставлять значение при отрицательной ошибке, поэтому.
теперь давайте попробуем посмотреть, показывает ли он правильный результат.
#include <ios> #include <type_traits> template <class T1, class T2> struct Sub {}; template <class T1, class T2> struct Sub<Succ<T1>, Succ<T2>>: Sub<T1, T2> {}; template <class T1> struct Sub<T1, Zero> { using error = NoError; using type = T1; }; template <class T2> struct Sub<Zero, Succ<T2>> { using error = Negative; }; int main() { using One = Succ<Zero>; using Two = Succ<One>; using Three = Succ<Two>; using Four = Succ<Three>; std::cout << std::boolalpha; std::cout << std::is_same_v<typename Sub<One, One>::type, Zero> << '\n'; std::cout << std::is_same_v<typename Sub<Two, One>::type, One> << '\n'; std::cout << std::is_same_v<typename Sub<Four, Two>::type, Two> << '\n'; std::cout << std::is_same_v<Sub<Zero, Two>::error, Negative> << '\n'; } true true true true
и вуаля, это работает!
Реализация умножения
Теперь что касается большого умножения, вы знаете, что давайте запишем умножение как сложение.
4 * 3 равно 4 + 4 + 4
5 * 7 равно 5 + 5 + 5 + 5 + 5 + 5 + 5
2 * 4 — это 2 + 2 + 2 + 2
Здесь я вижу закономерность. Мы сохраняем первый операнд константой и добавляем его к самому себе N раз (N = значение второго операнда), что-то вроде сложения и вычитания
Давайте запишем это в функциях.
int multiply(int a, int b) { int c = a; for(int i = 1; i < b; ++i) { c += a; } return c; }
работает отлично, но мы не можем использовать циклы for в шаблонах, все, что у нас есть, это рекурсия, давайте вместо этого будем использовать рекурсию
int multiply(int a, int b) { if(b == 1) return a; return a + multiply(a, b - 1); } // multiply(4, 3) => 4 + multiply(4, 2) => 4 + 4 + multiply(4, 1) => 4 + 4 + 4 = 12
Однако эта реализация может выполнять больше вычислений, чем необходимо, если b или a равно 0.
int multiply(int a, int b) { if(b == 1) return a; if(b == 0) return 0; return a + multiply(a, b - 1); } // or even better int multiply(int a, int b) { if(b == 0 || a == 0) return 0; return a + multiply(a, b - 1); }
перевод этого в шаблоны C++ дает.
#include<type_traits> template <class T1, class T2> struct Mul {}; template <class T1, class T2> struct Mul<T1, Succ<T2>> { using type = std::conditional_t<std::is_same_v<T1, Zero>, Zero, typename Add<T1, typename Mul<T1, T2>::type>::type>; // std::condtitional_t here works like if(a == 0) return 0 }; // if (b == 0) return 0 template <class T1> struct Mul<T1, Zero> { using type = Zero; };
тестирование
#include<type_traits> #include<ios> template <class T1, class T2> struct Mul {}; template <class T1, class T2> struct Mul<T1, Succ<T2>> { using type = std::conditional_t<std::is_same_v<T1, Zero>, Zero, typename Add<T1, typename Mul<T1, T2>::type>::type>; // std::condtitional_t here works like if(a == 0) return 0 }; // if (b == 0) return 0 template <class T1> struct Mul<T1, Zero> { using type = Zero; }; int main() { using One = Succ<Zero>; using Two = Succ<One>; using Three = Succ<Two>; using Four = Succ<Three>; std::cout << std::boolalpha; std::cout << std::is_same_v<typename Mul<One, One>::type, One> << '\n'; std::cout << std::is_same_v<typename Mul<Two, One>::type, Two> << '\n'; std::cout << std::is_same_v<typename Mul<Four, Zero>::type, Zero> << '\n'; std::cout << std::is_same_v<typename Mul<Zero, Zero>::type, Zero> << '\n'; std::cout << std::is_same_v<typename Mul<Zero, Two>::type, Zero> << '\n'; std::cout << std::is_same_v<typename Mul<Two, Two>::type, Four> << '\n'; }
Компиляция этого дает нам
true true true true true true
???
Это часть первой части, и если вы еще не разобрались, вы можете попробовать решить оставшуюся часть самостоятельно.