1
\$\begingroup\$

This is a follow-up question for A Summation Function For Various Type Arbitrary Nested Iterable Implementation in C++, An arithmetic_mean Function For Various Type Arbitrary Nested Iterable Implementation in C++, A non-nested test_vectors_generator Function for arithmetic_mean Function Testing in C++ and Non-nested std::deque and std::list Generator Function for arithmetic_mean Function Testing in C++. Besides calculating summation and arithmetic mean value of arbitrary nested iterable, I am trying to implement an arithmetic_variance function which can calculate population variance value with the following formula.

is population variance value of x, is the value of i-th element, is the population mean which is calculated by arithmetic_mean template function and N is the population size which is calculated by recursive_size function (refer to the previous question A recursive_count Function For Various Type Arbitrary Nested Iterable Implementation in C++).

The usage description

The input of population_variance template function is a arbitrary Nested Iterable. For example, given a test_vector: std::vector<double> test_vector{ 1, 2, 3, 4, 5 };. The population_variance template function can be called like this std::cout << "population_variance: " << population_variance(test_vector) << std::endl; and the output is

population_variance: 2

The experimental implementation

The experimental implementation of population_variance template function is here.

//  population_variance function implementation
template<class T1, class T2>
requires (is_iterable<T1> && is_recursive_reduceable<T1> && is_recursive_sizeable<T1> && is_minusable2<std::iter_value_t<T1>, T2>)
// non-recursive version
auto _population_variance(const T1& input, const T2 arithmetic_mean_result)
{
    return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [arithmetic_mean_result](auto& element) {
        return std::pow(element - arithmetic_mean_result, 2);
        });
}

template<class T1, class T2>
requires (is_iterable<T1> && is_elements_iterable<T1> && is_recursive_reduceable<T1> && is_recursive_sizeable<T1>)
auto _population_variance(const T1& input, const T2 arithmetic_mean_result)
{
    return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [arithmetic_mean_result](auto& element) {
        return _population_variance(element, arithmetic_mean_result);
        });
}

template<class T>
requires (is_recursive_reduceable<T> && is_recursive_sizeable<T>)
auto population_variance(const T& input)
{
    return _population_variance(input, arithmetic_mean(input)) / (recursive_size(input));
}

The used is_iterable, is_elements_iterable, is_recursive_reduceable, is_recursive_sizeable and is_minusable2 concepts are as below.

template<typename T>
concept is_iterable = requires(T x)
{
    *std::begin(x);
    std::end(x);
};

template<typename T>
concept is_elements_iterable = requires(T x)
{
    std::begin(x)->begin();
    std::end(x)->end();
};

template<typename T>
concept is_recursive_reduceable = requires(T x)
{
    recursive_reduce(x, 0.0);
};

template<typename T>
concept is_recursive_sizeable = requires(T x)
{
    recursive_size(x);
};

template<typename T>
concept is_minusable = requires(T x) { x - x; };

template<typename T1, typename T2>
concept is_minusable2 = requires(T1 x1, T2 x2) { x1 - x2; };

The implementation of the used arithmetic_mean function:

template<class T> requires (is_recursive_reduceable<T> && is_recursive_sizeable<T>)
auto arithmetic_mean(const T& input)
{
    return (recursive_reduce(input, 0.0)) / (recursive_size(input));
}

The implementation of the used recursive_size function:

//  recursive_size implementation
template<class T> requires (!is_iterable<T>)
auto recursive_size(const T& input)
{
    return 1;
}

template<class T> requires (!is_elements_iterable<T> && is_iterable<T>)
auto recursive_size(const T& input)
{
    return input.size();
}

template<class T> requires (is_elements_iterable<T>)
auto recursive_size(const T& input)
{
    return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [](auto& element) {
        return recursive_size(element);
        });
}

Test cases

A more complex example is like:

//  std::vector<std::vector<int>> case
std::vector<double> test_vector{ 1, 2, 3, 4, 5 };
std::cout << "recursive_size of test_vector: " << recursive_size(test_vector) << std::endl;
std::cout << "population_variance of test_vector: " << population_variance(test_vector) << std::endl;

std::vector<decltype(test_vector)> test_vector2;
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);

std::cout << "recursive_size of test_vector2: " << recursive_size(test_vector2) << std::endl;
std::cout << "population_variance of test_vector2: " << population_variance(test_vector2) << std::endl;

auto test_vector3 = n_dim_container_generator<10, std::vector, decltype(test_vector)>(test_vector, 3);
std::cout << "recursive_size of test_vector3: " << recursive_size(test_vector3) << std::endl;
std::cout << "population_variance of test_vector3: " << population_variance(test_vector3) << std::endl;

The used n_dim_container_generator template function is as follows. Thanks to G. Sliepen's answer.

template<std::size_t dim, template<class...> class Container = std::vector, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        return Container(times, n_dim_container_generator<dim - 1, Container, T>(input, times));
    }
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Consider using namespace detail to make functions private

