193 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___CXX03___ALGORITHM_ITERATOR_OPERATIONS_H10#define _LIBCPP___CXX03___ALGORITHM_ITERATOR_OPERATIONS_H11 12#include <__cxx03/__algorithm/iter_swap.h>13#include <__cxx03/__assert>14#include <__cxx03/__config>15#include <__cxx03/__iterator/advance.h>16#include <__cxx03/__iterator/distance.h>17#include <__cxx03/__iterator/iterator_traits.h>18#include <__cxx03/__iterator/next.h>19#include <__cxx03/__iterator/prev.h>20#include <__cxx03/__type_traits/enable_if.h>21#include <__cxx03/__type_traits/is_reference.h>22#include <__cxx03/__type_traits/is_same.h>23#include <__cxx03/__type_traits/remove_cvref.h>24#include <__cxx03/__utility/declval.h>25#include <__cxx03/__utility/forward.h>26#include <__cxx03/__utility/move.h>27 28#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)29# pragma GCC system_header30#endif31 32_LIBCPP_PUSH_MACROS33#include <__cxx03/__undef_macros>34 35_LIBCPP_BEGIN_NAMESPACE_STD36 37template <class _AlgPolicy>38struct _IterOps;39 40struct _ClassicAlgPolicy {};41 42template <>43struct _IterOps<_ClassicAlgPolicy> {44 template <class _Iter>45 using __value_type = typename iterator_traits<_Iter>::value_type;46 47 template <class _Iter>48 using __iterator_category = typename iterator_traits<_Iter>::iterator_category;49 50 template <class _Iter>51 using __difference_type = typename iterator_traits<_Iter>::difference_type;52 53 // advance54 template <class _Iter, class _Distance>55 _LIBCPP_HIDE_FROM_ABI static void advance(_Iter& __iter, _Distance __count) {56 std::advance(__iter, __count);57 }58 59 // distance60 template <class _Iter>61 _LIBCPP_HIDE_FROM_ABI static typename iterator_traits<_Iter>::difference_type distance(_Iter __first, _Iter __last) {62 return std::distance(__first, __last);63 }64 65 template <class _Iter>66 using __deref_t = decltype(*std::declval<_Iter&>());67 68 template <class _Iter>69 using __move_t = decltype(std::move(*std::declval<_Iter&>()));70 71 template <class _Iter>72 _LIBCPP_HIDE_FROM_ABI static void __validate_iter_reference() {73 static_assert(74 is_same<__deref_t<_Iter>, typename iterator_traits<__remove_cvref_t<_Iter> >::reference>::value,75 "It looks like your iterator's `iterator_traits<It>::reference` does not match the return type of "76 "dereferencing the iterator, i.e., calling `*it`. This is undefined behavior according to [input.iterators] "77 "and can lead to dangling reference issues at runtime, so we are flagging this.");78 }79 80 // iter_move81 template <class _Iter, __enable_if_t<is_reference<__deref_t<_Iter> >::value, int> = 0>82 _LIBCPP_HIDE_FROM_ABI static83 // If the result of dereferencing `_Iter` is a reference type, deduce the result of calling `std::move` on it.84 // Note that the C++03 mode doesn't support `decltype(auto)` as the return type.85 __move_t<_Iter>86 __iter_move(_Iter&& __i) {87 __validate_iter_reference<_Iter>();88 89 return std::move(*std::forward<_Iter>(__i));90 }91 92 template <class _Iter, __enable_if_t<!is_reference<__deref_t<_Iter> >::value, int> = 0>93 _LIBCPP_HIDE_FROM_ABI static94 // If the result of dereferencing `_Iter` is a value type, deduce the return value of this function to also be a95 // value -- otherwise, after `operator*` returns a temporary, this function would return a dangling reference to96 // that temporary. Note that the C++03 mode doesn't support `auto` as the return type.97 __deref_t<_Iter>98 __iter_move(_Iter&& __i) {99 __validate_iter_reference<_Iter>();100 101 return *std::forward<_Iter>(__i);102 }103 104 // iter_swap105 template <class _Iter1, class _Iter2>106 _LIBCPP_HIDE_FROM_ABI static void iter_swap(_Iter1&& __a, _Iter2&& __b) {107 std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b));108 }109 110 // next111 template <class _Iterator>112 _LIBCPP_HIDE_FROM_ABI static _Iterator next(_Iterator, _Iterator __last) {113 return __last;114 }115 116 template <class _Iter>117 _LIBCPP_HIDE_FROM_ABI static __remove_cvref_t<_Iter>118 next(_Iter&& __it, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {119 return std::next(std::forward<_Iter>(__it), __n);120 }121 122 // prev123 template <class _Iter>124 _LIBCPP_HIDE_FROM_ABI static __remove_cvref_t<_Iter>125 prev(_Iter&& __iter, typename iterator_traits<__remove_cvref_t<_Iter> >::difference_type __n = 1) {126 return std::prev(std::forward<_Iter>(__iter), __n);127 }128 129 template <class _Iter>130 _LIBCPP_HIDE_FROM_ABI static void __advance_to(_Iter& __first, _Iter __last) {131 __first = __last;132 }133 134 // advance with sentinel, a la std::ranges::advance135 template <class _Iter>136 _LIBCPP_HIDE_FROM_ABI static __difference_type<_Iter>137 __advance_to(_Iter& __iter, __difference_type<_Iter> __count, const _Iter& __sentinel) {138 return _IterOps::__advance_to(__iter, __count, __sentinel, typename iterator_traits<_Iter>::iterator_category());139 }140 141private:142 // advance with sentinel, a la std::ranges::advance -- InputIterator specialization143 template <class _InputIter>144 _LIBCPP_HIDE_FROM_ABI static __difference_type<_InputIter> __advance_to(145 _InputIter& __iter, __difference_type<_InputIter> __count, const _InputIter& __sentinel, input_iterator_tag) {146 __difference_type<_InputIter> __dist = 0;147 for (; __dist < __count && __iter != __sentinel; ++__dist)148 ++__iter;149 return __count - __dist;150 }151 152 // advance with sentinel, a la std::ranges::advance -- BidirectionalIterator specialization153 template <class _BiDirIter>154 _LIBCPP_HIDE_FROM_ABI static __difference_type<_BiDirIter>155 __advance_to(_BiDirIter& __iter,156 __difference_type<_BiDirIter> __count,157 const _BiDirIter& __sentinel,158 bidirectional_iterator_tag) {159 __difference_type<_BiDirIter> __dist = 0;160 if (__count >= 0)161 for (; __dist < __count && __iter != __sentinel; ++__dist)162 ++__iter;163 else164 for (__count = -__count; __dist < __count && __iter != __sentinel; ++__dist)165 --__iter;166 return __count - __dist;167 }168 169 // advance with sentinel, a la std::ranges::advance -- RandomIterator specialization170 template <class _RandIter>171 _LIBCPP_HIDE_FROM_ABI static __difference_type<_RandIter>172 __advance_to(_RandIter& __iter,173 __difference_type<_RandIter> __count,174 const _RandIter& __sentinel,175 random_access_iterator_tag) {176 auto __dist = _IterOps::distance(__iter, __sentinel);177 _LIBCPP_ASSERT_VALID_INPUT_RANGE(178 __count == 0 || (__dist < 0) == (__count < 0), "__sentinel must precede __iter when __count < 0");179 if (__count < 0)180 __dist = __dist > __count ? __dist : __count;181 else182 __dist = __dist < __count ? __dist : __count;183 __iter += __dist;184 return __count - __dist;185 }186};187 188_LIBCPP_END_NAMESPACE_STD189 190_LIBCPP_POP_MACROS191 192#endif // _LIBCPP___CXX03___ALGORITHM_ITERATOR_OPERATIONS_H193