Computing truncated mean between two forward indicators

Question

I have already computed the truncated mean of a vector via the function truncated_mean(std::vector& v, double trimming fraction). This function takes as inputs the vector v and the fraction that we want to remove to calculate the mean (e.g. 10% so we remove the highest and lowest 10% values and then we compute the mean), I created it using the Standard Library.

For example, v = [0,1,2....,9], then truncated_mean(v, 0.10) = 4.5.

Now, I want to reuse the same function but instead of having v as input, I want to have 2 forward iterators, v.begin() and v.end(). I am provided with the template of typename forward that I should use to check if its value_type (accessed via std::iterator_traits) meets a certain criteria. My understanding of the problem is that first I need to check if the inputs belong to a vector and from there I should access the vector in itself to compute the truncated mean.

How can I adapt my function to take as input the beginning and end of the vector rather than the vector itself?

Answer 1

Assuming sequence passed in is sorted you could simply use std::distance to figure out the length and skip the appropriate number of elements at the start and the end:

Edit: Extended code to use std::accumulate for random access iterators; Use concepts instead of distinguishing iterator types vis additional parameter, if you're allowed to use C++20 features.

template<typename RandomAccessIterator>
double truncated_mean_impl(RandomAccessIterator begin, RandomAccessIterator end, double trimming_fraction, std::random_access_iterator_tag)
{
    if (trimming_fraction < 0)
    {
        throw std::range_error("trimming_fraction must not be negative");
    }
    if(trimming_fraction >= 0.5)
    {
        return std::numeric_limits<double>::quiet_NaN(); // no elements left after trimming
    }

    auto const count = std::distance(begin, end);
    auto const skippedElementCountFront = static_cast<decltype(count)>(count * trimming_fraction);
    auto const summandCount = count - 2 * skippedElementCountFront;

    return std::accumulate<RandomAccessIterator, double>(begin + skippedElementCountFront, end - skippedElementCountFront, 0) / summandCount;
}


template<typename ForwardIterator>
double truncated_mean_impl(ForwardIterator begin, ForwardIterator end, double trimming_fraction, std::forward_iterator_tag)
{
    if (trimming_fraction < 0)
    {
        throw std::range_error("trimming_fraction must not be negative");
    }
    if(trimming_fraction >= 0.5)
    {
        return std::numeric_limits<double>::quiet_NaN(); // no elements left after trimming
    }

    auto const count = std::distance(begin, end);

    auto const skippedElementCountFront = static_cast<decltype(count)>(count * trimming_fraction);
    
    // skip elements in the front
    for (auto i = skippedElementCountFront; i != 0; --i, ++begin) {}

    auto const summandCount = count - 2 * skippedElementCountFront;

    double sum = 0;

    for (auto i = summandCount; i != 0; --i, ++begin)
    {
        sum += *begin;
    }

    return sum / summandCount;
}

template<typename ForwardIterator>
double truncated_mean(ForwardIterator begin, ForwardIterator end, double trimming_fraction)
{
    return truncated_mean_impl<ForwardIterator>(begin, end, trimming_fraction, typename std::iterator_traits<ForwardIterator>::iterator_category());
}

int main()
{
    std::vector<int> const values  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << truncated_mean(values.cbegin(), values.cend(), 0.1) << '\n';
}

If the input sequence is not sorted and you cannot or don't want to sort the input copying the elements to a new vector and applying your original algorithm to this vector would probably be best.