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

#include <Unbounded_Set_Ex.h>

Collaboration diagram for ACE_Unbounded_Set_Ex< T, C >:

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. More...

ACE_Unbounded_Set_Ex< T, C > &	operator= (const ACE_Unbounded_Set_Ex< T, C > &)
	Assignment operator. More...

	~ACE_Unbounded_Set_Ex (void)
	Destructor. More...

bool	is_empty (void) const
	Returns `true` if the container is empty, otherwise returns `false`. More...

bool	is_full (void) const
	Returns `false`. More...

int	insert (const T &new_item)
	Linear insertion of an item. More...

int	insert_tail (const T &item)

int	remove (const T &item)
	Linear remove operation. More...

int	find (const T &item) const

size_t	size (void) const
	Size of the set. More...

void	dump (void) const
	Dump the state of an object. More...

void	reset (void)
	Reset the ACE_Unbounded_Set_Ex to be empty. More...

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. More...

Private Member Functions
void	delete_nodes (void)
	Delete all the nodes in the Set. More...

void	copy_nodes (const ACE_Unbounded_Set_Ex< T, C > &)
	Copy nodes into this set. More...

Private Attributes
NODE *	head_
	Head of the linked list of Nodes. More...

size_t	cur_size_
	Current size of the set. More...

ACE_Allocator *	allocator_
	Allocation strategy of the set. More...

COMP	comp_
	Comparator to be used. More...

Friends
class	ACE_Unbounded_Set_Ex_Iterator< T, C >

class	ACE_Unbounded_Set_Ex_Const_Iterator< T, C >

Detailed Description

template<class T, class C>
class ACE_Unbounded_Set_Ex< T, C >

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

template<class T, class C>

typedef C ACE_Unbounded_Set_Ex< T, C >::COMP

template<class T, class C>

typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::CONST_ITERATOR

template<class T, class C>

typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::const_iterator

template<class T, class C>

typedef const_value_type* ACE_Unbounded_Set_Ex< T, C >::const_pointer

template<class T, class C>

typedef const_value_type& ACE_Unbounded_Set_Ex< T, C >::const_reference

template<class T, class C>

typedef T const ACE_Unbounded_Set_Ex< T, C >::const_value_type

template<class T, class C>

typedef ptrdiff_t ACE_Unbounded_Set_Ex< T, C >::difference_type

template<class T, class C>

typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::ITERATOR

template<class T, class C>

typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::iterator

template<class T, class C>

typedef ACE_Node<T, C> ACE_Unbounded_Set_Ex< T, C >::NODE

template<class T, class C>

typedef value_type* ACE_Unbounded_Set_Ex< T, C >::pointer

template<class T, class C>

typedef value_type& ACE_Unbounded_Set_Ex< T, C >::reference

template<class T, class C>

typedef T ACE_Unbounded_Set_Ex< T, C >::value_type

Constructor & Destructor Documentation

template<class T , class C >

ACE_Unbounded_Set_Ex< T, C >::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.

template<class T , class C>

ACE_Unbounded_Set_Ex< T, C >::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.

template<class T, class C>

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

Copy constructor.

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

template<class T , class C >

ACE_Unbounded_Set_Ex< T, C >::~ACE_Unbounded_Set_Ex ( void )

Destructor.

Destroy the nodes of the set.

Member Function Documentation

template<class T , class C >

ACE_Unbounded_Set_Ex< T, C >::iterator ACE_Unbounded_Set_Ex< T, C >::begin ( void )

template<class T , class C >

ACE_Unbounded_Set_Ex< T, C >::const_iterator ACE_Unbounded_Set_Ex< T, C >::begin ( void ) const

template<class T, class C>

void ACE_Unbounded_Set_Ex< T, C >::copy_nodes ( const ACE_Unbounded_Set_Ex< T, C > & us )

private

Copy nodes into this set.

template<class T , class C >

void ACE_Unbounded_Set_Ex< T, C >::delete_nodes ( void )

private

Delete all the nodes in the Set.

template<class T , class C >

void ACE_Unbounded_Set_Ex< T, C >::dump ( void ) const

Dump the state of an object.

template<class T , class C >

ACE_Unbounded_Set_Ex< T, C >::iterator ACE_Unbounded_Set_Ex< T, C >::end ( void )

template<class T , class C >

ACE_Unbounded_Set_Ex< T, C >::const_iterator ACE_Unbounded_Set_Ex< T, C >::end ( void ) const

template<class T, class C >

int ACE_Unbounded_Set_Ex< T, C >::find ( const T & item ) const

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

template<class T, class C >

int ACE_Unbounded_Set_Ex< T, C >::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.

template<class T, class C >

int ACE_Unbounded_Set_Ex< T, C >::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.

template<class T , class C >

bool ACE_Unbounded_Set_Ex< T, C >::is_empty ( void ) const

inline

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

Constant time is_empty check.

template<class T , class C >

bool ACE_Unbounded_Set_Ex< T, C >::is_full ( void ) const

inline

Returns false.

Always returns false since the set can never fill up.

template<class T, class C>

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

Assignment operator.

Perform a deep copy of the rhs into the lhs.

template<class T, class C >

int ACE_Unbounded_Set_Ex< T, C >::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.

template<class T , class C >

void ACE_Unbounded_Set_Ex< T, C >::reset ( void )

Reset the ACE_Unbounded_Set_Ex to be empty.

Delete the nodes of the set.

template<class T , class C >

size_t ACE_Unbounded_Set_Ex< T, C >::size ( void ) const

Size of the set.

Access the size of the set.

Friends And Related Function Documentation

template<class T, class C>

friend class ACE_Unbounded_Set_Ex_Const_Iterator< T, C >

friend

template<class T, class C>

friend class ACE_Unbounded_Set_Ex_Iterator< T, C >

friend

Member Data Documentation

template<class T, class C>

ACE_Unbounded_Set_Ex< T, C >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

template<class T, class C>

ACE_Allocator* ACE_Unbounded_Set_Ex< T, C >::allocator_

private

Allocation strategy of the set.

template<class T, class C>

COMP ACE_Unbounded_Set_Ex< T, C >::comp_

private

Comparator to be used.

template<class T, class C>

size_t ACE_Unbounded_Set_Ex< T, C >::cur_size_

private

Current size of the set.

template<class T, class C>

NODE* ACE_Unbounded_Set_Ex< T, C >::head_

private

Head of the linked list of Nodes.

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

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

template<class T, class C> class ACE_Unbounded_Set_Ex< T, C >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class T, class C>
class ACE_Unbounded_Set_Ex< T, C >