ARTICLE AD BOX
I implement quicksort algorithm. It works normally on simple ranges: std::vector, etc.
template <typename R, typename Comp = std::ranges::less> void quicksort(R&& range, Comp comp = {}) { namespace rng = std::ranges; if (rng::size(range) <= 1) { return; } auto pivot = HoarePartition(range, comp); quicksort(rng::subrange(rng::begin(range), pivot), comp); quicksort(rng::subrange(pivot + 1, rng::end(range)), comp); } template <typename R, typename Comp> std::ranges::iterator_t<R> HoarePartition(R&& range, Comp comp) { namespace rng = std::ranges; auto pivot = rng::begin(range) + rng::size(range) / 2; // NB: Median of Medians -> 3:7 auto i = rng::begin(range); auto j = rng::begin(range) + rng::size(range) - 1; while (rng::distance(i, j) > 0) { while (comp(*i, *pivot)) { ++i; } while (comp(*pivot, *j)) { --j; } std::swap(*i, *j); // <-- CE here if (pivot == i) { pivot = j; ++i; } else if (pivot == j) { pivot = i; --j; } else { ++i; --j; } } return pivot; } #include <iostream> #include <vector> #include <ranges> #include <algorithm> int main() { std::vector v = {3, 2, 4, 1, 5}; std::vector u1 = v; quicksort(u1); // OK auto u2 = v | std::views::transform([](auto x) { return x * 2; }); quicksort(u2); // CE }However, when I modify a container with e.g. std::views::transform the error at *j says that it cannot bind non-const lvalue reference of type ‘int&’ to an rvalue of type ‘int’. Whereas the error at std::swap says no matching function for call to ‘swap(int, int)’. Why does it treat dereferenced value both as int reference and int? What is the problem? How to fix Hoare partition function?
What is more interesting it works with std::views::reverse.
