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

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.