24#ifndef PXR_BASE_TF_DENSE_HASH_SET_H
25#define PXR_BASE_TF_DENSE_HASH_SET_H
31#include "pxr/base/tf/hashmap.h"
36PXR_NAMESPACE_OPEN_SCOPE
52 class EqualElement = std::equal_to<Element>,
53 unsigned Threshold = 128
59 typedef Element value_type;
66 typedef std::vector<Element> _Vector;
69 typedef TfHashMap<Element, size_t, HashFn, EqualElement> _HashMap;
78 typedef typename _Vector::const_iterator
iterator;
91 const HashFn &hashFn = HashFn(),
92 const EqualElement &equalElement = EqualElement())
95 _equ() = equalElement;
101 : _storage(rhs._storage) {
103 _h = std::make_unique<_HashMap>(*rhs._h);
113 template <
class Iterator>
121 insert(l.begin(), l.end());
142 insert(l.begin(), l.end());
157 if (!rhs.
count(*iter))
165 return !(*
this == rhs);
178 _storage.swap(rhs._storage);
185 return _vec().empty();
191 return _vec().size();
197 return _vec().begin();
211 typename _HashMap::const_iterator iter = _h->find(k);
212 if (iter == _h->end())
215 return _vec().begin() + iter->second;
218 typename _Vector::const_iterator iter,
end = _vec().end();
220 for(iter = _vec().
begin(); iter !=
end; ++iter)
221 if (_equ()(*iter, k))
229 size_t count(
const Element &k)
const {
243 std::pair<typename _HashMap::iterator, bool> res =
244 _h->insert(std::make_pair(v,
size()));
259 _CreateTableIfNeeded();
267 template<
class IteratorType>
268 void insert(IteratorType i0, IteratorType i1) {
273 if (
size() + std::distance(i0, i1) >= Threshold)
277 for (IteratorType iter = i0; iter != i1; ++iter)
284 template <
class Iterator>
289 _CreateTableIfNeeded();
317 if (iter != std::prev(
end())) {
323 swap(*
const_cast<Element *
>(&(*iter)), _vec().back());
327 (*_h)[*iter] = iter - _vec().begin();
339 _h->erase(iter->first);
345 for(; vremain != _vec().end(); ++vremain)
346 (*_h)[*vremain] = vremain - _vec().begin();
355 _vec().shrink_to_fit();
363 if (sz < Threshold) {
370 _h.reset(
new _HashMap(sz, _hash(), _equ()));
371 for(
size_t i=0; i<sz; ++i)
372 (*_h)[_vec()[i]] = i;
380 return _vec()[index];
389 return _storage.vector;
398 EqualElement &_equ() {
403 const _Vector &_vec()
const {
404 return _storage.vector;
408 const HashFn &_hash()
const {
413 const EqualElement &_equ()
const {
418 inline void _CreateTableIfNeeded() {
419 if (
size() >= Threshold) {
426 inline void _CreateTable() {
428 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
429 for(
size_t i=0; i <
size(); ++i)
430 (*_h)[_vec()[i]] = i;
439 private EqualElement,
private HashFn {
440 static_assert(!std::is_same<EqualElement, HashFn>::value,
441 "EqualElement and HashFn must be distinct types.");
442 _CompressedStorage() =
default;
443 _CompressedStorage(
const EqualElement& equal,
const HashFn& hashFn)
444 : EqualElement(equal), HashFn(hashFn) {}
446 void swap(_CompressedStorage& other) {
448 vector.swap(other.vector);
449 swap(
static_cast<EqualElement&
>(*
this),
450 static_cast<EqualElement&
>(other));
451 swap(
static_cast<HashFn&
>(*
this),
static_cast<HashFn&
>(other));
456 _CompressedStorage _storage;
459 std::unique_ptr<_HashMap> _h;
462PXR_NAMESPACE_CLOSE_SCOPE
Define function attributes.
#define ARCH_EMPTY_BASES
Macro to begin the definition of a class that is using private inheritance to take advantage of the e...
This is a space efficient container that mimics the TfHashSet API that uses a vector for storage when...
size_t erase(const Element &k)
Erase element with key k.
size_t size() const
Returns the size of the set.
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the set.
TfDenseHashSet(TfDenseHashSet &&rhs)=default
Move Ctor.
TfDenseHashSet(Iterator begin, Iterator end)
Construct from range.
const Element & operator[](size_t index) const
Index into set via index.
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash set.
size_t count(const Element &k) const
Returns the number of elements with key k.
TfDenseHashSet(const HashFn &hashFn=HashFn(), const EqualElement &equalElement=EqualElement())
Ctor.
void shrink_to_fit()
Optimize storage space.
bool empty() const
true if the set's size is 0.
void erase(const iterator &i0, const iterator &i1)
Erases a range from the set.
void erase(const iterator &iter)
Erases element pointed to by iter.
TfDenseHashSet & operator=(TfDenseHashSet &&rhs)=default
Move assignment operator.
void swap(TfDenseHashSet &rhs)
Swaps the contents of two sets.
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
const_iterator find(const Element &k) const
Finds the element with key k.
TfDenseHashSet(std::initializer_list< Element > l)
Construct from an initializer_list.
_Vector::const_iterator const_iterator
A const_iterator type for this set.
bool operator==(const TfDenseHashSet &rhs) const
Equality operator.
insert_result insert(const value_type &v)
Returns a pair of <iterator, bool> where iterator points to the element in the list and bool is true ...
void clear()
Erases all of the elements.
TfDenseHashSet & operator=(const TfDenseHashSet &rhs)
Copy assignment operator.
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
const_iterator end() const
Returns an const_iterator pointing to the end of the set.
_Vector::const_iterator iterator
An iterator type for this set.
TfDenseHashSet(const TfDenseHashSet &rhs)
Copy Ctor.
TfDenseHashSet & operator=(std::initializer_list< Element > l)
Assignment from an initializer_list.
#define TF_VERIFY(cond, format,...)
Checks a condition and reports an error if it evaluates false.