Names starting with an underscore in the global namespace are reserved by the C++ language. In general, avoid starting any name with an underscore unless you really want to memorize all the rules surrounding them. The typical solution C++ libraries use to make things "private" in header-only libraries is to introduce a namespace detail in which they put private variables, functions and classes. So:

namespace detail {

template<class T1, class T2> requires ...
// non-recursive version
auto population_variance(const T1& input, const T2 arithmetic_mean_result) {...}

template<class T1, class T2> requires ...
auto population_variance(const T1& input, const T2 arithmetic_mean_result) {...}

}

template<class T> requires (is_recursive_reduceable<T> && is_recursive_sizeable<T>)
auto population_variance(const T& input)
{
    return detail::population_variance(...) / ...;
}

Use the correct types

The whole point of writing templates is so that they work with different types. This means you have to be careful to hardcode types, or to use literal constants of the wrong type. For example, in your code, you have:

return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [arithmetic_mean_result](auto& element) {...});

Here you force the accumulator to be of std::size_t. But what if I want to calculate the mean and variance of floating point values between 0.0 and 1.0? Everything would be cast to std::size_t in your code, making the final result 0 no matter what. You should ensure the type matches that of the values stored in the nested container.

For the detail::population_variance() functions which take a parameter with the mean, I would just use the type of the mean:

template<class T1, class T2> requires ...
auto population_variance(const T1& input, const T2 mean)
{
    return std::transform_reduce(std::begin(input), std::end(input), T2{}, std::plus<T2>(), [mean](auto& element) {
        return std::pow(element - mean, 2);
    });
}

So now the problem is in arithmetic_mean(). There you have:

return (recursive_reduce(input, 0.0)) / (recursive_size(input));

The literal 0.0 forces the result to be double. This might be OK, it probably is what you want even if the input is a nested container of integers, but it might also be wrong. Consider that the values in the container might be a std::complex, or some other custom type? Maybe the concept of variance doesn't make sense anymore for these types, but that means you have to make a decision:

  1. Only accept containers of value types that have a mean and variance that can be accurately described by a double.
  2. Deduce the value type of the nested container and use that type for the initial value.
  3. Allow the user to specify the type used to represent the mean and variance.

The STL typically lets the caller specify the type of the result in some way, usually by taking a parameter for the initial value. That of course doesn't make sense for arithmetic_mean and population_variance, but then I would use a template parameter for that. Unfortunately, you cannot have a default value for a template parameter that depends on a subsequent parameter, so I think this is the best compromise:

template<class T = double, class Container> requires ...
auto arithmetic_mean(const Container& input)
{
    return recursive_reduce(input, T{}) / recursive_size(input);
}

template<class T = double, class Container> requires ...
auto population_variance(const Container& input)
{
    return detail::population_variance(input, arithmetic_mean<T>(input)) / recursive_size(input);
}

Use of concepts

Try to reduce the number of concepts used in the requires statements. Also, if the concepts are very specific and use derived types, as in:

requires (... && is_minusable2<std::iter_value_t<T1>, T2>)

Then if this fails the error message will probably be as crytped as if you did not require this concept and the error would occur in the body of the instantiated template.

You should first use concepts to ensure the right template variant is chosen, and for that you just need is_elements_iterable to distinguish between the recursive and non-recursive variants. Everything else is just to give a better error message. In this case, I would just write one concept that checks whether the given value type can have the variance calculated of:

template<typename T>
concept can_calculate_variance_of(const T& value)
{
    (std::pow(value, 2) - value) / std::size_t{1};
}

Also, you shouldn't check for those requirements in detail::population_variance(), but rather in the public population_variance() function. Otherwise, the error will still happen inside the body of population_variance(), and will be more cryptic than necessary. So ideally you want something like:

template<class T>
requires (... && can_calculate_variance_of<recursive_iter_value_t<T>>)
auto population_variance(const T& input)
{
    return detail::population_variance(input, arithmetic_mean(input)) / recursive_size(input);
}

Cleaner way to handle recursion

In this case it is not necessary to have both detail::population_variance() functions call std::transform_reduce(). That looks like unnecessary repetition. You can instead write:

namespace detail
{

template<class T1, class T2>
requires (!is_iterable<T1>)
auto population_variance(const T1& input, const T2 mean)
{
    return std::pow(input - mean, 2);
}

template<class T1, class T2>
auto population_variance(const T1& input, const T2 mean)
{
    return std::transform_reduce(std::begin(input), std::end(input), T2{}, std::plus<T2>(), [mean](auto& element) {
        return population_variance(element, mean);
    });
}

}

But perhaps even better would be to have a recursive_transform_reduce(), so you can get rid of the detail functions and replace the public function with:

template<class T, class Container>
requires (...)
auto population_variance(const Container& input)
{
    auto mean = arithmetic_mean<T>(input);
    return recursive_transform_reduce(input, T{}, std::plus<T>(), [mean](auto &element) {
        return std::pow(element - mean, 2);
    }) / recursive_size(input);
}
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.