Pythagorean Triples Code

Range-V3要進C++20 Standard，看了一下他給的範例

Pythagorean triple如何印出前十組Pythagorean triple

從最簡單的方案開始看

Direct Method

#include <stdio.h>

int main() {
	int i = 0;
	for (int z = 1; true; ++z) {
		for (int x = 1; x < z; ++x) {
			for (int y = x; y < z; ++y) {
				if (x * x + y * y == z * z) {
					printf("(%d,%d,%d)\n", x, y, z);
					if (++i == 10) goto done;
				}
			}
		}
	}
done:;
}

不會很難理解，必須迴圈外部維護一個狀態，當狀態滿足之後強行離開迴圈

Callback Solution

#include <iostream>
#include <tuple>
#include <type_traits>

template<class F>
auto boolify(F& f) {
	return [&](auto&&... args) {
		using R = decltype(f(std::forward<decltype(args)>(args)...));
		if constexpr (std::is_void_v<R>) {
			f(std::forward<decltype(args)>(args)...);
			return false;
		}
		else {
			return f(std::forward<decltype(args)>(args)...);
		}
	};
}

template<class F>
void generate_triples(F f) {
	for (int z = 1; true; ++z) {
		for (int x = 1; x < z; ++x) {
			for (int y = x; y < z; ++y) {
				if (x*x + y * y == z * z) {
					bool stop = boolify(f)(std::make_tuple(x, y, z));
					if (stop) return;
				}
			}
		}
	}
}

template<class F>
auto take(int k, F f) {
	return [f, i = k](auto x) mutable -> bool {
		return (i-- == 0) || boolify(f)(x);
	};
}

int main() {
	generate_triples(
		take(10,
			[&](auto triple) {
				std::cout << '('
					<< std::get<0>(triple) << ','
					<< std::get<1>(triple) << ','
					<< std::get<2>(triple) << ')' << '\n';
			}
		)
	);
}

這個難看懂很多
首先程式主體

template<class F>
void generate_triples(F f) {
	for (int z = 1; true; ++z) {
		for (int x = 1; x < z; ++x) {
			for (int y = x; y < z; ++y) {
				if (x*x + y * y == z * z) {
					bool stop = boolify(f)(std::make_tuple(x, y, z));
					if (stop) return;
				}
			}
		}
	}
}

是沒壁的，我們的中止條件就在 take(10, ...)這個函數之間
一旦滿足條件，整個genertat4e_tyiples就結束了
我們看看 take的實作

template<class F>
auto take(int k, F f) {
	return [f, i = k](auto x) mutable -> bool {
		return (i-- == 0) || boolify(f)(x);
	};
}

我們把state包含在lambda之中，避免被外界汙染
至於boolify這個函數不重要，不影響分析

這個版本比起上面那個，邏輯切個更清晰
不過複雜度也跟著增加了

Coroutine Solution

隨著C++20加入stackless coroutine，這個問題也可以用coroutine來解

#include <iostream>
#include <tuple>
#include <experimental/coroutine>

template<class T>
struct generator {
	struct promise_type;
	using handle = std::experimental::coroutine_handle<promise_type>;
	struct promise_type {
		T current_value;
		auto get_return_object() { return generator{ handle::from_promise(*this) }; }
		auto initial_suspend() { return std::experimental::suspend_always{}; }
		auto final_suspend() { return std::experimental::suspend_always{}; }
		void unhandled_exception() { std::terminate(); }
		void return_void() {}
		auto yield_value(T value) {
			current_value = value;
			return std::experimental::suspend_always{};
		}
	};
	bool move_next() { return coro ? (coro.resume(), !coro.done()) : false; }
	T current_value() { return coro.promise().current_value; }
	generator(generator const&) = delete;
	generator(generator && rhs) : coro(rhs.coro) { rhs.coro = nullptr; }
	~generator() { if (coro) coro.destroy(); }
private:
	generator(handle h) : coro(h) {}
	handle coro;
};

auto triples() -> generator<std::tuple<int, int, int>> {
	for (int z = 1; true; ++z) {
		for (int x = 1; x < z; ++x) {
			for (int y = x; y < z; ++y) {
				if (x*x + y * y == z * z) {
					co_yield std::make_tuple(x, y, z);
				}
			}
		}
	}
}

int main() {
	auto g = triples();
	for (int i = 0; i < 10; ++i) {
		g.move_next();
		auto triple = g.current_value();
		std::cout << '('
			<< std::get<0>(triple) << ','
			<< std::get<1>(triple) << ','
			<< std::get<2>(triple) << ')' << '\n';
	}
}

由於coroutine還是新玩意，目前對他的掌握度不適很高，這個方案僅供參考

Range-V3 Solution

// A sample standard C++20 program that prints
// the first N Pythagorean triples.
#include <iostream>
#include <optional>
#include <range/v3/all.hpp>
 
using std::get;
using std::optional;
using std::make_tuple;
using std::cout;
using ranges::view_interface;
using ranges::iterator_t;
namespace view = ranges::v3::view;

// maybe_view defines a view over zero or one
// objects.
template<class T>
struct maybe_view : view_interface<maybe_view<T>> {
  maybe_view() = default;
  maybe_view(T t) : data_(std::move(t)) {
  }
  T const *begin() const noexcept {
    return data_ ? &*data_ : nullptr;
  }
  T const *end() const noexcept {
    return data_ ? &*data_ + 1 : nullptr;
  }
private:
  optional<T> data_{};
};
 
// "for_each" creates a new view by applying a
// transformation to each element in an input
// range, and flattening the resulting range of
// ranges.
// (This uses one syntax for constrained lambdas
// in C++20.)
inline constexpr auto for_each =
  [](auto&& r, auto fun) {
      return decltype(r)(r)
        | view::transform(std::move(fun))
        | view::join;
  };
 
// "yield_if" takes a bool and a value and
// returns a view of zero or one elements.
inline constexpr auto yield_if =
  [](bool b, auto x) {
    return b ? maybe_view{std::move(x)}
             : maybe_view<decltype(x)>{};
  };
 
int main() {
  // Define an infinite range of all the
  // Pythagorean triples:
  using view::iota;
  auto triples =
    for_each(iota(1), [](int z) {
      return for_each(iota(1, z+1), [=](int x) {
        return for_each(iota(x, z+1), [=](int y) {
          return yield_if(x*x + y*y == z*z,
            make_tuple(x, y, z));
        });
      });
    });
 
    // Display the first 10 triples
    for(auto triple : triples | view::take(10)) {
      cout << '('
           << get<0>(triple) << ','
           << get<1>(triple) << ','
           << get<2>(triple) << ')' << '\n';
  }
}

看起來還不錯，不過編譯時間嚇死人…
目前還是先考慮方案一或二吧，三和四等掌握度高一點再說