پیاده سازی تابع Median به صورت generic

Question

سلام به همگی.

خیلی فکر کردم که تایعی به صورت generic بنویسم که Median را محاسبه کنه میخوام جوری باشه مثلاً بشه روی متغیر های عضو کلاس یا struct هم میانه را محاسبه کرد.

آیا کسی همچین کاری انجام داده؟ که بتونه یه راهنمایی کوچیک یا سر نخ بده به من.

Answer 1

اگر قصد دارید متعیر های عضو کلاس بر پایه آنها median گرفته شه و generic هم باشه به عبارتی این پارامتر را به صورت عبارت lambda وارد کنید بایستی پارامتر مورد نظر به صورت std::function تعریف شه.به صورت زیر.

 std::function<bool(int)> func

مابقی پارامترها نیز فرستادن iterator به تابع Median هستش.

	template <typename InputIterator, typename T>
	double MedianEx(InputIterator  src_begin, InputIterator  src_end, std::function<T(IteratorType<InputIterator>)> func){

		using U = typename std::iterator_traits<InputIterator>::value_type;
		size_t count = std::distance(src_begin, src_end);
		sort(src_begin, src_end, [&](U a, U b){return func(a) < func(b); });

		double median;

		if (count % 2 == 0)
			median = (func(*(src_begin + (count / 2 + 1))) + func(*(src_begin + (count / 2)))) / 2.f;
		else median = func(*(src_begin + (count / 2)));


		return median;
	}

 

Answer 2

به این شکل هم قابل انجام هست :

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

template<class T>
struct Null_Function{
	const T& operator()(const T& t)const{
		return t;
	}
};

template <typename IT>
using is_const_iterator =
	std::is_const<typename std::remove_reference<typename std::iterator_traits<IT>::reference>::type>;


template <typename Iterator, typename Func = Null_Function<typename std::iterator_traits<Iterator>::value_type>>
typename std::enable_if<
	 	   !is_const_iterator<Iterator>::value,
		   typename std::iterator_traits<Iterator>::value_type>::type
	 Median(Iterator src_begin, Iterator src_end, Func func = Func()) {
		using value_type = typename std::iterator_traits<Iterator>::value_type;
		size_t count = std::distance(src_begin, src_end);
		std::nth_element(src_begin, src_begin + (count / 2), src_end,
			[&](value_type a, value_type b) { return func(a) < func(b); });
		return count > 0 ? func(*(src_begin + (count / 2))) : 0;
}

template <typename ConstIterator, typename Func = Null_Function<typename std::iterator_traits<ConstIterator>::value_type>>
typename std::enable_if<
		 is_const_iterator<ConstIterator>::value,
		 typename std::iterator_traits<ConstIterator>::value_type>::type
	 Median(ConstIterator src_begin, ConstIterator src_end, Func func = Func()) {
		using value_type = typename std::iterator_traits<ConstIterator>::value_type;
		std::vector<value_type> src_cpy(src_begin, src_end);
		auto src_cpy_begin = src_cpy.begin();
		auto src_cpy_end = src_cpy.end();

		size_t count = std::distance(src_cpy_begin, src_cpy_end);
		std::nth_element(src_cpy_begin, src_cpy_begin + (count / 2), src_cpy_end,
			[&](value_type a, value_type b) { return func(a) < func(b); });
		return count >0 ? func(*(src_cpy_begin + (count / 2))) : 0;
}

int main()
{
	const std::vector<double> arr = { 5, 2, 32, 11, 7, 8, 9 };
	std::cout << Median(arr.begin(), arr.end());//use second overload slower

	std::vector<double> arr2 = { 5, 2, 32, 11, 7, 8, 9 };
	std::cout << Median(arr2.begin(), arr2.end());//use first overload (find median inplace ) faster

	std::vector<double> arr3 = { 5, 2, 32, 11, 7, 8, 9 };
	std::cout << Median(arr3.begin(), arr3.end(), [](const double& a){
		return a / 2;
	});//use function pointer
}

 

اجرا کد بالا 

 

در کد بالا overload اول برای زمان هایی هست که ورودی تابع غیر const باشه و بدون کپی با (O(n مدیان برگشت داده میشه .

ولی overload دوم برای ورودی های const هست. زمانی که ورودی const باشه یک کپی قبل از استفاده از std::nth_element گرفته میشه .