RWTIsvDlist< TL > Class Template Reference

Implements intrusive doubly-linked lists. More...

#include <rw/tidlist.h>

Inherits RWIsvDlist.

Public Member Functions
	RWTIsvDlist ()
	RWTIsvDlist (RWTIsvDlist &&lst)
	RWTIsvDlist (TL *a)
void	append (TL *a)
void	apply (void(*applyFun)(TL *, void *), void *d)
TL *	at (size_t i) const
void	clear ()
void	clearAndDestroy ()
bool	contains (bool(*testFun)(const TL *, void *), void *d) const
bool	containsReference (const TL *a) const
size_t	entries () const
TL *	find (bool(*testFun)(const TL *, void *), void *d) const
TL *	first () const
TL *	get ()
size_t	index (bool(*testFun)(const TL *, void *), void *d) const
void	insert (TL *a)
void	insertAt (size_t i, TL *a)
bool	isEmpty () const
TL *	last () const
size_t	occurrencesOf (bool(*testFun)(const TL *, void *), void *d) const
size_t	occurrencesOfReference (const TL *a) const
RWTIsvDlist &	operator= (RWTIsvDlist &&lst)
void	prepend (TL *a)
TL *	remove (bool(*testFun)(const TL *, void *), void *d)
TL *	removeAt (size_t i)
TL *	removeFirst ()
TL *	removeLast ()
TL *	removeReference (TL *a)
void	swap (RWTIsvDlist< TL > &lst)

Friends
class	RWTIsvDlistIterator< TL >

Detailed Description

template<class TL>
class RWTIsvDlist< TL >

Class RWTIsvDlist implements intrusive doubly-linked lists.

An intrusive list requires that all members of the list inherit from a common base class, in this case RWIsvDlink. The advantage of such a list is that memory and space requirements are minimized. The disadvantage is that the inheritance hierarchy is inflexible, possibly complicating its use with an existing class. Class RWTValDlist is offered as an alternative, non-intrusive, linked list.

This class is not CopyConstructible or CopyAssignable but is MoveConstructible and MoveAssignable.

See Stroustrup (1991; Section 8.3.1) for more information about intrusive lists.

Note

When you insert an item into an intrusive list, the actual item (not a copy) is inserted. Because each item carries only one link field, the same item cannot be inserted into more than one list, nor can it be inserted into the same list more than once.

Synopsis

#include <rw/tidlist.h>
RWTIsvDlist<T> list;

Example

#include <rw/cstring.h>
#include <rw/tidlist.h>
#include <iostream>
 
struct MySymbol : public RWIsvDlink {
  MySymbol(const char* s) : s_(s) {}
 
  const RWCString& name() const { return s_; }
 
 private:
  RWCString s_;
};
 
void printem(MySymbol* s, void*) { std::cout << s->name() << std::endl; }
 
int main() {
  RWTIsvDlist<MySymbol> list;
 
  list.insert(new MySymbol("one"));
  list.insert(new MySymbol("two"));
  list.prepend(new MySymbol("zero"));
 
  list.apply(printem, 0);
  list.clearAndDestroy();  // Deletes the items inserted into
                           // the list
 
  return 0;
}

Program Output:

zero
one
two

Constructor & Destructor Documentation

RWTIsvDlist() [1/3]

template<class TL >

RWTIsvDlist< TL >::RWTIsvDlist ( )

inline

Constructs an empty list.

RWTIsvDlist() [2/3]

template<class TL >

RWTIsvDlist< TL >::RWTIsvDlist ( TL * a )

inline

Constructs a list containing the single item pointed to by a.

RWTIsvDlist() [3/3]

template<class TL >

RWTIsvDlist< TL >::RWTIsvDlist ( RWTIsvDlist< TL > && lst )

inline

Move constructor. The constructed RWTIsvDlist takes ownership of the data owned by lst.

Condition:

This method is available only on platforms with rvalue reference support.

Member Function Documentation

append()

template<class TL >

void RWTIsvDlist< TL >::append ( TL * a )

inline

Appends the item pointed to by a to the end of the list.

apply()

template<class TL >

void RWTIsvDlist< TL >::apply	(	void(*	applyFun )(TL *, void *),
		void *	d )

Calls the function pointed to by applyFun to every item in the collection. Client data may be passed through as parameter d.

at()

template<class TL >

TL * RWTIsvDlist< TL >::at ( size_t i ) const

inline

Returns the item at index i.

Exceptions

RWBoundsErr

Thrown if the index i is not between zero and the number of items in the collection less one.

clear()

template<class TL >

void RWTIsvDlist< TL >::clear ( )

inline

Removes all items from the list.

clearAndDestroy()

template<class TL >

void RWTIsvDlist< TL >::clearAndDestroy

(

)

Removes and calls delete for each item in the list. Note that this assumes that each item was allocated off the heap.

contains()

template<class TL >

