How to use range projection in a sorting algorithm?-CodePudding

I'm trying to wrap my bonehead around the ranges. So decided to implement some basic sort procedures as a range algorithm and like in the std::ranges::sort(). I peeked its implementation but didn't understand how to make use of projection:

#include <iterator>
#include <functional>
#include <ranges>

namespace sort {

namespace ranges {

struct insertion_fn {
  template <std::random_access_iterator I, std::sentinel_for<I> S,
            typename Comp = std::ranges::less, typename Proj = std::identity>
  requires std::sortable<I, Comp, Proj>
  constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const {
    if (first == last)
      return first;

    std::size_t N = std::ranges::distance(first, last);

    I last_iter = std::ranges::next(first, last);

    for (std::size_t i = 1; i < N;   i) {
      for (std::size_t j = i; j > 0 && comp(*(first   j), *(first   j - 1)); --j) {
        std::iter_swap(first   j, first   j - 1);
      }
    }

    return last_iter;
  }

  template <std::ranges::random_access_range R, class Comp = std::ranges::less,
            class Proj = std::identity>
  requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
  constexpr std::ranges::borrowed_iterator_t<R> operator()(R &&r, Comp comp = {},
                                                           Proj proj = {}) const {
    return (*this)(std::ranges::begin(r), std::ranges::end(r), std::move(comp), std::move(proj));
  }
};

inline constexpr insertion_fn insertion;

} // namespace ranges
} // namespace sort

This test fails:

TEST_CASE("Insertion: Make use of range projection") {
  namespace stdr = std::ranges;
  using person = std::pair<std::string, std::string>;

  std::vector<person> people{
      {"tintin", "detective"}, {"snowy", "lifeguard"}, {"haddock", "captain"}};

  auto expected = people;
  stdr::sort(expected, std::less{}, &person::first);

  auto test = people;
  sort::ranges::insertion(people, std::less{}, &person::first);

  REQUIRE_EQ(test, expected);
}

My question is how to where to handle projection into the this implementation. Sorry for the long code snippets.

CodePudding user response：

The point of the projection in sort is to change the comparison being used. For example:

std::vector<std::string> words = {"a", "quick", "brown", "fox"}; 

// sorts by normal lexicographic order, so you get [a, brown, fox, quick]
std::ranges::sort(words);

// same, but reversed, so [quick, fox, brown, a]
std::ranges::sort(words, std::greater());

// sorts words in increasing order by size, so [a, fox, brown, quick]
// (or quick, brown)
std::ranges::sort(words, std::less(), std::ranges::size);

Your code is simply comparing the elements directly:

comp(*(first   j), *(first   j - 1))

Which itself is a long form of:

comp(first[j], first[j-1])

Instead of comparing the elements directly, you need to compared the projected elements:

comp(proj(first[j]), proj(first[j-1]))

A different way of thinking about it is that a projection is a convenient way of alternating part of the comparison - so you can keep the < part (the Comp parameter) but just change which part you're <-ing (the Proj parameter).