HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > Class Template Reference

#include <UT_ArraySet.h>

+ Inheritance diagram for UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >:

Classes

class  const_iterator
 
class  iterator_t
 Set iterator class. More...
 

Public Types

typedef ArraySet< Key, MULTI,
MAX_LOAD_FACTOR_256, Clearer,
Hash, KeyEqual > 
set_type
 
typedef Key key_type
 
typedef Key value_type
 
typedef std::size_t size_type
 
typedef std::ptrdiff_t difference_type
 
typedef Hash hasher
 
typedef KeyEqual key_equal
 
typedef value_typereference
 
typedef const value_typeconst_reference
 
typedef value_typepointer
 
typedef const value_typeconst_pointer
 
typedef Clearer clearer_type
 
typedef iterator_t< false > iterator
 Iterator type for iterating over non-constant elements. More...
 

Public Member Functions

 ArraySet ()
 
 ArraySet (size_type init_bucket_count)
 
 ArraySet (set_type &&that)
 Move constructor, destroying the source. More...
 
 ArraySet (const set_type &that)
 
template<typename INPUT_ITERATOR >
 ArraySet (INPUT_ITERATOR start_input, INPUT_ITERATOR end_input, size_type init_bucket_count=0)
 Inserts all of the items in the range [start_input,end_input). More...
 
 ArraySet (std::initializer_list< value_type > init, size_type init_bucket_count=0)
 
set_typeoperator= (const set_type &that)
 
set_typeoperator= (std::initializer_list< value_type > init)
 
set_typeoperator= (set_type &&that)
 
bool operator== (const set_type &that) const
 
bool operator!= (const set_type &that) const
 
void swap (set_type &that)
 Swaps another set with this one. More...
 
 ~ArraySet ()
 
bool empty () const
 Returns true iff there are no items in the set. More...
 
size_type size () const
 Returns the number of items in the set. More...
 
void clear ()
 
void destroy ()
 Removes all items from the set and frees all the memory. More...
 
size_type bucket_count () const
 Returns the current number of buckets. More...
 
size_type bucket_size (size_type i) const
 
float load_factor () const
 Returns the current portion of buckets that are occupied. More...
 
void rehash (size_type new_num_buckets)
 
void reserve (size_type num_items)
 
void setNumBuckets (size_type new_num_buckets)
 
void bumpNumBuckets (size_type new_num_items)
 
iterator begin ()
 Returns a non-const iterator for the beginning of the set. More...
 
const_iterator cbegin () const
 Returns a const iterator for the beginning of the set. More...
 
const_iterator begin () const
 Returns a const iterator for the beginning of the set. More...
 
iterator end ()
 Returns a non-const end iterator for the set. More...
 
const_iterator cend () const
 Returns a const end iterator for the set. More...
 
const_iterator end () const
 Returns a const end iterator for the set. More...
 
size_type count (const Key &key) const
 
bool contains (const Key &key) const
 
template<typename INPUT_ITERATOR >
void insert (INPUT_ITERATOR start_input, INPUT_ITERATOR end_input)
 Inserts all of the items in the range [start_input,end_input). More...
 
void insert (std::initializer_list< value_type > list)
 Inserts all of the items from the initializer_list. More...
 
template<typename... Args>
std::pair< iterator, bool > emplace (Args &&...args)
 
iterator erase (iterator iter)
 
iterator erase (iterator start_iter, iterator end_iter)
 
size_type erase (const Key &key)
 
int64 getMemoryUsage (bool inclusive) const
 
template<typename FUNCTOR >
SYS_FORCE_INLINE void forEach (FUNCTOR &&functor) const
 
iterator find (const Key &key)
 
const_iterator find (const Key &key) const
 
std::pair< const_iterator,
const_iterator
equal_range (const Key &key) const
 
std::pair< iterator, iteratorequal_range (const Key &key)
 
std::pair< iterator, bool > insert (const value_type &value)
 
std::pair< iterator, bool > insert (value_type &&value)
 

Static Public Member Functions

static size_type max_size ()
 
static size_type max_bucket_count ()
 
