libstdc++
lu_map_.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2025 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file list_update_map_/lu_map_.hpp
38 * Contains a list update map.
39 */
40
41#include <utility>
42#include <iterator>
43#include <ext/pb_ds/detail/cond_dealtor.hpp>
44#include <ext/pb_ds/tag_and_trait.hpp>
45#include <ext/pb_ds/detail/types_traits.hpp>
46#include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp>
47#include <ext/pb_ds/exception.hpp>
48#ifdef _GLIBCXX_DEBUG
49#include <ext/pb_ds/detail/debug_map_base.hpp>
50#endif
51#ifdef PB_DS_LU_MAP_TRACE_
52#include <iostream>
53#endif
54#include <debug/debug.h>
55
56namespace __gnu_pbds
57{
58 namespace detail
59 {
60#ifdef PB_DS_DATA_TRUE_INDICATOR
61#define PB_DS_LU_NAME lu_map
62#endif
63
64#ifdef PB_DS_DATA_FALSE_INDICATOR
65#define PB_DS_LU_NAME lu_set
66#endif
67
68#define PB_DS_CLASS_T_DEC \
69 template<typename Key, typename Mapped, typename Eq_Fn, \
70 typename _Alloc, typename Update_Policy>
71
72#define PB_DS_CLASS_C_DEC \
73 PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy>
74
75#define PB_DS_LU_TRAITS_BASE \
76 types_traits<Key, Mapped, _Alloc, false>
77
78#ifdef _GLIBCXX_DEBUG
79#define PB_DS_DEBUG_MAP_BASE_C_DEC \
80 debug_map_base<Key, Eq_Fn, \
81 typename rebind_traits<_Alloc, Key>::const_reference>
82#endif
83
84 /// list-based (with updates) associative container.
85 /// Skip to the lu, my darling.
86 template<typename Key,
87 typename Mapped,
88 typename Eq_Fn,
89 typename _Alloc,
90 typename Update_Policy>
91 class PB_DS_LU_NAME :
92#ifdef _GLIBCXX_DEBUG
93 protected PB_DS_DEBUG_MAP_BASE_C_DEC,
94#endif
95 public PB_DS_LU_TRAITS_BASE
96 {
97 private:
98 typedef PB_DS_LU_TRAITS_BASE traits_base;
99
100 struct entry
101 : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
102 {
103 typename traits_base::value_type m_value;
104 typename rebind_traits<_Alloc, entry>::pointer m_p_next;
105 };
106
107 typedef rebind_traits<_Alloc, entry> entry_alloc_traits;
108 typedef typename entry_alloc_traits::allocator_type entry_allocator;
109 typedef typename entry_alloc_traits::pointer entry_pointer;
110 typedef typename entry_alloc_traits::const_pointer const_entry_pointer;
111 typedef typename entry_alloc_traits::reference entry_reference;
112 typedef typename entry_alloc_traits::const_reference const_entry_reference;
113
114 typedef rebind_traits<_Alloc, entry_pointer> entry_pointer_alloc_traits;
115 typedef typename entry_pointer_alloc_traits::allocator_type entry_pointer_allocator;
116 typedef typename entry_pointer_alloc_traits::pointer entry_pointer_array;
117
118 typedef typename traits_base::value_type value_type_;
119 typedef typename traits_base::pointer pointer_;
120 typedef typename traits_base::const_pointer const_pointer_;
121 typedef typename traits_base::reference reference_;
122 typedef typename traits_base::const_reference const_reference_;
123
124#define PB_DS_GEN_POS entry_pointer
125
126#include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
127#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
128#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
129#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
130
131#undef PB_DS_GEN_POS
132
133
134#ifdef _GLIBCXX_DEBUG
135 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
136#endif
137
138 typedef cond_dealtor<entry, _Alloc> cond_dealtor_t;
139
140 public:
141 typedef _Alloc allocator_type;
142 typedef typename _Alloc::size_type size_type;
143 typedef typename _Alloc::difference_type difference_type;
144 typedef Eq_Fn eq_fn;
145 typedef Update_Policy update_policy;
146 typedef typename Update_Policy::metadata_type update_metadata;
147 typedef typename traits_base::key_type key_type;
148 typedef typename traits_base::key_pointer key_pointer;
149 typedef typename traits_base::key_const_pointer key_const_pointer;
150 typedef typename traits_base::key_reference key_reference;
151 typedef typename traits_base::key_const_reference key_const_reference;
152 typedef typename traits_base::mapped_type mapped_type;
153 typedef typename traits_base::mapped_pointer mapped_pointer;
154 typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
155 typedef typename traits_base::mapped_reference mapped_reference;
156 typedef typename traits_base::mapped_const_reference mapped_const_reference;
157 typedef typename traits_base::value_type value_type;
158 typedef typename traits_base::pointer pointer;
159 typedef typename traits_base::const_pointer const_pointer;
160 typedef typename traits_base::reference reference;
161 typedef typename traits_base::const_reference const_reference;
162
163#ifdef PB_DS_DATA_TRUE_INDICATOR
164 typedef point_iterator_ point_iterator;
165#endif
166
167#ifdef PB_DS_DATA_FALSE_INDICATOR
168 typedef point_const_iterator_ point_iterator;
169#endif
170
171 typedef point_const_iterator_ point_const_iterator;
172
173#ifdef PB_DS_DATA_TRUE_INDICATOR
174 typedef iterator_ iterator;
175#endif
176
177#ifdef PB_DS_DATA_FALSE_INDICATOR
178 typedef const_iterator_ iterator;
179#endif
180
181 typedef const_iterator_ const_iterator;
182
183 public:
184 PB_DS_LU_NAME();
185
186 PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&);
187
188 virtual
189 ~PB_DS_LU_NAME();
190
191 template<typename It>
192 PB_DS_LU_NAME(It, It);
193
194 void
195 swap(PB_DS_CLASS_C_DEC&);
196
197 inline size_type
198 size() const;
199
200 inline size_type
201 max_size() const;
202
203 _GLIBCXX_NODISCARD inline bool
204 empty() const;
205
206 inline mapped_reference
207 operator[](key_const_reference r_key)
208 {
209#ifdef PB_DS_DATA_TRUE_INDICATOR
210 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
211 return insert(std::make_pair(r_key, mapped_type())).first->second;
212#else
213 insert(r_key);
214 return traits_base::s_null_type;
215#endif
216 }
217
218 inline std::pair<point_iterator, bool>
219 insert(const_reference);
220
221 inline point_iterator
222 find(key_const_reference r_key)
223 {
224 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
225 entry_pointer p_e = find_imp(r_key);
226 return point_iterator(p_e == 0 ? 0: &p_e->m_value);
227 }
228
229 inline point_const_iterator
230 find(key_const_reference r_key) const
231 {
232 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
233 entry_pointer p_e = find_imp(r_key);
234 return point_const_iterator(p_e == 0 ? 0: &p_e->m_value);
235 }
236
237 inline bool
238 erase(key_const_reference);
239
240 template<typename Pred>
241 inline size_type
242 erase_if(Pred);
243
244 void
245 clear();
246
247 inline iterator
248 begin();
249
250 inline const_iterator
251 begin() const;
252
253 inline iterator
254 end();
255
256 inline const_iterator
257 end() const;
258
259#ifdef _GLIBCXX_DEBUG
260 void
261 assert_valid(const char* file, int line) const;
262#endif
263
264#ifdef PB_DS_LU_MAP_TRACE_
265 void
266 trace() const;
267#endif
268
269 protected:
270
271 template<typename It>
272 void
273 copy_from_range(It, It);
274
275 private:
276#ifdef PB_DS_DATA_TRUE_INDICATOR
277 friend class iterator_;
278#endif
279
280 friend class const_iterator_;
281
282 inline entry_pointer
283 allocate_new_entry(const_reference, false_type);
284
285 inline entry_pointer
286 allocate_new_entry(const_reference, true_type);
287
288 template<typename Metadata>
289 inline static void
290 init_entry_metadata(entry_pointer, type_to_type<Metadata>);
291
292 inline static void
293 init_entry_metadata(entry_pointer, type_to_type<null_type>);
294
295 void
296 deallocate_all();
297
298 void
299 erase_next(entry_pointer);
300
301 void
302 actual_erase_entry(entry_pointer);
303
304 void
305 inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
306 {
307 r_pos = r_pos->m_p_next;
308 r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value;
309 }
310
311 template<typename Metadata>
312 inline static bool
313 apply_update(entry_pointer, type_to_type<Metadata>);
314
315 inline static bool
316 apply_update(entry_pointer, type_to_type<null_type>);
317
318 inline entry_pointer
319 find_imp(key_const_reference) const;
320
321 static entry_allocator s_entry_allocator;
322 static Eq_Fn s_eq_fn;
323 static Update_Policy s_update_policy;
324 static type_to_type<update_metadata> s_metadata_type_indicator;
325 static null_type s_null_type;
326
327 mutable entry_pointer m_p_l;
328 };
329
330#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
331#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
332#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
333#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
334#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
335#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
336#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
337#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
338
339#undef PB_DS_CLASS_T_DEC
340#undef PB_DS_CLASS_C_DEC
341#undef PB_DS_LU_TRAITS_BASE
342#undef PB_DS_DEBUG_MAP_BASE_C_DEC
343#undef PB_DS_LU_NAME
344 } // namespace detail
345} // namespace __gnu_pbds
std::make_pair
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.
Definition stl_pair.h:1166
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition assoc_container.hpp:52
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
__gnu_pbds::null_type
Represents no type, or absence of type, for template tricks.
Definition tag_and_trait.hpp:210
__gnu_pbds::detail::cond_dealtor
Conditional deallocate constructor argument.
Definition cond_dealtor.hpp:53
__gnu_pbds::detail::rebind_traits
Consistent API for accessing allocator-related types.
Definition types_traits.hpp:140