v1/__iterator/counted_iterator.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___ITERATOR_COUNTED_ITERATOR_H
0011 #define _LIBCPP___ITERATOR_COUNTED_ITERATOR_H
0012
0013 #include <__assert>
0014 #include <__compare/ordering.h>
0015 #include <__concepts/assignable.h>
0016 #include <__concepts/common_with.h>
0017 #include <__concepts/constructible.h>
0018 #include <__concepts/convertible_to.h>
0019 #include <__concepts/same_as.h>
0020 #include <__config>
0021 #include <__iterator/concepts.h>
0022 #include <__iterator/default_sentinel.h>
0023 #include <__iterator/incrementable_traits.h>
0024 #include <__iterator/iter_move.h>
0025 #include <__iterator/iter_swap.h>
0026 #include <__iterator/iterator_traits.h>
0027 #include <__iterator/readable_traits.h>
0028 #include <__memory/pointer_traits.h>
0029 #include <__type_traits/add_pointer.h>
0030 #include <__type_traits/conditional.h>
0031 #include <__utility/move.h>
0032
0033 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0034 #  pragma GCC system_header
0035 #endif
0036
0037 _LIBCPP_PUSH_MACROS
0038 #include <__undef_macros>
0039
0040 _LIBCPP_BEGIN_NAMESPACE_STD
0041
0042 #if _LIBCPP_STD_VER >= 20
0043
0044 template <class>
0045 struct __counted_iterator_concept {};
0046
0047 template <class _Iter>
0048   requires requires { typename _Iter::iterator_concept; }
0049 struct __counted_iterator_concept<_Iter> {
0050   using iterator_concept = typename _Iter::iterator_concept;
0051 };
0052
0053 template <class>
0054 struct __counted_iterator_category {};
0055
0056 template <class _Iter>
0057   requires requires { typename _Iter::iterator_category; }
0058 struct __counted_iterator_category<_Iter> {
0059   using iterator_category = typename _Iter::iterator_category;
0060 };
0061
0062 template <class>
0063 struct __counted_iterator_value_type {};
0064
0065 template <indirectly_readable _Iter>
0066 struct __counted_iterator_value_type<_Iter> {
0067   using value_type = iter_value_t<_Iter>;
0068 };
0069
0070 template <input_or_output_iterator _Iter>
0071 class counted_iterator
0072     : public __counted_iterator_concept<_Iter>,
0073       public __counted_iterator_category<_Iter>,
0074       public __counted_iterator_value_type<_Iter> {
0075 public:
0076   using iterator_type   = _Iter;
0077   using difference_type = iter_difference_t<_Iter>;
0078
0079   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator()
0080     requires default_initializable<_Iter>
0081   = default;
0082
0083   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator(_Iter __iter, iter_difference_t<_Iter> __n)
0084       : __current_(std::move(__iter)), __count_(__n) {
0085     _LIBCPP_ASSERT_UNCATEGORIZED(__n >= 0, "__n must not be negative.");
0086   }
0087
0088   template <class _I2>
0089     requires convertible_to<const _I2&, _Iter>
0090   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator(const counted_iterator<_I2>& __other)
0091       : __current_(__other.__current_), __count_(__other.__count_) {}
0092
0093   template <class _I2>
0094     requires assignable_from<_Iter&, const _I2&>
0095   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator=(const counted_iterator<_I2>& __other) {
0096     __current_ = __other.__current_;
0097     __count_   = __other.__count_;
0098     return *this;
0099   }
0100
0101   _LIBCPP_HIDE_FROM_ABI constexpr const _Iter& base() const& noexcept { return __current_; }
0102
0103   _LIBCPP_HIDE_FROM_ABI constexpr _Iter base() && { return std::move(__current_); }
0104
0105   _LIBCPP_HIDE_FROM_ABI constexpr iter_difference_t<_Iter> count() const noexcept { return __count_; }
0106
0107   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() {
0108     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__count_ > 0, "Iterator is equal to or past end.");
0109     return *__current_;
0110   }
0111
0112   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const
0113     requires __dereferenceable<const _Iter>
0114   {
0115     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__count_ > 0, "Iterator is equal to or past end.");
0116     return *__current_;
0117   }
0118
0119   _LIBCPP_HIDE_FROM_ABI constexpr auto operator->() const noexcept
0120     requires contiguous_iterator<_Iter>
0121   {
0122     return std::to_address(__current_);
0123   }
0124
0125   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator++() {
0126     _LIBCPP_ASSERT_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end.");
0127     ++__current_;
0128     --__count_;
0129     return *this;
0130   }
0131
0132   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator++(int) {
0133     _LIBCPP_ASSERT_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end.");
0134     --__count_;
0135 #  if _LIBCPP_HAS_EXCEPTIONS
0136     try {
0137       return __current_++;
0138     } catch (...) {
0139       ++__count_;
0140       throw;
0141     }
0142 #  else
0143     return __current_++;
0144 #  endif // _LIBCPP_HAS_EXCEPTIONS
0145   }
0146
0147   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator++(int)
0148     requires forward_iterator<_Iter>
0149   {
0150     _LIBCPP_ASSERT_UNCATEGORIZED(__count_ > 0, "Iterator already at or past end.");
0151     counted_iterator __tmp = *this;
0152     ++*this;
0153     return __tmp;
0154   }
0155
0156   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator--()
0157     requires bidirectional_iterator<_Iter>
0158   {
0159     --__current_;
0160     ++__count_;
0161     return *this;
0162   }
0163
0164   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator--(int)
0165     requires bidirectional_iterator<_Iter>
0166   {
0167     counted_iterator __tmp = *this;
0168     --*this;
0169     return __tmp;
0170   }
0171
0172   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator+(iter_difference_t<_Iter> __n) const
0173     requires random_access_iterator<_Iter>
0174   {
0175     return counted_iterator(__current_ + __n, __count_ - __n);
0176   }
0177
0178   _LIBCPP_HIDE_FROM_ABI friend constexpr counted_iterator
0179   operator+(iter_difference_t<_Iter> __n, const counted_iterator& __x)
0180     requires random_access_iterator<_Iter>
0181   {
0182     return __x + __n;
0183   }
0184
0185   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator+=(iter_difference_t<_Iter> __n)
0186     requires random_access_iterator<_Iter>
0187   {
0188     _LIBCPP_ASSERT_UNCATEGORIZED(__n <= __count_, "Cannot advance iterator past end.");
0189     __current_ += __n;
0190     __count_ -= __n;
0191     return *this;
0192   }
0193
0194   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator operator-(iter_difference_t<_Iter> __n) const
0195     requires random_access_iterator<_Iter>
0196   {
0197     return counted_iterator(__current_ - __n, __count_ + __n);
0198   }
0199
0200   template <common_with<_Iter> _I2>
0201   _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_I2>
0202   operator-(const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) {
0203     return __rhs.__count_ - __lhs.__count_;
0204   }
0205
0206   _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_Iter>
0207   operator-(const counted_iterator& __lhs, default_sentinel_t) {
0208     return -__lhs.__count_;
0209   }
0210
0211   _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_Iter>
0212   operator-(default_sentinel_t, const counted_iterator& __rhs) {
0213     return __rhs.__count_;
0214   }
0215
0216   _LIBCPP_HIDE_FROM_ABI constexpr counted_iterator& operator-=(iter_difference_t<_Iter> __n)
0217     requires random_access_iterator<_Iter>
0218   {
0219     _LIBCPP_ASSERT_UNCATEGORIZED(
0220         -__n <= __count_,
0221         "Attempt to subtract too large of a size: "
0222         "counted_iterator would be decremented before the "
0223         "first element of its range.");
0224     __current_ -= __n;
0225     __count_ += __n;
0226     return *this;
0227   }
0228
0229   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator[](iter_difference_t<_Iter> __n) const
0230     requires random_access_iterator<_Iter>
0231   {
0232     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < __count_, "Subscript argument must be less than size.");
0233     return __current_[__n];
0234   }
0235
0236   template <common_with<_Iter> _I2>
0237   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
0238   operator==(const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) {
0239     return __lhs.__count_ == __rhs.__count_;
0240   }
0241
0242   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const counted_iterator& __lhs, default_sentinel_t) {
0243     return __lhs.__count_ == 0;
0244   }
0245
0246   template <common_with<_Iter> _I2>
0247   _LIBCPP_HIDE_FROM_ABI friend constexpr strong_ordering
0248   operator<=>(const counted_iterator& __lhs, const counted_iterator<_I2>& __rhs) {
0249     return __rhs.__count_ <=> __lhs.__count_;
0250   }
0251
0252   _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
0253   iter_move(const counted_iterator& __i) noexcept(noexcept(ranges::iter_move(__i.__current_)))
0254     requires input_iterator<_Iter>
0255   {
0256     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i.__count_ > 0, "Iterator must not be past end of range.");
0257     return ranges::iter_move(__i.__current_);
0258   }
0259
0260   template <indirectly_swappable<_Iter> _I2>
0261   _LIBCPP_HIDE_FROM_ABI friend constexpr void
0262   iter_swap(const counted_iterator& __x,
0263             const counted_iterator<_I2>& __y) noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) {
0264     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0265         __x.__count_ > 0 && __y.__count_ > 0, "Iterators must not be past end of range.");
0266     return ranges::iter_swap(__x.__current_, __y.__current_);
0267   }
0268
0269 private:
0270   _LIBCPP_NO_UNIQUE_ADDRESS _Iter __current_ = _Iter();
0271   iter_difference_t<_Iter> __count_          = 0;
0272   template <input_or_output_iterator _OtherIter>
0273   friend class counted_iterator;
0274 };
0275 _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(counted_iterator);
0276
0277 template <input_iterator _Iter>
0278   requires same_as<_ITER_TRAITS<_Iter>, iterator_traits<_Iter>>
0279 struct iterator_traits<counted_iterator<_Iter>> : iterator_traits<_Iter> {
0280   using pointer = conditional_t<contiguous_iterator<_Iter>, add_pointer_t<iter_reference_t<_Iter>>, void>;
0281 };
0282
0283 #endif // _LIBCPP_STD_VER >= 20
0284
0285 _LIBCPP_END_NAMESPACE_STD
0286
0287 _LIBCPP_POP_MACROS
0288
0289 #endif // _LIBCPP___ITERATOR_COUNTED_ITERATOR_H