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
40  typedef internal::node_handle<Key, Key, allocator_type> node_type;
41 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
42 
43  enum { allow_multimapping = Allow_multimapping };
44 
47 
48  static const Key& get_key(const value_type& value) {
49  return value;
50  }
51 
52  hash_compare my_hash_compare; // the comparator predicate for keys
53 };
54 
55 template<typename Key, typename Hasher, typename Key_equality, typename Allocator>
57 
58 template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<Key> >
59 class concurrent_unordered_set : public internal::concurrent_unordered_base< concurrent_unordered_set_traits<Key, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
60 {
61  // Base type definitions
62  typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
64  typedef internal::concurrent_unordered_base< traits_type > base_type;
65 #if __TBB_EXTRA_DEBUG
66 public:
67 #endif
69 public:
70  using base_type::insert;
71 
72  // Type definitions
73  typedef Key key_type;
74  typedef typename base_type::value_type value_type;
75  typedef Key mapped_type;
76  typedef Hasher hasher;
77  typedef Key_equality key_equal;
79 
80  typedef typename base_type::allocator_type allocator_type;
81  typedef typename base_type::pointer pointer;
82  typedef typename base_type::const_pointer const_pointer;
83  typedef typename base_type::reference reference;
84  typedef typename base_type::const_reference const_reference;
85 
86  typedef typename base_type::size_type size_type;
87  typedef typename base_type::difference_type difference_type;
88 
89  typedef typename base_type::iterator iterator;
90  typedef typename base_type::const_iterator const_iterator;
91  typedef typename base_type::iterator local_iterator;
92  typedef typename base_type::const_iterator const_local_iterator;
93 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
94  typedef typename base_type::node_type node_type;
95 #endif /*__TBB_UNORDERED_NODE_HANDLE_PRESENT*/
96 
97  // Construction/destruction/copying
98  explicit concurrent_unordered_set(size_type n_of_buckets = base_type::initial_bucket_number, const hasher& a_hasher = hasher(),
99  const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
100  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
101  {}
102 
104  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
105  {}
106 
107  concurrent_unordered_set(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
108  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
109  {}
110 
112  {}
113 
114  template <typename Iterator>
115  concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
116  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
117  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
118  {
119  insert(first, last);
120  }
121 
122  template <typename Iterator>
123  concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
124  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
125  {
126  insert(first, last);
127  }
128 
129  template <typename Iterator>
130  concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
131  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
132  {
133  insert(first, last);
134  }
135 
136 #if __TBB_INITIALIZER_LISTS_PRESENT
137  concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number, const hasher& a_hasher = hasher(),
139  const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
140  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
141  {
142  insert(il.begin(),il.end());
143  }
144 
145  concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
146  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
147  {
148  insert(il.begin(), il.end());
149  }
150 
151  concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
152  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
153  {
154  insert(il.begin(), il.end());
155  }
156 
157 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
158 
159 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
161  : base_type(table)
162  {}
163 
165  {
166  return static_cast<concurrent_unordered_set&>(base_type::operator=(table));
167  }
168 
170  : base_type(std::move(table))
171  {}
172 
174  {
175  return static_cast<concurrent_unordered_set&>(base_type::operator=(std::move(table)));
176  }
177 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
178 
179 #if __TBB_CPP11_RVALUE_REF_PRESENT
181  : base_type(std::move(table), a)
182  {}
183 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
184 
185 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
186  template<typename Hash, typename Equality>
188  { this->internal_merge(source); }
189 
190  template<typename Hash, typename Equality>
192  { this->internal_merge(source); }
193 
194  template<typename Hash, typename Equality>
196  { this->internal_merge(source); }
197 
198  template<typename Hash, typename Equality>
200  { this->internal_merge(source); }
201 
202 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
203 
204  concurrent_unordered_set(const concurrent_unordered_set& table, const Allocator& a)
205  : base_type(table, a)
206  {}
207 
208 };
209 
210 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
211 
212 namespace internal {
213 using namespace tbb::internal;
214 
215 template <template<typename...> typename Set, typename T, typename... Args>
216 using cu_set_t = Set <
217  T,
218  std::conditional_t< (sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
219  pack_element_t<0, Args...>, tbb_hash<T> >,
220  std::conditional_t< (sizeof...(Args)>1) && !is_allocator_v< pack_element_t<1, Args...> >,
221  pack_element_t<1, Args...>, std::equal_to<T> >,
222  std::conditional_t< (sizeof...(Args)>0) && is_allocator_v< pack_element_t<sizeof...(Args)-1, Args...> >,
223  pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<T> >
224 >;
225 }
226 
227 // Deduction guide for the constructor from two iterators
228 template<typename I>
229 concurrent_unordered_set(I, I)
230 -> internal::cu_set_t<concurrent_unordered_set, internal::iterator_value_t<I>>;
231 
232 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
233 template<typename I, typename... Args>
234 concurrent_unordered_set(I, I, size_t, Args...)
235 -> internal::cu_set_t<concurrent_unordered_set, internal::iterator_value_t<I>, Args...>;
236 
237 // Deduction guide for the constructor from an initializer_list
238 template<typename T>
239 concurrent_unordered_set(std::initializer_list<T>)
240 -> internal::cu_set_t<concurrent_unordered_set, T>;
241 
242 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
243 template<typename T, typename... Args>
244 concurrent_unordered_set(std::initializer_list<T>, size_t, Args...)
245 -> internal::cu_set_t<concurrent_unordered_set, T, Args...>;
246 
247 #endif /*__TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
248 
249 template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
250  typename Allocator = tbb::tbb_allocator<Key> >
251 class concurrent_unordered_multiset :
252  public internal::concurrent_unordered_base< concurrent_unordered_set_traits<Key,
253  internal::hash_compare<Key, Hasher, Key_equality>, Allocator, true> >
254 {
255  // Base type definitions
256  typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
258  typedef internal::concurrent_unordered_base< traits_type > base_type;
259 #if __TBB_EXTRA_DEBUG
260 public:
261 #endif
262  using traits_type::allow_multimapping;
263 public:
264  using base_type::insert;
265 
266  // Type definitions
267  typedef Key key_type;
268  typedef typename base_type::value_type value_type;
269  typedef Key mapped_type;
270  typedef Hasher hasher;
271  typedef Key_equality key_equal;
273 
274  typedef typename base_type::allocator_type allocator_type;
275  typedef typename base_type::pointer pointer;
276  typedef typename base_type::const_pointer const_pointer;
277  typedef typename base_type::reference reference;
278  typedef typename base_type::const_reference const_reference;
279 
280  typedef typename base_type::size_type size_type;
281  typedef typename base_type::difference_type difference_type;
282 
283  typedef typename base_type::iterator iterator;
284  typedef typename base_type::const_iterator const_iterator;
285  typedef typename base_type::iterator local_iterator;
286  typedef typename base_type::const_iterator const_local_iterator;
287 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
288  typedef typename base_type::node_type node_type;
289 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
290 
291  // Construction/destruction/copying
292  explicit concurrent_unordered_multiset(size_type n_of_buckets = base_type::initial_bucket_number,
293  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
294  const allocator_type& a = allocator_type())
295  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
296  {}
297 
299  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
300  {}
301 
302  concurrent_unordered_multiset(size_type n_of_buckets, const hasher& a_hasher,
303  const allocator_type& a)
304  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
305  {}
306 
307  explicit concurrent_unordered_multiset(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
308  {}
309 
310  template <typename Iterator>
311  concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
312  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
313  const allocator_type& a = allocator_type())
314  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
315  {
316  insert(first, last);
317  }
318 
319  template <typename Iterator>
320  concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
321  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
322  {
323  insert(first, last);
324  }
325 
326  template <typename Iterator>
327  concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
328  const allocator_type& a)
329  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
330  {
331  insert(first, last);
332  }
333 
334 #if __TBB_INITIALIZER_LISTS_PRESENT
335  concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
337  const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
338  : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
339  {
340  insert(il.begin(),il.end());
341  }
342 
343  concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
344  : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
345  {
346  insert(il.begin(), il.end());
347  }
348 
349  concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
350  const allocator_type& a)
351  : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
352  {
353  insert(il.begin(), il.end());
354  }
355 
356 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
357 
358 
359 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
361  : base_type(table)
362  {}
363 
365  {
366  return static_cast<concurrent_unordered_multiset&>(base_type::operator=(table));
367  }
368 
369  concurrent_unordered_multiset(concurrent_unordered_multiset&& table)
370  : base_type(std::move(table))
371  {}
372 
373  concurrent_unordered_multiset& operator=(concurrent_unordered_multiset&& table)
374  {
375  return static_cast<concurrent_unordered_multiset&>(base_type::operator=(std::move(table)));
376  }
377 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
378 
379 #if __TBB_CPP11_RVALUE_REF_PRESENT
381  : base_type(std::move(table), a)
382  {
383  }
384 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
385 
386 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
387  template<typename Hash, typename Equality>
389  { this->internal_merge(source); }
390 
391  template<typename Hash, typename Equality>
393  { this->internal_merge(source); }
394 
395  template<typename Hash, typename Equality>
397  { this->internal_merge(source); }
398 
399  template<typename Hash, typename Equality>
401  { this->internal_merge(source); }
402 
403 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
404 
406  : base_type(table, a)
407  {}
408 };
409 
410 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
411 
412 // Deduction guide for the constructor from two iterators
413 template<typename I>
415 -> internal::cu_set_t<concurrent_unordered_multiset, internal::iterator_value_t<I>>;
416 
417 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
418 template<typename I, typename... Args>
419 concurrent_unordered_multiset(I, I, size_t, Args...)
420 -> internal::cu_set_t<concurrent_unordered_multiset, internal::iterator_value_t<I>, Args...>;
421 
422 // Deduction guide for the constructor from an initializer_list
423 template<typename T>
424 concurrent_unordered_multiset(std::initializer_list<T>)
425 -> internal::cu_set_t<concurrent_unordered_multiset, T>;
426 
427 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
428 template<typename T, typename... Args>
429 concurrent_unordered_multiset(std::initializer_list<T>, size_t, Args...)
430 -> internal::cu_set_t<concurrent_unordered_multiset, T, Args...>;
431 
432 #endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
433 } // namespace interface5
434 
435 using interface5::concurrent_unordered_set;
436 using interface5::concurrent_unordered_multiset;
437 
438 } // namespace tbb
439 
440 #endif// __TBB_concurrent_unordered_set_H
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_set_traits< Key, hash_compare, Allocator, false > traits_type
concurrent_unordered_multiset(std::initializer_list< value_type > il, size_type n_of_buckets, const allocator_type &a)
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &source)
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
internal::node_handle< Key, Key, allocator_type > node_type
concurrent_unordered_set_traits< Key, hash_compare, Allocator, true > traits_type
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())
internal::concurrent_unordered_base< traits_type > base_type
static const Key & get_key(const value_type &value)
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
Definition: tbb_allocator.h:58
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)
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &source)
tbb::internal::allocator_rebind< Allocator, value_type >::type allocator_type
concurrent_unordered_set(std::initializer_list< value_type > il, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
The graph class.
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &source)
Class for determining type of std::allocator<T>::value_type.
Definition: tbb_stddef.h:450
concurrent_unordered_multiset(size_type n_of_buckets, const allocator_type &a)
concurrent_unordered_multiset(const concurrent_unordered_multiset &table, const Allocator &a)
concurrent_unordered_multiset(std::initializer_list< value_type > il, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &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
concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const hasher &a_hasher, const allocator_type &a)
auto first(Container &c) -> decltype(begin(c))
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())
void merge(concurrent_unordered_set< Key, Hash, Equality, Allocator > &&source)
concurrent_unordered_set(std::initializer_list< value_type > il, size_type n_of_buckets, const allocator_type &a)
allocator_traits< Alloc >::template rebind_alloc< T >::other type
concurrent_unordered_multiset(concurrent_unordered_multiset &&table, const Allocator &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())
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)
auto last(Container &c) -> decltype(begin(c))
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &&source)
void merge(concurrent_unordered_multiset< Key, Hash, Equality, Allocator > &&source)
concurrent_unordered_set(size_type n_of_buckets, const allocator_type &a)
internal::hash_compare< Key, Hasher, Key_equality > hash_compare
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(concurrent_unordered_set &&table, const Allocator &a)
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())
concurrent_unordered_multiset(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
internal::concurrent_unordered_base< traits_type > base_type

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.