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