Generic implementation of median #2: Follow up

Question

Follow on from this codereview:

generic implementation of median

As before the vector2 class is just for illustrative purposes and not the focus.

I have incorporated all the excellent feedback from G.Sliepen from previous codereview linked above:

• 2 versions median() and median_in_place(). The former makes a copy.
• constrain inputs with concepts
• simpler syntax for default input parameters
• provides overloads which accept a range
• uses a projection parameter - no more extract
• uses std::invoke to support member functions
• uses std::midpoint for a safer average

Two main questions:

1. Use of concepts: It is "best/preferable" to constrain each of the wrappers as shown below, ie median() wraps median_in_place() and concepts are used at both levels. This is somewhat repetitive, but has subtle differences. Or would it be better, to use Duck typing for the wrappers and only put concept constraints on the main, inner function. Discuss.
2. Would it be helpful to specify the return types using trailing return syntax? If so, I was unable to find a syntax which works. I suspect, I failed because I needed one or more of std::remove_cv or std::remove_const or std::decay. How to do that? Or not worth it? Discuss.

#include <algorithm>
#include <cmath>
#include <exception>
#include <iostream>
#include <iterator>
#include <numeric>
#include <ostream>
#include <ranges>
#include <stdexcept>
#include <vector>
#include <list>

template <typename T>
class vector2 {
public:
  T x{};
  T y{};

  constexpr vector2(T x_, T y_) : x(x_), y(y_) {}

  constexpr vector2() = default;

  [[nodiscard]] T       mag() const { return std::hypot(x, y); }
  [[nodiscard]] vector2 norm() const { return *this / this->mag(); }
  [[nodiscard]] double  dot(const vector2& rhs) const { return x * rhs.x + y * rhs.y; }

  // clang-format off
  vector2& operator+=(const vector2& obj) { x += obj.x; y += obj.y; return *this; }
  vector2& operator-=(const vector2& obj) { x -= obj.x; y -= obj.y; return *this; }
  vector2& operator*=(const double& scale) { x *= scale; y *= scale; return *this; }
  vector2& operator/=(const double& scale) { x /= scale; y /= scale; return *this; }
  // clang-format on

  friend vector2 operator+(vector2 lhs, const vector2& rhs) { return lhs += rhs; }
  friend vector2 operator-(vector2 lhs, const vector2& rhs) { return lhs -= rhs; }
  friend vector2 operator*(vector2 lhs, const double& scale) { return lhs *= scale; }
  friend vector2 operator*(const double& scale, vector2 rhs) { return rhs *= scale; }
  friend vector2 operator/(vector2 lhs, const double& scale) { return lhs /= scale; }

  friend std::ostream& operator<<(std::ostream& os, const vector2& v) {
    return os << '[' << v.x << ", " << v.y << ']';
  }
};

using vec2  = vector2<double>;
using vec2I = vector2<int>;

template <typename RandomAccessIter, typename Comp = std::ranges::less,
          typename Proj = std::identity>
requires std::random_access_iterator <RandomAccessIter> && std::sortable<RandomAccessIter, Comp, Proj>
auto median_in_place(RandomAccessIter first, RandomAccessIter last, const Comp& comp = {},
                     const Proj& proj = {}) {

  auto size = std::distance(first, last);
  if (size == 0) throw std::domain_error("Can't find median of an empty range.");

  auto middle = first + (size / 2);

  std::ranges::nth_element(first, middle, last, comp, proj);

  if (size % 2 == 1) return std::invoke(proj, *middle);

  auto below_middle = std::ranges::max_element(first, middle, comp, proj);

  return std::midpoint(std::invoke(proj, *middle), std::invoke(proj, *below_middle));
}

template <typename RandomAcccessRange, typename Comp = std::less<>, typename Proj = std::identity>
requires std::ranges::random_access_range<RandomAcccessRange> &&
    std::sortable<typename RandomAcccessRange::iterator, Comp, Proj>
auto median_in_place(RandomAcccessRange& range, const Comp& comp = {}, const Proj& proj = {}) {
  return median_in_place(range.begin(), range.end(), comp, proj);
}

template <typename InputIter, typename Comp = std::ranges::less, typename Proj = std::identity>
requires std::input_iterator<InputIter> &&
    std::sortable<typename std::vector<std::iter_value_t<InputIter>>::iterator, Comp, Proj>
auto median(InputIter first, InputIter last, const Comp& comp = {}, const Proj& proj = {}) {
  std::vector<std::iter_value_t<InputIter>> input_copy(first, last); // always make a copy
  return median_in_place(input_copy.begin(), input_copy.end(), comp, proj);
}

template <typename InputRange, typename Comp = std::less<>, typename Proj = std::identity>
requires std::ranges::input_range<InputRange> &&
    std::sortable<typename std::vector<std::ranges::range_value_t<InputRange>>::iterator, Comp,
                  Proj>
auto median(const InputRange& range, const Comp& comp = {}, const Proj& proj = {}) {
  return median(range.begin(), range.end(), comp, proj);
}

template <typename T>
void print(const std::vector<T>& v) {
  std::cout << "[";
  char delim[2]{}; // NOLINT char[] OK here
  for (const auto& e: v) {
    std::cout << static_cast<char*>(delim) << e;
    delim[0] = ',';
  }
  std::cout << "]\n";
}