static float max_load_factor ()
 
static hasher hash_function ()
 
static key_equal key_eq ()
 

Protected Member Functions

pointer searchStart (const Key &key)
 
const_pointer searchStart (const Key &key) const
 
template<bool fail_on_equal = !MULTI, bool check_realloc = true>
bool insertHelper (pointer pstart, size_type nbuckets, const value_type &value, pointer &destp)
 

Static Protected Member Functions

static size_type minBuckets (size_type size)
 

Protected Attributes

pointer myBuckets
 
size_type myNumBuckets
 

Detailed Description

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
class UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >

This is close to a drop-in replacement for std::unordered_set, except that it uses a single array of items and empty spaces marked with a dedicated "clear" value. It also has a fixed maximum load factor, and doesn't store a hasher, comparator, or allocator object as member data, avoiding unnecessary overhead, but these differences introduce some interface incompatibilities.

The incompatibility that will probably be encountered most often is the lack of time guarantees. This structure is more efficient in many common cases, due to better memory coherency and fewer memory allocations, but cannot guarantee as good time scaling in worst or even average case as std::unordered_set guarantees for most functions.

Because there is only space for one item in each bucket, if a collision is hit on insertion, the structure will scan forward until a "clear" bucket is found. However, items in a contiguous block will always be sorted in the order of their ideal bucket numbers. If the end of the array is reached without finding a clear bucket, instead of the obvious approach of wrapping to the beginning of the array, the block will be shifted backward, so some items in this block at the end may be earlier than their ideal bucket number. This is about as complicated as wrapping, or not sorting, but avoids an awkward issue when erasing while iterating where an item might get visited multiple times due to the wrapping, or items might be missed due to the lack of order. Even still, unlike std::unordered_set, erase may invalidate other iterators and references. Also, insert may invalidate other iterators and references.

Definition at line 160 of file UT_ArraySet.h.

Member Typedef Documentation

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef Clearer UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::clearer_type

Definition at line 174 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef const value_type* UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::const_pointer

Definition at line 173 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef const value_type& UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::const_reference

Definition at line 171 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef std::ptrdiff_t UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::difference_type

Definition at line 167 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef Hash UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::hasher

Definition at line 168 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef iterator_t<false> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::iterator

Iterator type for iterating over non-constant elements.

Definition at line 635 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef KeyEqual UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::key_equal

Definition at line 169 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef Key UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::key_type

Definition at line 164 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef value_type* UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::pointer

Definition at line 172 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef value_type& UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::reference

Definition at line 170 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef ArraySet<Key,MULTI,MAX_LOAD_FACTOR_256,Clearer,Hash,KeyEqual> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::set_type

Definition at line 163 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef std::size_t UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::size_type

Definition at line 166 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef Key UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::value_type

Definition at line 165 of file UT_ArraySet.h.

Constructor & Destructor Documentation

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::ArraySet ( )
inline

Definition at line 176 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::ArraySet ( size_type  init_bucket_count)
inlineexplicit

Definition at line 182 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::ArraySet ( set_type &&  that)
inline

Move constructor, destroying the source.

Definition at line 191 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::ArraySet ( const set_type that)
inlineexplicit

Copy constructor. Avoid accidental copying by making the constructor explicit.

Definition at line 201 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
template<typename INPUT_ITERATOR >
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::ArraySet ( INPUT_ITERATOR  start_input,
INPUT_ITERATOR  end_input,
size_type  init_bucket_count = 0 
)
inline

Inserts all of the items in the range [start_input,end_input).

Definition at line 210 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::ArraySet ( std::initializer_list< value_type init,
size_type  init_bucket_count = 0 
)
inline

Constructs a set from an initializer list, with an optional bucket count, e.g.: UT::ArraySet<int> some_set({5,123,500}, 20);

Definition at line 234 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::~ArraySet ( )
inline

Definition at line 334 of file UT_ArraySet.h.

Member Function Documentation

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::begin ( void  )
inline

Returns a non-const iterator for the beginning of the set.

Definition at line 652 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const_iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::begin ( void  ) const
inline

