sets.h File Reference

Implementation of set containers. 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:

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.

Detailed Description

Implementation of set containers.

Provides three set implementations with different underlying data structures:

1. hashSet - Hash table based implementation
2. treeSet - Red-Black Tree based implementation
3. JSet - Skip List based implementation

Common Features:

• Unique element storage (no duplicates)
• Full iterator support
• Customizable comparison/hash functions
• Customizable allocators
• Exception safety guarantees
• Polymorphic usage through set interface

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
• Use treeSet for ordered traversal and consistent performance
• Use JSet for concurrent scenarios or when probabilistic balance is preferred

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