bool RWTIsvDlist< TL >::contains ( bool(* testFun )(const TL *, void *), void * d ) const

inline

Returns true if the list contains an item for which the user-defined function pointed to by testFun returns true.

For each item in the list, this function is called with the item as the first argument. Client data may be passed through as parameter d.

containsReference()

template<class TL >

bool RWTIsvDlist< TL >::containsReference ( const TL * a ) const

inline

Returns true if the list contains an item with the address a.

entries()

template<class TL >

size_t RWTIsvDlist< TL >::entries ( ) const

inline

Returns the number of items currently in the list.

find()

template<class TL >

TL * RWTIsvDlist< TL >::find	(	bool(*	testFun )(const TL *, void *),
		void *	d ) const

Returns the first item in the list for which the user-defined function pointed to by testFun returns true. If there is no such item, then returns rwnil.

For each item in the list, this function is called with the item as the first argument. Client data may be passed through as parameter d.

first()

template<class TL >

TL * RWTIsvDlist< TL >::first ( ) const

inline

Returns (but does not remove) the first item in the list, or returns rwnil if the list is empty.

get()

template<class TL >

TL * RWTIsvDlist< TL >::get ( )

inline

Returns and removes the first item in the list, or rwnil if the list is empty.

index()

template<class TL >

size_t RWTIsvDlist< TL >::index	(	bool(*	testFun )(const TL *, void *),
		void *	d ) const

Returns the index of the first item in the list for which the user-defined function pointed to by testFun returns true. If there is no such item, then returns RW_NPOS.

For each item in the list, this function is called with the item as the first argument. Client data may be passed through as parameter d.

insert()

template<class TL >

void RWTIsvDlist< TL >::insert ( TL * a )

inline

Appends the item pointed to by a to the end of the list. This item cannot be inserted into more than one list, nor can it be inserted into the same list more than once.

insertAt()

template<class TL >

void RWTIsvDlist< TL >::insertAt ( size_t i, TL * a )

inline

Inserts the item pointed to by a at the index position i. The item cannot be inserted into more than one list, nor can it be inserted into the same list more than once.

Exceptions

RWBoundsErr

Thrown if the index i is not between zero and the number of items in the list.

isEmpty()

template<class TL >

bool RWTIsvDlist< TL >::isEmpty ( ) const

inline

Returns true if there are no items in the list, false otherwise.

last()

template<class TL >

TL * RWTIsvDlist< TL >::last ( ) const

inline

Returns (but does not remove) the last item in the list, or rwnil if the list is empty.

occurrencesOf()

template<class TL >

size_t RWTIsvDlist< TL >::occurrencesOf	(	bool(*	testFun )(const TL *, void *),
		void *	d ) const

Traverses the list and returns the number of times for which the user-defined function pointed to by testFun returned true.

For each item in the list, this function is called with the item as the first argument. Client data may be passed through as parameter d.

occurrencesOfReference()

template<class TL >

size_t RWTIsvDlist< TL >::occurrencesOfReference ( const TL * a ) const

inline

Returns the number of times which the item pointed to by a occurs in the list. Because items cannot be inserted into a list more than once, this function can only return zero or one.

operator=()

template<class TL >

RWTIsvDlist & RWTIsvDlist< TL >::operator= ( RWTIsvDlist< TL > && lst )

inline

Move assignment. Self takes ownership of the data owned by lst.

Condition:

This method is available only on platforms with rvalue reference support.

prepend()

template<class TL >

void RWTIsvDlist< TL >::prepend ( TL * a )

inline

Prepends the item pointed to by a to the beginning of the list.

remove()

template<class TL >

TL * RWTIsvDlist< TL >::remove	(	bool(*	testFun )(const TL *, void *),
		void *	d )

Removes and returns the first item for which the user-defined tester function pointed to by testFun returns true, or rwnil if there is no such item.

For each item in the list, this function is called with the item as the first argument. Client data may be passed through as parameter d.

removeAt()

template<class TL >

TL * RWTIsvDlist< TL >::removeAt ( size_t i )

inline

Removes and returns the item at index i.

Exceptions

RWBoundsErr

Thrown if the index i is not between zero and the number of items in the collection less one.

removeFirst()

template<class TL >

TL * RWTIsvDlist< TL >::removeFirst ( )

inline

Removes and returns the first item in the list, or rwnil if there are no items in the list.

removeLast()

template<class TL >

TL * RWTIsvDlist< TL >::removeLast ( )

inline

Removes and returns the last item in the list, or rwnil if there are no items in the list.

removeReference()

template<class TL >

TL * RWTIsvDlist< TL >::removeReference ( TL * a )

inline

Removes and returns the item with address a, or rwnil if there is no such item.

swap()

template<class TL >

void RWTIsvDlist< TL >::swap ( RWTIsvDlist< TL > & lst )

inline

Swaps the data owned by self with the data owned by lst.