9
\$\begingroup\$

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.

\$\endgroup\$
15
  • 2
    \$\begingroup\$ std::midpoint was added in C++20, I believe. \$\endgroup\$ Jun 7, 2021 at 15:23
  • 1
    \$\begingroup\$ Having a difference that's a distinct type from a position is normally part of an affine space. Browsing that, I see the definition doesn't include scalar multiplication (which I thought was part of it) so that might be a good name. T is an affine_point. \$\endgroup\$
    – JDługosz
    Jun 7, 2021 at 20:38
  • 1
    \$\begingroup\$ I mean, you require forward iterators, but ban (via requires (!std::bidirectional_iterator<T>)) bidi iterators so, for example, std::list::iterator won’t work with any overload. Why ban bidi iterators? \$\endgroup\$
    – indi
    Jun 8, 2021 at 19:55
  • 1
    \$\begingroup\$ Heh. You got it. 👍 \$\endgroup\$
    – indi
    Jun 8, 2021 at 20:26
  • 1
    \$\begingroup\$ @jdt, it might look out of place, but that's the standard way to fall back to std::swap if no more specific swap() function is found during argument-dependent lookup. \$\endgroup\$ Nov 30, 2021 at 12:58

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The std::array overload was to some extent a sample, but also a basis for geometric vector types which might use std::array as storage. Overloading for std::vector is generally less useful - and we're not able to compile-time ensure that they have equal lengths as we can for arrays. \$\endgroup\$ Jun 8, 2021 at 19:52
  • \$\begingroup\$ Thanks for the heads-up on sentinels. I think I'll want to use std::ranges::distance(a, b) to handle that transparently. I'll re-think the split between "main" and "iterator" overloads now. \$\endgroup\$ Jun 8, 2021 at 20:22
3
\$\begingroup\$
  • _ 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; }
\$\endgroup\$
5
  • \$\begingroup\$ "Identifiers that start with an underscore are reserved in the global scope". I'd always believed that only identifiers that start with underscore followed by a letter or another underscore are reserved - thanks for picking up on that. \$\endgroup\$ Jun 7, 2021 at 16:09
  • \$\begingroup\$ Would it be better to just dispense with the isnan() check, since it's an unlikely path, and the arithmetic gives the correct result anyway? \$\endgroup\$ Jun 7, 2021 at 16:10
  • 2
    \$\begingroup\$ @TobySpeight Yes, I would remove the isnan check since the rest of the function doesn't rely on that. I did check with GCC and clang. None seems to elide that check either. \$\endgroup\$ Jun 7, 2021 at 16:15
  • \$\begingroup\$ It looks like I can use _ as a namespace identifier within my own namespace. \$\endgroup\$ Jun 7, 2021 at 16:28
  • \$\begingroup\$ A nested detail namespace is not in the global scope. Putting any simple name at global scope is asking for a clash as libraries and other code is combined. It's odd that his "private details" namespace is not nested but stand-alone -- that would be better off using his name. \$\endgroup\$
    – JDługosz
    Jun 7, 2021 at 19:40

Your Answer

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

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