sets.h File Reference

Implementation of set containers with different underlying data structures. More...

#include "allocator.h"
#include "couple.h"
#include "hash.h"
#include "hashTable.h"
#include "set.h"
#include "ownerPtr.h"
#include "comparator.h"
#include "RBTree.h"
#include "skipList.h"

Include dependency graph for sets.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	original::hashSet< TYPE, HASH, ALLOC >
	Hash table based implementation of the set interface. More...
class	original::hashSet< TYPE, HASH, ALLOC >::Iterator
	Forward iterator for hashSet. More...
class	original::treeSet< TYPE, Compare, ALLOC >
	Red-Black Tree based implementation of the set interface. More...
class	original::treeSet< TYPE, Compare, ALLOC >::Iterator
	Bidirectional iterator for treeSet. More...
class	original::JSet< TYPE, Compare, ALLOC >
	Skip List based implementation of the set interface. More...
class	original::JSet< TYPE, Compare, ALLOC >::Iterator
	Forward iterator for JSet. More...

Namespaces
namespace	original
	Main namespace for the project Original.
namespace	std
	Standard namespace extensions for original::alternative.

Functions
template<typename TYPE , typename HASH , typename ALLOC >
void	std::swap (original::hashSet< TYPE, HASH, ALLOC > &lhs, original::hashSet< TYPE, HASH, ALLOC > &rhs) noexcept
	std::swap specialization for hashSet
template<typename TYPE , typename COMPARE , typename ALLOC >
void	std::swap (original::treeSet< TYPE, COMPARE, ALLOC > &lhs, original::treeSet< TYPE, COMPARE, ALLOC > &rhs) noexcept
	std::swap specialization for treeSet
template<typename TYPE , typename COMPARE , typename ALLOC >
void	std::swap (original::JSet< TYPE, COMPARE, ALLOC > &lhs, original::JSet< TYPE, COMPARE, ALLOC > &rhs) noexcept
	std::swap specialization for JSet

Detailed Description

Implementation of set containers with different underlying data structures.

Provides three set implementations with different performance characteristics and iteration capabilities:

1. hashSet - Hash table based implementation (unordered, fastest average case)
2. treeSet - Red-Black Tree based implementation (ordered, consistent performance)
3. JSet - Skip List based implementation (ordered, probabilistic balance)

Common Features:

• Unique element storage (no duplicates)
• Full iterator support with different capabilities
• Customizable comparison/hash functions
• Customizable allocators with propagation support
• Exception safety guarantees (basic guarantee for most operations)
• Polymorphic usage through set interface
• Integration with printable for string representation

Performance Characteristics:

Container	Insertion	Lookup	Deletion	Ordered	Memory Usage
hashSet	O(1) avg	O(1)	O(1)	No	Medium-High
treeSet	O(log n)	O(log n)	O(log n)	Yes	Low
JSet	O(log n) avg	O(log n)	O(log n)	Yes	Medium

Usage Guidelines:

• Use hashSet for maximum performance when order doesn't matter and elements are hashable
• Use treeSet for ordered traversal, range queries, and consistent worst-case performance
• Use JSet for concurrent scenarios (external synchronization) or when probabilistic balance is preferred

Iterator Invalidation:

• hashSet: Iterators invalidate on rehash (insertion that causes capacity change)
• treeSet: Iterators invalidate on element removal that affects the current position
• JSet: Iterators invalidate on any structural modification

Exception Safety:

• Basic guarantee: Container remains valid but unspecified state on exception
• Strong guarantee for some operations (no-throw if element operations are noexcept)
• Allocator-aware exception handling

See also

set.h For the base interface definition

hashTable.h For hashSet implementation details

RBTree.h For treeSet implementation details

skipList.h For JSet implementation details

printable.h For string formatting support