[PATCH] libstdc++: P0769R2 Add shift to <algorithm>

[Stephan Bergmann]

On 21/02/2020 20:29, Patrick Palka wrote:
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index 7de1072abf0..c36afc6e19b 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -3683,6 +3683,54 @@ namespace ranges
>     inline constexpr __prev_permutation_fn prev_permutation{};
>   
>   } // namespace ranges
> +
> +  template<class ForwardIterator>
> +    constexpr ForwardIterator
> +    shift_left(ForwardIterator __first, ForwardIterator __last,
> +	       typename iterator_traits<ForwardIterator>::difference_type __n)
> +    {
> +      __glibcxx_assert(__n >= 0);
> +      if (__n == 0)
> +	return __last;
> +
> +      auto __mid = ranges::next(__first, __n, __last);
> +      if (__mid == __last)
> +	return __first;
> +      return std::move(std::move(__mid), std::move(__last), std::move(__first));
> +    }
> +
> +  template<class ForwardIterator>
> +    constexpr ForwardIterator
> +    shift_right(ForwardIterator __first, ForwardIterator __last,
> +		typename iterator_traits<ForwardIterator>::difference_type __n)
> +    {
> +      __glibcxx_assert(__n >= 0);
> +      if (__n == 0)
> +	return __first;
> +
> +      using _Cat = iterator_traits<ForwardIterator>::iterator_category;

^ FYI, the above line causes recent Clang 10 trunk with -std=c++20 to 
fail due to a "missing" typedef

> +      if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
> +	{
> +	  auto __mid = ranges::next(__last, -__n, __first);
> +	  if (__mid == __first)
> +	    return __last;
> +	  return std::move_backward(std::move(__first), std::move(__mid),
> +				    std::move(__last));
> +	}
> +      else
> +	{
> +	  auto __result = ranges::next(__first, __n, __last);
> +	  if (__result == __last)
> +	    return __last;
> +	  auto __dest = __result;
> +	  do
> +	    __dest = ranges::swap_ranges(__first, __result,
> +					 std::move(__dest), __last).in2;
> +	  while (__dest != __last);
> +	  return __result;
> +	}
> +    }
> +
>   _GLIBCXX_END_NAMESPACE_VERSION
>   } // namespace std
>   #endif // concepts