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