libcxx/include/__iterator/reverse_iterator.h

   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  = decltype(__unwrap_iter_impl<_Iter>::__unwrap(std::declval<_Iter>()));
 333   using _ReverseWrapper = 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