Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
concurrent_unordered_set.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 */
16 
17 /* Container implementations in this header are based on PPL implementations
18  provided by Microsoft. */
19 
20 #ifndef __TBB_concurrent_unordered_set_H
21 #define __TBB_concurrent_unordered_set_H
22 
24 
25 namespace tbb
26 {
27 
28 namespace interface5 {
29 
30 // Template class for hash set traits
31 template<typename Key, typename Hash_compare, typename Allocator, bool Allow_multimapping>
33 {
34 protected:
35  typedef Key value_type;
36  typedef Key key_type;
37  typedef Hash_compare hash_compare;
39 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
42  allocator_type> node_type;
43 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
44 
45  enum { allow_multimapping = Allow_multimapping };
46 
48  concurrent_unordered_set_traits(const hash_compare& hc) : my_hash_compare(hc) {}
49 
50  static const Key& get_key(const value_type& value) {
51  return value;
52  }
53 
54  hash_compare my_hash_compare; // the comparator predicate for keys
55 };
56 
57 template<typename Key, typename Hasher, typename Key_equality, typename Allocator>
59 
60 template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<Key> >
61 class concurrent_unordered_set : public internal::concurrent_unordered_base< concurrent_unordered_set_traits<Key, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
62 {
63  // Base type definitions
64  typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
66  typedef internal::concurrent_unordered_base< traits_type > base_type;
67 #if __TBB_EXTRA_DEBUG
68 public:
69 #endif
70  using traits_type::allow_multimapping;
71 public:
72  using base_type::insert;
73 
74  // Type definitions
75  typedef Key key_type;
76  typedef typename base_type::value_type value_type;
77  typedef Key mapped_type;
78  typedef Hasher hasher;
79  typedef Key_equality key_equal;
80  typedef hash_compare key_compare;
81 
82  typedef typename base_type::allocator_type allocator_type;
83  typedef typename base_type::pointer pointer;
84  typedef typename base_type::const_pointer const_pointer;
85  typedef typename base_type::reference reference;
86  typedef typename base_type::const_reference const_reference;
87 
88  typedef typename base_type::size_type size_type;
89  typedef typename base_type::difference_type difference_type;
90 
91  typedef typename base_type::iterator iterator;
92  typedef typename base_type::const_iterator const_iterator;
93  typedef typename base_type::iterator local_iterator;
94  typedef typename base_type::const_iterator const_local_iterator;
95 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
96  typedef typename base_type::node_type node_type;
97 #endif /*__TBB_UNORDERED_NODE_HANDLE_PRESENT*/
98 
99  // Construction/destruction/copying
100  explicit concurrent_unordered_set(size_type n_of_buckets = base_type::initial_bucket_number, const hasher& a_hasher = hasher(),
101  const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
102  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
103  {}
104 
105  concurrent_unordered_set(size_type n_of_buckets, const allocator_type& a)
106  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
107  {}
108 
109  concurrent_unordered_set(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
110  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
111  {}
112 
113  explicit concurrent_unordered_set(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
114  {}
115 
116  template <typename Iterator>
117  concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
118  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
119  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
120  {
121  insert(first, last);
122  }
123 
124  template <typename Iterator>
125  concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
126  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
127  {
128  insert(first, last);
129  }
130 
131  template <typename Iterator>
132  concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
133  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
134  {
135  insert(first, last);
136  }
137 
138 #if __TBB_INITIALIZER_LISTS_PRESENT
139  concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number, const hasher& a_hasher = hasher(),
141  const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
142  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
143  {
144  insert(il.begin(),il.end());
145  }
146 
147  concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
148  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
149  {
150  insert(il.begin(), il.end());
151  }
152 
153  concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
154  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
155  {
156  insert(il.begin(), il.end());
157  }
158 
159 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
160 
161 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
163  : base_type(table)
164  {}
165 
166  concurrent_unordered_set& operator=(const concurrent_unordered_set& table)
167  {
168  return static_cast<concurrent_unordered_set&>(base_type::operator=(table));
169  }
170 
171  concurrent_unordered_set(concurrent_unordered_set&& table)
172  : base_type(std::move(table))
173  {}
174 
175  concurrent_unordered_set& operator=(concurrent_unordered_set&& table)
176  {
177  return static_cast<concurrent_unordered_set&>(base_type::operator=(std::move(table)));
178  }
179 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
180 
181 #if __TBB_CPP11_RVALUE_REF_PRESENT
182  concurrent_unordered_set(concurrent_unordered_set&& table, const Allocator& a)
183  : base_type(std::move(table), a)
184  {}
185 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
186 
187 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
188  template<typename Hash, typename Equality>
190  { this->internal_merge(source); }
191 
192  template<typename Hash, typename Equality>
194  { this->internal_merge(source); }
195 
196  template<typename Hash, typename Equality>
198  { this->internal_merge(source); }
199 
200  template<typename Hash, typename Equality>
202  { this->internal_merge(source); }
203 
204 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
205 
206  concurrent_unordered_set(const concurrent_unordered_set& table, const Allocator& a)
207  : base_type(table, a)
208  {}
209 
210 };
211 
212 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
213 
214 namespace internal {
215 using namespace tbb::internal;
216 
217 template <template<typename...> typename Set, typename T, typename... Args>
218 using cu_set_t = Set <
219  T,
220  std::conditional_t< (sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
221  pack_element_t<0, Args...>, tbb_hash<T> >,
222  std::conditional_t< (sizeof...(Args)>1) && !is_allocator_v< pack_element_t<1, Args...> >,
223  pack_element_t<1, Args...>, std::equal_to<T> >,
224  std::conditional_t< (sizeof...(Args)>0) && is_allocator_v< pack_element_t<sizeof...(Args)-1, Args...> >,
225  pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<T> >
226 >;
227 }
228 
229 // Deduction guide for the constructor from two iterators
230 template<typename I>
232 -> internal::cu_set_t<concurrent_unordered_set, internal::iterator_value_t<I>>;
233 
234 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
235 template<typename I, typename... Args>
236 concurrent_unordered_set(I, I, size_t, Args...)
237 -> internal::cu_set_t<concurrent_unordered_set, internal::iterator_value_t<I>, Args...>;
238 
239 // Deduction guide for the constructor from an initializer_list
240 template<typename T>
241 concurrent_unordered_set(std::initializer_list<T>)
242 -> internal::cu_set_t<concurrent_unordered_set, T>;
243 
244 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
245 template<typename T, typename... Args>
246 concurrent_unordered_set(std::initializer_list<T>, size_t, Args...)
247 -> internal::cu_set_t<concurrent_unordered_set, T, Args...>;
248 
249 #endif /*__TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
250 
251 template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
252  typename Allocator = tbb::tbb_allocator<Key> >
254  public internal::concurrent_unordered_base< concurrent_unordered_set_traits<Key,
255  internal::hash_compare<Key, Hasher, Key_equality>, Allocator, true> >
256 {
257  // Base type definitions
258  typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
260  typedef internal::concurrent_unordered_base< traits_type > base_type;
261 #if __TBB_EXTRA_DEBUG
262 public:
263 #endif
264  using traits_type::allow_multimapping;
265 public:
266  using base_type::insert;
267 
268  // Type definitions
269  typedef Key key_type;
270  typedef typename base_type::value_type value_type;
271  typedef Key mapped_type;
272  typedef Hasher hasher;
273  typedef Key_equality key_equal;
274  typedef hash_compare key_compare;
275 
276  typedef typename base_type::allocator_type allocator_type;
277  typedef typename base_type::pointer pointer;
278  typedef typename base_type::const_pointer const_pointer;
279  typedef typename base_type::reference reference;
280  typedef typename base_type::const_reference const_reference;
281 
282  typedef typename base_type::size_type size_type;
283  typedef typename base_type::difference_type difference_type;
284 
285  typedef typename base_type::iterator iterator;
286  typedef typename base_type::const_iterator const_iterator;
287  typedef typename base_type::iterator local_iterator;
288  typedef typename base_type::const_iterator const_local_iterator;
289 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
290  typedef typename base_type::node_type node_type;
291 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
292 
293  // Construction/destruction/copying
294  explicit concurrent_unordered_multiset(size_type n_of_buckets = base_type::initial_bucket_number,
295  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
296  const allocator_type& a = allocator_type())
297  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
298  {}
299 
300  concurrent_unordered_multiset(size_type n_of_buckets, const allocator_type& a)
301  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
302  {}
303 
304  concurrent_unordered_multiset(size_type n_of_buckets, const hasher& a_hasher,
305  const allocator_type& a)
306  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
307  {}
308 
309  explicit concurrent_unordered_multiset(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
310  {}
311 
312  template <typename Iterator>
313  concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
314  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
315  const allocator_type& a = allocator_type())
316  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
317  {
318  insert(first, last);
319  }
320 
321  template <typename Iterator>
322  concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
323  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
324  {
325  insert(first, last);
326  }
327 
328  template <typename Iterator>
329  concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
330  const allocator_type& a)
331  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
332  {
333  insert(first, last);
334  }
335 
336 #if __TBB_INITIALIZER_LISTS_PRESENT
337  concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
339  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
340  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
341  {
342  insert(il.begin(),il.end());
343  }
344 
345  concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
346  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
347  {
348  insert(il.begin(), il.end());
349  }
350 
351  concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
352  const allocator_type& a)
353  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
354  {
355  insert(il.begin(), il.end());
356  }
357 
358 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
359 
360 
361 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
363  : base_type(table)
364  {}
365 
366  concurrent_unordered_multiset& operator=(const concurrent_unordered_multiset& table)
367  {
368  return static_cast<concurrent_unordered_multiset&>(base_type::operator=(table));
369  }
370 
371  concurrent_unordered_multiset(concurrent_unordered_multiset&& table)
372  : base_type(std::move(table))
373  {}
374 
375  concurrent_unordered_multiset& operator=(concurrent_unordered_multiset&& table)
376  {
377  return static_cast<concurrent_unordered_multiset&>(base_type::operator=(std::move(table)));
378  }
379 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
380 
381 #if __TBB_CPP11_RVALUE_REF_PRESENT
382  concurrent_unordered_multiset(concurrent_unordered_multiset&& table, const Allocator& a)
383  : base_type(std::move(table), a)
384  {
385  }
386 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
387 
388 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
389  template<typename Hash, typename Equality>
391  { this->internal_merge(source); }
392 
393  template<typename Hash, typename Equality>
395  { this->internal_merge(source); }
396 
397  template<typename Hash, typename Equality>
399  { this->internal_merge(source); }
400 
401  template<typename Hash, typename Equality>
403  { this->internal_merge(source); }
404 
405 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
406 
407  concurrent_unordered_multiset(const concurrent_unordered_multiset& table, const Allocator& a)
408  : base_type(table, a)
409  {}
410 };
411 
412 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
413 
414 // Deduction guide for the constructor from two iterators
415 template<typename I>
417 -> internal::cu_set_t<concurrent_unordered_multiset, internal::iterator_value_t<I>>;
418 
419 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
420 template<typename I, typename... Args>
421 concurrent_unordered_multiset(I, I, size_t, Args...)
422 -> internal::cu_set_t<concurrent_unordered_multiset, internal::iterator_value_t<I>, Args...>;
423 
424 // Deduction guide for the constructor from an initializer_list
425 template<typename T>
426 concurrent_unordered_multiset(std::initializer_list<T>)
427 -> internal::cu_set_t<concurrent_unordered_multiset, T>;
428 
429 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
430 template<typename T, typename... Args>
431 concurrent_unordered_multiset(std::initializer_list<T>, size_t, Args...)
432 -> internal::cu_set_t<concurrent_unordered_multiset, T, Args...>;
433 
434 #endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
435 } // namespace interface5
436 
439 
440 } // namespace tbb
441 
442 #endif// __TBB_concurrent_unordered_set_H
concurrent_unordered_set_traits< Key, hash_compare, Allocator, false > traits_type
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &source)
concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type &a)
concurrent_unordered_set(const concurrent_unordered_set &table, const Allocator &a)
concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type &a)
internal::hash_compare< Key, Hasher, Key_equality > hash_compare
tbb::internal::allocator_rebind< Allocator, value_type >::type allocator_type
auto last(Container &c) -> decltype(begin(c))
concurrent_unordered_multiset(size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
concurrent_unordered_multiset(std::initializer_list< value_type > il, size_type n_of_buckets, const allocator_type &a)
concurrent_unordered_set(std::initializer_list< value_type > il, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
concurrent_unordered_set(size_type n_of_buckets=base_type::initial_bucket_number, const hasher &a_hasher=hasher(), const key_equal &a_keyeq=key_equal(), const allocator_type &a=allocator_type())
concurrent_unordered_multiset(size_type n_of_buckets, const allocator_type &a)
static const Key & get_key(const value_type &value)
allocator_traits< Alloc >::template rebind_alloc< T >::other type
internal::concurrent_unordered_base< traits_type > base_type
auto first(Container &c) -> decltype(begin(c))
The graph class.
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &source)
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &&source)
concurrent_unordered_set(size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &source)
concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets=base_type::initial_bucket_number, const hasher &a_hasher=hasher(), const key_equal &a_keyeq=key_equal(), const allocator_type &a=allocator_type())
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
concurrent_unordered_multiset(size_type n_of_buckets=base_type::initial_bucket_number, const hasher &a_hasher=hasher(), const key_equal &a_keyeq=key_equal(), const allocator_type &a=allocator_type())
tbb::internal::node_handle< key_type, key_type, typename internal::split_ordered_list< key_type, allocator_type >::node, allocator_type > node_type
concurrent_unordered_set(size_type n_of_buckets, const allocator_type &a)
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &source)
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
concurrent_unordered_set(std::initializer_list< value_type > il, size_type n_of_buckets, const allocator_type &a)
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &&source)
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
Definition: tbb_allocator.h:58
internal::concurrent_unordered_base< traits_type > base_type
STL namespace.
concurrent_unordered_multiset(std::initializer_list< value_type > il, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
Identifiers declared inside namespace internal should never be used directly by client code...
Definition: atomic.h:51
concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets=base_type::initial_bucket_number, const hasher &a_hasher=hasher(), const key_equal &a_keyeq=key_equal(), const allocator_type &a=allocator_type())
concurrent_unordered_set(concurrent_unordered_set &&table, const Allocator &a)
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &&source)
concurrent_unordered_set_traits< Key, hash_compare, Allocator, true > traits_type
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &&source)
concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
concurrent_unordered_multiset(concurrent_unordered_multiset &&table, const Allocator &a)
internal::hash_compare< Key, Hasher, Key_equality > hash_compare
concurrent_unordered_multiset(const concurrent_unordered_multiset &table, const Allocator &a)

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.