Skip to content

Instantly share code, notes, and snippets.

@jw910731
Last active November 17, 2023 06:41
Show Gist options
  • Save jw910731/90eb8eab4587e59722872eb5258cab5e to your computer and use it in GitHub Desktop.
Save jw910731/90eb8eab4587e59722872eb5258cab5e to your computer and use it in GitHub Desktop.
merge sort with c++20 ranges library
#include <ranges>
#include <type_traits>
#include <vector>
#include <list>
#include <iostream>
template <typename T> requires std::ranges::sized_range<T>
T &&merge_sort(T &&arr) {
if (std::ranges::size(arr) < 2) return std::forward<T>(arr);
auto mid_len = std::ranges::size(arr) / 2;
auto mid = std::ranges::next(std::ranges::begin(arr), mid_len);
auto left = merge_sort(std::ranges::subrange(std::ranges::begin(arr), mid, mid_len));
auto right = merge_sort(std::ranges::subrange(mid, std::ranges::end(arr), std::ranges::size(arr) - mid_len));
auto l = left.begin(), r = right.begin();
std::vector<std::ranges::range_value_t<T>> ret;
ret.reserve(arr.size());
while (l != left.end() && r != right.end()) {
if (*l < *r) {
ret.emplace_back(*l++);
} else {
ret.emplace_back(*r++);
}
}
ret.insert(ret.end(), l, left.end());
ret.insert(ret.end(), r, right.end());
using std::copy;
copy(ret.begin(), ret.end(), arr.begin());
return std::forward<T>(arr);
}
int main() {
std::list<int> arr{1, 3, 2, 8, 30, 4, 5};
merge_sort(arr);
for (auto &v : arr) {
std::cout << v << std::endl;
}
std::cout << "-------\n";
std::vector<int> arr1{1, 3, 2, 8, 30, 4, 5};
merge_sort(arr1);
for (auto &v : arr1) {
std::cout << v << std::endl;
}
}
@jw910731
Copy link
Author

Isn't it copies when passing an l value into r value ref?

By leveraging the template system and reference collapsing, the rvalue ref will collapse to lvalue ref when passing lvalue ref.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment