Saat mempelajari C++ Anda menemukan template cara yang keren untuk membuat fungsi dan kelas generik tetapi ini C++, ayolah Anda bisa melakukan lebih dari itu, template C++ sobat, jangan berhenti di kelas & fungsi saja, ini adalah dunia lain, the dunia liar pemrograman meta templat. Tapi bagaimanapun Anda hanya ingin mahir dalam template C++, jangan khawatir, saya menyajikan masalah template C++ yang layak, ini disebut 'Nomor Peano'.
Anda dapat melanjutkan dan menyelesaikannya di sini Nomor Peano.
Sebelumnya, jangan googling, jangan stackoverflow, jangan chatgpt-it, jangan kode llama-it pokoknya kamu paham.
Cobalah sendiri, buang waktu sampai kamu berhasil atau merasa terhina lalu verifikasi solusinya.
Larutan
Kamu menyerah ? 😒
Tidak dapat memikirkan solusinya? Besar
Tidak perlu malu untuk mencoba, saya juga berjuang dengan masalah ini.
Jadi kita punya titik awal
struct Peano {};
struct Zero: Peano {};
template<class T>
struct Succ: Peano {};
Ini menyerupai 0 dan angka yang lebih besar atau sama dengan 1 sehingga kita dapat mewakili angka apa pun.
Mari kita uraikan ini dan fokus pada bagian yang lebih kecil karena saya melakukannya dengan cara templat, pertama-tama saya perlu memiliki gambaran tentang apa yang terjadi dan bagaimana saya akan mendekati masalah tersebut.
Menerapkan tambahan
template <class T1, class T2> struct Add {};
Jadi sekarang, bagaimana saya bisa melakukan ini? Saya tidak bisa menggunakan operator bawaan atau bilangan bulat.
Saya harus mengandalkan template yang ditawarkan oleh sihir C++.
Baiklah, Pak template C++ :
- Anda dapat melakukan spesialisasi template
- Anda dapat berperilaku seperti pencocokan pola tetapi untuk tipe
- Anda dapat melakukan rekursi
Karena saya tidak bisa menggunakan operator, saya sangat terbatas jadi saya harus kreatif dengan ini, saya tahu saya memerlukan rekursi untuk mengulangi operasi dan spesialisasi template untuk membuat pengecualian bagaimana kompiler harus berperilaku ketika memenuhi kriteria tertentu.
Mari kita lihat bagaimana saya bisa menggunakan spesialisasi template, menurut soal 1 dan 0 direpresentasikan sebagai 'Succ‹Zero›' dan 'Zero' kita dapat membungkus sebanyak 'Succ' yang kita bisa untuk merepresentasikan sebuah digit, itu adalah penjumlahan dasar dengan 1 bagaimana dengan pengurangan dengan 1 ?
Saya kira saya bisa melakukan yang sebaliknya dan membuka nomor bagian dalamnya.
template <class T1, class T2> struct Add {};
template <class T1, class T2> struct Add<T1, Succ<T2>> {};
Sekarang kita punya T1 yang merupakan angka dan T2 yang merupakan angka-1 lainnya.
Saya melihat sesuatu di sini. Kalau dipikir-pikir, saya bisa merepresentasikan penjumlahan sebagai pengurangan 1 dari operan kanan dan menambahkan 1 ke operan kiri.
Bagaimana jika saya terus menambahkan 1 dan mengurangi 1 hingga operan kanan adalah 'Nol' Saya rasa saya mengerti. Dengan templat C++ yang bersifat rekursif, saya dapat memanggil operasi yang sama berulang kali dan bertindak sebagai perulangan.
Fantastis.
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;
};
Rekursi woopse tanpa titik berhenti ya… mari kita tambahkan di mana ia harus berhenti.
Karena kita tidak berurusan dengan bilangan negatif, kita bisa berhenti ketika operan kedua bernilai Nol.
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;
};
Dan sekarang waktunya untuk pengujian sesungguhnya.
C++ memiliki serangkaian utilitas untuk menangani template yang ditentukan dalam header '‹type_traits›'.
di header type_traits saya memerlukan “std::is_same_v‹T1, T2›” yang memeriksa apakah T1 dan T2 bertipe sama dan menghasilkan nilai benar atau salah.
#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';
}
mengkompilasi dan menjalankan kode berikut memberi kita:
1 1 1
1 untuk benar dan 0 untuk salah (kita dapat menggunakan std::boolalpha untuk menampilkan nilai boolean)
Sejauh ini! keren semuanya berfungsi. Sekarang dengan pikiran itu saya bisa menjalankan perkalian & pengurangan dan pembagian hanyalah barisan pengurangan juga menilai ganjil & genap dan menerapkan seluruh operasi aritmatika, kalkulus, aljabar, mekanika kuantum juga.
Menerapkan Pengurangan
Baiklah, mari kita coba pengurangan. Masalahnya menyarankan kita memeriksa kesalahan jika hasilnya negatif.
template <class T1, class T2> struct Sub {};
Sedangkan untuk penjumlahan saya terus membungkus operan kiri dalam Succ N kali hingga operan kedua mencapai Nol.
Untuk pengurangan saya dapat melakukan hal yang sama tetapi dengan membuka bungkus operan kiri sebanyak N kali hingga operan kedua mencapai Nol.
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;
};
Tapi saya harus menangani kasus di mana operan pertama mencapai Nol sebelum operan kanan, dengan menambahkan jenis kesalahan dan menyetelnya ke Negatif ketika operan pertama adalah Nol dan NoError ketika operasi dapat diselesaikan tanpa kesalahan.
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;
};
Kali ini saya menggunakan subkelas dan tidak menentukan `tipe` secara eksplisit karena saya tidak ingin memberikan nilai ketika ada kesalahan Negatif.
sekarang mari kita coba dan lihat apakah hasilnya benar.
#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
dan voila berhasil!
Menerapkan Perkalian
Sekarang untuk Perkalian boi besar, kamu sudah tahu apa yang harus kita tuliskan perkalian sebagai penjumlahan.
4 * 3 adalah 4 + 4 + 4
5 * 7 adalah 5 + 5 + 5 + 5 + 5 + 5 + 5
2 * 4 adalah 2 + 2 + 2 + 2
Saya dapat melihat polanya di sini. Kita menjaga operan pertama tetap konstan dan menambahkannya ke dirinya sendiri sebanyak N kali (N = nilai operan kedua) seperti Penjumlahan & Pengurangan
Mari kita tuliskan dalam fungsi.
int multiply(int a, int b) {
int c = a;
for(int i = 1; i < b; ++i) {
c += a;
}
return c;
}
berfungsi dengan baik tetapi kita tidak dapat memiliki loop for di templat yang kita miliki hanyalah rekursi, mari kita gunakan rekursi saja
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
Namun implementasi ini mungkin melakukan perhitungan lebih banyak dari yang diperlukan jika b atau a adalah 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);
}
menerjemahkan ini dalam templat C++ memberi.
#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;
};
pengujian
#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';
}
Mengkompilasi ini memberi kita
true true true true true true
???
Ini dia untuk bagian 1 dan jika Anda belum mengetahuinya, Anda dapat mencoba menyelesaikan sisanya sendiri.
