230 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H10#define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H11 12#include <__algorithm/iter_swap.h>13#include <__algorithm/ranges_iterator_concept.h>14#include <__assert>15#include <__config>16#include <__iterator/advance.h>17#include <__iterator/distance.h>18#include <__iterator/incrementable_traits.h>19#include <__iterator/iter_move.h>20#include <__iterator/iter_swap.h>21#include <__iterator/iterator_traits.h>22#include <__iterator/next.h>23#include <__iterator/prev.h>24#include <__iterator/readable_traits.h>25#include <__type_traits/enable_if.h>26#include <__type_traits/is_reference.h>27#include <__type_traits/is_same.h>28#include <__type_traits/remove_cvref.h>29#include <__utility/declval.h>30#include <__utility/forward.h>31#include <__utility/move.h>32 33#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)34# pragma GCC system_header35#endif36 37_LIBCPP_PUSH_MACROS38#include <__undef_macros>39 40_LIBCPP_BEGIN_NAMESPACE_STD41 42template <class _AlgPolicy>43struct _IterOps;44 45#if _LIBCPP_STD_VER >= 2046struct _RangeAlgPolicy {};47 48template <>49struct _IterOps<_RangeAlgPolicy> {50 template <class _Iter>51 using __value_type _LIBCPP_NODEBUG = iter_value_t<_Iter>;52 53 template <class _Iter>54 using __iterator_category _LIBCPP_NODEBUG = ranges::__iterator_concept<_Iter>;55 56 template <class _Iter>57 using __difference_type _LIBCPP_NODEBUG = iter_difference_t<_Iter>;58 59 static constexpr auto advance = ranges::advance;60 static constexpr auto distance = ranges::distance;61 static constexpr auto __iter_move = ranges::iter_move;62 static constexpr auto iter_swap = ranges::iter_swap;63 static constexpr auto next = ranges::next;64 static constexpr auto prev = ranges::prev;65 static constexpr auto __advance_to = ranges::advance;66};67 68#endif69 70struct _ClassicAlgPolicy {};71 72template <>73struct _IterOps<_ClassicAlgPolicy> {74 template <class _Iter>75 using __value_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::value_type;76 77 template <class _Iter>78 using __iterator_category _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category;79 80 template <class _Iter>81 using __difference_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type;82 83 // advance84 template <class _Iter, class _Distance>85 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static void advance(_Iter& __iter, _Distance __count) {86 std::advance(__iter, __count);87 }88 89 // distance90 template <class _Iter>91 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static typename iterator_traits<_Iter>::difference_type92 distance(_Iter __first, _Iter __last) {93 return std::distance(__first, __last);94 }95 96 template <class _Iter>97 using __deref_t _LIBCPP_NODEBUG = decltype(*std::declval<_Iter&>());98 99 template <class _Iter>100 using __move_t _LIBCPP_NODEBUG = decltype(std::move(*std::declval<_Iter&>()));101 102 template <class _Iter>103 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static void __validate_iter_reference() {104 static_assert(105 is_same<__deref_t<_Iter>, typename iterator_traits<__remove_cvref_t<_Iter> >::reference>::value,106 "It looks like your iterator's `iterator_traits<It>::reference` does not match the return type of "107 "dereferencing the iterator, i.e., calling `*it`. This is undefined behavior according to [input.iterators] "108 "and can lead to dangling reference issues at runtime, so we are flagging this.");109 }110 111 // iter_move112 template <class _Iter, __enable_if_t<is_reference<__deref_t<_Iter> >::value, int> = 0>113 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static114 // If the result of dereferencing `_Iter` is a reference type, deduce the result of calling `std::move` on it.115 // Note that the C++03 mode doesn't support `decltype(auto)` as the return type.116 __move_t<_Iter>117 __iter_move(_Iter&& __i) {118 __validate_iter_reference<_Iter>();119 120 return std::move(*std::forward<_Iter>(__i));121 }122 123 template <class _Iter, __enable_if_t<!is_reference<__deref_t<_Iter> >::value, int> = 0>124 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static125 // If the result of dereferencing `_Iter` is a value type, deduce the return value of this function to also be a126 // value -- otherwise, after `operator*` returns a temporary, this function would return a dangling reference to127 // that temporary. Note that the C++03 mode doesn't support `auto` as the return type.128 __deref_t<_Iter>129 __iter_move(_Iter&& __i) {130 __validate_iter_reference<_Iter>();131 132 return *std::forward<_Iter>(__i);133 }134 135 // iter_swap136 template <class _Iter1, class _Iter2>137 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static void iter_swap(_Iter1&& __a, _Iter2&& __b) {138 std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b));139 }140 141 // next142 template <class _Iterator>143 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iterator next(_Iterator, _Iterator __last) {144 return __last;145 }146 147 template <class _Iter>148 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 __remove_cvref_t<_Iter>149 next(_Iter&& __it, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {150 return std::next(std::forward<_Iter>(__it), __n);151 }152 153 // prev154 template <class _Iter>155 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 __remove_cvref_t<_Iter>156 prev(_Iter&& __iter, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {157 return std::prev(std::forward<_Iter>(__iter), __n);158 }159 160 template <class _Iter>161 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX14 void __advance_to(_Iter& __first, _Iter __last) {162 __first = __last;163 }164 165 // advance with sentinel, a la std::ranges::advance166 template <class _Iter>167 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_Iter>168 __advance_to(_Iter& __iter, __difference_type<_Iter> __count, const _Iter& __sentinel) {169 return _IterOps::__advance_to(__iter, __count, __sentinel, typename iterator_traits<_Iter>::iterator_category());170 }171 172private:173 // advance with sentinel, a la std::ranges::advance -- InputIterator specialization174 template <class _InputIter>175 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_InputIter> __advance_to(176 _InputIter& __iter, __difference_type<_InputIter> __count, const _InputIter& __sentinel, input_iterator_tag) {177 __difference_type<_InputIter> __dist = 0;178 for (; __dist < __count && __iter != __sentinel; ++__dist)179 ++__iter;180 return __count - __dist;181 }182 183 // advance with sentinel, a la std::ranges::advance -- BidirectionalIterator specialization184 template <class _BiDirIter>185 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_BiDirIter>186 __advance_to(_BiDirIter& __iter,187 __difference_type<_BiDirIter> __count,188 const _BiDirIter& __sentinel,189 bidirectional_iterator_tag) {190 __difference_type<_BiDirIter> __dist = 0;191 if (__count >= 0)192 for (; __dist < __count && __iter != __sentinel; ++__dist)193 ++__iter;194 else195 for (__count = -__count; __dist < __count && __iter != __sentinel; ++__dist)196 --__iter;197 return __count - __dist;198 }199 200 // advance with sentinel, a la std::ranges::advance -- RandomIterator specialization201 template <class _RandIter>202 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static __difference_type<_RandIter>203 __advance_to(_RandIter& __iter,204 __difference_type<_RandIter> __count,205 const _RandIter& __sentinel,206 random_access_iterator_tag) {207 auto __dist = _IterOps::distance(__iter, __sentinel);208 _LIBCPP_ASSERT_VALID_INPUT_RANGE(209 __count == 0 || (__dist < 0) == (__count < 0), "__sentinel must precede __iter when __count < 0");210 if (__count < 0)211 __dist = __dist > __count ? __dist : __count;212 else213 __dist = __dist < __count ? __dist : __count;214 __iter += __dist;215 return __count - __dist;216 }217};218 219template <class _AlgPolicy, class _Iter>220using __policy_iter_diff_t _LIBCPP_NODEBUG = typename _IterOps<_AlgPolicy>::template __difference_type<_Iter>;221 222template <class _AlgPolicy, class _Iter>223using __policy_value_type _LIBCPP_NODEBUG = typename _IterOps<_AlgPolicy>::template __value_type<_Iter>;224 225_LIBCPP_END_NAMESPACE_STD226 227_LIBCPP_POP_MACROS228 229#endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H230