Programs & Examples
Operator Overloading · Study material
Fibonacci numbers with an overloaded matrix multiplication
Once a 2×2 matrix type has operator*, fast exponentiation works on it like on numbers, giving F(n) in O(log n) steps.
#include <array>
#include <iostream>
struct Mat2 {
std::array<long, 4> a; // [0 1; 2 3]
Mat2 operator*(const Mat2& o) const {
return {{a[0] * o.a[0] + a[1] * o.a[2], a[0] * o.a[1] + a[1] * o.a[3],
a[2] * o.a[0] + a[3] * o.a[2], a[2] * o.a[1] + a[3] * o.a[3]}};
}
bool operator==(const Mat2&) const = default;
};
Mat2 power(Mat2 m, int n) { // fast exponentiation, using only operator*
Mat2 r{{1, 0, 0, 1}};
while (n) {
if (n & 1) r = r * m;
m = m * m;
n >>= 1;
}
return r;
}
int main() {
Mat2 fib{{1, 1, 1, 0}};
for (int n : {10, 30, 50}) std::cout << "F(" << n << ") = " << power(fib, n).a[1] << '\n';
std::cout << (power(fib, 2) == fib * fib) << '\n';
return 0;
}
F(10) = 55 F(30) = 832040 F(50) = 12586269025 1
A 2D vector type with arithmetic and printing
The first example in the introduction shows the core arithmetic operators, unary minus, equality and stream output for a small value type.
Sorting with the spaceship operator
The comparison example shows a defaulted <=> for version numbers and a custom one that sorts students by marks, then name.