#include <evo/sethash.h>

Inheritance diagram for SetHash< TKey, THash, TSize >:

Detailed Description

template<class TKey, class THash = CompareHash<TKey>, class TSize = SizeT>
class evo::SetHash< TKey, THash, TSize >

Set implemented as a hash table.

Template Parameters

TKey	Set key type
THash	Hash and comparison type to use
TSize	Size type to use for size values (must be unsigned integer) – default: SizeT

Features

Similar to STL set, with an implementation similar to STL unordered_set
Values are always unique (no duplicates)
This uses a hash table – lookups and inserts use constant time O(1), as long as a good hash function is used (low collisions)
This uses PtrList internally for buckets, and Array for collisions
- No memory allocated by new empty set
- Sharing makes copying efficient
- See PtrList features

C++11:

Range-based for loop – see STL Compatibility
SetHash<int> hash;
for (auto num : hash.asconst()) {
}
Initialization lists
SetHash<int> hash = {3, 1, 2};
SetHash<String> strhash = {"foo", "bar"};
Move semantics

Hashing and Comparison

You can leave the default hashing and comparison type (CompareHash) or specify an alternative.

CompareHash

See: Primitives & Containers

Iterators

SetHash::Iter – Read-Only Iterator (IteratorBi)
SetHash::IterM – Mutable Iterator (IteratorBi)

Caution: Modifying or resizing a set will shift or invalidate existing iterators (and pointers) using it.

Constructors

SetHash()
SetHash(const SetBaseType&)
SetHash(const ThisType&)
SetHash(std::initializer_list<Value>) [C++11]
SetHash(ThisType&&) [C++11]

Read Access

asconst()
size()
contains()
cbegin(), cend()
- begin() const, end() const
iter()
operator==()
- operator!=()

Modifiers

Examples

Example using a set of numbers

#include <evo/string.h>
#include <evo/sethash.h>
#include <evo/io.h>
using namespace evo;
static Console& c = con();
int main() {
    // Create set with numeric values
    SetHash<int> set;
    set.add(20);
    set.add(10);
    // Add more values from delimited string
    set.addsplit("30,40");
    // Join set as delimited string and print it
    String str;
    str.join(set);
    c.out << str << NL;
    // Check if set contains value
    bool has10 = set.contains(10);      // true
    bool has50 = set.contains(50);      // false
    // Iterate and print values
    for (SetHash<int>::Iter iter(set); iter; ++iter)
        c.out << *iter << NL;
    return 0;
}

Output:

10,20,40,30
10
20
40
30

Public Types
typedef void	EvoContainerType

typedef THash	Hash
	Hashing type – default: CompareHash. More...

typedef TKey	Item
	Item type (same as Value) More...

typedef IteratorBi< ThisType >::Const	Iter
	Iterator (const) - IteratorBi. More...

typedef IteratorBi< ThisType >	IterM
	Iterator (mutable) - IteratorBi. More...

typedef TKey	Key
	Key type (same as Value) More...

typedef Set< TKey, TSize >	SetBaseType
	Set base type More...

typedef TSize	Size
	Size type for size values (must be unsigned integer) – default: SizeT. More...

typedef SetHash< TKey, THash, TSize >	ThisType
	This type. More...

typedef TKey	Value
	Value type. More...

Public Member Functions
	SetHash ()
	Constructor. More...

	SetHash (const SetBaseType &src)
	Copy constructor. More...

	SetHash (const ThisType &src)
	Copy constructor. More...

	SetHash (std::initializer_list< Value > init)
	Sequence constructor (C++11). More...

	SetHash (ThisType &&src)
	Move constructor (C++11). More...

Value &	add (const Value &value, bool update=false)
	Add or update using given item. More...

template<class T >
Size	addfrom (const T &items, bool update=false)
	Add items from given list or set. More...

template<class T >
Size	addsplit (const T &str, char delim=',')
	Split delimited string into set items. More...

const ThisType &	asconst () const
	Explicitly use a const reference to this. More...

IterM	begin ()
	Get iterator at first item (mutable). More...

Iter	begin () const
	Get iterator at first item (const). More...

Size	capacity () const
	Get set capacity. More...

ThisType &	capacity (Size size)
	Set hash set capacity (capacity). More...

