Implement a simple unordered set of <T> of unbounded size. More...

#include <Unbounded_Set_Ex.h>

Collaboration diagram for ACE_Unbounded_Set_Ex:

Public Types
typedef ACE_Unbounded_Set_Ex_Iterator < T, C >	ITERATOR
typedef ACE_Unbounded_Set_Ex_Iterator < T, C >	iterator
typedef ACE_Unbounded_Set_Ex_Const_Iterator < T, C >	CONST_ITERATOR
typedef ACE_Unbounded_Set_Ex_Const_Iterator < T, C >	const_iterator
typedef C	COMP
typedef ACE_Node< T, C >	NODE
typedef T	value_type
typedef T const	const_value_type
typedef value_type &	reference
typedef const_value_type &	const_reference
typedef value_type *	pointer
typedef const_value_type *	const_pointer
typedef ptrdiff_t	difference_type
Public Member Functions
	ACE_Unbounded_Set_Ex (ACE_Allocator *alloc=0)
	ACE_Unbounded_Set_Ex (const C &comparator, ACE_Allocator *alloc=0)
	ACE_Unbounded_Set_Ex (const ACE_Unbounded_Set_Ex< T, C > &)
	Copy constructor.
ACE_Unbounded_Set_Ex< T, C > &	operator= (const ACE_Unbounded_Set_Ex< T, C > &)
	Assignment operator.
	~ACE_Unbounded_Set_Ex (void)
	Destructor.
bool	is_empty (void) const
	Returns `true` if the container is empty, otherwise returns `false`.
bool	is_full (void) const
	Returns `false`.
int	insert (const T &new_item)
	Linear insertion of an item.
int	insert_tail (const T &item)
int	remove (const T &item)
	Linear remove operation.
int	find (const T &item) const
size_t	size (void) const
	Size of the set.
void	dump (void) const
	Dump the state of an object.
void	reset (void)
	Reset the ACE_Unbounded_Set_Ex to be empty.
iterator	begin (void)
iterator	end (void)
const_iterator	begin (void) const
const_iterator	end (void) const
Public Attributes
	ACE_ALLOC_HOOK_DECLARE
	Declare the dynamic allocation hooks.
Private Member Functions
void	delete_nodes (void)
	Delete all the nodes in the Set.
void	copy_nodes (const ACE_Unbounded_Set_Ex< T, C > &)
	Copy nodes into this set.
Private Attributes
NODE *	head_
	Head of the linked list of Nodes.
size_t	cur_size_
	Current size of the set.
ACE_Allocator *	allocator_
	Allocation strategy of the set.
COMP	comp_
	Comparator to be used.
Friends
class	ACE_Unbounded_Set_Ex_Iterator< T, C >
class	ACE_Unbounded_Set_Ex_Const_Iterator< T, C >

Detailed Description

Implement a simple unordered set of <T> of unbounded size.

This implementation of an unordered set uses a circular linked list with a dummy node. This implementation does not allow duplicates, but it maintains FIFO ordering of insertions.

This implementation may also be parameterized with a comparator functor, which must implement bool operator () (const T&, const T&) const, returning true if the given items are equivalent. The default comparator is sufficient for objects reliably compared with operator==.

Requirements and Performance Characteristics

Internal Structure Circular linked list
Duplicates allowed? No
Random access allowed? No
Search speed Linear
Insert/replace speed Linear
Iterator still valid after change to container? Yes
Frees memory for removed elements? Yes
Items inserted by Value
Requirements for contained type
1. Default constructor
2. Copy constructor
3. operator=
4. operator== const

Member Typedef Documentation

typedef C ACE_Unbounded_Set_Ex::COMP

typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex::CONST_ITERATOR

typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex::const_iterator

typedef const_value_type* ACE_Unbounded_Set_Ex::const_pointer

typedef const_value_type& ACE_Unbounded_Set_Ex::const_reference

typedef T const ACE_Unbounded_Set_Ex::const_value_type

typedef ptrdiff_t ACE_Unbounded_Set_Ex::difference_type

typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex::ITERATOR

typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex::iterator

typedef ACE_Node<T, C> ACE_Unbounded_Set_Ex::NODE

