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_COUNTED_ITERATOR_H 11 #define _LIBCPP___ITERATOR_COUNTED_ITERATOR_H 12 13 #include <__assert> 14 #include <__concepts/assignable.h> 15 #include <__concepts/common_with.h> 16 #include <__concepts/constructible.h> 17 #include <__concepts/convertible_to.h> 18 #include <__concepts/same_as.h> 19 #include <__config> 20 #include <__iterator/concepts.h> 21 #include <__iterator/default_sentinel.h> 22 #include <__iterator/incrementable_traits.h> 23 #include <__iterator/iter_move.h> 24 #include <__iterator/iter_swap.h> 25 #include <__iterator/iterator_traits.h> 26 #include <__iterator/readable_traits.h> 27 #include <__memory/pointer_traits.h> 28 #include <__type_traits/add_pointer.h> 29 #include <__type_traits/conditional.h> 30 #include <__utility/move.h> 31 #include <compare> 32 33 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 34 # pragma GCC system_header 35 #endif 36 37 _LIBCPP_PUSH_MACROS 38 #include <__undef_macros> 39 40 _LIBCPP_BEGIN_NAMESPACE_STD 41 42 #if _LIBCPP_STD_VER >= 20 43 44 template <class> 45 struct __counted_iterator_concept {}; 46 47 template <class _Iter> 48 requires requires { typename _Iter::iterator_concept; } 49 struct __counted_iterator_concept<_Iter> { 50 using iterator_concept = typename _Iter::iterator_concept; 51 }; 52 53 template <class> 54 struct __counted_iterator_category {}; 55 56 template <class _Iter> 57 requires requires { typename _Iter::iterator_category; } 58 struct __counted_iterator_category<_Iter> { 59 using iterator_category = typename _Iter::iterator_category; 60 }; 61 62 template <class> 63 struct __counted_iterator_value_type {}; 64 65 template <indirectly_readable _Iter> 66 struct __counted_iterator_value_type<_Iter> { 67 using value_type = iter_value_t<_Iter>; 68 }; 69 70 template <input_or_output_iterator _Iter> 71 class counted_iterator 72 : public __counted_iterator_concept<_Iter>, 73 public __counted_iterator_category<_Iter>, 74 public __counted_iterator_value_type<_Iter> { 75 public: 76 using iterator_type = _Iter; 77 using difference_type = iter_difference_t<_Iter>; 78 79 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator() 80 requires default_initializable<_Iter> 81 = default; 82 83 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator(_Iter __iter, iter_difference_t<_Iter> __n) 84 : __current_(std::move(__iter)), __count_(__n) { 85 _LIBCPP_ASSERT_UNCATEGORIZED(__n >= 0, "__n must not be negative."); 86 } 87 88 template <class _I2> 89 requires convertible_to<const _I2&, _Iter> 90 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator(const counted_iterator<_I2>& __other) 91 : __current_(__other.__current_), __count_(__other.__count_) {} 92 93 template <class _I2> 94 requires assignable_from<_Iter&, const _I2&> 95 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator=(const counted_iterator<_I2>& __other) { 96 __current_ = __other.__current_; 97 __count_ = __other.__count_; 98 return *this; 99 } 100 101 _LIBCPP_HIDE_FROM_ABI constexpr const _Iter& base() const& noexcept { return __current_; } 102 103 _LIBCPP_HIDE_FROM_ABI constexpr _Iter base() && { return std::move(__current_); } 104 105 _LIBCPP_HIDE_FROM_ABI constexpr iter_difference_t<_Iter> count() const noexcept { return __count_; } 106 107 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() { 108 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__count_ > 0, "Iterator is equal to or past end."); 109 return *__current_; 110 } 111 112 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const 113 requires __dereferenceable<const _Iter> 114 { 115 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__count_ > 0, "Iterator is equal to or past end."); 116 return *__current_; 117 } 118 119 _LIBCPP_HIDE_FROM_ABI constexpr auto operator->() const noexcept 120 requires contiguous_iterator<_Iter> 121 { 122 return std::to_address(__current_); 123 } 124 125 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator++() { 126 _LIBCPP_ASSERT_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end."); 127 ++__current_; 128 --__count_; 129 return *this; 130 } 131 132 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator++(int) { 133 _LIBCPP_ASSERT_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end."); 134 --__count_; 135 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 136 try { 137 return __current_++; 138 } catch (...) { 139 ++__count_; 140 throw; 141 } 142 # else 143 return __current_++; 144 # endif // _LIBCPP_HAS_NO_EXCEPTIONS 145 } 146 147 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator++(int) 148 requires forward_iterator<_Iter> 149 { 150 _LIBCPP_ASSERT_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end."); 151 counted_iterator __tmp = *this; 152 ++*this; 153 return __tmp; 154 } 155 156 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator--() 157 requires bidirectional_iterator<_Iter> 158 { 159 --__current_; 160 ++__count_; 161 return *this; 162 } 163 164 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator--(int) 165 requires bidirectional_iterator<_Iter> 166 { 167 counted_iterator __tmp = *this; 168 --*this; 169 return __tmp; 170 } 171 172 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator+(iter_difference_t<_Iter> __n) const 173 requires random_access_iterator<_Iter> 174 { 175 return counted_iterator(__current_ + __n, __count_ - __n); 176 } 177 178 _LIBCPP_HIDE_FROM_ABI friend constexpr counted_iterator 179 operator+(iter_difference_t<_Iter> __n, const counted_iterator& __x) 180 requires random_access_iterator<_Iter> 181 { 182 return __x + __n; 183 } 184 185 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator+=(iter_difference_t<_Iter> __n) 186 requires random_access_iterator<_Iter> 187 { 188 _LIBCPP_ASSERT_UNCATEGORIZED(__n <= __count_, "Cannot advance iterator past end."); 189 __current_ += __n; 190 __count_ -= __n; 191 return *this; 192 } 193 194 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator-(iter_difference_t<_Iter> __n) const 195 requires random_access_iterator<_Iter> 196 { 197 return counted_iterator(__current_ - __n, __count_ + __n); 198 } 199 200 template <common_with<_Iter> _I2> 201 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_I2> 202 operator-(const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) { 203 return __rhs.__count_ - __lhs.__count_; 204 } 205 206 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_Iter> 207 operator-(const counted_iterator& __lhs, default_sentinel_t) { 208 return -__lhs.__count_; 209 } 210 211 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_Iter> 212 operator-(default_sentinel_t, const counted_iterator& __rhs) { 213 return __rhs.__count_; 214 } 215 216 _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator-=(iter_difference_t<_Iter> __n) 217 requires random_access_iterator<_Iter> 218 { 219 _LIBCPP_ASSERT_UNCATEGORIZED( 220 -__n <= __count_, 221 "Attempt to subtract too large of a size: " 222 "counted_iterator would be decremented before the " 223 "first element of its range."); 224 __current_ -= __n; 225 __count_ += __n; 226 return *this; 227 } 228 229 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator[](iter_difference_t<_Iter> __n) const 230 requires random_access_iterator<_Iter> 231 { 232 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < __count_, "Subscript argument must be less than size."); 233 return __current_[__n]; 234 } 235 236 template <common_with<_Iter> _I2> 237 _LIBCPP_HIDE_FROM_ABI friend constexpr bool 238 operator==(const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) { 239 return __lhs.__count_ == __rhs.__count_; 240 } 241 242 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const counted_iterator& __lhs, default_sentinel_t) { 243 return __lhs.__count_ == 0; 244 } 245 246 template <common_with<_Iter> _I2> 247 _LIBCPP_HIDE_FROM_ABI friend constexpr strong_ordering 248 operator<=>(const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) { 249 return __rhs.__count_ <=> __lhs.__count_; 250 } 251 252 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_rvalue_reference_t<_Iter> 253 iter_move(const counted_iterator& __i) noexcept(noexcept(ranges::iter_move(__i.__current_))) 254 requires input_iterator<_Iter> 255 { 256 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i.__count_ > 0, "Iterator must not be past end of range."); 257 return ranges::iter_move(__i.__current_); 258 } 259 260 template <indirectly_swappable<_Iter> _I2> 261 _LIBCPP_HIDE_FROM_ABI friend constexpr void 262 iter_swap(const counted_iterator& __x, 263 const counted_iterator<_I2>& __y) noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) { 264 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 265 __x.__count_ > 0 && __y.__count_ > 0, "Iterators must not be past end of range."); 266 return ranges::iter_swap(__x.__current_, __y.__current_); 267 } 268 269 private: 270 _LIBCPP_NO_UNIQUE_ADDRESS _Iter __current_ = _Iter(); 271 iter_difference_t<_Iter> __count_ = 0; 272 template <input_or_output_iterator _OtherIter> 273 friend class counted_iterator; 274 }; 275 _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(counted_iterator); 276 277 template <input_iterator _Iter> 278 requires same_as<_ITER_TRAITS<_Iter>, iterator_traits<_Iter>> 279 struct iterator_traits<counted_iterator<_Iter>> : iterator_traits<_Iter> { 280 using pointer = conditional_t<contiguous_iterator<_Iter>, add_pointer_t<iter_reference_t<_Iter>>, void>; 281 }; 282 283 #endif // _LIBCPP_STD_VER >= 20 284 285 _LIBCPP_END_NAMESPACE_STD 286 287 _LIBCPP_POP_MACROS 288 289 #endif // _LIBCPP___ITERATOR_COUNTED_ITERATOR_H 290