ThisType &	capacitymin (Size min)
	Set set capacity to at least given minimum. More...

Iter	cbegin () const
	Get iterator at first item (const). More...

Iter	cend () const
	Get iterator at end (const). More...

ThisType &	clear ()
	Clear by removing all items. More...

virtual SetBaseType &	compact ()
	Reduce capacity to fit current size (modifier). More...

bool	contains (const Value &value) const
	Get whether the set contains the given value. More...

bool	empty () const
	Get whether set is empty (size is 0). More...

IterM	end ()
	Get iterator at end. More...

Iter	end () const
	Get iterator at end (const). More...

Value &	get (const Value &value, bool *created=NULL)
	Get value, create if needed (mutable). More...

const Hash &	get_compare () const
	Get hash & comparison object being used for hashing and comparisons (const). More...

Hash &	get_compare ()
	Get hash & comparison object being used for hashing and comparisons. More...

Iter	iter (const Value &value) const
	Find (lookup) iterator for given value (const). More...

IterM	iterM (const Value &value)
	Find (lookup) iterator for given value (mutable). More...

bool	null () const
	Get whether set is null. More...

bool	operator!= (const SetBaseType &set) const
	Inequality operator. More...

bool	operator!= (const ThisType &set) const
	Inequality operator. More...

ThisType &	operator= (ThisType &&src)
	Move assignment operator (C++11). More...

ThisType &	operator= (const SetBaseType &src)
	Assignment operator. More...

ThisType &	operator= (const ThisType &src)
	Assignment operator. More...

bool	operator== (const SetBaseType &set) const
	Equality operator. More...

bool	operator== (const ThisType &set) const
	Equality operator. More...

bool	ordered () const
	Get whether set is ordered. More...

bool	remove (const Value &value)
	Find and remove given value. More...

bool	remove (typename SetBaseType::IterM &iter, IteratorDir dir=iterNONE)
	Remove item using given iterator. More...

bool	remove (IterM &iter, IteratorDir dir=iterNONE)
	Remove item using given iterator. More...

ThisType &	reserve (Size size)
	Reserve space for new items. More...

virtual SetBaseType &	set (const SetBaseType &src)=0
	Set as copy of given set. More...

ThisType &	set ()
	Set as null and empty. More...

ThisType &	set (const SetBaseType &src)
	Set as copy of given set. More...

ThisType &	set (const ThisType &src)
	Set as copy of given set. More...

ThisType &	setempty ()
	Set as empty but not null. More...

bool	shared () const
	Get whether shared. More...

Size	size () const
	Get set size (number of items). More...

ThisType &	unshare ()
	Make data unique by allocating new buffer, if needed (modifier). More...

Protected Member Functions
const Value *	getiter (IterKey &iterkey, const Value &value) const
	Used by base class to get data to initialize iterator. More...

Protected Attributes
Size	size_
	Set size (number of items, automatically updated by concrete set members) More...

Member Typedef Documentation

◆ EvoContainerType

typedef void EvoContainerType

◆ Hash

typedef THash Hash

Hashing type – default: CompareHash.

◆ Item

typedef TKey Item

inherited

Item type (same as Value)

◆ Iter

typedef IteratorBi<ThisType>::Const Iter

Iterator (const) - IteratorBi.

◆ IterM

typedef IteratorBi<ThisType> IterM

Iterator (mutable) - IteratorBi.

◆ Key

typedef TKey Key

inherited

Key type (same as Value)

◆ SetBaseType

typedef Set<TKey,TSize> SetBaseType

inherited

Set base type

◆ Size

typedef TSize Size

inherited

Size type for size values (must be unsigned integer) – default: SizeT.

◆ ThisType

typedef SetHash<TKey,THash,TSize> ThisType

This type.

◆ Value

typedef TKey Value

inherited

Value type.

Constructor & Destructor Documentation

◆ SetHash() [1/5]

SetHash ( )

inline

Constructor.

◆ SetHash() [2/5]

SetHash ( const SetBaseType & src )

inline

Copy constructor.

Parameters

src	Source to copy

◆ SetHash() [3/5]

SetHash ( const ThisType & src )

inline

Copy constructor.

Parameters