Returns a const iterator for the beginning of the set.

Definition at line 662 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::bucket_count ( ) const
inline

Returns the current number of buckets.

Definition at line 400 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::bucket_size ( size_type  i) const
inline

This only exists because the standard requires it. This function doesn't really make sense for this implementation, but it returns 1 if the bucket is occupied, and 0 if it is not.

Definition at line 415 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::bumpNumBuckets ( size_type  new_num_items)
inline

This increases the number of buckets, if needed, for the specified number of items

Definition at line 530 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const_iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::cbegin ( ) const
inline

Returns a const iterator for the beginning of the set.

Definition at line 657 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const_iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::cend ( ) const
inline

Returns a const end iterator for the set.

Definition at line 673 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::clear ( void  )
inline

Removes all items from the set, but does not free the memory. Call destroy() to free all the memory.

Definition at line 360 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
bool UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::contains ( const Key &  key) const
inline

Returns true iff the set contains the given key. This should be faster than count() if MULTI is true.

Definition at line 787 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::count ( const Key &  key) const
inline

Returns the number of entries matching key. If MULTI is false, this will only return either 0 or 1.

Definition at line 748 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::destroy ( void  )
inline

Removes all items from the set and frees all the memory.

Definition at line 377 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
template<typename... Args>
std::pair<iterator,bool> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::emplace ( Args &&...  args)
inline

Inserts an element constructed with the given arguments. Maybe the standard implementation can somehow get a speedup from this, but we need the item's hash before inserting, so it needs to be constructed first.

Definition at line 1019 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
bool UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::empty ( void  ) const
inline

Returns true iff there are no items in the set.

Definition at line 340 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::end ( void  )
inline

Returns a non-const end iterator for the set.

Definition at line 667 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const_iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::end ( void  ) const
inline

Returns a const end iterator for the set.

Definition at line 679 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
std::pair<const_iterator,const_iterator> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::equal_range ( const Key &  key) const
inline

Returns a pair of iterators representing the range of values matching key, as [first,second).

Definition at line 818 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
std::pair<iterator,iterator> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::equal_range ( const Key &  key)
inline

Returns a pair of iterators representing the range of values matching key, as [first,second).

Definition at line 883 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::erase ( iterator  iter)
inline

Removes the item at the specified iterator location, returning an iterator to the next item.

Unlike std::unordered_set::erase(const_iterator), this may invalidate iterators and references to other items in the map, if they are in a contiguous block of non-empty items with the item that iter points to. Also, this only accepts an iterator, instead of a const_iterator. (Why would std::unordered_set::erase accept a const_iterator?)

Definition at line 1033 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::erase ( iterator  start_iter,
iterator  end_iter 
)
inline

Removes all items in the range [start_iter,end_iter), and returns an iterator immediately following that range.

Unlike std::unordered_set::erase(const_iterator,const_iterator), this may invalidate iterators and references to other items in the map, if they are in a contiguous block of non-empty items with the items in the erased range. Also, this only accepts iterator's, instead of const_iterator's. (Why would std::unordered_set::erase accept a const_iterator?)

Definition at line 1148 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::erase ( const Key &  key)
inline

Removes all items matching key and returns the number of items removed.

Definition at line 1240 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::find ( const Key &  key)
inline

Returns an iterator to the first item matching key, or an end iterator if no items match key.

Definition at line 688 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const_iterator UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::find ( const Key &  key) const
inline

Returns an iterator to the first item matching key, or an end iterator if no items match key.

Definition at line 716 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
template<typename FUNCTOR >
SYS_FORCE_INLINE void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::forEach ( FUNCTOR &&  functor) const
inline

Definition at line 1284 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
int64 UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::getMemoryUsage ( bool  inclusive) const
inline

Returns the amount of memory used by this, excluding any memory that might be allocated by any of the items, themselves.

Definition at line 1275 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
static hasher UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::hash_function ( )
inlinestatic

NOTE: std::unordered_set::hash_function() isn't static, but here, we're not storing a hasher as a data member, so it's independent of the instance.