template <typename T>
void print(const std::list<T>& v) {
  std::cout << "[";
  char delim[2]{}; // NOLINT char[] OK here
  for (const auto& e: v) {
    std::cout << static_cast<char*>(delim) << e;
    delim[0] = ',';
  }
  std::cout << "]\n";
}

int main() {
  {
    const std::vector<int> ints{9, 8, 7, 6, 5, 4, 3, 2, 1};
    print(ints);
    std::cout << "median(ints) = " << median(ints) << "\n";
    print(ints);
  }
  {
    std::vector<int> ints{9, 8, 7, 6, 5, 4, 3, 2, 1};
    print(ints);
    std::cout << "median_in_place(ints) = " << median_in_place(ints) << "\n";
    print(ints);
  }
  {
    const std::list<vec2> vec2s{{9, 8}, {7, 6}, {5, 4}, {3, 2}};
    print(vec2s);
    std::cout << "median(mag(vec2)) = " << median(vec2s, {}, &vec2::mag) << "\n";
    print(vec2s);
  }
  {
    std::vector<vec2> vec2s{{9, 8}, {7, 6}, {5, 4}, {3, 2}};
    print(vec2s);
    std::cout << "median_in_place(mag(vec2)) using lambda = "
              << median_in_place(vec2s, {}, [](const auto& v) { return v.mag(); }) << "\n";
    print(vec2s);
  }
  {
    std::vector<vec2> vec2s{{9, 8}, {7, 6}, {5, 4}, {3, 2}};
    print(vec2s);
    std::cout << "median_in_place(mag(vec2) using iters) = "
              << median_in_place(vec2s.begin(), vec2s.end(), {},
                                 [](const auto& v) { return v.mag(); })
              << "\n";
    print(vec2s);
  }
}

Answer 1

Be as generic as possible

Your median() and median_in_place() functions don't work on all things that are ranges, because you didn't use generic functions/types everywhere. Consider for example trying to get the median of a plain array:

double values[] = {1, 2, 3, 4, 5, 6, 7, 8};
std::cout << median(values) << '\n';

This will fail because you are using range.begin() and range.end() instead of std::ranges::begin(range) and std::ranges::end(range). Fixing that, there still is an issue if you use median_in_place(), since you constrained it to:

std::sortable<typename RandomAcccessRange::iterator, Comp, Proj>

This should be:

std::sortable<std::ranges::iterator_t<RandomAcccessRange>, Comp, Proj>

There's also a problem with your print() function. Instead of making it a template on the value type, and have explicit overloads for the different containers, make it a template on the container type (or rather, range) instead:

template <std::ranges::input_range T>
void print(const T& v) {
  std::cout << "[";
  const char *delim = "";
  for (const auto& e: v) {
    std::cout << delim << e;
    delim = ", ";
  }
  std::cout << "]\n";
}

Now you can even print a plain array. And as Toby Speight did in his answer, even avoid it always printing to std::cout, and have it take a std::ostream reference parameter.

Answers to your questions

1. Use of concepts: It is "best/preferable" to constrain each of the wrappers as shown below, ie median() wraps median_in_place() and concepts are used at both levels. This is somewhat repetitive, but has subtle differences. Or would it be better, to use Duck typing for the wrappers and only put concept constraints on the main, inner function.

For the most concise error messages, it's best to add concepts to all public functions.

2. Would it be helpful to specify the return types using trailing return syntax? If so, I was unable to find a syntax which works. I suspect, I failed because I needed one or more of std::remove_cv or std::remove_const or std::decay. How to do that? Or not worth it?

I personally don't see the need to specify a return type at all. Just let it be automatically deduced. If you do want it though, then it probably should be this:

template <...>
requires ...
auto median_in_place(RandomAccessIter first, RandomAccessIter last,
                     const Comp& comp = {}, const Proj& proj = {})
-> std::decay_t<std::invoke_result_t<Proj, std::iter_value_t<RandomAccessIter>>>
{
    ...
}

The std::iter_value_t is required to get the value type of the range, then you need to get the result type after Proj is applied, but since that might be a reference (especially if it's std::identity), you also need to use std::decay_t on that.

Answer 2

Instead of using std::midpoint(), it might be better to allow types to have their own midpoint() function (in their namespace), and only fall back on std::midpoint() if that's not found:

using std::midpoint;
return midpoint(std::invoke(proj, *middle),
                std::invoke(proj, *below_middle));

We have median_in_place() that accepts a range, but then miss our chance to use it.

return median_in_place(input_copy, comp, proj);

We can use short form of constrained templates:

template <std::random_access_iterator RandomAccessIter,
          typename Comp = std::ranges::less,
          typename Proj = std::identity>
requires std::sortable<RandomAccessIter, Comp, Proj>

We might want a constraint that RandomAccessIter::value_type is copyable or movable as appropriate in the functions, too.

---

The tests are weak, because the inputs are always sorted or reverse-sorted. Some extra tests with the median at beginning or end would give extra confidence that nth_element() was actually being called!

We're missing tests that use a provided comparator. Perhaps we could compare vector2 objects by their x coordinate?

We don't need a separate print() for each container type. And we can avoid the static_cast by reassigning a pointer:

void print(std::ranges::input_range auto const& v,
           std::ostream& os = std::cout)
{
    os << "[";
    const char* delim = "";
    for (const auto& e: v) {
        os << delim << e;
        delim = ",";
    }
    os << "]\n";
}

---

The vector2 implementation should accept double arguments by value. Passing as double const& gives no benefit.