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 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_UNCATEGORIZED(__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_UNCATEGORIZED(__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_UNCATEGORIZED(__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_UNCATEGORIZED(__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_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end."); 145 --__count_; 146 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS 147 try { return __current_++; } 148 catch(...) { ++__count_; throw; } 149 #else 150 return __current_++; 151 #endif // _LIBCPP_HAS_NO_EXCEPTIONS 152 } 153 154 _LIBCPP_HIDE_FROM_ABI 155 constexpr counted_iterator operator++(int) 156 requires forward_iterator<_Iter> 157 { 158 _LIBCPP_ASSERT_UNCATEGORIZED(__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_UNCATEGORIZED(__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_UNCATEGORIZED(-__n <= __count_, 241 "Attempt to subtract too large of a size: " 242 "counted_iterator would be decremented before the " 243 "first element of its range."); 244 __current_ -= __n; 245 __count_ += __n; 246 return *this; 247 } 248 249 _LIBCPP_HIDE_FROM_ABI 250 constexpr decltype(auto) operator[](iter_difference_t<_Iter> __n) const 251 requires random_access_iterator<_Iter> 252 { 253 _LIBCPP_ASSERT_UNCATEGORIZED(__n < __count_, "Subscript argument must be less than size."); 254 return __current_[__n]; 255 } 256 257 template<common_with<_Iter> _I2> 258 _LIBCPP_HIDE_FROM_ABI 259 friend constexpr bool operator==( 260 const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) 261 { 262 return __lhs.__count_ == __rhs.__count_; 263 } 264 265 _LIBCPP_HIDE_FROM_ABI 266 friend constexpr bool operator==( 267 const counted_iterator& __lhs, default_sentinel_t) 268 { 269 return __lhs.__count_ == 0; 270 } 271 272 template<common_with<_Iter> _I2> 273 _LIBCPP_HIDE_FROM_ABI friend constexpr strong_ordering operator<=>( 274 const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) 275 { 276 return __rhs.__count_ <=> __lhs.__count_; 277 } 278 279 _LIBCPP_HIDE_FROM_ABI 280 friend constexpr iter_rvalue_reference_t<_Iter> iter_move(const counted_iterator& __i) 281 noexcept(noexcept(ranges::iter_move(__i.__current_))) 282 requires input_iterator<_Iter> 283 { 284 _LIBCPP_ASSERT_UNCATEGORIZED(__i.__count_ > 0, "Iterator must not be past end of range."); 285 return ranges::iter_move(__i.__current_); 286 } 287 288 template<indirectly_swappable<_Iter> _I2> 289 _LIBCPP_HIDE_FROM_ABI 290 friend constexpr void iter_swap(const counted_iterator& __x, const counted_iterator<_I2>& __y) 291 noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) 292 { 293 _LIBCPP_ASSERT_UNCATEGORIZED(__x.__count_ > 0 && __y.__count_ > 0, 294 "Iterators must not be past end of range."); 295 return ranges::iter_swap(__x.__current_, __y.__current_); 296 } 297 298 private: 299 _LIBCPP_NO_UNIQUE_ADDRESS _Iter __current_ = _Iter(); 300 iter_difference_t<_Iter> __count_ = 0; 301 template<input_or_output_iterator _OtherIter> 302 friend class counted_iterator; 303 }; 304 _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(counted_iterator); 305 306 template<input_iterator _Iter> 307 requires same_as<_ITER_TRAITS<_Iter>, iterator_traits<_Iter>> 308 struct iterator_traits<counted_iterator<_Iter>> : iterator_traits<_Iter> { 309 using pointer = conditional_t<contiguous_iterator<_Iter>, 310 add_pointer_t<iter_reference_t<_Iter>>, void>; 311 }; 312 313 #endif // _LIBCPP_STD_VER >= 20 314 315 _LIBCPP_END_NAMESPACE_STD 316 317 _LIBCPP_POP_MACROS 318 319 #endif // _LIBCPP___ITERATOR_COUNTED_ITERATOR_H 320