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