1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ITERATOR_REVERSE_ITERATOR_H 11 #define _LIBCPP___ITERATOR_REVERSE_ITERATOR_H 12 13 #include <__algorithm/unwrap_iter.h> 14 #include <__compare/compare_three_way_result.h> 15 #include <__compare/three_way_comparable.h> 16 #include <__concepts/convertible_to.h> 17 #include <__config> 18 #include <__iterator/advance.h> 19 #include <__iterator/concepts.h> 20 #include <__iterator/incrementable_traits.h> 21 #include <__iterator/iter_move.h> 22 #include <__iterator/iter_swap.h> 23 #include <__iterator/iterator.h> 24 #include <__iterator/iterator_traits.h> 25 #include <__iterator/next.h> 26 #include <__iterator/prev.h> 27 #include <__iterator/readable_traits.h> 28 #include <__iterator/segmented_iterator.h> 29 #include <__memory/addressof.h> 30 #include <__ranges/access.h> 31 #include <__ranges/concepts.h> 32 #include <__ranges/subrange.h> 33 #include <__type_traits/conditional.h> 34 #include <__type_traits/enable_if.h> 35 #include <__type_traits/is_assignable.h> 36 #include <__type_traits/is_convertible.h> 37 #include <__type_traits/is_nothrow_constructible.h> 38 #include <__type_traits/is_pointer.h> 39 #include <__type_traits/is_same.h> 40 #include <__utility/declval.h> 41 #include <__utility/move.h> 42 43 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 44 # pragma GCC system_header 45 #endif 46 47 _LIBCPP_BEGIN_NAMESPACE_STD 48 49 _LIBCPP_SUPPRESS_DEPRECATED_PUSH 50 template <class _Iter> 51 class _LIBCPP_TEMPLATE_VIS reverse_iterator 52 #if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 53 : public iterator<typename iterator_traits<_Iter>::iterator_category, 54 typename iterator_traits<_Iter>::value_type, 55 typename iterator_traits<_Iter>::difference_type, 56 typename iterator_traits<_Iter>::pointer, 57 typename iterator_traits<_Iter>::reference> 58 #endif 59 { 60 _LIBCPP_SUPPRESS_DEPRECATED_POP 61 62 private: 63 #ifndef _LIBCPP_ABI_NO_ITERATOR_BASES 64 _Iter __t_; // no longer used as of LWG #2360, not removed due to ABI break 65 #endif 66 67 #if _LIBCPP_STD_VER >= 20 68 static_assert(__has_bidirectional_iterator_category<_Iter>::value || bidirectional_iterator<_Iter>, 69 "reverse_iterator<It> requires It to be a bidirectional iterator."); 70 #endif // _LIBCPP_STD_VER >= 20 71 72 protected: 73 _Iter current; 74 75 public: 76 using iterator_type = _Iter; 77 78 using iterator_category = 79 _If<__has_random_access_iterator_category<_Iter>::value, 80 random_access_iterator_tag, 81 typename iterator_traits<_Iter>::iterator_category>; 82 using pointer = typename iterator_traits<_Iter>::pointer; 83 #if _LIBCPP_STD_VER >= 20 84 using iterator_concept = _If<random_access_iterator<_Iter>, random_access_iterator_tag, bidirectional_iterator_tag>; 85 using value_type = iter_value_t<_Iter>; 86 using difference_type = iter_difference_t<_Iter>; 87 using reference = iter_reference_t<_Iter>; 88 #else 89 using value_type = typename iterator_traits<_Iter>::value_type; 90 using difference_type = typename iterator_traits<_Iter>::difference_type; 91 using reference = typename iterator_traits<_Iter>::reference; 92 #endif 93 94 #ifndef _LIBCPP_ABI_NO_ITERATOR_BASES 95 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator() : __t_(), current() {} 96 97 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 explicit reverse_iterator(_Iter __x) : __t_(__x), current(__x) {} 98 99 template <class _Up, __enable_if_t<!is_same<_Up, _Iter>::value && is_convertible<_Up const&, _Iter>::value, int> = 0> 100 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator(const reverse_iterator<_Up>& __u) 101 : __t_(__u.base()), current(__u.base()) {} 102 103 template <class _Up, 104 __enable_if_t<!is_same<_Up, _Iter>::value && is_convertible<_Up const&, _Iter>::value && 105 is_assignable<_Iter&, _Up const&>::value, 106 int> = 0> 107 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator& operator=(const reverse_iterator<_Up>& __u) { 108 __t_ = current = __u.base(); 109 return *this; 110 } 111 #else 112 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator() : current() {} 113 114 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 explicit reverse_iterator(_Iter __x) : current(__x) {} 115 116 template <class _Up, __enable_if_t<!is_same<_Up, _Iter>::value && is_convertible<_Up const&, _Iter>::value, int> = 0> 117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator(const reverse_iterator<_Up>& __u) 118 : current(__u.base()) {} 119 120 template <class _Up, 121 __enable_if_t<!is_same<_Up, _Iter>::value && is_convertible<_Up const&, _Iter>::value && 122 is_assignable<_Iter&, _Up const&>::value, 123 int> = 0> 124 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator& operator=(const reverse_iterator<_Up>& __u) { 125 current = __u.base(); 126 return *this; 127 } 128 #endif 129 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 _Iter base() const { return current; } 130 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reference operator*() const { 131 _Iter __tmp = current; 132 return *--__tmp; 133 } 134 135 #if _LIBCPP_STD_VER >= 20 136 _LIBCPP_HIDE_FROM_ABI constexpr pointer operator->() const 137 requires is_pointer_v<_Iter> || requires(const _Iter __i) { __i.operator->(); } 138 { 139 _Iter __tmp = current; 140 --__tmp; 141 if constexpr (is_pointer_v<_Iter>) { 142 return __tmp; 143 } else { 144 return __tmp.operator->(); 145 } 146 } 147 #else 148 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pointer operator->() const { return std::addressof(operator*()); } 149 #endif // _LIBCPP_STD_VER >= 20 150 151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator& operator++() { 152 --current; 153 return *this; 154 } 155 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator operator++(int) { 156 reverse_iterator __tmp(*this); 157 --current; 158 return __tmp; 159 } 160 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator& operator--() { 161 ++current; 162 return *this; 163 } 164 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator operator--(int) { 165 reverse_iterator __tmp(*this); 166 ++current; 167 return __tmp; 168 } 169 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator operator+(difference_type __n) const { 170 return reverse_iterator(current - __n); 171 } 172 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator& operator+=(difference_type __n) { 173 current -= __n; 174 return *this; 175 } 176 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator operator-(difference_type __n) const { 177 return reverse_iterator(current + __n); 178 } 179 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator& operator-=(difference_type __n) { 180 current += __n; 181 return *this; 182 } 183 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reference operator[](difference_type __n) const { 184 return *(*this + __n); 185 } 186 187 #if _LIBCPP_STD_VER >= 20 188 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_rvalue_reference_t<_Iter> iter_move(const reverse_iterator& __i) noexcept( 189 is_nothrow_copy_constructible_v<_Iter> && noexcept(ranges::iter_move(--std::declval<_Iter&>()))) { 190 auto __tmp = __i.base(); 191 return ranges::iter_move(--__tmp); 192 } 193 194 template <indirectly_swappable<_Iter> _Iter2> 195 _LIBCPP_HIDE_FROM_ABI friend constexpr void 196 iter_swap(const reverse_iterator& __x, const reverse_iterator<_Iter2>& __y) noexcept( 197 is_nothrow_copy_constructible_v<_Iter> && is_nothrow_copy_constructible_v<_Iter2> && 198 noexcept(ranges::iter_swap(--std::declval<_Iter&>(), --std::declval<_Iter2&>()))) { 199 auto __xtmp = __x.base(); 200 auto __ytmp = __y.base(); 201 ranges::iter_swap(--__xtmp, --__ytmp); 202 } 203 #endif // _LIBCPP_STD_VER >= 20 204 }; 205 206 template <class _Iter1, class _Iter2> 207 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 bool 208 operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 209 #if _LIBCPP_STD_VER >= 20 210 requires requires { 211 { __x.base() == __y.base() } -> convertible_to<bool>; 212 } 213 #endif // _LIBCPP_STD_VER >= 20 214 { 215 return __x.base() == __y.base(); 216 } 217 218 template <class _Iter1, class _Iter2> 219 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 bool 220 operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 221 #if _LIBCPP_STD_VER >= 20 222 requires requires { 223 { __x.base() > __y.base() } -> convertible_to<bool>; 224 } 225 #endif // _LIBCPP_STD_VER >= 20 226 { 227 return __x.base() > __y.base(); 228 } 229 230 template <class _Iter1, class _Iter2> 231 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 bool 232 operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 233 #if _LIBCPP_STD_VER >= 20 234 requires requires { 235 { __x.base() != __y.base() } -> convertible_to<bool>; 236 } 237 #endif // _LIBCPP_STD_VER >= 20 238 { 239 return __x.base() != __y.base(); 240 } 241 242 template <class _Iter1, class _Iter2> 243 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 bool 244 operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 245 #if _LIBCPP_STD_VER >= 20 246 requires requires { 247 { __x.base() < __y.base() } -> convertible_to<bool>; 248 } 249 #endif // _LIBCPP_STD_VER >= 20 250 { 251 return __x.base() < __y.base(); 252 } 253 254 template <class _Iter1, class _Iter2> 255 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 bool 256 operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 257 #if _LIBCPP_STD_VER >= 20 258 requires requires { 259 { __x.base() <= __y.base() } -> convertible_to<bool>; 260 } 261 #endif // _LIBCPP_STD_VER >= 20 262 { 263 return __x.base() <= __y.base(); 264 } 265 266 template <class _Iter1, class _Iter2> 267 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 bool 268 operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 269 #if _LIBCPP_STD_VER >= 20 270 requires requires { 271 { __x.base() >= __y.base() } -> convertible_to<bool>; 272 } 273 #endif // _LIBCPP_STD_VER >= 20 274 { 275 return __x.base() >= __y.base(); 276 } 277 278 #if _LIBCPP_STD_VER >= 20 279 template <class _Iter1, three_way_comparable_with<_Iter1> _Iter2> 280 _LIBCPP_HIDE_FROM_ABI constexpr compare_three_way_result_t<_Iter1, _Iter2> 281 operator<=>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) { 282 return __y.base() <=> __x.base(); 283 } 284 #endif // _LIBCPP_STD_VER >= 20 285 286 #ifndef _LIBCPP_CXX03_LANG 287 template <class _Iter1, class _Iter2> 288 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 auto 289 operator-(const reverse_iterator<_Iter1>& __x, 290 const reverse_iterator<_Iter2>& __y) -> decltype(__y.base() - __x.base()) { 291 return __y.base() - __x.base(); 292 } 293 #else 294 template <class _Iter1, class _Iter2> 295 inline _LIBCPP_HIDE_FROM_ABI typename reverse_iterator<_Iter1>::difference_type 296 operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) { 297 return __y.base() - __x.base(); 298 } 299 #endif 300 301 template <class _Iter> 302 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator<_Iter> 303 operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x) { 304 return reverse_iterator<_Iter>(__x.base() - __n); 305 } 306 307 #if _LIBCPP_STD_VER >= 20 308 template <class _Iter1, class _Iter2> 309 requires(!sized_sentinel_for<_Iter1, _Iter2>) 310 inline constexpr bool disable_sized_sentinel_for<reverse_iterator<_Iter1>, reverse_iterator<_Iter2>> = true; 311 #endif // _LIBCPP_STD_VER >= 20 312 313 #if _LIBCPP_STD_VER >= 14 314 template <class _Iter> 315 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reverse_iterator<_Iter> make_reverse_iterator(_Iter __i) { 316 return reverse_iterator<_Iter>(__i); 317 } 318 #endif 319 320 #if _LIBCPP_STD_VER >= 20 321 template <ranges::bidirectional_range _Range> 322 _LIBCPP_HIDE_FROM_ABI constexpr ranges::subrange<reverse_iterator<ranges::iterator_t<_Range>>, 323 reverse_iterator<ranges::iterator_t<_Range>>> 324 __reverse_range(_Range&& __range) { 325 auto __first = ranges::begin(__range); 326 return {std::make_reverse_iterator(ranges::next(__first, ranges::end(__range))), std::make_reverse_iterator(__first)}; 327 } 328 #endif 329 330 template <class _Iter, bool __b> 331 struct __unwrap_iter_impl<reverse_iterator<reverse_iterator<_Iter> >, __b> { 332 using _UnwrappedIter _LIBCPP_NODEBUG = decltype(__unwrap_iter_impl<_Iter>::__unwrap(std::declval<_Iter>())); 333 using _ReverseWrapper _LIBCPP_NODEBUG = reverse_iterator<reverse_iterator<_Iter> >; 334 335 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ReverseWrapper 336 __rewrap(_ReverseWrapper __orig_iter, _UnwrappedIter __unwrapped_iter) { 337 return _ReverseWrapper( 338 reverse_iterator<_Iter>(__unwrap_iter_impl<_Iter>::__rewrap(__orig_iter.base().base(), __unwrapped_iter))); 339 } 340 341 static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _UnwrappedIter __unwrap(_ReverseWrapper __i) _NOEXCEPT { 342 return __unwrap_iter_impl<_Iter>::__unwrap(__i.base().base()); 343 } 344 }; 345 346 _LIBCPP_END_NAMESPACE_STD 347 348 #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H 349