218 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___FLAT_MAP_KEY_VALUE_ITERATOR_H11#define _LIBCPP___FLAT_MAP_KEY_VALUE_ITERATOR_H12 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 24#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)25# pragma GCC system_header26#endif27 28_LIBCPP_PUSH_MACROS29#include <__undef_macros>30 31#if _LIBCPP_STD_VER >= 2332 33_LIBCPP_BEGIN_NAMESPACE_STD34 35/**36 * __key_value_iterator is a proxy iterator which zips the underlying37 * _KeyContainer::iterator and the underlying _MappedContainer::iterator.38 * The two underlying iterators will be incremented/decremented together.39 * And the reference is a pair of the const key reference and the value reference.40 */41template <class _Owner, class _KeyContainer, class _MappedContainer, bool _Const>42struct __key_value_iterator {43private:44 using __key_iterator _LIBCPP_NODEBUG = typename _KeyContainer::const_iterator;45 using __mapped_iterator _LIBCPP_NODEBUG =46 _If<_Const, typename _MappedContainer::const_iterator, typename _MappedContainer::iterator>;47 using __reference _LIBCPP_NODEBUG = _If<_Const, typename _Owner::const_reference, typename _Owner::reference>;48 49 struct __arrow_proxy {50 __reference __ref_;51 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __reference* operator->() { return std::addressof(__ref_); }52 };53 54 __key_iterator __key_iter_;55 __mapped_iterator __mapped_iter_;56 57 friend _Owner;58 59 template <class, class, class, bool>60 friend struct __key_value_iterator;61 62 friend struct __product_iterator_traits<__key_value_iterator>;63 64public:65 using iterator_concept = random_access_iterator_tag;66 // `__key_value_iterator` only satisfy "Cpp17InputIterator" named requirements, because67 // its `reference` is not a reference type.68 // However, to avoid surprising runtime behaviour when it is used with the69 // Cpp17 algorithms or operations, iterator_category is set to random_access_iterator_tag.70 using iterator_category = random_access_iterator_tag;71 using value_type = typename _Owner::value_type;72 using difference_type = typename _Owner::difference_type;73 74 _LIBCPP_HIDE_FROM_ABI __key_value_iterator() = default;75 76 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX2677 __key_value_iterator(__key_value_iterator<_Owner, _KeyContainer, _MappedContainer, !_Const> __i)78 requires _Const && convertible_to<typename _KeyContainer::iterator, __key_iterator> &&79 convertible_to<typename _MappedContainer::iterator, __mapped_iterator>80 : __key_iter_(std::move(__i.__key_iter_)), __mapped_iter_(std::move(__i.__mapped_iter_)) {}81 82 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX2683 __key_value_iterator(__key_iterator __key_iter, __mapped_iterator __mapped_iter)84 : __key_iter_(std::move(__key_iter)), __mapped_iter_(std::move(__mapped_iter)) {}85 86 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __reference operator*() const {87 return __reference(*__key_iter_, *__mapped_iter_);88 }89 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __arrow_proxy operator->() const { return __arrow_proxy{**this}; }90 91 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator++() {92 ++__key_iter_;93 ++__mapped_iter_;94 return *this;95 }96 97 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator operator++(int) {98 __key_value_iterator __tmp(*this);99 ++*this;100 return __tmp;101 }102 103 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator--() {104 --__key_iter_;105 --__mapped_iter_;106 return *this;107 }108 109 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator operator--(int) {110 __key_value_iterator __tmp(*this);111 --*this;112 return __tmp;113 }114 115 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator+=(difference_type __x) {116 __key_iter_ += __x;117 __mapped_iter_ += __x;118 return *this;119 }120 121 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_value_iterator& operator-=(difference_type __x) {122 __key_iter_ -= __x;123 __mapped_iter_ -= __x;124 return *this;125 }126 127 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __reference operator[](difference_type __n) const {128 return *(*this + __n);129 }130 131 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool132 operator==(const __key_value_iterator& __x, const __key_value_iterator& __y) {133 return __x.__key_iter_ == __y.__key_iter_;134 }135 136 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool137 operator<(const __key_value_iterator& __x, const __key_value_iterator& __y) {138 return __x.__key_iter_ < __y.__key_iter_;139 }140 141 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool142 operator>(const __key_value_iterator& __x, const __key_value_iterator& __y) {143 return __y < __x;144 }145 146 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool147 operator<=(const __key_value_iterator& __x, const __key_value_iterator& __y) {148 return !(__y < __x);149 }150 151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend bool152 operator>=(const __key_value_iterator& __x, const __key_value_iterator& __y) {153 return !(__x < __y);154 }155 156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend auto157 operator<=>(const __key_value_iterator& __x, const __key_value_iterator& __y)158 requires three_way_comparable<__key_iterator>159 {160 return __x.__key_iter_ <=> __y.__key_iter_;161 }162 163 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend __key_value_iterator164 operator+(const __key_value_iterator& __i, difference_type __n) {165 auto __tmp = __i;166 __tmp += __n;167 return __tmp;168 }169 170 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend __key_value_iterator171 operator+(difference_type __n, const __key_value_iterator& __i) {172 return __i + __n;173 }174 175 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend __key_value_iterator176 operator-(const __key_value_iterator& __i, difference_type __n) {177 auto __tmp = __i;178 __tmp -= __n;179 return __tmp;180 }181 182 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 friend difference_type183 operator-(const __key_value_iterator& __x, const __key_value_iterator& __y) {184 return difference_type(__x.__key_iter_ - __y.__key_iter_);185 }186};187 188template <class _Owner, class _KeyContainer, class _MappedContainer, bool _Const>189struct __product_iterator_traits<__key_value_iterator<_Owner, _KeyContainer, _MappedContainer, _Const>> {190 static constexpr size_t __size = 2;191 192 template <size_t _Nth, class _Iter>193 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static decltype(auto) __get_iterator_element(_Iter&& __it)194 requires(_Nth <= 1)195 {196 if constexpr (_Nth == 0) {197 return std::forward<_Iter>(__it).__key_iter_;198 } else {199 return std::forward<_Iter>(__it).__mapped_iter_;200 }201 }202 203 template <class _KeyIter, class _MappedIter>204 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static auto205 __make_product_iterator(_KeyIter&& __key_iter, _MappedIter&& __mapped_iter) {206 return __key_value_iterator<_Owner, _KeyContainer, _MappedContainer, _Const>(207 std::forward<_KeyIter>(__key_iter), std::forward<_MappedIter>(__mapped_iter));208 }209};210 211_LIBCPP_END_NAMESPACE_STD212 213#endif // _LIBCPP_STD_VER >= 23214 215_LIBCPP_POP_MACROS216 217#endif // _LIBCPP___FLAT_MAP_KEY_VALUE_ITERATOR_H218