Find the mean of two values

Question

A very easily stated problem that has a surprising number of gotchas - return a value that's midway between the two supplied values.

Depending on the types given, we need to be aware of

• arithmetic overflow and underflow
• infinities
• NaNs
• rounding

For pointers and iterators, the mean only makes sense if the values point into the same object; the results are otherwise undefined. For forward-only iterators, the arguments need to be in the correct order; for other types, either order is accepted.

For aggregate types, we just need to compute the mean element-wise. I've provided code for arrays and complex numbers; third-party aggregates (e.g. "point" and "vector" geometric types) can be implemented by following the existing pattern.

I expect the template to work unaltered for other arithmetic classes (e.g. bignum and rational types).

#include <cmath>
#include <concepts>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <utility>

namespace std {
    template<typename T> class complex;
    template<typename T, std::size_t N> class array;
}

namespace _
{
    template<typename T>
    concept arithmetic = std::regular<T> && requires(T a, T b) {
        a + (b - a); a < b;
    };

    template<arithmetic T>
    T midpoint(T a, T b)
    {
        if (a == b) {
            // this ensures infinities are correctly returned
            return a;
        }

        if constexpr (std::is_floating_point_v<T>) {
            if (std::isnan(a)) { return a; }
            if (std::isnan(b)) { return b; }
        }

        if constexpr (std::is_arithmetic_v<T>) {
            if ((a < 0) != (b < 0)) {
                return (a + b) / 2;
            }
        }

        if (a > b) {
            using std::swap;
            swap(a, b);
        }

        return a + (b - a) / 2;
    }

    // Non-random-access iterators
    // a MUST be before b
    template<std::forward_iterator T>
    requires (!std::bidirectional_iterator<T>)
    T midpoint(T a, T b)
    {
        bool skip = false;
        T mid = a;
        while (a != b) {
            ++a;
            if (!skip) { ++mid; }
            skip = !skip;
        }
        return mid;
    }

    // Aggregate types follow
    // Pattern can be extended, e.g. for popular geometry types

    template<arithmetic T>
    std::complex<T> midpoint(std::complex<T> a, std::complex<T> b)
    {
        return {
            midpoint(a.real(), b.real()),
            midpoint(a.imag(), b.imag())
        };
    }

    template<arithmetic T, std::size_t N>
    std::array<T,N> midpoint(const std::array<T,N>& a, const std::array<T,N>& b)
    {
        std::array<T,N> result;
        for (std::size_t i = 0;  i < N;  ++i) {
            result[i] = midpoint(a[i], b[i]);
        }
        return result;
    }
}

using _::midpoint;

// Tests

#include <gtest/gtest.h>

#include <climits>
TEST(midpoint, int)
{
    EXPECT_EQ(midpoint(0, 0), 0);
    EXPECT_EQ(midpoint(0, 1), 0);
    EXPECT_EQ(midpoint(0, 2), 1);
    EXPECT_EQ(midpoint(1, 3), 2);
    EXPECT_EQ(midpoint(4, 1), 2);
    EXPECT_EQ(midpoint(INT_MIN, 0), INT_MIN/2);
    EXPECT_EQ(midpoint(INT_MAX, 0), INT_MAX/2);
    EXPECT_EQ(midpoint(INT_MAX, -INT_MAX), 0);
}

#include <limits>
TEST(midpoint, double)
{
    static constexpr auto inf = std::numeric_limits<double>::infinity();
    static constexpr auto nan = std::numeric_limits<double>::quiet_NaN();
    EXPECT_EQ(midpoint(0.0, 0.0), 0.0);
    EXPECT_EQ(midpoint(1.0, 2.0), 1.5);
    EXPECT_EQ(midpoint(1.0, inf), inf);
    EXPECT_EQ(midpoint(1.0, -inf), -inf);
    EXPECT_EQ(midpoint(inf, inf), inf);
    EXPECT_EQ(midpoint(-inf, -inf), -inf);
    EXPECT_TRUE(std::isnan(midpoint(inf, -inf)));
    EXPECT_TRUE(std::isnan(midpoint(nan, 0.0)));
    EXPECT_TRUE(std::isnan(midpoint(0.0, nan)));
    EXPECT_TRUE(std::isnan(midpoint(nan, nan)));
}

