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___FLAT_MAP_KEY_VALUE_ITERATOR_H 11 #define _LIBCPP___FLAT_MAP_KEY_VALUE_ITERATOR_H 12 13 #include <__compare/three_way_comparable.h> 14 #include <__concepts/convertible_to.h> 15 #include <__config> 16 #include <__cstddef/size_t.h> 17 #include <__iterator/iterator_traits.h> 18 #include <__iterator/product_iterator.h> 19 #include <__memory/addressof.h> 20 #include <__type_traits/conditional.h> 21 #include <__utility/forward.h> 22 #include <__utility/move.h> 23 #include <__utility/pair.h> 24 25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26 # pragma GCC system_header 27 #endif 28 29 _LIBCPP_PUSH_MACROS 30 #include <__undef_macros> 31 32 #if _LIBCPP_STD_VER >= 23 33 34 _LIBCPP_BEGIN_NAMESPACE_STD 35 36 /** 37 * __key_value_iterator is a proxy iterator which zips the underlying 38 * _KeyContainer::iterator and the underlying _MappedContainer::iterator. 39 * The two underlying iterators will be incremented/decremented together. 40 * And the reference is a pair of the const key reference and the value reference. 41 */ 42 template <class _Owner, class _KeyContainer, class _MappedContainer, bool _Const> 43 struct __key_value_iterator { 44 private: 45 using __key_iterator _LIBCPP_NODEBUG = typename _KeyContainer::const_iterator; 46 using __mapped_iterator _LIBCPP_NODEBUG = 47 _If<_Const, typename _MappedContainer::const_iterator, typename _MappedContainer::iterator>; 48 using __reference _LIBCPP_NODEBUG = _If<_Const, typename _Owner::const_reference, typename _Owner::reference>; 49 50 struct __arrow_proxy { 51 __reference __ref_; 52 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __reference* operator->() { return std::addressof(__ref_); } 53 }; 54 55 __key_iterator __key_iter_; 56 __mapped_iterator __mapped_iter_; 57 58 friend _Owner; 59 60 template <class, class, class, bool> 61 friend struct __key_value_iterator; 62 63 friend struct __product_iterator_traits<__key_value_iterator>; 64 65 public: 66 using iterator_concept = random_access_iterator_tag; 67 // `__key_value_iterator` only satisfy "Cpp17InputIterator" named requirements, because 68 // its `reference` is not a reference type. 69 // However, to avoid surprising runtime behaviour when it is used with the 70 // Cpp17 algorithms or operations, iterator_category is set to random_access_iterator_tag. 71 using iterator_category = random_access_iterator_tag; 72 using value_type = typename _Owner::value_type; 73 using difference_type = typename _Owner::difference_type; 74 75 _LIBCPP_HIDE_FROM_ABI __key_value_iterator() = default; 76 77 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 78 __key_value_iterator(__key_value_iterator<_Owner, _KeyContainer, _MappedContainer, !_Const> __i) 79 requires _Const && convertible_to<typename _KeyContainer::iterator, __key_iterator> && 80 convertible_to<typename _MappedContainer::iterator, __mapped_iterator> 81 : __key_iter_(std::move(__i.__key_iter_)), __mapped_iter_(std::move(__i.__mapped_iter_)) {} 82 83 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 84 __key_value_iterator(__key_iterator __key_iter, __mapped_iterator __mapped_iter) 85 : __key_iter_(std::move(__key_iter)), __mapped_iter_(std::move(__mapped_iter)) {} 86 87 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __reference operator*() const { 88 return __reference(*__key_iter_, *__mapped_iter_); 89 } 90 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __arrow_proxy operator->() const { return __arrow_proxy{**this}; } 91 92 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator++() { 93 ++__key_iter_; 94 ++__mapped_iter_; 95 return *this; 96 } 97 98 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator operator++(int) { 99 __key_value_iterator __tmp(*this); 100 ++*this; 101 return __tmp; 102 } 103 104 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator--() { 105 --__key_iter_; 106 --__mapped_iter_; 107 return *this; 108 } 109 110 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator operator--(int) { 111 __key_value_iterator __tmp(*this); 112 --*this; 113 return __tmp; 114 } 115 116 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator+=(difference_type __x) { 117 __key_iter_ += __x; 118 __mapped_iter_ += __x; 119 return *this; 120 } 121 122 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator-=(difference_type __x) { 123 __key_iter_ -= __x; 124 __mapped_iter_ -= __x; 125 return *this; 126 } 127 128 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __reference operator[](difference_type __n) const { 129 return *(*this + __n); 130 } 131 132 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool 133 operator==(const __key_value_iterator& __x, const __key_value_iterator& __y) { 134 return __x.__key_iter_ == __y.__key_iter_; 135 } 136 137 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool 138 operator<(const __key_value_iterator& __x, const __key_value_iterator& __y) { 139 return __x.__key_iter_ < __y.__key_iter_; 140 } 141 142 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool 143 operator>(const __key_value_iterator& __x, const __key_value_iterator& __y) { 144 return __y < __x; 145 } 146 147 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool 148 operator<=(const __key_value_iterator& __x, const __key_value_iterator& __y) { 149 return !(__y < __x); 150 } 151 152 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool 153 operator>=(const __key_value_iterator& __x, const __key_value_iterator& __y) { 154 return !(__x < __y); 155 } 156 157 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend auto 158 operator<=>(const __key_value_iterator& __x, const __key_value_iterator& __y) 159 requires three_way_comparable<__key_iterator> 160 { 161 return __x.__key_iter_ <=> __y.__key_iter_; 162 } 163 164 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend __key_value_iterator 165 operator+(const __key_value_iterator& __i, difference_type __n) { 166 auto __tmp = __i; 167 __tmp += __n; 168 return __tmp; 169 } 170 171 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend __key_value_iterator 172 operator+(difference_type __n, const __key_value_iterator& __i) { 173 return __i + __n; 174 } 175 176 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend __key_value_iterator 177 operator-(const __key_value_iterator& __i, difference_type __n) { 178 auto __tmp = __i; 179 __tmp -= __n; 180 return __tmp; 181 } 182 183 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend difference_type 184 operator-(const __key_value_iterator& __x, const __key_value_iterator& __y) { 185 return difference_type(__x.__key_iter_ - __y.__key_iter_); 186 } 187 }; 188 189 template <class _Owner, class _KeyContainer, class _MappedContainer, bool _Const> 190 struct __product_iterator_traits<__key_value_iterator<_Owner, _KeyContainer, _MappedContainer, _Const>> { 191 static constexpr size_t __size = 2; 192 193 template <size_t _Nth, class _Iter> 194 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static decltype(auto) __get_iterator_element(_Iter&& __it) 195 requires(_Nth <= 1) 196 { 197 if constexpr (_Nth == 0) { 198 return std::forward<_Iter>(__it).__key_iter_; 199 } else { 200 return std::forward<_Iter>(__it).__mapped_iter_; 201 } 202 } 203 204 template <class _KeyIter, class _MappedIter> 205 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto 206 __make_product_iterator(_KeyIter&& __key_iter, _MappedIter&& __mapped_iter) { 207 return __key_value_iterator<_Owner, _KeyContainer, _MappedContainer, _Const>( 208 std::forward<_KeyIter>(__key_iter), std::forward<_MappedIter>(__mapped_iter)); 209 } 210 }; 211 212 _LIBCPP_END_NAMESPACE_STD 213 214 #endif // _LIBCPP_STD_VER >= 23 215 216 _LIBCPP_POP_MACROS 217 218 #endif // _LIBCPP___FLAT_MAP_KEY_VALUE_ITERATOR_H 219