v1/__algorithm/iterator_operations.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
0010 #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
0011
0012 #include <__algorithm/iter_swap.h>
0013 #include <__algorithm/ranges_iterator_concept.h>
0014 #include <__assert>
0015 #include <__config>
0016 #include <__iterator/advance.h>
0017 #include <__iterator/distance.h>
0018 #include <__iterator/incrementable_traits.h>
0019 #include <__iterator/iter_move.h>
0020 #include <__iterator/iter_swap.h>
0021 #include <__iterator/iterator_traits.h>
0022 #include <__iterator/next.h>
0023 #include <__iterator/prev.h>
0024 #include <__iterator/readable_traits.h>
0025 #include <__type_traits/enable_if.h>
0026 #include <__type_traits/is_reference.h>
0027 #include <__type_traits/is_same.h>
0028 #include <__type_traits/remove_cvref.h>
0029 #include <__utility/declval.h>
0030 #include <__utility/forward.h>
0031 #include <__utility/move.h>
0032
0033 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0034 #  pragma GCC system_header
0035 #endif
0036
0037 _LIBCPP_PUSH_MACROS
0038 #include <__undef_macros>
0039
0040 _LIBCPP_BEGIN_NAMESPACE_STD
0041
0042 template <class _AlgPolicy>
0043 struct _IterOps;
0044
0045 #if _LIBCPP_STD_VER >= 20
0046 struct _RangeAlgPolicy {};
0047
0048 template <>
0049 struct _IterOps<_RangeAlgPolicy> {
0050   template <class _Iter>
0051   using __value_type _LIBCPP_NODEBUG = iter_value_t<_Iter>;
0052
0053   template <class _Iter>
0054   using __iterator_category _LIBCPP_NODEBUG = ranges::__iterator_concept<_Iter>;
0055
0056   template <class _Iter>
0057   using __difference_type _LIBCPP_NODEBUG = iter_difference_t<_Iter>;
0058
0059   static constexpr auto advance      = ranges::advance;
0060   static constexpr auto distance     = ranges::distance;
0061   static constexpr auto __iter_move  = ranges::iter_move;
0062   static constexpr auto iter_swap    = ranges::iter_swap;
0063   static constexpr auto next         = ranges::next;
0064   static constexpr auto prev         = ranges::prev;
0065   static constexpr auto __advance_to = ranges::advance;
0066 };
0067
0068 #endif
0069
0070 struct _ClassicAlgPolicy {};
0071
0072 template <>
0073 struct _IterOps<_ClassicAlgPolicy> {
0074   template <class _Iter>
0075   using __value_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::value_type;
0076
0077   template <class _Iter>
0078   using __iterator_category _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category;
0079
0080   template <class _Iter>
0081   using __difference_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type;
0082
0083   // advance
0084   template <class _Iter, class _Distance>
0085   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static void advance(_Iter& __iter, _Distance __count) {
0086     std::advance(__iter, __count);
0087   }
0088
0089   // distance
0090   template <class _Iter>
0091   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static typename iterator_traits<_Iter>::difference_type
0092   distance(_Iter __first, _Iter __last) {
0093     return std::distance(__first, __last);
0094   }
0095
0096   template <class _Iter>
0097   using __deref_t _LIBCPP_NODEBUG = decltype(*std::declval<_Iter&>());
0098
0099   template <class _Iter>
0100   using __move_t _LIBCPP_NODEBUG = decltype(std::move(*std::declval<_Iter&>()));
0101
0102   template <class _Iter>
0103   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static void __validate_iter_reference() {
0104     static_assert(
0105         is_same<__deref_t<_Iter>, typename iterator_traits<__remove_cvref_t<_Iter> >::reference>::value,
0106         "It looks like your iterator's `iterator_traits<It>::reference` does not match the return type of "
0107         "dereferencing the iterator, i.e., calling `*it`. This is undefined behavior according to [input.iterators] "
0108         "and can lead to dangling reference issues at runtime, so we are flagging this.");
0109   }
0110
0111   // iter_move
0112   template <class _Iter, __enable_if_t<is_reference<__deref_t<_Iter> >::value, int> = 0>
0113   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static
0114       // If the result of dereferencing `_Iter` is a reference type, deduce the result of calling `std::move` on it.
0115       // Note that the C++03 mode doesn't support `decltype(auto)` as the return type.
0116       __move_t<_Iter>
0117       __iter_move(_Iter&& __i) {
0118     __validate_iter_reference<_Iter>();
0119
0120     return std::move(*std::forward<_Iter>(__i));
0121   }
0122
0123   template <class _Iter, __enable_if_t<!is_reference<__deref_t<_Iter> >::value, int> = 0>
0124   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static
0125       // If the result of dereferencing `_Iter` is a value type, deduce the return value of this function to also be a
0126       // value -- otherwise, after `operator*` returns a temporary, this function would return a dangling reference to
0127       // that temporary. Note that the C++03 mode doesn't support `auto` as the return type.
0128       __deref_t<_Iter>
0129       __iter_move(_Iter&& __i) {
0130     __validate_iter_reference<_Iter>();
0131
0132     return *std::forward<_Iter>(__i);
0133   }
0134
0135   // iter_swap
0136   template <class _Iter1, class _Iter2>
0137   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static void iter_swap(_Iter1&& __a, _Iter2&& __b) {
0138     std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b));
0139   }
0140
0141   // next
0142   template <class _Iterator>
0143   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator next(_Iterator, _Iterator __last) {
0144     return __last;
0145   }
0146
0147   template <class _Iter>
0148   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 __remove_cvref_t<_Iter>
0149   next(_Iter&& __it, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {
0150     return std::next(std::forward<_Iter>(__it), __n);
0151   }
0152
0153   // prev
0154   template <class _Iter>
0155   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 __remove_cvref_t<_Iter>
0156   prev(_Iter&& __iter, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {
0157     return std::prev(std::forward<_Iter>(__iter), __n);
0158   }
0159
0160   template <class _Iter>
0161   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 void __advance_to(_Iter& __first, _Iter __last) {
0162     __first = __last;
0163   }
0164
0165   // advance with sentinel, a la std::ranges::advance
0166   template <class _Iter>
0167   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_Iter>
0168   __advance_to(_Iter& __iter, __difference_type<_Iter> __count, const _Iter& __sentinel) {
0169     return _IterOps::__advance_to(__iter, __count, __sentinel, typename iterator_traits<_Iter>::iterator_category());
0170   }
0171
0172 private:
0173   // advance with sentinel, a la std::ranges::advance -- InputIterator specialization
0174   template <class _InputIter>
0175   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_InputIter> __advance_to(
0176       _InputIter& __iter, __difference_type<_InputIter> __count, const _InputIter& __sentinel, input_iterator_tag) {
0177     __difference_type<_InputIter> __dist = 0;
0178     for (; __dist < __count && __iter != __sentinel; ++__dist)
0179       ++__iter;
0180     return __count - __dist;
0181   }
0182
0183   // advance with sentinel, a la std::ranges::advance -- BidirectionalIterator specialization
0184   template <class _BiDirIter>
0185   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_BiDirIter>
0186   __advance_to(_BiDirIter& __iter,
0187                __difference_type<_BiDirIter> __count,
0188                const _BiDirIter& __sentinel,
0189                bidirectional_iterator_tag) {
0190     __difference_type<_BiDirIter> __dist = 0;
0191     if (__count >= 0)
0192       for (; __dist < __count && __iter != __sentinel; ++__dist)
0193         ++__iter;
0194     else
0195       for (__count = -__count; __dist < __count && __iter != __sentinel; ++__dist)
0196         --__iter;
0197     return __count - __dist;
0198   }
0199
0200   // advance with sentinel, a la std::ranges::advance -- RandomIterator specialization
0201   template <class _RandIter>
0202   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_RandIter>
0203   __advance_to(_RandIter& __iter,
0204                __difference_type<_RandIter> __count,
0205                const _RandIter& __sentinel,
0206                random_access_iterator_tag) {
0207     auto __dist = _IterOps::distance(__iter, __sentinel);
0208     _LIBCPP_ASSERT_VALID_INPUT_RANGE(
0209         __count == 0 || (__dist < 0) == (__count < 0), "__sentinel must precede __iter when __count < 0");
0210     if (__count < 0)
0211       __dist = __dist > __count ? __dist : __count;
0212     else
0213       __dist = __dist < __count ? __dist : __count;
0214     __iter += __dist;
0215     return __count - __dist;
0216   }
0217 };
0218
0219 template <class _AlgPolicy, class _Iter>
0220 using __policy_iter_diff_t _LIBCPP_NODEBUG = typename _IterOps<_AlgPolicy>::template __difference_type<_Iter>;
0221
0222 _LIBCPP_END_NAMESPACE_STD
0223
0224 _LIBCPP_POP_MACROS
0225
0226 #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H