Implement a simple ordered multiset of {T} of unbounded size that allows duplicates. This class template requires that < operator semantics be defined for the parameterized type {T}, but does not impose any restriction on how that ordering operator is implemented. The set is implemented as a linked list. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Ordered_MultiSet< T >:

[legend]

Public Types
typedef ACE_Ordered_MultiSet_Iterator< T >	ITERATOR

Public Member Functions
	ACE_Ordered_MultiSet (ACE_Allocator *the_allocator=0)

	ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet< T > &)
	Copy constructor. More...

	~ACE_Ordered_MultiSet (void)
	Destructor. More...

void	operator= (const ACE_Ordered_MultiSet< T > &)
	Assignment operator. More...

int	is_empty (void) const
	Returns 1 if the container is empty, otherwise returns 0. More...

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

int	insert (const T &new_item)

int	insert (const T &new_item, ITERATOR &iter)
	Linear time insert beginning at the point specified by the provided iterator. More...

int	remove (const T &item)

int	find (const T &item, ITERATOR &iter) const
	Linear find operation. More...

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

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

Public Attributes
	ACE_ALLOC_HOOK_DECLARE
	Declare the dynamic allocation hooks. More...

Private Member Functions
int	insert_from (const T &item, ACE_DNode< T > start_position, ACE_DNode< T > *new_position)

int	locate (const T &item, ACE_DNode< T > start_position, ACE_DNode< T > &new_position) const

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

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

Private Attributes
ACE_DNode< T > *	head_
	Head of the bilinked list of Nodes. More...

ACE_DNode< T > *	tail_
	Head of the bilinked list of Nodes. More...

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

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

Friends
class	ACE_Ordered_MultiSet_Iterator< T >

Detailed Description

template<class T>
class ACE_Ordered_MultiSet< T >

Implement a simple ordered multiset of {T} of unbounded size that allows duplicates. This class template requires that < operator semantics be defined for the parameterized type {T}, but does not impose any restriction on how that ordering operator is implemented. The set is implemented as a linked list.

Requirements and Performance Characteristics

Internal Structure Double linked list
Duplicates allowed? Yes
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==
5. operator<

Member Typedef Documentation

template<class T >

typedef ACE_Ordered_MultiSet_Iterator<T> ACE_Ordered_MultiSet< T >::ITERATOR

Constructor & Destructor Documentation

template<class T >

ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet ( ACE_Allocator * the_allocator = 0 )

Constructor. Use user specified allocation strategy if specified. Initialize the set using the allocation strategy specified. If none, use the default strategy.

template<class T >

ACE_Ordered_MultiSet< T >::ACE_Ordered_MultiSet ( const ACE_Ordered_MultiSet< T > & us )

Copy constructor.

Initialize the set to be a copy of the provided set.

template<class T >

ACE_Ordered_MultiSet< T >::~ACE_Ordered_MultiSet ( void )

Destructor.

Delete the nodes of the set.

Member Function Documentation

template<class T >

void ACE_Ordered_MultiSet< T >::copy_nodes ( const ACE_Ordered_MultiSet< T > & us )

private

Copy nodes into this set.

template<class T >

void ACE_Ordered_MultiSet< T >::delete_nodes ( void )

private

Delete all the nodes in the Set.

template<class T >

void ACE_Ordered_MultiSet< T >::dump ( void ) const

Dump the state of an object.

template<class T >

int ACE_Ordered_MultiSet< T >::find	(	const T &	item,
		ITERATOR &	iter
	)		const

Linear find operation.

Finds first occurrence of item in the multiset, using the iterator's current position as a hint to improve performance. If find succeeds, it positions the iterator at that node and returns 0, or if it cannot locate the node, it leaves the iterator alone and just returns -1.

template<class T >

int ACE_Ordered_MultiSet< T >::insert ( const T & new_item )

Insert new_item into the ordered multiset. Returns -1 if failures occur, else 0. Linear time, order preserving insert into the set beginning at the head.

template<class T >

int ACE_Ordered_MultiSet< T >::insert	(	const T &	new_item,
		ITERATOR &	iter
	)

Linear time insert beginning at the point specified by the provided iterator.

Insert new_item into the ordered multiset, starting its search at the node pointed to by the iterator, and if insertion was successful, updates the iterator to point to the newly inserted node. Returns -1 if failures occur, else 0.

template<class T >

int ACE_Ordered_MultiSet< T >::insert_from	(	const T &	item,
		ACE_DNode< T > *	start_position,
		ACE_DNode< T > **	new_position
	)

private

Insert item, starting its search at the position given, and if successful updates the passed pointer to point to the newly inserted item's node.

template<class T >

int ACE_Ordered_MultiSet< T >::is_empty ( void ) const

inline

Returns 1 if the container is empty, otherwise returns 0.

Constant time check to determine if the set is empty.

template<class T >

int ACE_Ordered_MultiSet< T >::locate	(	const T &	item,
		ACE_DNode< T > *	start_position,
		ACE_DNode< T > *&	new_position
	)		const

private

Looks for first occurrence of item in the ordered set, using the passed starting position as a hint: if there is such an instance, it updates the new_position pointer to point to this node and returns 0; if there is no such node, then if there is a node before where the item would have been, it updates the new_position pointer to point to this node and returns -1; if there is no such node, then if there is a node after where the item would have been, it updates the new_position pointer to point to this node (or 0 if there is no such node) and returns 1;

template<class T >

void ACE_Ordered_MultiSet< T >::operator= ( const ACE_Ordered_MultiSet< T > & us )

Assignment operator.

Delete the nodes in lhs, and copy the nodes from the rhs.

template<class T >

int ACE_Ordered_MultiSet< T >::remove ( const T & item )

Remove first occurrence of item from the set. Returns 0 if it removes the item, -1 if it can't find the item. Linear time search operation which removes the item from the set if found .

template<class T >

void ACE_Ordered_MultiSet< T >::reset ( void )

Reset the ACE_Ordered_MultiSet to be empty.

Delete the nodes inside the set.

template<class T >

size_t ACE_Ordered_MultiSet< T >::size ( void ) const

inline

Size of the set.

Constant time check to determine the size of the set.

Friends And Related Function Documentation

template<class T >

friend class ACE_Ordered_MultiSet_Iterator< T >

friend

Member Data Documentation

template<class T >

ACE_Ordered_MultiSet< T >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

template<class T >

ACE_Allocator* ACE_Ordered_MultiSet< T >::allocator_

private

Allocation strategy of the set.

template<class T >

size_t ACE_Ordered_MultiSet< T >::cur_size_

private

Current size of the set.

template<class T >

ACE_DNode<T>* ACE_Ordered_MultiSet< T >::head_

private

Head of the bilinked list of Nodes.

template<class T >

ACE_DNode<T>* ACE_Ordered_MultiSet< T >::tail_

private

Head of the bilinked 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 ACE_Ordered_MultiSet< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class T>
class ACE_Ordered_MultiSet< T >