#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_type &	reference

typedef const value_type &	const_reference

typedef value_type *	pointer

typedef const value_type *	const_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_type &	operator= (const set_type &that)

set_type &	operator= (std::initializer_list< value_type > init)

set_type &	operator= (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 S >
bool	containsAll (const S &src) 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)

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, iterator >	equal_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 = hboost::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 227 of file UT_ArraySet.h.