Line data Source code
1 : // Author(s): Jan Friso Groote, Maurice Laveaux
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 : //
10 : /// \file mcrl2/data/standard_containers/unordered_map.h
11 : /// \brief This file contains a unordered_map class that behaves
12 : /// exactly as a standard unordered_map. It can only be used
13 : /// to store class instances that derive from aterms.
14 : /// The stored aterms are protected as a whole, i.e.,
15 : /// time and memory is saved as individual protection
16 : /// per element is unnecessary.
17 :
18 : #ifndef MCRL2_ATERMPP_STANDARD_CONTAINER_UNORDERED_MAP_H
19 : #define MCRL2_ATERMPP_STANDARD_CONTAINER_UNORDERED_MAP_H
20 : #pragma once
21 :
22 : #include <unordered_map>
23 : #include "mcrl2/atermpp/detail/aterm_container.h"
24 : #include "mcrl2/utilities/shared_mutex.h"
25 :
26 : /// \brief The main namespace for the aterm++ library.
27 : namespace atermpp
28 : {
29 :
30 : /// \brief A unordered_map class in which aterms can be stored.
31 : template < class Key,
32 : class T,
33 : class Hash = std::hash<detail::reference_aterm<Key> >,
34 : class Pred = std::equal_to<detail::reference_aterm<Key> >,
35 : class Alloc = std::allocator< std::pair<const detail::reference_aterm<Key>, detail::reference_aterm<T> > > >
36 :
37 : class unordered_map : public std::unordered_map< detail::reference_aterm<Key>, detail::reference_aterm<T>, Hash, Pred, Alloc >
38 : {
39 : protected:
40 : typedef std::unordered_map< detail::reference_aterm<Key>, detail::reference_aterm<T>, Hash, Pred, Alloc > super;
41 :
42 : detail::generic_aterm_container<std::unordered_map< detail::reference_aterm<Key>, detail::reference_aterm<T>, Hash, Pred, Alloc > > container_wrapper;
43 :
44 : public:
45 :
46 : /// Standard typedefs.
47 : typedef typename super::allocator_type allocator_type;
48 : typedef typename super::value_type value_type;
49 : typedef typename super::size_type size_type;
50 : typedef typename super::node_type node_type;
51 : typedef typename super::reference reference;
52 : typedef typename super::iterator iterator;
53 : typedef typename super::const_iterator const_iterator;
54 : typedef typename super::insert_return_type insert_return_type;
55 :
56 : /// \brief Default constructor.
57 119 : unordered_map()
58 : : super(),
59 119 : container_wrapper(*this)
60 119 : {}
61 :
62 : /// \brief Constructor.
63 : explicit unordered_map (const allocator_type& alloc)
64 : : super::unordered_map(alloc),
65 : container_wrapper(*this)
66 : {}
67 :
68 : /// \brief Constructor.
69 : explicit unordered_map (size_type n, const allocator_type& alloc = allocator_type())
70 : : super::unordered_map(n, alloc),
71 : container_wrapper(*this)
72 : {}
73 :
74 : unordered_map (size_type n, const value_type& val, const allocator_type& alloc = allocator_type())
75 : : super::unordered_map(n, detail::reference_aterm(val), alloc),
76 : container_wrapper(*this)
77 : {}
78 :
79 : /// \brief Constructor.
80 : template <class InputIterator>
81 : unordered_map (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
82 : : super::unordered_map(first, last, alloc),
83 : container_wrapper(*this)
84 : {}
85 :
86 : /// \brief Constructor.
87 : unordered_map (const unordered_map& x)
88 : : super::unordered_map(x),
89 : container_wrapper(*this)
90 : {}
91 :
92 : /// \brief Constructor.
93 : unordered_map (const unordered_map& x, const allocator_type& alloc)
94 : : super::unordered_map(x, alloc),
95 : container_wrapper(*this)
96 : {}
97 :
98 : /// \brief Constructor.
99 : unordered_map (unordered_map&& x)
100 : : super::unordered_map(std::move(x)),
101 : container_wrapper(*this)
102 : {}
103 :
104 :
105 : /// \brief Constructor.
106 : unordered_map (unordered_map&& x, const allocator_type& alloc)
107 : : super::unordered_map(std::move(x), alloc),
108 : container_wrapper(*this)
109 : {}
110 :
111 : /// \brief Constructor. To be done later....
112 : unordered_map (std::initializer_list<value_type> il, const allocator_type& alloc = allocator_type())
113 : : super::unordered_map(il, alloc),
114 : container_wrapper(*this)
115 : {}
116 :
117 : /// \brief Standard assignment.
118 : unordered_map& operator=(const unordered_map& other)=default;
119 :
120 : /// \brief Standard move assignment.
121 : unordered_map& operator=(unordered_map&& other)=default;
122 :
123 : /// \brief Standard destructor.
124 119 : ~unordered_map()=default;
125 :
126 : void clear() noexcept;
127 :
128 : /// \brief Inserts an element referring to a default value in the map.
129 : std::pair<iterator,bool> insert( const value_type& value );
130 :
131 : template< class P >
132 : std::pair<iterator,bool> insert( P&& value );
133 :
134 : iterator insert( const_iterator hint, const value_type& value );
135 :
136 : template< class P >
137 : iterator insert( const_iterator hint, P&& value );
138 :
139 : template< class InputIt >
140 : void insert( InputIt first, InputIt last );
141 :
142 : void insert( std::initializer_list<value_type> ilist );
143 :
144 : insert_return_type insert( node_type&& nh );
145 :
146 : iterator insert( const_iterator hint, node_type&& nh );
147 :
148 : template <class M>
149 : std::pair<iterator, bool> insert_or_assign( const Key& k, M&& obj );
150 :
151 : template <class M>
152 : std::pair<iterator, bool> insert_or_assign( Key&& k, M&& obj );
153 :
154 : template <class M>
155 : iterator insert_or_assign( const_iterator hint, const Key& k, M&& obj );
156 :
157 : template <class M>
158 : iterator insert_or_assign( const_iterator hint, Key&& k, M&& obj );
159 :
160 : template< class... Args >
161 : std::pair<iterator,bool> emplace( Args&&... args );
162 :
163 : template <class... Args>
164 : iterator emplace_hint( const_iterator hint, Args&&... args );
165 :
166 : template< class... Args >
167 : std::pair<iterator, bool> try_emplace( const Key& k, Args&&... args );
168 :
169 : template< class... Args >
170 : std::pair<iterator, bool> try_emplace( Key&& k, Args&&... args );
171 :
172 : template< class... Args >
173 : iterator try_emplace( const_iterator hint, const Key& k, Args&&... args );
174 :
175 : template< class... Args >
176 : iterator try_emplace( const_iterator hint, Key&& k, Args&&... args );
177 :
178 : iterator erase( iterator pos );
179 :
180 : iterator erase( const_iterator pos );
181 :
182 : iterator erase( const_iterator first, const_iterator last );
183 :
184 : size_type erase( const Key& key );
185 :
186 : void swap( unordered_map& other );
187 :
188 : node_type extract( const_iterator position );
189 :
190 : node_type extract( const Key& k );
191 :
192 : template<class H2, class P2>
193 : void merge( std::unordered_map<Key, T, H2, P2, allocator_type>& source );
194 :
195 : template<class H2, class P2>
196 : void merge( std::unordered_map<Key, T, H2, P2, allocator_type>&& source );
197 :
198 : template<class H2, class P2>
199 : void merge( std::unordered_multimap<Key, T, H2, P2, allocator_type>& source );
200 :
201 : template<class H2, class P2>
202 : void merge( std::unordered_multimap<Key, T, H2, P2, allocator_type>&& source );
203 :
204 42853 : std::size_t size() const
205 : {
206 42853 : return super::size();
207 : }
208 :
209 : /// \returns An iterator over all keys.
210 : inline
211 : iterator begin();
212 :
213 : inline
214 : iterator end();
215 :
216 : /// \returns A const iterator over all keys.
217 : const_iterator begin() const;
218 : const_iterator end() const;
219 :
220 : /// \returns A const iterator over all keys.
221 : const_iterator cbegin() const;
222 : const_iterator cend() const;
223 :
224 : /// \returns True iff the set is empty.
225 : bool empty() const noexcept;
226 :
227 : /// \returns The amount of elements stored in this set.
228 : size_type max_size() const noexcept;
229 : };
230 :
231 : namespace utilities
232 : {
233 : /// \brief A unordered_map class in which aterms can be stored.
234 : template < class Key,
235 : class T,
236 : class Hash = std::hash<detail::reference_aterm<Key> >,
237 : class Pred = std::equal_to<detail::reference_aterm<Key> >,
238 : class Alloc = std::allocator< std::pair<const detail::reference_aterm<Key>, detail::reference_aterm<T> > >,
239 : bool ThreadSafe = false >
240 :
241 : class unordered_map : public mcrl2::utilities::unordered_map< detail::reference_aterm<Key>,
242 : detail::reference_aterm<T>, Hash, Pred, Alloc, ThreadSafe, false >
243 : {
244 : protected:
245 : typedef mcrl2::utilities::unordered_map< detail::reference_aterm<Key>, detail::reference_aterm<T>, Hash, Pred, Alloc, ThreadSafe, false > super;
246 :
247 : detail::generic_aterm_container<mcrl2::utilities::unordered_map< detail::reference_aterm<Key>, detail::reference_aterm<T>, Hash, Pred, Alloc, ThreadSafe, false > > container_wrapper;
248 :
249 : public:
250 :
251 : /// Standard typedefs.
252 : typedef typename super::allocator_type allocator_type;
253 : typedef typename super::value_type value_type;
254 : typedef typename super::size_type size_type;
255 : typedef typename super::reference reference;
256 : typedef typename super::iterator iterator;
257 : typedef typename super::const_iterator const_iterator;
258 :
259 : /// \brief Default constructor.
260 21733 : unordered_map()
261 : : super(),
262 21733 : container_wrapper(*this)
263 21733 : {}
264 :
265 : /// \brief Constructor.
266 : explicit unordered_map(const allocator_type& alloc)
267 : : super::unordered_map(alloc),
268 : container_wrapper(*this)
269 : {}
270 :
271 : /// \brief Constructor.
272 : explicit unordered_map(size_type n, const allocator_type& alloc = allocator_type())
273 : : super::unordered_map(n, alloc),
274 : container_wrapper(*this)
275 : {}
276 :
277 : unordered_map(size_type n, const value_type& val, const allocator_type& alloc = allocator_type())
278 : : super::unordered_map(n, detail::reference_aterm(val), alloc),
279 : container_wrapper(*this)
280 : {}
281 :
282 : /// \brief Constructor.
283 : template <class InputIterator>
284 : unordered_map(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
285 : : super::unordered_map(first, last, alloc),
286 : container_wrapper(*this)
287 : {}
288 :
289 : /// \brief Constructor.
290 915 : unordered_map(const unordered_map& x)
291 : : super::unordered_map(x),
292 915 : container_wrapper(*this)
293 915 : {}
294 :
295 : /// \brief Constructor.
296 : unordered_map(const unordered_map& x, const allocator_type& alloc)
297 : : super::unordered_map(x, alloc),
298 : container_wrapper(*this)
299 : {}
300 :
301 : /// \brief Constructor.
302 : unordered_map(unordered_map&& x)
303 : : super::unordered_map(std::move(x)),
304 : container_wrapper(*this)
305 : {}
306 :
307 : /// \brief Constructor.
308 : unordered_map(unordered_map&& x, const allocator_type& alloc)
309 : : super::unordered_map(std::move(x), alloc),
310 : container_wrapper(*this)
311 : {}
312 :
313 : /// \brief Constructor. To be done later....
314 : unordered_map(std::initializer_list<value_type> il, const allocator_type& alloc = allocator_type())
315 : : super::unordered_map(il, alloc),
316 : container_wrapper(*this)
317 : {}
318 :
319 : /// \brief Standard assignment.
320 0 : unordered_map& operator=(const unordered_map& other) = default;
321 :
322 : /// \brief Standard move assignment.
323 : unordered_map& operator=(unordered_map&& other) = default;
324 :
325 : /// \brief Standard destructor.
326 22648 : ~unordered_map() = default;
327 :
328 : void clear() noexcept;
329 :
330 : /// \brief Standard find function in a map.
331 : /// \returns Element with the specified key.
332 : template<typename ...Args>
333 : iterator find(const Args&... args);
334 :
335 : /// \brief Standard find function in a map.
336 : /// \returns Element with the specified key.
337 : template<typename ...Args>
338 : const_iterator find(const Args&... args) const;
339 :
340 : std::pair<iterator, bool> insert(const value_type& value);
341 :
342 : template< class P >
343 : std::pair<iterator, bool> insert(P&& value);
344 :
345 : iterator insert(const_iterator hint, value_type&& value);
346 :
347 : template< class P >
348 : iterator insert(const_iterator hint, P&& value);
349 :
350 : template< class InputIt >
351 : void insert(InputIt first, InputIt last);
352 :
353 : void insert(std::initializer_list<value_type> ilist);
354 :
355 : /*
356 : insert_return_type insert(node_type&& nh);
357 :
358 : iterator insert(const_iterator hint, node_type&& nh);
359 : */
360 :
361 : template <class M>
362 : std::pair<iterator, bool> insert_or_assign(const Key& k, M&& obj);
363 :
364 : template <class M>
365 : std::pair<iterator, bool> insert_or_assign(Key&& k, M&& obj);
366 :
367 : template <class M>
368 : iterator insert_or_assign(const_iterator hint, const Key& k, M&& obj);
369 :
370 : template <class M>
371 : iterator insert_or_assign(const_iterator hint, Key&& k, M&& obj);
372 :
373 : template< class... Args >
374 : std::pair<iterator, bool> emplace(Args&&... args);
375 :
376 : template <class... Args>
377 : iterator emplace_hint(const_iterator hint, Args&&... args);
378 :
379 : template< class... Args >
380 : std::pair<iterator, bool> try_emplace(const Key& k, Args&&... args);
381 :
382 : template< class... Args >
383 : std::pair<iterator, bool> try_emplace(Key&& k, Args&&... args);
384 :
385 : template< class... Args >
386 : iterator try_emplace(const_iterator hint, const Key& k, Args&&... args);
387 :
388 : template< class... Args >
389 : iterator try_emplace(const_iterator hint, Key&& k, Args&&... args);
390 :
391 : iterator erase(iterator pos);
392 :
393 : iterator erase(const_iterator pos);
394 :
395 : iterator erase(const_iterator first, const_iterator last);
396 :
397 : size_type erase(const Key& key);
398 :
399 : void swap(unordered_map& other);
400 :
401 : /*
402 : node_type extract(const_iterator position);
403 :
404 : node_type extract(const Key& k);
405 :
406 : template<class H2, class P2>
407 : void merge(std::unordered_map<Key, T, H2, P2, allocator_type>& source);
408 :
409 : template<class H2, class P2>
410 : void merge(std::unordered_map<Key, T, H2, P2, allocator_type>&& source);
411 :
412 : template<class H2, class P2>
413 : void merge(std::unordered_multimap<Key, T, H2, P2, allocator_type>& source);
414 :
415 : template<class H2, class P2>
416 : void merge(std::unordered_multimap<Key, T, H2, P2, allocator_type>&& source);
417 : */
418 :
419 : std::size_t size() const
420 : {
421 : return super::size();
422 : }
423 :
424 : /// \returns An iterator over all keys.
425 : iterator begin();
426 : iterator end();
427 :
428 : /// \returns A const iterator over all keys.
429 : const_iterator begin() const;
430 : const_iterator end() const;
431 :
432 : /// \returns A const iterator over all keys.
433 : const_iterator cbegin() const;
434 : const_iterator cend() const;
435 :
436 : /// \returns True iff the set is empty.
437 : bool empty() const noexcept;
438 :
439 : /// \returns The amount of elements stored in this set.
440 : size_type max_size() const noexcept;
441 :
442 : protected:
443 :
444 : /// Function below is implemented in a .cpp file.
445 : void rehash(std::size_t /* new_size */);
446 :
447 : void rehash_if_needed();
448 : };
449 : }
450 :
451 : } // namespace atermpp
452 : #endif // MCRL2_ATERMPP_STANDARD_CONTAINER_UNORDERED_MAP_H
453 :
454 :
|
