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