src	Source to copy

◆ SetHash() [4/5]

SetHash ( std::initializer_list< Value > init )

inline

Sequence constructor (C++11).

Parameters

init	Initializer list, passed as comma-separated values in braces `{ }`

◆ SetHash() [5/5]

SetHash ( ThisType && src )

inline

Move constructor (C++11).

Parameters

src	Source to move

Member Function Documentation

◆ add()

Value& add	(	const Value &	value,
		bool	update = `false`
	)

inlinevirtual

Add or update using given item.

Parameters

value	Value to add (copied)
update	Whether to update existing item, true to overwrite existing item – use when items that compare as equal can have diff metadata

Returns: Reference to added item

Implements Set< TKey, TSize >.

◆ addfrom()

Size addfrom	(	const T &	items,
		bool	update = `false`
	)

inlineinherited

Add items from given list or set.

Template Parameters

T	Container type to add from – can be Set, List, Array, or similar

Parameters

items	List to add items from
update	Whether to update existing item, true to overwrite existing items – use when items that compare as equal can have diff metadata

Returns: Number of new items added

◆ addsplit()

Size addsplit	(	const T &	str,
		char	delim = `','`
	)

inlineinherited

Split delimited string into set items.

This parses/tokenizes str and adds each item to set, using convert() for conversion to set item type
Set value types must be convertible from String via convert()
See joinset() to join set back into string

Template Parameters

T	String type to parse – inferred from str parameter

Parameters

str	String to parse
delim	Value delimiter to use

Returns: Number of items added to set

◆ asconst()

const ThisType& asconst ( ) const

inline

Explicitly use a const reference to this.

This is useful to force using this as const without casting

Returns: This

◆ begin() [1/2]

IterM begin ( )

inline

Get iterator at first item (mutable).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly
cbegin() is more efficient, since this effectively calls unshare() to make items mutable

Returns: Iterator at first item, or at end position if empty

See also: IterM, end(), cbegin(), cend()

◆ begin() [2/2]

Iter begin ( ) const

inline

