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