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