Definition at line 1260 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
std::pair<iterator, bool> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::insert ( const value_type value)
inline

Inserts the given value into the set, unless MULTI is false and there's already an item for which key_equal()(value,other) returns true. Returns a pair of iterator to the inserted value (or the existing item if not inserted), and a bool that's true iff the item was inserted.

Definition at line 956 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
std::pair<iterator, bool> UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::insert ( value_type &&  value)
inline

Inserts the given value into the set, unless MULTI is false and there's already an item for which key_equal()(value,other) returns true. Returns a pair of iterator to the inserted value (or the existing item if not inserted), and a bool that's true iff the item was inserted.

Definition at line 967 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
template<typename INPUT_ITERATOR >
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::insert ( INPUT_ITERATOR  start_input,
INPUT_ITERATOR  end_input 
)
inline

Inserts all of the items in the range [start_input,end_input).

Definition at line 982 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::insert ( std::initializer_list< value_type list)
inline

Inserts all of the items from the initializer_list.

Definition at line 1008 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
template<bool fail_on_equal = !MULTI, bool check_realloc = true>
bool UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::insertHelper ( pointer  pstart,
size_type  nbuckets,
const value_type value,
pointer destp 
)
inlineprotected

Definition at line 1322 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
static key_equal UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::key_eq ( )
inlinestatic

NOTE: std::unordered_set::key_eq() isn't static, but here, we're not storing a key_equal as a data member, so it's independent of the instance.

Definition at line 1268 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
float UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::load_factor ( ) const
inline

Returns the current portion of buckets that are occupied.

Definition at line 436 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
static size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::max_bucket_count ( )
inlinestatic

This only exists because the standard requires it. The only hard limit is what memory will allow.

Definition at line 407 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
static float UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::max_load_factor ( )
inlinestatic

Returns the portion of buckets that need to be occupied before reallocation occurs. Unlike in the standard, the maximum load factor is a constant in this implementation, so max_load_factor() is a static function.

Definition at line 430 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
static size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::max_size ( )
inlinestatic

This only exists because the standard requires it. The only hard limit is what memory will allow.

Definition at line 353 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
static size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::minBuckets ( size_type  size)
inlinestaticprotected

Definition at line 1296 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
bool UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::operator!= ( const set_type that) const
inline

Definition at line 318 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
set_type& UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::operator= ( const set_type that)
inline

Definition at line 251 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
set_type& UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::operator= ( std::initializer_list< value_type init)
inline

Definition at line 278 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
set_type& UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::operator= ( set_type &&  that)
inline

Definition at line 285 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
bool UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::operator== ( const set_type that) const
inline

Definition at line 295 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::rehash ( size_type  new_num_buckets)
inline

Sets the number of buckets to larger of new_num_buckets and the required minimum number of buckets for size() items, unless that number is the same as the current number of buckets.

Definition at line 444 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::reserve ( size_type  num_items)
inline

Sets the number of buckets to the required minimum number of buckets for the larger of num_items and size().

Definition at line 458 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
pointer UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::searchStart ( const Key &  key)
inlineprotected

Definition at line 1310 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const_pointer UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::searchStart ( const Key &  key) const
inlineprotected

Definition at line 1315 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::setNumBuckets ( size_type  new_num_buckets)
inline

Sets the number of buckets to new_num_buckets, regardless of the required minimum number of buckets for size() items, though you probably shouldn't be calling it with num_new_buckets < size(), except that if num_new_buclets==0, this calls destroy().

Definition at line 468 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::size ( void  ) const
inline

Returns the number of items in the set.

Definition at line 346 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::swap ( set_type that)
inline

Swaps another set with this one.

Definition at line 324 of file UT_ArraySet.h.

Member Data Documentation

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
pointer UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::myBuckets
protected

Definition at line 1477 of file UT_ArraySet.h.

template<typename Key, bool MULTI = false, std::size_t MAX_LOAD_FACTOR_256 = 128, typename Clearer = DefaultClearer<Key>, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_type UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual >::myNumBuckets
protected

Definition at line 1478 of file UT_ArraySet.h.


The documentation for this class was generated from the following file: