5
\$\begingroup\$

This is a follow up to this question. I'm only interested to see if this is implemented correctly for move-only types.

#include <vector>
#include <iterator>
#include <algorithm>
#include <utility>

namespace sorting {
  namespace detail {
    template<typename RandomIt>
    RandomIt middle_iterator(RandomIt begin, RandomIt end) {
      return std::next(begin, (end - begin) / 2);
    }

    template<typename RandomIt1, typename RandomIt2, typename OutIt>
    OutIt merge(RandomIt1 left, RandomIt1 left_end, RandomIt2 right, RandomIt2 right_end, OutIt out) {
      while(left < left_end && right < right_end) {
        if (*left < *right) {
          *out++ = std::move(*left++);
        } else {
          *out++ = std::move(*right++);
        }
      }

      std::move(left, left_end, out);
      std::move(right, right_end, out);
      return out;
    }
  }

  template<typename RandomIt1, typename RandomIt2>
  void merge_sort(RandomIt1 begin, RandomIt2 end, RandomIt2 scratch_begin, RandomIt2 scratch_end) {
    if (end - begin > 1) {
      const auto mid = detail::middle_iterator(begin, end);
      const auto scratch_mid = detail::middle_iterator(scratch_begin, scratch_end);
      merge_sort(scratch_begin, scratch_mid, begin, mid);
      merge_sort(scratch_mid, scratch_end, mid, end);
      detail::merge(scratch_begin, scratch_mid, scratch_mid, scratch_end, begin);
    }
  }

  template<typename RandomIt>
  void merge_sort(RandomIt begin, RandomIt end) {
    using value_type = typename std::iterator_traits<RandomIt>::value_type;
    auto scratch_buffer = std::vector<value_type>(std::make_move_iterator(begin), std::make_move_iterator(end));
    merge_sort(begin, end, scratch_buffer.begin(), scratch_buffer.end());
  }
}
\$\endgroup\$
3
\$\begingroup\$

It certainly looks clean and well-written.
Just one thing, I really hate horizontal scrolling. I acknowlege this site is very restrictive there though.

  1. Make sure your use of move-semantics is type-appropriate:

    • Move if it's a move-only type.
    • Move if moveing is noexcept.
    • Otherwise, don't move it.

    The standard-library already has to do that in many places, and thankfully it is available to the public as std::move_if_noexcept() analogous to std::move.

    I suggest adding your own helper which does that for iterators.

  2. You know, it's itching in my fingers to modify merge() to use the conditional operator. Especially after applying the above point, which makes the common part even bigger.

  3. One of the advantages moveing is that it allows for guaranteed success in more cases. Yes, writing flexible and comprehensive noexcept-specifications can be a pain, but your callers will thank you.

    Without doing that work, a good part of the advantage of the two-range version is lost.

  4. I would suggest renaming your iterator-ranges source and target respectively, neither is properly scratch. Also, I would use the more common temp as a name in merge_sort(begin, end).

  5. Are you aware of the sordid tale that is std::vector<bool>?
    I'm not saying it won't work in this case, though slowly.

  6. You do know that C++17 has class template argument deduction?

  7. It's nice to see that you only use < for comparisons, just like the standard-library. That should enable you to easily modify your code to allow for a custom comparison-object.

  8. But there is a problem in how you do the comparisons, as your merge() is needlessly not stable: If both are equal, you should take from the left range instead.

  9. Consider asserting that the two iterator-types fit together in the function, or testing it for SFINAE outside.

\$\endgroup\$
  • \$\begingroup\$ Is there a move iterator analagous to move_if_noexcept? same for std::move from <algorithm>? I'm also not sure what you're trying to say with 5-6. \$\endgroup\$ – Brady Dean Aug 19 '18 at 3:55
  • \$\begingroup\$ I see your suggestion to do it myself now :). Good news, I wrote my own move_if_noexcept (analogous to std::move from algorithm) and I'm using a for loop with std::move_if_noexcept to make the initial copy into the vector. I don't really know how to write an iterator but that's my next challenge... \$\endgroup\$ – Brady Dean Aug 19 '18 at 4:29
  • \$\begingroup\$ @BradyDean I wouldn't write such an iterator, but an iterator-maker which is either pass-through or uses std::make_move_iterator(). No Need to make things complicated. I added a point about stability. \$\endgroup\$ – Deduplicator Aug 19 '18 at 11:53
2
\$\begingroup\$

Avoid use of dereference operator and increment operator together

I think expressions that use the dereference operator and the increment operators, be it pre-increment or post-increment, are more often sources of off-by-one bugs. It is better to separate them into two statements. I would replace the while loop with the following for loop.

for ( ; left < left_end && right < right_end; ++out )
{
   if (*left < *right)
   {
      *out = std::move(*left);
      ++left;
   }
   else
  {
      *out = std::move(*right);
      ++right;
   }
}

Move the helper merge function inside detail namespace.

As far as I can tell, the second, helper, merge function is a detail. That should be moved into the detail namespace, just like where the other helper functions are.

\$\endgroup\$
  • 1
    \$\begingroup\$ 1. One really has to understand the interaction between dereference and pre-/post-increment/decrement to be a basically competent programmer. And prattling is a sin to avoid. while (left < left_end && right < right_end) *out++ = std::move_if_noexcept(*right < *left ? *right++ : *left++); is concise, nice and understandable. 2. You mean merge_sort(4 iterators)? One can make a case for making it public in case the caller already has a fitting scratch-buffer, but it's a bit weak. \$\endgroup\$ – Deduplicator Aug 19 '18 at 11:51
  • 1
    \$\begingroup\$ @Deduplicator, one has to walk the fine line between prattling and being cryptic. As with many things in life, including coding style, where that line is drawn seems to be subjective. I understand and appreciate your point of view. \$\endgroup\$ – R Sahu Aug 19 '18 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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