3
\$\begingroup\$

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);
  }
}

\$\endgroup\$
1
  • \$\begingroup\$ Completely coincidentally, I was playing with a median implementation today, with slightly different emphasis. I don't use a separate projection function (but can get the same effect with a custom midpoint()). If you're interested, my review request is Find median of values without copying. \$\endgroup\$ Commented Feb 12, 2022 at 17:38

2 Answers 2

6
\$\begingroup\$

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.

  1. 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.

\$\endgroup\$
6
  • \$\begingroup\$ The first point applied to my recent question, and I've now fixed it, so thank you for educating more than just the asker! \$\endgroup\$ Commented Feb 12, 2022 at 18:27
  • \$\begingroup\$ Thanks for the point on c-arrays. Not "sloppy", I am simply not yet used to writing generic code in a world with ranges. The print function was purely ad hoc, not serious code. I hate writing these container printers, and in my code proper, I always use std::format which solves this properly. But it is not yet supported by most compilers so I don't use it on CR. Hence the ad-hoc print(). I also find the clobbering of the const char* ptr "hacky". The whole (two) function(s) shouldn't exist. Thanks for answers to questions, particularly the return type. \$\endgroup\$ Commented Feb 12, 2022 at 20:26
  • \$\begingroup\$ Please don't take criticism personal. I mentioned sloppy because you did use things like std::iter_value_t<InputIter> correctly in some places, instead of InputIter::value_type. Printing containers can be done in a one-liner using std::ranges::copy(range, std::ostream_iterator<type>(std::cout, ",")) for example, or indeed use the excellent std::format(). I don't think changing a mutable pointer to point to something else is hacky. You could've used a std::string instead to avoid this altogether. \$\endgroup\$
    – G. Sliepen
    Commented Feb 12, 2022 at 20:36
  • \$\begingroup\$ All of the print options (other than std::format) are bad. They are either verbose and/or don't integrate well. Passing std::ostream as second param doesn't solve anything, really, because we still can't use operator<< because that is in std::. This was just a glaring hole, for doing sth trivial, with many "clever yet inadequate solutions", in c++ for > 20yrs. std::format finally solves it. \$\endgroup\$ Commented Feb 12, 2022 at 20:43
  • \$\begingroup\$ Changing the const char* ptr is no better than changing the stack based char[]... they are both bad, because they are "bending over backwards" to do something which is unbelievably awkward to solve, because it should have been solved with std::vector::operator<< 20 yrs ago. \$\endgroup\$ Commented Feb 12, 2022 at 20:49
3
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Interesting point on midpoint... similar to what happens with std::swap. I like that. Your pedantically worded comments on the "tests" are not really appreciated. This is clearly not a test suite, but merely a demo of SOME of the features. The combinatorial explosion of a proper test suite would have meant that they they would have taken up 90% of the code. You didn't answer the questions.. \$\endgroup\$ Commented Feb 12, 2022 at 19:51
  • 2
    \$\begingroup\$ Yes, proper unit tests would certainly be helpful - I probably should have suggested that. \$\endgroup\$ Commented Feb 12, 2022 at 19:58
  • \$\begingroup\$ CR is not a forum to submit production quality libraries with full test suites, benchmarks, continuous integration testing on multiple platforms etc. That takes a proper repository not a couple of markup boxes. Which is why CR is so limited in the code it can realistically hope to evaluate. I had this debate last year and stopped answering questions as a result. It's "Stack Overflow... with slightly longer, and hopefully slightly better thought through, questions". It can't be more, due to the format. \$\endgroup\$ Commented Feb 12, 2022 at 20:03
  • 1
    \$\begingroup\$ @OliverSchönrock I agree that including long test suites in the question is probably not helpful if you just want to focus on the actual code, but Toby's remark that your tests are weak is still valid criticism. Had you implemented more tests, you probably would've caught some of the issues we have found. Also, CR and StackOverflow are not just for the benefit of the OP, they are also for others who are just browsing questions and trying to learn from them, so any advice given that might not be useful for you might still be useful for others. \$\endgroup\$
    – G. Sliepen
    Commented Feb 12, 2022 at 20:09
  • \$\begingroup\$ @G.Sliepen I disagree. Those comments were not valid or helpful. Your comment about c-arrays is helpful. And those are not TESTS. They are demo code, specifically for the purpose of posting on CR. All in one file.. demo in main without any test framework.. And the wording.. "Your tests are WEAK"... they are NOT tests. Sorry, in my eye he purely postured and didn't even bother to answer the actual questions. Personally I only posted this CR because you advised me to do so. There is barely any additional content here beyond the first one. \$\endgroup\$ Commented Feb 12, 2022 at 20:15

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.