Get iterator at first item (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly

Returns: Iterator at first item, or at end position if empty

See also: end() const, cbegin()

◆ capacity() [1/2]

Size capacity ( ) const

inlinevirtual

Get set capacity.

Returns: Current capacity

Implements Set< TKey, TSize >.

◆ capacity() [2/2]

ThisType& capacity ( Size size )

inlinevirtual

Set hash set capacity (capacity).

Use to suggest a new capacity before adding a batch of items
This will set hash size to nearest power of 2 that can fit both current items and given size
Caution: This will invalidate iterators and pointers to values on this set

Parameters

size	New suggested capacity

Returns: This

Implements Set< TKey, TSize >.

◆ capacitymin()

ThisType& capacitymin ( Size min )

inlinevirtual

Set set capacity to at least given minimum.

Parameters

min	Minimum capacity

Returns: This

Implements Set< TKey, TSize >.

◆ cbegin()

Iter cbegin ( ) const

inline

Get iterator at first item (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly

Returns: Iterator at first item, or at end position if empty

See also: Iter, cend(), begin(), end()

◆ cend()

Iter cend ( ) const

inline

Get iterator at end (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly
This really just creates an empty iterator

Returns: Iterator at end position

See also: Iter, cbegin(), begin(), end()

◆ clear()

ThisType& clear ( )

inlinevirtual

Clear by removing all items.

Does not set as null – null status is unchanged

Returns: This

Implements Set< TKey, TSize >.

◆ compact()

virtual SetBaseType& compact ( )

inlinevirtualinherited

Reduce capacity to fit current size (modifier).

Call to save memory when done adding items
This is just a suggestion – some implementations may ignore it

Returns: This

Reimplemented in SetList< TKey, TCompare, TSize >, and SetList< String >.

◆ contains()

bool contains ( const Value & value ) const

inlinevirtual

Get whether the set contains the given value.

Parameters

value Value to look for

Returns: Whether value was found

Implements Set< TKey, TSize >.

◆ empty()

bool empty ( ) const

inlineinherited

Get whether set is empty (size is 0).

Returns: Whether empty

◆ end() [1/2]

IterM end ( )

inline

Get iterator at end.

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly
This really just creates an empty iterator

Returns: Iterator at end position

See also: IterM, begin(), cbegin(), cend()

◆ end() [2/2]

Iter end ( ) const

inline

Get iterator at end (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly
This really just creates an empty iterator

Returns: Iterator at end position

See also: begin() const, cend()

◆ get()

Value& get	(	const Value &	value,
		bool *	created = `NULL`
	)

inlinevirtual

Get value, create if needed (mutable).

Existing value is returned as-is
New value is created via copy constructor

Parameters

value	Value to use, copied if new value is created
created	Stores whether new item was created, if not NULL

Returns: Reference to new value

Implements Set< TKey, TSize >.

◆ get_compare() [1/2]

const Hash& get_compare ( ) const

inline

Get hash & comparison object being used for hashing and comparisons (const).

Returns: Hash & comparison object reference

◆ get_compare() [2/2]

Hash& get_compare ( )

inline

Get hash & comparison object being used for hashing and comparisons.

Returns: Hash & comparison object reference

◆ getiter()

const Value* getiter	(	IterKey &	iterkey,
		const Value &	value
	)		const

inlineprotectedvirtual

Used by base class to get data to initialize iterator.

Parameters

iterkey	Set to iterator data, if item found
value	Value to find

Returns: Value pointer, NULL if not found

Implements Set< TKey, TSize >.

◆ iter()

Iter iter ( const Value & value ) const

inline

Find (lookup) iterator for given value (const).

Parameters

value Value to find

Returns: Iterator, at end position if value not found

◆ iterM()

IterM iterM ( const Value & value )

inline

Find (lookup) iterator for given value (mutable).

Caution: Results are undefined if value is modified in a way that changes it's ordered position in set

Parameters

value Value to find

Returns: Iterator, at end position if value not found

◆ null()

bool null ( ) const

inlinevirtual

Get whether set is null.

Returns: Whether null

Implements Set< TKey, TSize >.

◆ operator!=() [1/2]

bool operator!= ( const SetBaseType & set ) const

inlineinherited

Inequality operator.

Parameters

set	Set to compare to

Returns: Whether sets are not equal (don't have same items)

◆ operator!=() [2/2]

bool operator!= ( const ThisType & set ) const

inline

Inequality operator.

Parameters

set	Set to compare to

Returns: Whether sets are not equal (don't have same items)

◆ operator=() [1/3]

ThisType& operator= ( ThisType && src )

inline

Move assignment operator (C++11).

Parameters

src	Source to move

Returns: This

◆ operator=() [2/3]

ThisType& operator= ( const SetBaseType & src )

inline

Assignment operator.

Parameters

src	Source to copy

Returns: This

◆ operator=() [3/3]

ThisType& operator= ( const ThisType & src )

inline

Assignment operator.

Parameters

src	Source to copy

Returns: This

◆ operator==() [1/2]

bool operator== ( const SetBaseType & set ) const

inlineinherited

Equality operator.

Parameters

set	Set to compare to

Returns: Whether sets are equal (have same items)

◆ operator==() [2/2]

bool operator== ( const ThisType & set ) const

inline

Equality operator.

Parameters

set	Set to compare to

Returns: Whether sets are equal (have same items)

◆ ordered()

bool ordered ( ) const

inlinevirtual

Get whether set is ordered.

Ordered sets keep items in order by value so iteration order is predictable

Implements Set< TKey, TSize >.

◆ remove() [1/3]

bool remove ( const Value & value )

inlinevirtual

Find and remove given value.

Caution: Removing an item may shift other iterators on same set, in an unpredictable way – see remove(IterM&,IteratorDir)

Parameters

value Value to use

Returns: Whether value was removed, false if not found

Implements Set< TKey, TSize >.

◆ remove() [2/3]

bool remove	(	typename SetBaseType::IterM &	iter,
		IteratorDir	dir = `iterNONE`
	)

inlinevirtual

Remove item using given iterator.

This will move the iterator to the next item according to dir, or end position if no more
Caution: Removing an item may shift other iterators on same set, in an unpredictable way

Parameters

iter	Iterator position
dir	Direction to move iterator to next item, iterNONE for end position

Returns: Whether item was removed, false if iterator at end position

Implements Set< TKey, TSize >.

◆ remove() [3/3]

bool remove	(	IterM &	iter,
		IteratorDir	dir = `iterNONE`
	)

inlinevirtual

Remove item using given iterator.

This will move the iterator to the next item according to dir, or end position if no more
Caution: Removing an item may shift other iterators on same set, in an unpredictable way

Parameters

iter	Iterator position
dir	Direction to move iterator to next item, iterNONE for end position

Returns: Whether item was removed, false if iterator at end position

Implements Set< TKey, TSize >.

◆ reserve()

ThisType& reserve ( Size size )

inline

Reserve space for new items.

For best performance, call this before adding multiple values
This calls capacitymin() with current size + size to reserve space
This is just a suggestion – some implementations may ignore it

Parameters

size	Size to reserve

Returns: This

◆ set() [1/4]

virtual SetBaseType& set ( const SetBaseType & src )

pure virtualinherited

Set as copy of given set.

This clears all items in current set.

Parameters

src	Source items

Returns: This

Implemented in SetList< TKey, TCompare, TSize >, and SetList< String >.

◆ set() [2/4]

ThisType& set ( )

inlinevirtual

Set as null and empty.

Returns: This

Implements Set< TKey, TSize >.

◆ set() [3/4]

ThisType& set ( const SetBaseType & src )

inline

Set as copy of given set.

This clears all items in current set.

Parameters

src	Source items

Returns: This

◆ set() [4/4]

ThisType& set ( const ThisType & src )

inline

Set as copy of given set.

This clears all items in current set.

Parameters

src	Source items

Returns: This

◆ setempty()

ThisType& setempty ( )

inlinevirtual

Set as empty but not null.

Returns: This

Implements Set< TKey, TSize >.

◆ shared()

bool shared ( ) const

inlinevirtual

Get whether shared.

Data is shared when referencing external data or buffer is allocated and shared (reference count > 1)

Returns: Whether shared

Implements Set< TKey, TSize >.

◆ size()

Size size ( ) const

inlineinherited

Get set size (number of items).

Returns: Set size

◆ unshare()

ThisType& unshare ( )

inlinevirtual

Make data unique by allocating new buffer, if needed (modifier).

Use reserve() instead to reserve additional space while unsharing
Use to make buffer unique (not shared) and writable (when not empty)
This is called automatically by mutable/modifier methods
This does nothing if empty or not shared

Returns: This

Implements Set< TKey, TSize >.

Member Data Documentation

◆ size_

Size size_

protectedinherited

Set size (number of items, automatically updated by concrete set members)

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

evo/sethash.h

Detailed Description

template<class TKey, class THash = CompareHash<TKey>, class TSize = SizeT> class evo::SetHash< TKey, THash, TSize >

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ EvoContainerType

◆ Hash

◆ Item

◆ Iter

◆ IterM

◆ Key

◆ SetBaseType

◆ Size

◆ ThisType

◆ Value

Constructor & Destructor Documentation

◆ SetHash() [1/5]

◆ SetHash() [2/5]

◆ SetHash() [3/5]

◆ SetHash() [4/5]

◆ SetHash() [5/5]

Member Function Documentation

◆ add()

◆ addfrom()

◆ addsplit()

◆ asconst()

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity() [1/2]

◆ capacity() [2/2]

◆ capacitymin()

◆ cbegin()

◆ cend()

◆ clear()

◆ compact()

◆ contains()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ get()

◆ get_compare() [1/2]

◆ get_compare() [2/2]

◆ getiter()

◆ iter()

◆ iterM()

◆ null()

◆ operator!=() [1/2]

◆ operator!=() [2/2]

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ operator==() [1/2]

◆ operator==() [2/2]

◆ ordered()

◆ remove() [1/3]

◆ remove() [2/3]

◆ remove() [3/3]

◆ reserve()

◆ set() [1/4]

◆ set() [2/4]

◆ set() [3/4]

◆ set() [4/4]

◆ setempty()

◆ shared()

◆ size()

◆ unshare()

Member Data Documentation

◆ size_

template<class TKey, class THash = CompareHash<TKey>, class TSize = SizeT>
class evo::SetHash< TKey, THash, TSize >