15#ifndef PXR_BASE_TF_HASHSET_H
16#define PXR_BASE_TF_HASHSET_H
19#include "pxr/base/arch/defines.h"
21#if defined(ARCH_HAS_GNU_STL_EXTENSIONS)
22#include <ext/hash_set>
24#include <unordered_set>
27PXR_NAMESPACE_OPEN_SCOPE
29#if defined(ARCH_HAS_GNU_STL_EXTENSIONS)
31template<
class Key,
class HashFn = __gnu_cxx::hash<Key>,
32 class EqualKey = __gnu_cxx::equal_to<Key>,
33 class Alloc = __gnu_cxx::allocator<Key> >
35 private __gnu_cxx::hash_set<Key, HashFn, EqualKey, Alloc> {
36 typedef __gnu_cxx::hash_set<Key, HashFn, EqualKey, Alloc> _Base;
38 typedef typename _Base::key_type key_type;
39 typedef typename _Base::value_type value_type;
40 typedef typename _Base::hasher hasher;
41 typedef typename _Base::key_equal key_equal;
42 typedef typename _Base::size_type size_type;
43 typedef typename _Base::difference_type difference_type;
44 typedef typename _Base::pointer pointer;
45 typedef typename _Base::const_pointer const_pointer;
46 typedef typename _Base::reference reference;
47 typedef typename _Base::const_reference const_reference;
48 typedef typename _Base::iterator iterator;
49 typedef typename _Base::const_iterator const_iterator;
50 typedef typename _Base::allocator_type allocator_type;
53 TfHashSet() : _Base() { }
55 TfHashSet(size_type n,
const hasher& hf = hasher(),
56 const key_equal& eql = key_equal(),
57 const allocator_type& alloc = allocator_type()) :
58 _Base(n, hf, eql, alloc) { }
60 TfHashSet(
const allocator_type& alloc) :
61 _Base(0, hasher(), key_equal(), alloc) { }
62 template<
class InputIterator>
63 TfHashSet(InputIterator first, InputIterator last,
64 size_type n = 0,
const hasher& hf = hasher(),
65 const key_equal& eql = key_equal(),
66 const allocator_type& alloc = allocator_type()) :
67 _Base(first, last, n, hf, eql, alloc) { }
68 TfHashSet(
const TfHashSet& other) : _Base(other) { }
70 TfHashSet& operator=(
const TfHashSet& rhs) {
71 _Base::operator=(rhs);
75 iterator begin() {
return _Base::begin(); }
76 const_iterator begin()
const {
return const_iterator(_Base::begin()); }
78 using _Base::bucket_count;
79 size_type bucket_size(size_type n)
const {
return _Base::elems_in_bucket(n); }
80 const_iterator cbegin()
const {
return const_iterator(_Base::begin()); }
81 const_iterator cend()
const {
return const_iterator(_Base::end()); }
85 iterator end() {
return _Base::end(); }
86 const_iterator end()
const {
return const_iterator(_Base::end()); }
87 std::pair<iterator,iterator> equal_range(
const key_type& key) {
88 return _Base::equal_range(key);
90 std::pair<const_iterator,const_iterator> equal_range(
const key_type& key)
const {
91 return _Base::equal_range(key);
93 size_type erase(
const key_type& key) {
return _Base::erase(key); }
94 void erase(const_iterator position) {
95 _Base::erase(_MakeIterator(position));
97 void erase(const_iterator first, const_iterator last) {
98 _Base::erase(_MakeIterator(first), _MakeIterator(last));
100 iterator find(
const key_type& key) {
return _Base::find(key); }
101 const_iterator find(
const key_type& key)
const {
102 return const_iterator(_Base::find(key));
104 using _Base::get_allocator;
105 hasher hash_function()
const {
return _Base::hash_funct(); }
107 iterator insert(const_iterator,
const value_type& v) {
108 return insert(v).first;
111 float load_factor()
const {
112 return static_cast<float>(
static_cast<double>(size()) / bucket_count());
114 using _Base::max_bucket_count;
115 float max_load_factor()
const {
return 1.0; }
117 using _Base::max_size;
118 void rehash(size_type n) { _Base::resize(__gnu_cxx::__stl_next_prime(n)); }
119 void reserve(size_type n) { _Base::resize(n); }
121 void swap(TfHashSet& other) { _Base::swap(other); }
123 template<
class Key2,
class HashFn2,
class EqualKey2,
class Alloc2>
125 operator==(
const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&,
126 const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&);
131 static const iterator& _MakeIterator(
const const_iterator& i) {
132 return reinterpret_cast<const iterator&
>(i);
136template<
class Key,
class HashFn = __gnu_cxx::hash<Key>,
137 class EqualKey = __gnu_cxx::equal_to<Key>,
138 class Alloc = __gnu_cxx::allocator<Key> >
139class TfHashMultiSet :
140 private __gnu_cxx::hash_multiset<Key, HashFn, EqualKey, Alloc> {
141 typedef __gnu_cxx::hash_multiset<Key, HashFn, EqualKey, Alloc> _Base;
143 typedef typename _Base::key_type key_type;
144 typedef typename _Base::value_type value_type;
145 typedef typename _Base::hasher hasher;
146 typedef typename _Base::key_equal key_equal;
147 typedef typename _Base::size_type size_type;
148 typedef typename _Base::difference_type difference_type;
149 typedef typename _Base::pointer pointer;
150 typedef typename _Base::const_pointer const_pointer;
151 typedef typename _Base::reference reference;
152 typedef typename _Base::const_reference const_reference;
153 typedef typename _Base::iterator iterator;
154 typedef typename _Base::const_iterator const_iterator;
155 typedef typename _Base::allocator_type allocator_type;
158 TfHashMultiSet() : _Base() { }
160 TfHashMultiSet(size_type n,
const hasher& hf = hasher(),
161 const key_equal& eql = key_equal(),
162 const allocator_type& alloc = allocator_type()) :
163 _Base(n, hf, eql, alloc) { }
165 TfHashMultiSet(
const allocator_type& alloc) :
166 _Base(0, hasher(), key_equal(), alloc) { }
167 template<
class InputIterator>
168 TfHashMultiSet(InputIterator first, InputIterator last,
169 size_type n = 0,
const hasher& hf = hasher(),
170 const key_equal& eql = key_equal(),
171 const allocator_type& alloc = allocator_type()) :
172 _Base(first, last, n, hf, eql, alloc) { }
173 TfHashMultiSet(
const TfHashMultiSet& other) : _Base(other) { }
175 TfHashMultiSet& operator=(
const TfHashMultiSet& rhs) {
176 _Base::operator=(rhs);
180 iterator begin() {
return _Base::begin(); }
181 const_iterator begin()
const {
return const_iterator(_Base::begin()); }
183 using _Base::bucket_count;
184 size_type bucket_size(size_type n)
const {
return _Base::elems_in_bucket(n); }
185 const_iterator cbegin()
const {
return const_iterator(_Base::begin()); }
186 const_iterator cend()
const {
return const_iterator(_Base::end()); }
190 iterator end() {
return _Base::end(); }
191 const_iterator end()
const {
return const_iterator(_Base::end()); }
192 std::pair<iterator,iterator> equal_range(
const key_type& key) {
193 return _Base::equal_range(key);
195 std::pair<const_iterator,const_iterator> equal_range(
const key_type& key)
const {
196 return _Base::equal_range(key);
198 size_type erase(
const key_type& key) {
return _Base::erase(key); }
199 void erase(const_iterator position) {
200 _Base::erase(_MakeIterator(position));
202 void erase(const_iterator first, const_iterator last) {
203 _Base::erase(_MakeIterator(first), _MakeIterator(last));
205 iterator find(
const key_type& key) {
return _Base::find(key); }
206 const_iterator find(
const key_type& key)
const {
207 return const_iterator(_Base::find(key));
209 using _Base::get_allocator;
210 hasher hash_function()
const {
return _Base::hash_funct(); }
212 iterator insert(const_iterator,
const value_type& v) {
213 return insert(v).first;
216 float load_factor()
const {
217 return static_cast<float>(
static_cast<double>(size()) / bucket_count());
219 using _Base::max_bucket_count;
220 float max_load_factor()
const {
return 1.0; }
222 using _Base::max_size;
223 void rehash(size_type n) { _Base::resize(__gnu_cxx::__stl_next_prime(n)); }
224 void reserve(size_type n) { _Base::resize(n); }
226 void swap(TfHashMultiSet& other) { _Base::swap(other); }
228 template<
class Key2,
class HashFn2,
class EqualKey2,
class Alloc2>
230 operator==(
const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&,
231 const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&);
236 static const iterator& _MakeIterator(
const const_iterator& i) {
237 return reinterpret_cast<const iterator&
>(i);
243template<
class Key,
class HashFn = std::hash<Key>,
244 class EqualKey = std::equal_to<Key>,
245 class Alloc = std::allocator<Key> >
247 private std::unordered_set<Key, HashFn, EqualKey, Alloc> {
248 typedef std::unordered_set<Key, HashFn, EqualKey, Alloc> _Base;
250 typedef typename _Base::key_type key_type;
251 typedef typename _Base::value_type value_type;
252 typedef typename _Base::hasher hasher;
253 typedef typename _Base::key_equal key_equal;
254 typedef typename _Base::size_type size_type;
255 typedef typename _Base::difference_type difference_type;
256 typedef typename _Base::pointer pointer;
257 typedef typename _Base::const_pointer const_pointer;
258 typedef typename _Base::reference reference;
259 typedef typename _Base::const_reference const_reference;
260 typedef typename _Base::iterator iterator;
261 typedef typename _Base::const_iterator const_iterator;
262 typedef typename _Base::allocator_type allocator_type;
265 TfHashSet() : _Base() { }
267 TfHashSet(size_type n,
const hasher& hf = hasher(),
268 const key_equal& eql = key_equal(),
269 const allocator_type& alloc = allocator_type()) :
270 _Base(n, hf, eql, alloc) { }
272 TfHashSet(
const allocator_type& alloc) : _Base(alloc) { }
273 template<
class InputIterator>
274 TfHashSet(InputIterator first, InputIterator last,
275 size_type n = 0,
const hasher& hf = hasher(),
276 const key_equal& eql = key_equal(),
277 const allocator_type& alloc = allocator_type()) :
278 _Base(first, last, n, hf, eql, alloc) { }
279 TfHashSet(
const TfHashSet& other) : _Base(other) { }
281 TfHashSet& operator=(
const TfHashSet& rhs) {
282 _Base::operator=(rhs);
286 iterator begin() {
return _Base::begin(); }
287 const_iterator begin()
const {
return _Base::begin(); }
289 using _Base::bucket_count;
290 using _Base::bucket_size;
291 const_iterator cbegin()
const {
return _Base::cbegin(); }
292 const_iterator cend()
const {
return _Base::cend(); }
296 iterator end() {
return _Base::end(); }
297 const_iterator end()
const {
return _Base::end(); }
298 using _Base::equal_range;
299 size_type erase(
const key_type& key) {
return _Base::erase(key); }
300 void erase(const_iterator position) { _Base::erase(position); }
301 void erase(const_iterator first, const_iterator last) {
302 _Base::erase(first, last);
305 using _Base::get_allocator;
306 using _Base::hash_function;
307 std::pair<iterator, bool> insert(
const value_type& v) {
308 return _Base::insert(v);
310 iterator insert(const_iterator hint,
const value_type& v) {
311 return _Base::insert(hint, v);
313 template<
class InputIterator>
314 void insert(InputIterator first, InputIterator last) {
315 _Base::insert(first, last);
318 using _Base::load_factor;
319 using _Base::max_bucket_count;
320 using _Base::max_load_factor;
322 using _Base::max_size;
324 using _Base::reserve;
326 void swap(TfHashSet& other) { _Base::swap(other); }
328 template<
class Key2,
class HashFn2,
class EqualKey2,
class Alloc2>
330 operator==(
const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&,
331 const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&);
334template<
class Key,
class HashFn = std::hash<Key>,
335 class EqualKey = std::equal_to<Key>,
336 class Alloc = std::allocator<Key> >
337class TfHashMultiSet :
338 private std::unordered_multiset<Key, HashFn, EqualKey, Alloc> {
339 typedef std::unordered_multiset<Key, HashFn, EqualKey, Alloc> _Base;
341 typedef typename _Base::key_type key_type;
342 typedef typename _Base::value_type value_type;
343 typedef typename _Base::hasher hasher;
344 typedef typename _Base::key_equal key_equal;
345 typedef typename _Base::size_type size_type;
346 typedef typename _Base::difference_type difference_type;
347 typedef typename _Base::pointer pointer;
348 typedef typename _Base::const_pointer const_pointer;
349 typedef typename _Base::reference reference;
350 typedef typename _Base::const_reference const_reference;
351 typedef typename _Base::iterator iterator;
352 typedef typename _Base::const_iterator const_iterator;
353 typedef typename _Base::allocator_type allocator_type;
356 TfHashMultiSet() : _Base() { }
358 TfHashMultiSet(size_type n,
const hasher& hf = hasher(),
359 const key_equal& eql = key_equal(),
360 const allocator_type& alloc = allocator_type()) :
361 _Base(n, hf, eql, alloc) { }
363 TfHashMultiSet(
const allocator_type& alloc) : _Base(alloc) { }
364 template<
class InputIterator>
365 TfHashMultiSet(InputIterator first, InputIterator last,
366 size_type n = 0,
const hasher& hf = hasher(),
367 const key_equal& eql = key_equal(),
368 const allocator_type& alloc = allocator_type()) :
369 _Base(first, last, n, hf, eql, alloc) { }
370 TfHashMultiSet(
const TfHashMultiSet& other) : _Base(other) { }
372 TfHashMultiSet& operator=(
const TfHashMultiSet& rhs) {
373 _Base::operator=(rhs);
377 iterator begin() {
return _Base::begin(); }
378 const_iterator begin()
const {
return _Base::begin(); }
380 using _Base::bucket_count;
381 using _Base::bucket_size;
382 const_iterator cbegin()
const {
return _Base::cbegin(); }
383 const_iterator cend()
const {
return _Base::cend(); }
387 iterator end() {
return _Base::end(); }
388 const_iterator end()
const {
return _Base::end(); }
389 using _Base::equal_range;
390 size_type erase(
const key_type& key) {
return _Base::erase(key); }
391 void erase(const_iterator position) { _Base::erase(position); }
392 void erase(const_iterator first, const_iterator last) {
393 _Base::erase(first, last);
396 using _Base::get_allocator;
397 using _Base::hash_function;
398 iterator insert(
const value_type& v) {
399 return _Base::insert(v);
401 iterator insert(const_iterator hint,
const value_type& v) {
402 return _Base::insert(hint, v);
404 template<
class InputIterator>
405 void insert(InputIterator first, InputIterator last) {
406 _Base::insert(first, last);
409 using _Base::load_factor;
410 using _Base::max_bucket_count;
411 using _Base::max_load_factor;
413 using _Base::max_size;
415 using _Base::reserve;
417 void swap(TfHashMultiSet& other) { _Base::swap(other); }
419 template<
class Key2,
class HashFn2,
class EqualKey2,
class Alloc2>
421 operator==(
const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&,
422 const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&);
427template<
class Key,
class HashFn,
class EqualKey,
class Alloc>
429swap(TfHashSet<Key, HashFn, EqualKey, Alloc>& lhs,
430 TfHashSet<Key, HashFn, EqualKey, Alloc>& rhs)
435template<
class Key,
class HashFn,
class EqualKey,
class Alloc>
437operator==(
const TfHashSet<Key, HashFn, EqualKey, Alloc>& lhs,
438 const TfHashSet<Key, HashFn, EqualKey, Alloc>& rhs)
440 typedef typename TfHashSet<Key, HashFn, EqualKey, Alloc>::_Base _Base;
441 return static_cast<const _Base&
>(lhs) ==
static_cast<const _Base&
>(rhs);
444template<
class Key,
class HashFn,
class EqualKey,
class Alloc>
446operator!=(
const TfHashSet<Key, HashFn, EqualKey, Alloc>& lhs,
447 const TfHashSet<Key, HashFn, EqualKey, Alloc>& rhs)
449 return !(lhs == rhs);
452template<
class Key,
class HashFn,
class EqualKey,
class Alloc>
454swap(TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& lhs,
455 TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& rhs)
460template<
class Key,
class HashFn,
class EqualKey,
class Alloc>
462operator==(
const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& lhs,
463 const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& rhs)
465 typedef typename TfHashMultiSet<Key, HashFn, EqualKey, Alloc>::_Base _Base;
466 return static_cast<const _Base&
>(lhs) ==
static_cast<const _Base&
>(rhs);
469template<
class Key,
class HashFn,
class EqualKey,
class Alloc>
471operator!=(
const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& lhs,
472 const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& rhs)
474 return !(lhs == rhs);
477PXR_NAMESPACE_CLOSE_SCOPE