7 #ifndef PXR_BASE_TF_DENSE_HASH_SET_H
8 #define PXR_BASE_TF_DENSE_HASH_SET_H
35 class EqualElement = std::equal_to<Element>,
36 unsigned Threshold = 128
49 typedef std::vector<Element> _Vector;
61 typedef typename _Vector::const_iterator
iterator;
74 const HashFn &hashFn = HashFn(),
75 const EqualElement &equalElement = EqualElement())
78 _equ() = equalElement;
84 : _storage(rhs._storage) {
86 _h = std::make_unique<_HashMap>(*rhs._h);
96 template <
class Iterator>
104 insert(l.begin(), l.end());
125 insert(l.begin(), l.end());
140 if (!rhs.
count(*iter))
148 return !(*
this == rhs);
161 _storage.swap(rhs._storage);
168 return _vec().empty();
174 return _vec().size();
180 return _vec().begin();
195 if (iter == _h->end())
198 return _vec().begin() + iter->second;
201 typename _Vector::const_iterator iter,
end = _vec().end();
203 for(iter = _vec().
begin(); iter !=
end; ++iter)
204 if (_equ()(*iter, k))
226 std::pair<typename _HashMap::iterator, bool> res =
227 _h->insert(std::make_pair(v,
size()));
242 _CreateTableIfNeeded();
250 template<
class IteratorType>
260 for (IteratorType iter = i0; iter !=
i1; ++iter)
267 template <
class Iterator>
271 _vec().assign(begin, end);
272 _CreateTableIfNeeded();
300 if (iter != std::prev(
end())) {
306 swap(*const_cast<Element *>(&(*iter)), _vec().back());
310 (*_h)[*iter] = iter - _vec().begin();
322 _h->erase(iter->first);
328 for(; vremain != _vec().end(); ++vremain)
329 (*_h)[*vremain] = vremain - _vec().begin();
338 _vec().shrink_to_fit();
346 if (sz < Threshold) {
353 _h.reset(
new _HashMap(sz, _hash(), _equ()));
354 for(
size_t i=0; i<sz; ++i)
355 (*_h)[_vec()[i]] = i;
362 TF_VERIFY(index <
size());
363 return _vec()[
index];
372 return _storage.vector;
381 EqualElement &_equ() {
386 const _Vector &_vec()
const {
387 return _storage.vector;
391 const HashFn &_hash()
const {
396 const EqualElement &_equ()
const {
401 inline void _CreateTableIfNeeded() {
402 if (
size() >= Threshold) {
409 inline void _CreateTable() {
411 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
412 for(
size_t i=0; i <
size(); ++i)
413 (*_h)[_vec()[i]] = i;
421 struct ARCH_EMPTY_BASES _CompressedStorage :
422 private EqualElement,
private HashFn {
424 "EqualElement and HashFn must be distinct types.");
425 _CompressedStorage() =
default;
426 _CompressedStorage(
const EqualElement&
equal,
const HashFn& hashFn)
427 : EqualElement(equal), HashFn(hashFn) {}
429 void swap(_CompressedStorage& other) {
431 vector.swap(other.vector);
432 swap(static_cast<EqualElement&>(*
this),
433 static_cast<EqualElement&>(other));
434 swap(static_cast<HashFn&>(*
this), static_cast<HashFn&>(other));
439 _CompressedStorage _storage;
442 std::unique_ptr<_HashMap> _h;
447 #endif // PXR_BASE_TF_DENSE_HASH_SET_H
_Base::const_iterator const_iterator
void erase(const iterator &i0, const iterator &i1)
bool operator==(const TfDenseHashSet &rhs) const
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
const_iterator end() const
GLsizei const GLfloat * value
void erase(const iterator &iter)
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
TfDenseHashSet(const TfDenseHashSet &rhs)
const_iterator find(const Element &k) const
size_t count(const Element &k) const
void insert(IteratorType i0, IteratorType i1)
const Element & operator[](size_t index) const
TfDenseHashSet & operator=(const TfDenseHashSet &rhs)
TfDenseHashSet(const HashFn &hashFn=HashFn(), const EqualElement &equalElement=EqualElement())
TfDenseHashSet & operator=(std::initializer_list< Element > l)
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
TfDenseHashSet(Iterator begin, Iterator end)
TfDenseHashSet(std::initializer_list< Element > l)
_Vector::const_iterator iterator
#define PXR_NAMESPACE_CLOSE_SCOPE
void swap(TfDenseHashSet &rhs)
size_t erase(const Element &k)
bool operator!=(const TfDenseHashSet &rhs) const
void insert_unique(Iterator begin, Iterator end)
insert_result insert(const value_type &v)
SIM_API const UT_StringHolder distance
const_iterator begin() const
_Vector::const_iterator const_iterator
A const_iterator type for this set.