#include <complex>
TEST(midpoint, complex)
{
    auto const a = std::complex{2,10};
    auto const b = std::complex{0,20};
    auto const c = std::complex{1,15};
    EXPECT_EQ(midpoint(a, b), c);
}

TEST(midpoint, pointer)
{
    auto const s = "_abcdefghijklmnopqrstuvwxyz";
    EXPECT_EQ(midpoint(s+1, s+25), s+13);
    EXPECT_EQ(midpoint(s+25, s+1), s+13);
}

#include <string_view>
TEST(midpoint, iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    EXPECT_EQ(*midpoint(s.begin(), s.end()), 'n');
    EXPECT_EQ(*midpoint(s.end(), s.begin()), 'n');
}

#include <forward_list>
TEST(midpoint, forward_iterator)
{
    auto const s = std::string_view{"abcdefghijklmnopqrstuvwxyz"};
    auto const l = std::forward_list(s.begin(), s.end());
    EXPECT_EQ(*midpoint(l.begin(), l.end()), 'n');
}

#include <array>
TEST(midpoint, std_array)
{
    auto const a = std::array{ 0, 10, 20};
    auto const b = std::array{10, 10, 10};
    auto const c = std::array{5, 10, 15};
    EXPECT_EQ(midpoint(a, b), c);
}

I've intentionally included some questionable choices:

• _ as a namespace name is legal, but is it a good choice for the implementation-private namespace?
• I believe I can forward-declare the template classes that belong to std, rather than drag in their entire headers.
• The arithmetic concept has very similar name to std::is_arithmetic - could/should I change that?
• The unit-tests still pass if I remove the early exit for NaN inputs, but should I retain them anyway? (The checks were once needed, but refactoring them has left them redundant).
• In the first test case, I assume that -INT_MAX is valid - could that legally overflow?

I didn't yet enclose the code in a namespace - I would do that when I add include guards and make it a header.

Answer 1

Missing check for > in concept arithmetic

Your concept arithmetic checks for <, in your code you are using both < and > to compare values of type T. Either check that both operators are supported, or use if (!(a < b)) to check if you need to swap values.

Consider not adding an overload for std::array

You added an overload for computing the midpoint of a std::array, however that raises some questions. For example, if you do this, why are you not also supporting std::vector and other types as well? And is element-wise midpoint always the desired operation?

Instead of adding yet more overloads, I would just avoid these questions by omitting this overload, and let the caller do it themselves. They can do this easily using std::transform or similar algorithms, for example:

std::vector<float> a{1, 2.718, 3.1415};
std::vector<float> b{9, 42, 1729};
std::vector<float> c;
std::transform(a.begin(), a.end(), b.begin(), std::back_inserter(c), midpoint);

Pass parameters by const reference

I would pass parameters by const reference whenever possible in templates. An optimizing compiler will make this as fast as passing by value for small types, but for more complex types, especially thoses with non-trivial constructors, it might be forced to make expensive copies if you pass by value.

Be aware of C++20 iterator sentinels

C++20 allows ranges to have an end() iterator that has a different type than the begin() iterator. You might want to support that for your overload that works on iterators. You can use the std::sentinel_for concept to restrict the type of b.

Answer 2

• _ as a namespace name is legal, but is it a good choice for the implementation-private namespace?

This causes undefined behavior. Identifiers that start with an underscore are reserved in the global scope.

• I believe I can forward-declare the template classes that belong to std, rather than drag in their entire headers

Adding forward declarations to std is undefined behavior. Just include the appropriate headers instead.

---

if (std::isnan(a)) { return a; }
if (std::isnan(b)) { return b; }

This could be simplified to:

if (std::isnan(a) || std::isnan(b)) { return NAN; }