typedef value_type* ACE_Unbounded_Set_Ex::pointer

typedef value_type& ACE_Unbounded_Set_Ex::reference

typedef T ACE_Unbounded_Set_Ex::value_type

Constructor & Destructor Documentation

ACE_Unbounded_Set_Ex::ACE_Unbounded_Set_Ex ( ACE_Allocator * alloc = 0 )

Constructor. Use user specified allocation strategy if specified. Initialize an empty set using the allocation strategy of the user if provided.

ACE_Unbounded_Set_Ex::ACE_Unbounded_Set_Ex	(	const C &	comparator,
		ACE_Allocator *	alloc = `0`
	)

Initialize an empty set using the allocation strategy of the user if provided, and a given comparator functor.

ACE_Unbounded_Set_Ex::ACE_Unbounded_Set_Ex ( const ACE_Unbounded_Set_Ex< T, C > & )

Copy constructor.

Initialize this set to be an exact copy of the set provided.

ACE_Unbounded_Set_Ex::~ACE_Unbounded_Set_Ex ( void )

Destructor.

Destroy the nodes of the set.

Member Function Documentation

iterator ACE_Unbounded_Set_Ex::begin ( void )

const_iterator ACE_Unbounded_Set_Ex::begin ( void ) const

void ACE_Unbounded_Set_Ex::copy_nodes ( const ACE_Unbounded_Set_Ex< T, C > & ) [private]

Copy nodes into this set.

void ACE_Unbounded_Set_Ex::delete_nodes ( void ) [private]

Delete all the nodes in the Set.

void ACE_Unbounded_Set_Ex::dump ( void ) const

Dump the state of an object.

iterator ACE_Unbounded_Set_Ex::end ( void )

const_iterator ACE_Unbounded_Set_Ex::end ( void ) const

int ACE_Unbounded_Set_Ex::find ( const T & item ) const

Finds if item occurs in the set. Returns 0 if find succeeds, else -1. Performs a linear find operation.

int ACE_Unbounded_Set_Ex::insert ( const T & new_item )

Linear insertion of an item.

Insert new_item into the set (doesn't allow duplicates). Returns -1 if failures occur, 1 if item is already present, else 0.

int ACE_Unbounded_Set_Ex::insert_tail ( const T & item )

Insert item at the tail of the set (doesn't check for duplicates). Constant time insert at the end of the set.

bool ACE_Unbounded_Set_Ex::is_empty ( void ) const

Returns true if the container is empty, otherwise returns false.

Constant time is_empty check.

bool ACE_Unbounded_Set_Ex::is_full ( void ) const

Returns false.

Always returns false since the set can never fill up.

ACE_Unbounded_Set_Ex<T, C>& ACE_Unbounded_Set_Ex::operator= ( const ACE_Unbounded_Set_Ex< T, C > & )

Assignment operator.

Perform a deep copy of the rhs into the lhs.

int ACE_Unbounded_Set_Ex::remove ( const T & item )

Linear remove operation.

Remove first occurrence of item from the set. Returns 0 if it removes the item, -1 if it can't find the item, and -1 if a failure occurs.

void ACE_Unbounded_Set_Ex::reset ( void )

Reset the ACE_Unbounded_Set_Ex to be empty.

Delete the nodes of the set.

size_t ACE_Unbounded_Set_Ex::size ( void ) const

Size of the set.

Access the size of the set.

Friends And Related Function Documentation

friend class ACE_Unbounded_Set_Ex_Const_Iterator< T, C > [friend]

friend class ACE_Unbounded_Set_Ex_Iterator< T, C > [friend]

Member Data Documentation

ACE_Unbounded_Set_Ex::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

ACE_Allocator* ACE_Unbounded_Set_Ex::allocator_ [private]

Allocation strategy of the set.

COMP ACE_Unbounded_Set_Ex::comp_ [private]

Comparator to be used.

size_t ACE_Unbounded_Set_Ex::cur_size_ [private]

Current size of the set.

NODE* ACE_Unbounded_Set_Ex::head_ [private]

Head of the linked list of Nodes.

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

Unbounded_Set_Ex.h

Public Types

Public Member Functions

Public Attributes

Private Member Functions