51#ifdef PB_DS_LU_MAP_TRACE_
60#ifdef PB_DS_DATA_TRUE_INDICATOR
61#define PB_DS_LU_NAME lu_map
64#ifdef PB_DS_DATA_FALSE_INDICATOR
65#define PB_DS_LU_NAME lu_set
68#define PB_DS_CLASS_T_DEC \
69 template<typename Key, typename Mapped, typename Eq_Fn, \
70 typename _Alloc, typename Update_Policy>
72#define PB_DS_CLASS_C_DEC \
73 PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy>
75#define PB_DS_LU_TRAITS_BASE \
76 types_traits<Key, Mapped, _Alloc, false>
79#define PB_DS_DEBUG_MAP_BASE_C_DEC \
80 debug_map_base<Key, Eq_Fn, \
81 typename _Alloc::template rebind<Key>::other::const_reference>
86 template<
typename Key,
90 typename Update_Policy>
93 protected PB_DS_DEBUG_MAP_BASE_C_DEC,
95 public PB_DS_LU_TRAITS_BASE
101 :
public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
103 typename traits_base::value_type m_value;
104 typename _Alloc::template rebind<entry>::other::pointer m_p_next;
107 typedef typename _Alloc::template rebind<entry>::other entry_allocator;
108 typedef typename entry_allocator::pointer entry_pointer;
109 typedef typename entry_allocator::const_pointer const_entry_pointer;
110 typedef typename entry_allocator::reference entry_reference;
111 typedef typename entry_allocator::const_reference const_entry_reference;
113 typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
114 typedef typename entry_pointer_allocator::pointer entry_pointer_array;
116 typedef typename traits_base::value_type value_type_;
117 typedef typename traits_base::pointer pointer_;
118 typedef typename traits_base::const_pointer const_pointer_;
119 typedef typename traits_base::reference reference_;
120 typedef typename traits_base::const_reference const_reference_;
122#define PB_DS_GEN_POS entry_pointer
133 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
139 typedef _Alloc allocator_type;
140 typedef typename _Alloc::size_type size_type;
141 typedef typename _Alloc::difference_type difference_type;
143 typedef Update_Policy update_policy;
144 typedef typename Update_Policy::metadata_type update_metadata;
145 typedef typename traits_base::key_type key_type;
146 typedef typename traits_base::key_pointer key_pointer;
147 typedef typename traits_base::key_const_pointer key_const_pointer;
148 typedef typename traits_base::key_reference key_reference;
149 typedef typename traits_base::key_const_reference key_const_reference;
150 typedef typename traits_base::mapped_type mapped_type;
151 typedef typename traits_base::mapped_pointer mapped_pointer;
152 typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
153 typedef typename traits_base::mapped_reference mapped_reference;
154 typedef typename traits_base::mapped_const_reference mapped_const_reference;
155 typedef typename traits_base::value_type value_type;
156 typedef typename traits_base::pointer pointer;
157 typedef typename traits_base::const_pointer const_pointer;
158 typedef typename traits_base::reference reference;
159 typedef typename traits_base::const_reference const_reference;
161#ifdef PB_DS_DATA_TRUE_INDICATOR
165#ifdef PB_DS_DATA_FALSE_INDICATOR
171#ifdef PB_DS_DATA_TRUE_INDICATOR
175#ifdef PB_DS_DATA_FALSE_INDICATOR
184 PB_DS_LU_NAME(
const PB_DS_CLASS_C_DEC&);
189 template<
typename It>
190 PB_DS_LU_NAME(It, It);
193 swap(PB_DS_CLASS_C_DEC&);
201 _GLIBCXX_NODISCARD
inline bool
204 inline mapped_reference
205 operator[](key_const_reference r_key)
207#ifdef PB_DS_DATA_TRUE_INDICATOR
208 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
209 return insert(
std::make_pair(r_key, mapped_type())).first->second;
212 return traits_base::s_null_type;
217 insert(const_reference);
220 find(key_const_reference r_key)
222 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
223 entry_pointer p_e = find_imp(r_key);
228 find(key_const_reference r_key)
const
230 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
231 entry_pointer p_e = find_imp(r_key);
236 erase(key_const_reference);
238 template<
typename Pred>
259 assert_valid(
const char* file,
int line)
const;
262#ifdef PB_DS_LU_MAP_TRACE_
269 template<
typename It>
271 copy_from_range(It, It);
274#ifdef PB_DS_DATA_TRUE_INDICATOR
281 allocate_new_entry(const_reference, false_type);
284 allocate_new_entry(const_reference, true_type);
286 template<
typename Metadata>
288 init_entry_metadata(entry_pointer, type_to_type<Metadata>);
291 init_entry_metadata(entry_pointer, type_to_type<null_type>);
297 erase_next(entry_pointer);
300 actual_erase_entry(entry_pointer);
303 inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos)
const
305 r_pos = r_pos->m_p_next;
306 r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value;
309 template<
typename Metadata>
311 apply_update(entry_pointer, type_to_type<Metadata>);
314 apply_update(entry_pointer, type_to_type<null_type>);
317 find_imp(key_const_reference)
const;
319 static entry_allocator s_entry_allocator;
320 static Eq_Fn s_eq_fn;
321 static Update_Policy s_update_policy;
322 static type_to_type<update_metadata> s_metadata_type_indicator;
325 mutable entry_pointer m_p_l;
337#undef PB_DS_CLASS_T_DEC
338#undef PB_DS_CLASS_C_DEC
339#undef PB_DS_LU_TRAITS_BASE
340#undef PB_DS_DEBUG_MAP_BASE_C_DEC
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list.
GNU extensions for policy-based data structures for public use.
Struct holding two objects of arbitrary type.
Represents no type, or absence of type, for template tricks.
Conditional deallocate constructor argument.
Const range-type iterator.
Const point-type iterator.