24 #ifndef PXR_BASE_TF_DENSE_HASH_SET_H
25 #define PXR_BASE_TF_DENSE_HASH_SET_H
36 #include <hboost/iterator/iterator_facade.hpp>
54 class EqualElement = std::equal_to<Element>,
55 unsigned Threshold = 128
62 private HashFn,
private EqualElement
73 typedef std::vector<Element> _Vector;
85 typedef typename _Vector::const_iterator
iterator;
98 const HashFn &hashFn = HashFn(),
99 const EqualElement &equalElement = EqualElement()) :
101 EqualElement(equalElement) {}
108 _vector(rhs._vector),
109 _h(rhs._h ? std::make_unique<
_HashMap>(*rhs._h) : nullptr) {}
117 template <
class Iterator>
125 insert(l.begin(), l.end());
146 insert(l.begin(), l.end());
161 if (!rhs.
count(*iter))
169 return !(*
this == rhs);
183 swap(_hash(), rhs._hash());
184 swap(_equ(), rhs._equ());
185 _vector.swap(rhs._vector);
192 return _vec().empty();
198 return _vec().size();
204 return _vec().begin();
219 if (iter == _h->end())
222 return _vec().begin() + iter->second;
225 typename _Vector::const_iterator iter,
end = _vec().end();
227 for(iter = _vec().
begin(); iter !=
end; ++iter)
228 if (_equ()(*iter, k))
250 std::pair<typename _HashMap::iterator, bool> res =
251 _h->insert(std::make_pair(v,
size()));
266 _CreateTableIfNeeded();
274 template<
class IteratorType>
284 for (IteratorType iter = i0; iter !=
i1; ++iter)
291 template <
class Iterator>
295 _vec().assign(begin, end);
296 _CreateTableIfNeeded();
324 if (iter != std::prev(
end())) {
330 swap(*const_cast<Element *>(&(*iter)), _vec().back());
334 (*_h)[*iter] = iter - _vec().begin();
346 _h->erase(iter->first);
352 for(; vremain != _vec().end(); ++vremain)
353 (*_h)[*vremain] = vremain - _vec().begin();
362 _vec().shrink_to_fit();
370 if (sz < Threshold) {
377 _h.reset(
new _HashMap(sz, _hash(), _equ()));
378 for(
size_t i=0; i<sz; ++i)
379 (*_h)[_vec()[i]] = i;
386 TF_VERIFY(index <
size());
387 return _vec()[
index];
405 EqualElement &_equ() {
410 const _Vector &_vec()
const {
415 const HashFn &_hash()
const {
420 const EqualElement &_equ()
const {
425 inline void _CreateTableIfNeeded() {
426 if (
size() >= Threshold) {
433 inline void _CreateTable() {
435 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
436 for(
size_t i=0; i <
size(); ++i)
437 (*_h)[_vec()[i]] = i;
445 std::unique_ptr<_HashMap> _h;
450 #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
void erase(const iterator &iter)
void swap(T &lhs, T &rhs)
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
TfDenseHashSet(const TfDenseHashSet &rhs)
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
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.
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.