List Containers

List containers are singly or doubly linked lists. The choice of which type of list to use is determined by the direction in which the list is traversed and by what is stored in the list. A list to which items are just added and removed may be most efficiently implemented as a singly linked list. If frequent retrievals of items at given indexes within the list are made, doubly linked lists can offer some improved performance when searching.

There are three sets of list container classes:

Value lists: Value lists are the simplest to use, but have the most requirements on the type stored in the lists. Copies are made of the values stored in the list, which could be undesirable if the stored objects are complicated and copying is expensive. Value lists shouldn't be used to store objects of a base class if any derived types of different sizes would be stored in the list, or if the destructor for the derived class must be called.
The WCValSList<Type> container class implements singly linked value lists, and the WCValDList<Type> class, doubly linked value lists.
Pointer lists: Pointer list elements store pointers to objects. No creating, copying or destroying of objects stored in the list occurs. The only requirement of the type pointed to is that an equivalence operator is provided so that lookups can be performed.
The WCPtrSList<Type> class implements singly linked pointer lists, and the WCPtrDList<Type> class, doubly linked pointer lists.
Intrusive lists: Intrusive lists require that the list elements are objects derived from the WCSLink or WCDLink class, depending on whether a singly or doubly linked list is used. The list classes require nothing else from the list elements. No creating, destroying or copying of any object is performed by the intrusive list classes, and must be done by the user of the class. One advantage of an intrusive list is a list element can be removed from one list and inserted into another list without creating new list element objects or deleting old objects.
The WCIsvSList<Type> class implements singly linked intrusive lists, and the WCIsvDList<Type> class doubly linked intrusive lists.

A list may be traversed using the corresponding list iterator class. Iterators allow lists to be stepped through one or more elements at a time. The iterator classes that correspond to singly linked list containers have some functionality inhibited. If backward traversal is required, the doubly linked containers and iterators must be used.

The classes are presented in alphabetical order. The WCSLink and WCDLink classes provide a common control interface for the list elements for the intrusive classes.

Since the container classes are all template classes, most of the functionality is derived from common base classes. In the listing of class member functions, those public member functions that appear to be in the container class but are actually defined in the common base class are identified as if they were explicitly specified in the container class.

WCDLink Class

Declared:

wclcom.h

Derived from:

WCSLink

The WCDLink class is the building block for all of the doubly linked list classes. It's implemented in terms of the WCSLink base class. Since no user data is stored directly with it, the WCDLink class should only be used as a base class to derive a user-defined class.

When creating a doubly linked intrusive list, the WCDLink class is used to derive the user-defined class that holds the data to be inserted into the list.

The wclcom.h header file is included by the wclist.h header file. There's no need to explicitly include the wclcom.h header file unless the wclist.h header file isn't included. No errors will result if it is included.

The destructor is non-virtual so that list elements are of minimum size. Objects created as a class derived from the WCDLink class, but destroyed while typed as a WCDLink object won't invoke the destructor of the derived class.

Public Member Functions

The following public member functions are declared:

WCDLink();
~WCDLink();

WCDLink::WCDLink()

create a WCDLink object

Synopsis:

#include <wclist.h>
public:
WCDLink();

Semantics:

The public WCDLink constructor creates an WCDLink object. This constructor is used implicitly by the compiler when it generates a constructor for a derived class.

Results:

The public WCDLink constructor produces an initialized WCDLink object.

WCDLink::~WCDLink()

destroy a WCDLink object

Synopsis:

#include <wclist.h>
public:
~WCDLink();

Semantics:

The public WCDLink destructor doesn't do anything explicit. The call to it is inserted implicitly by the compiler at the point where the object derived from WCDLink goes out of scope.

Results:

The object derived from WCDLink is destroyed.

WCIsvDList<Type> and WCIsvSList<Type> Classes

Declared:

wclist.h

The WCIsvDList<Type> and WCIsvSList<Type> classes are the templated classes used to create objects that are singly or doubly linked lists. The created list is intrusive, which means that list elements that are inserted must be created with a library-supplied base class. The class WCSLink provides the base class definition for singly linked lists, and should be inherited by the definition of any list item for singly linked lists. It provides the linkage that is used to traverse the list elements. Similarly, the class WCDLink provides the base class definition for doubly linked lists, and should be inherited by the definition of any list item for doubly linked lists.

In the description of each member function, the text Type is used to indicate the type value specified as the template parameter. Type is the type of the list elements, derived from WCSLink or WCDLink.

The WCExcept class is a base class of the WCIsvDList<Type> and WCIsvSList<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCIsvDList<Type> and WCIsvSList<Type> objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCIsvSList<Type> class requires only that Type be derived from WCSLink. The WCIsvDList<Type> class requires only that Type be derived from WCDLink.

Private Member Functions

In an intrusive list, copying a list is undefined. Setting the copy constructor and assignment operator as private is the standard mechanism to ensure a copy can't be made. The following member functions are declared private:

void WCIsvSList( const WCIsvSList & );
void WCIsvDList( const WCIsvDList & );
WCIsvSList & WCIsvSList::operator =( const WCIsvSList & );
WCIsvDList & WCIsvDList::operator =( const WCIsvDList & );

Public Member Functions

The following member functions are declared in the public interface:

WCIsvSList();
~WCIsvSList();

WCIsvDList();
~WCIsvDList();

int append( Type * );
void clear();
void clearAndDestroy();
int contains( const Type * ) const;
int entries() const;
Type * find( int = 0 ) const;
Type * findLast() const;
void forAll( void (*)( Type *, void * ), void *);
Type * get( int = 0 );
int index( const Type * ) const;
int index( int (*)( const Type *, void * ), void * ) const;
int insert( Type * );
int isEmpty() const;

Public Member Operators

The following member operators are declared in the public interface:

int WCIsvSList::operator ==( const WCIsvSList & ) const;
int WCIsvDList::operator ==( const WCIsvDList & ) const;

Sample Program Using an Intrusive List

#include <wclist.h>
#include <iostream.h>

class int_ddata : public WCDLink {
public:
    inline int_ddata() {};
    inline ~int_ddata() {};
    inline int_ddata( int datum ) : info( datum ) {};

    int     info;
};

static void test1( void );

void data_isv_prt( int_ddata * data, void * str ) {
    cout << (char *)str << "[" << data->info << "]\n";
}

void main() {
    try {
        test1();
    } catch( ... ) {
        cout << "we caught an unexpected exception\n";
    }
    cout.flush();
}

void test1 ( void ) {
    WCIsvDList<int_ddata>   list;
    int_ddata               data1(1);
    int_ddata               data2(2);
    int_ddata               data3(3);
    int_ddata               data4(4);
    int_ddata               data5(5);

    list.exceptions( WCExcept::check_all );
    list.append( &data2 );
    list.append( &data3 );
    list.append( &data4 );

    list.insert( &data1 );
    list.append( &data5 );
    cout <<
      "<intrusive doubly linked list for int_ddata>\n";
    list.forAll( data_isv_prt, "" );
    data_isv_prt( list.find( 3 ), "<the fourth element>" );
    data_isv_prt( list.get( 2 ), "<the third element>" );
    data_isv_prt( list.get(), "<the first element>" );
    list.clear();
    cout.flush();
}

WCIsvSList<Type>::WCIsvSList()

create a WCIsvSList object

Synopsis:

#include <wclist.h>
public:
WCIsvSList();

Semantics:

The public WCIsvSList<Type> constructor creates an empty WCIsvSList object.

Results:

This constructor produces an initialized WCIsvSList object.

WCIsvSList<Type>::~WCIsvSList()

destroy a WCIsvSList object

Synopsis:

#include <wclist.h>
public:
~WCIsvSList();

Semantics:

The public WCIsvSList<Type> destructor destroys the WCIsvSList object. If the list isn't empty and the not_empty exception is enabled, the exception is thrown. If the not_empty exception isn't enabled and the list isn't empty, the list is cleared using the clear() member function.

The call to this destructor is inserted implicitly by the compiler at the point where the WCIsvSList object goes out of scope.

Results:

The WCIsvSList object is destroyed.

WCIsvDList<Type>::WCIsvDList()

create a WCIsvDList object

Synopsis:

#include <wclist.h>
public:
WCIsvDList();

Semantics:

The public WCIsvDList<Type> constructor creates an empty WCIsvDList object.

Results:

This constructor produces an initialized WCIsvDList object.

WCIsvDList<Type>::~WCIsvDList()

destroy a WCIsvDList object

Synopsis:

#include <wclist.h>
public:
~WCIsvDList();

Semantics:

The public WCIsvDList<Type> destructor destroys the WCIsvDList object. If the list isn't empty and the not_empty exception is enabled, the exception is thrown. If the not_empty exception isn't enabled and the list isn't empty, the list is cleared using the clear() member function.

The call to this destructor is inserted implicitly by the compiler at the point where the WCIsvDList object goes out of scope.

Results:

The WCIsvDList object is destroyed.

WCIsvDList<Type>::append(), WCIsvSList<Type>::append()

append an element to the end of the list

Synopsis:

#include <wclist.h>
public:
int append( Type * );

Semantics:

The append() public member function is used to append the list element object to the end of the list. The address of (that is, a pointer to) the list element object should be passed, not the value. Since the linkage information is stored in the list element, it isn't possible for the element to be in more than one list, or in the same list more than once.

The passed list element should be constructed using the appropriate link class as a base:

WCSLink must be used as a list element base class for singly linked lists
WCDLink must be used as a list element base class for doubly linked lists

Results:

The list element is appended to the end of the list and a TRUE value (non-zero) is returned.

WCIsvDList<Type>::clear(), WCIsvSList<Type>::clear()

clear the list object

Synopsis:

#include <wclist.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the list object and set it to the state it was in just after its initial construction. The list object isn't destroyed and re-created by this operator, so the object destructor isn't invoked. The list elements aren't cleared. Any list items still in the list are lost unless pointed to by some pointer object in the program code.

If any of the list elements aren't allocated with new (local variable or global list elements), then the clear() public member function must be used. When all list elements are allocated with new, the clearAndDestroy() member function should be used.

Results:

The clear() public member function resets the list object to the state it was in immediately after its initial construction.

WCIsvDList<Type>::clearAndDestroy(), WCIsvSList<Type>::clearAndDestroy()

clear the list object, deleting any list elements

Synopsis:

#include <wclist.h>
public:
void clearAndDestroy();

Semantics:

The clearAndDestroy() public member function is used to clear the list object and set it to the state it was in just after its initial construction. The list object isn't destroyed and re-created by this operator, so the object destructor isn't invoked. The link elements are deleted before the list is re-initialized.

If any elements in the list weren't allocated by the new operator, this function must not be called. It destroys each list element with the destructor for Type even if the list element was created as an object derived from Type, unless Type has a pure virtual destructor.

Results:

The clearAndDestroy() public member function resets the list object to the state it was in immediately after its initial construction, and deletes the list elements.

WCIsvDList<Type>::contains(), WCIsvSList<Type>::contains()

determine whether or not an element is already in the list

Synopsis:

#include <wclist.h>
public:
int contains( const Type * ) const;

Semantics:

The contains() public member function is used to determine if a list element object is already contained in the list. The address of (that is, a pointer to) the list element object should be passed, not the value. Each list element is compared to the passed element object to determine if it has the same address.

The comparison is of the addresses of the elements, not the contained values.

Results:

Zero(0) is returned if the passed list element object isn't found in the list; a non-zero result is returned if the element is found.

WCIsvDList<Type>::entries(), WCIsvSList<Type>::entries()

count the elements in the list

Synopsis:

#include <wclist.h>
public:
int entries() const;

Semantics:

The entries() public member function is used to determine the number of list elements contained in the list object.

Results:

The number of entries stored in the list is returned.

WCIsvDList<Type>::find(), WCIsvSList<Type>::find()

find the element in a given position in the list

Synopsis:

#include <wclist.h>
public:
Type * find( int = 0 ) const;

Semantics:

The find() public member function returns a pointer to a list element in the list object. The list element isn't removed from the list, so take care not to delete the element returned to you. The optional parameter specifies which element to locate, and defaults to the first element. Since the index of the first element of the list is zero, the index of the last element is the number of list entries minus one.

If the list is empty and the empty_container exception is enabled, the exception is thrown. If the index_range exception is enabled, the exception is thrown if the index value is negative or is greater than the number of list entries minus one.

Results:

A pointer to the selected list element or the closest list element is returned. If the index value is negative, the closest list element is the first element. The last element is the closest element if the index value is greater than the number of list entries minus one. A value of NULL(0) is returned if there are no elements in the list.

WCIsvDList<Type>::findLast(), WCIsvSList<Type>::findLast()

find the last element in the list

Synopsis:

#include <wclist.h>
public:
Type * findLast() const;

Semantics:

The findLast() public member function returns a pointer to the last list element in the list object. The list element isn't removed from the list, so take care not to delete the element returned to you.

If the list is empty, one of two exceptions can be thrown:

If the empty_container exception is enabled, it's thrown.
The index_range exception is thrown if it's enabled and the empty_container exception isn't enabled.

Results:

A pointer to the last list element is returned. A value of NULL(0) is returned if there are no elements in the list.

WCIsvDList<Type>::forAll(), WCIsvSList<Type>::forAll()

invoke a function for each element in the list

Synopsis:

#include <wclist.h>
public:
void forAll( void (*fn)( Type *, void * ), void *);

Semantics:

The forAll() public member function is used to cause the function fn to be invoked for each list element. The fn function should have the prototype

    void (*fn)( Type *, void * )

The first parameter of fn shall accept a pointer to the currently active list element. The second argument passed to fn is the second argument of the forAll() function. This allows a callback function to be defined that can accept data appropriate for the point at which the forAll() function is invoked.

WCIsvDList<Type>::get(), WCIsvSList<Type>::get()

get a pointer to an element, removing it from the list

Synopsis:

#include <wclist.h>
public:
Type * get( int = 0 );

Semantics:

The get() public member function returns a pointer to a list element in the list object. The element is also removed from the list. The optional parameter specifies which element to remove, and defaults to the first element. Since the index of the first element of the list is zero, the index of the last element is the number of list entries minus one.

If the list is empty and the empty_container exception is enabled, the exception is thrown. If the index_range exception trap is enabled, the exception is thrown if the index value is negative or is greater than the number of list entries minus one.

Results:

A pointer to the selected list element or the closest list element is removed and returned. If the index value is negative, the closest list element is the first element. The last element is the closest element if the index value is greater than the number of list entries minus one. A value of NULL(0) is returned if there are no elements in the list.

WCIsvDList<Type>::index(), WCIsvSList<Type>::index()

find the index of a given element in the list

Synopsis:

#include <wclist.h>
public:
int index( const Type * ) const;
int index( int (*test_fn)( const Type *, void * ),
           void * ) const;

Semantics:

The index() public member function is used to determine the index of an element in the list:

The first form determines the index of the first list element equivalent to the passed element. The address of (a pointer to) the list element object should be passed, not the value. Each list element is compared to the passed element object to determine if it has the same address.

The comparison is of the addresses of the elements, not the contained values.
The second form of this function is used to determine the index of the first list element for which the supplied test_fn function returns true. The test_fn function must have the prototype:
```
    int (*test_fn)( const Type *, void * );
    
```
Each list element is passed in turn to the test_fn function as the first argument. The second parameter passed is the second argument of the index() function. This allows the test_fn callback function to accept data appropriate for the point at which the index() function is invoked. The supplied test_fn shall return a TRUE (non-zero) value when the index of the passed element is desired. Otherwise, a FALSE (zero) value shall be returned.

Results:

For the first form of this function, the index of the first element equivalent to the passed element is returned. If the passed element isn't in the list, negative one (-1) is returned.
For the second form, the index of the first list element for which the test_fn function returns non-zero is returned. If the test_fn function returns zero for all list elements, negative one (-1) is returned.

WCIsvDList<Type>::insert(), WCIsvSList<Type>::insert()

add an element to the beginning of the list

Synopsis:

#include <wclist.h>
public:
int insert( Type * );

Semantics:

The insert() public member function is used to insert the list element object at the beginning of the list. The address of (that is, a pointer to) the list element object should be passed, not the value. Since the linkage information is stored in the list element, it isn't possible for the element to be in more than one list, or in the same list more than once.

The passed list element should be constructed using the appropriate link class as a base:

WCSLink for singly linked lists
WCDLink for doubly linked lists.

Results:

The list element is inserted as the first element of the list, and a TRUE value (non-zero) is returned.

WCIsvDList<Type>::isEmpty(), WCIsvSList<Type>::isEmpty()

determine whether or not the list has any elements

Synopsis:

#include <wclist.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if a list object has any list elements in it.

Results:

A TRUE value (non-zero) is returned if the list object doesn't have any list elements in it. A FALSE (zero) result is returned if the list contains at least one element.

WCIsvDList<Type>::operator ==(), WCIsvSList<Type>::operator ==()

compare two lists

Synopsis:

#include <wclist.h>
public:
int WCIsvSList::operator ==( 
        const WCIsvSList & ) const;
int WCIsvDList::operator ==( 
        const WCIsvDList & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCIsvDList<Type> and WCIsvSList<Type> classes. Two list objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side object and the right hand side objects are the same object. A FALSE (zero) value is returned otherwise.

WCPtrDList<Type> and WCPtrSList<Type> Classes

Declared:

wclist.h

The WCPtrDList<Type> and WCPtrSList<Type> classes are the templated classes used to create objects that are singly or doubly linked lists.

In the description of each member function, the text Type is used to indicate the type value specified as the template parameter. The pointers stored in the list point to values of type Type.

The WCExcept class is a base class of the WCPtrDList<Type> and WCPtrSList<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCPtrDList<Type> and WCPtrSList<Type> objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCPtrDList<Type> and WCPtrSList<Type> classes require Type to have:

An equivalence operator with constant parameters

    Type::operator ==( const Type & ) const

Public Member Functions

The following member functions are declared in the public interface:

WCPtrSList();
WCPtrSList( void * (*)( size_t ), void (*)( void *, size_t ));
WCPtrSList( const WCPtrSList & );
~WCPtrSList();

WCPtrDList();
WCPtrDList( void * (*)( size_t ), void (*)( void *, size_t ));
WCPtrDList( const WCPtrDList & );
~WCPtrDList();

int append( Type * );
void clear();
void clearAndDestroy();
int contains( const Type * ) const;
int entries() const;
Type * find( int = 0 ) const;
Type * findLast() const;
void forAll( void (*)( Type *, void * ), void *) const;
Type * get( int = 0 );
int index( const Type * ) const;
int insert( Type * );
int isEmpty() const;

Public Member Operators

The following member operators are declared in the public interface:

WCPtrSList & WCPtrSList::operator =( const WCPtrSList & );
WCPtrDList & WCPtrDList::operator =( const WCPtrDList & );
int WCPtrSList::operator ==( const WCPtrSList & ) const;
int WCPtrDList::operator ==( const WCPtrDList & ) const;

Sample Program Using a Pointer List

#include <wclist.h>
#include <iostream.h>

static void test1( void );

void data_ptr_prt( int * data, void * str ) {
    cout << (char *)str << "[" << *data << "]\n";
}

void main() {
    try {
        test1();
    } catch( ... ) {
        cout << "we caught an unexpected exception\n";
    }
    cout.flush();
}

void test1 ( void ) {
    WCPtrDList<int>         list;
    int                     data1(1);
    int                     data2(2);
    int                     data3(3);
    int                     data4(4);
    int                     data5(5);

    list.append( &data2 );
    list.append( &data3 );
    list.append( &data4 );

    list.insert( &data1 );
    list.append( &data5 );
    cout << "<pointer doubly linked list for int>\n";
    list.forAll( data_ptr_prt, "" );
    data_ptr_prt( list.find( 3 ), "<the fourth element>" );
    data_ptr_prt( list.get( 2 ), "<the third element>" );
    data_ptr_prt( list.get(), "<the first element>" );
    list.clear();
    cout.flush();
}

WCPtrSList<Type>::WCPtrSList()

create a WCPtrSList<Type> object

Synopsis:

#include <wclist.h>
public:
WCPtrSList();
WCPtrSList( void *(*allocator)( size_t ),
         void (*deallocator)( void *, size_t ) );
void WCPtrSList( const WCPtrSList & );

Semantics:

Three forms of the public WCPtrSList<Type> constructor are available:

The first creates an empty WCPtrSList object.
The second form also creates an empty WCPtrSList<Type> object, but allows you to specify the allocator function to perform all memory allocations of the list elements, and the deallocator function to perform all freeing of the list elements' memory.
These functions provide the ability to control how the allocation and freeing of memory is performed, allowing for more efficient memory handling than the general purpose global operator new() and operator delete() can provide. Memory management optimizations may potentially be made through the allocator and deallocator functions, but aren't recommended until you understand memory management, and determine it to be worthwhile.
The allocator function shall return a pointer to allocated memory of size at least the argument, or zero(0) if the allocation can't be performed. Initialization of the memory returned is performed by the WCPtrSList<Type> class.
The WCPtrSList<Type> class calls the deallocator function only on memory allocated by the allocator function. The deallocator shall free the memory pointed to by the first argument, the size of which is given by the second argument. The size passed to the deallocator function is guaranteed to be the same size passed to the allocator function when the memory was allocated.
The allocator and deallocator functions may assume that for a list object instance, the allocator is always called with the same first argument (that is, the size of the memory to be allocated). The WCValSListItemSize(Type)() macro returns the size of the elements that are allocated by the allocator function.
The third form of the public WCPtrSList<Type> constructor is the copy constructor for the singly linked list class. All of the list elements are copied to the new list, as well as the exception trap states, and any registered allocator and deallocator functions.
If all of the elements can't be copied, and the out_of_memory is enabled in the list being copied, the exception is thrown. The new list is created in a valid state, even if all of the list elements can't be copied.

Results:

The public WCPtrSList<Type> constructor produces an WCPtrSList object.

WCPtrSList<Type>::~WCPtrSList()

destroy a WCPtrSList<Type> object

Synopsis:

#include <wclist.h>
public:
~WCPtrSList();

Semantics:

The public WCPtrSList<Type> destructor destroys the WCPtrSList object.

If the list isn't empty and the not_empty exception is enabled, the exception is thrown. If the not_empty exception isn't enabled and the list isn't empty, the list is cleared using the clear() member function.

The call to the public WCPtrSList<Type> destructor is inserted implicitly by the compiler at the point where the WCPtrSList object goes out of scope.

Results:

The WCPtrSList object is destroyed.

WCPtrDList<Type>::WCPtrDList()

create a WCPtrDList<Type> object

Synopsis:

#include <wclist.h>
public:
WCPtrDList();
WCPtrDList( void *(*allocator)( size_t ),
         void (*deallocator)( void *, size_t ) );
WCPtrDList( const WCPtrDList & );

Semantics:

There are three forms of the public WCPtrDList<Type> constructor:

The first form creates an empty WCPtrDList object.
The second form also creates an empty WCPtrDList<Type> object, but allows you to specify the allocator function to perform all memory allocations of the list elements, and the deallocator function to perform all freeing of the list elements' memory.
These functions provide the ability to control how the allocation and freeing of memory is performed, allowing for more efficient memory handling than the general purpose global operator new() and operator delete() can provide. Memory management optimizations may potentially be made through the allocator and deallocator functions, but aren't recommended until you understand memory management, and determine it to be worthwhile.
The allocator function shall return a pointer to allocated memory of at least the size specified by the argument, or zero(0) if the allocation can't be performed. Initialization of the memory returned is performed by the WCPtrDList<Type> class.
The WCPtrDList<Type> class calls the deallocator function only on memory allocated by the allocator function. The deallocator shall free the memory pointed to by the first argument which is of size given by the second argument. The size passed to the deallocator function is guaranteed to be the same size passed to the allocator function when the memory was allocated.
The allocator and deallocator functions may assume that for a list object instance, the allocator is always called with the same first argument (the size of the memory to be allocated). The WCValDListItemSize(Type)() macro returns the size of the elements that are allocated by the allocator function.
The third form of the public WCPtrDList<Type> constructor is the copy constructor for the doubly linked list class. All of the list elements are copied to the new list, as well as the exception trap states, and any registered allocator and deallocator functions.
If all of the elements can't be copied and the out_of_memory is enabled in the list being copied, the exception is thrown. The new list is created in a valid state, even if all of the list elements can't be copied.

Results:

This constructor produces an WCPtrDList object.

WCPtrDList<Type>::~WCPtrDList()

destroy a WCPtrDList<Type> object

Synopsis:

#include <wclist.h>
public:
~WCPtrDList();

Semantics:

The ~WCPtrDList<Type> public member function destroys the WCPtrDList object.

The call to this destructor is inserted implicitly by the compiler at the point where the WCPtrDList object goes out of scope.

Results:

The WCPtrDList object is destroyed.

WCPtrDList<Type>::append(), WCPtrSList<Type>::append()

append an element to the end of the list

Synopsis:

#include <wclist.h>
public:
int append( Type * );

Semantics:

The append() public member function is used to append the data to the end of the list.

If the out_of_memory exception is enabled and the append operation fails, the exception is thrown.

Results:

The data element is appended to the end of the list. A TRUE value (non-zero) is returned if the append is successful. A FALSE (zero) result is returned if the append fails.

WCPtrDList<Type>::clear(), WCPtrSList<Type>::clear()

clear the list object

Synopsis:

#include <wclist.h>
public:
void clear();

Semantics:

Results:

The clear() public member function resets the list object to the state it was in immediately after its initial construction.

WCPtrDList<Type>::clearAndDestroy(), WCPtrSList<Type>::clearAndDestroy()

clear the list object, deleting any elements

Synopsis:

#include <wclist.h>
public:
void clearAndDestroy();

Semantics:

The clearAndDestroy() public member function is used to clear the list object and set it to the state it was in just after its initial construction. The list object isn't destroyed and re-created by this operator, so the object destructor isn't invoked. Before the list object is re-initialized, the the values pointed to by the list elements are deleted.

Results:

The clearAndDestroy() public member function resets the list object to the initial state it was in immediately after its initial construction, and deletes the list elements.

WCPtrDList<Type>::contains(), WCPtrSList<Type>::contains()

determine whether or not an element is in the list

Synopsis:

#include <wclist.h>
public:
int contains( const Type * ) const;

Semantics:

The contains() public member function is used to determine if a list element object is already contained in the list. Each list element is compared to the passed element using Type's operator ==() to determine if the passed element is contained in the list.

The comparison is of the objects themselves, not the pointers to them.

Results:

Zero(0) is returned if the passed list element object isn't found in the list. A non-zero result is returned if the element is found in the list.

WCPtrDList<Type>::entries(), WCPtrSList<Type>::entries()

count the elements in the list

Synopsis:

#include <wclist.h>
public:
int entries() const;

Semantics:

The entries() public member function is used to determine the number of list elements contained in the list object.

Results:

The number of entries stored in the list is returned.

WCPtrDList<Type>::find(), WCPtrSList<Type>::find()

find the element with the given index into the list

Synopsis:

#include <wclist.h>
public:
Type * find( int = 0 ) const;

Semantics:

The find() public member function returns the value of a list element in the list object. The optional parameter specifies which element to locate, and defaults to the first element. Since the index of the first element of the list is zero, the index of the last element is the number of list entries minus one.

Results:

The value of the selected list element or the closest element is returned. If the index value is negative, the closest list element is the first element. The last element is the closest element if the index value is greater than the number of list entries minus one. An uninitialized pointer is returned if there are no elements in the list.

WCPtrDList<Type>::findLast(), WCPtrSList<Type>::findLast()

find the last element in the list

Synopsis:

#include <wclist.h>
public:
Type * findLast() const;

Semantics:

The findLast() public member function returns the value of the last list element in the list object.

If the list is empty, one of two exceptions can be thrown:

If the empty_container exception is enabled, it's thrown.
The index_range exception is thrown if it's enabled and the empty_container exception isn't.

Results:

The value of the last list element is returned. An uninitialized pointer is returned if there are no elements in the list.

WCPtrDList<Type>::forAll(), WCPtrSList<Type>::forAll()

invoke a function for each element in the list

Synopsis:

#include <wclist.h>
public:
void forAll( void (*fn)( Type *, void * ), 
             void *) const;

Semantics:

The forAll() public member function is used to cause the function fn to be invoked for each list element. The fn function should have the prototype

    void (*fn)( Type *, void * )

The first parameter of fn shall accept the value of the currently active list element. The second argument passed to fn is the second argument of the forAll() function. This allows a callback function to be defined that can accept data appropriate for the point at which the forAll() function is invoked.

WCPtrDList<Type>::get(), WCPtrSList<Type>::get()

get an element, removing it from the list

Synopsis:

#include <wclist.h>
public:
Type * get( int = 0 );

Semantics:

The get() public member function returns the value of an element in the list object, removing the element from the list. The optional parameter specifies which element to remove, and defaults to the first element. Since the index of the first element of the list is zero, the index of the last element is the number of list entries minus one.

Results:

The value of the selected list element or the closest element is removed and returned. If the index value is negative, the closest list element is the first element. The last element is the closest element if the index value is greater than the number of list entries minus one. An uninitialized pointer is returned if there are no elements in the list.

WCPtrDList<Type>::index(), WCPtrSList<Type>::index()

find the index for a list element

Synopsis:

#include <wclist.h>
public:
int index( const Type * ) const;

Semantics:

The index() public member function is used to determine the index of the first list element equivalent to the passed element. Each list element is compared to the passed element using Type's operator ==() until the passed element is found, or all list elements have been checked.

The comparison is of the objects themselves, not the pointers to them.

Results:

The index of the first element equivalent to the passed element is returned. If the passed element isn't in the list, negative one (-1) is returned.

WCPtrDList<Type>::insert(), WCPtrSList<Type>::insert()

add an element to the beginning of the list

Synopsis:

#include <wclist.h>
public:
int insert( Type * );

Semantics:

The insert() public member function is used to insert the data as the first element of the list.

If the insertion fails, and the out_of_memory exception is enabled, it's thrown.

Results:

The data element is inserted at the beginning of the list. A TRUE value (non-zero) is returned if the insertion is successful, FALSE (zero) if it fails.

WCPtrDList<Type>::isEmpty(), WCPtrSList<Type>::isEmpty()

determine whether or not the list is empty

Synopsis:

#include <wclist.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if a list object has any list elements in it.

Results:

A TRUE value (non-zero) is returned if the list object doesn't have any list elements in it. A FALSE (zero) result is returned if the list contains at least one element.

WCPtrDList<Type>::operator =(), WCPtrSList<Type>::operator =()

assign a value to a list

Synopsis:

#include <wclist.h>
public
WCPtrSList & WCPtrSList::operator =( 
    const WCPtrSList & );
WCPtrDList & WCPtrDList::operator =( 
    const WCPtrDList & );

Semantics:

The operator =() public member function is the assignment operator for the class. The left hand side of the assignment is first cleared with the clear() member function. All elements in the right hand side list are then copied, as well as the exception trap states, and any registered allocator and deallocator functions.

If all of the elements can't be copied and the out_of_memory is enabled in the right hand side list, the exception is thrown. The new list is created in a valid state, even if all of the list elements can't be copied.

Results:

The operator =() public member function assigns the right hand side to the left hand side, and returns a reference to the left hand side.

WCPtrDList<Type>::operator ==(), WCPtrSList<Type>::operator ==()

determine whether or not two lists are equivalent

Synopsis:

#include <wclist.h>
public:
int WCPtrSList::operator ==( 
        const WCPtrSList & ) const;
int WCPtrDList::operator ==( 
        const WCPtrDList & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCPtrDList<Type> and WCPtrSList<Type> classes. Two list objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side object and the right hand side objects are the same object. A FALSE (zero) value is returned otherwise.

WCSLink Class

Declared:

wclcom.h

Derived from:

WCDLink

The WCSLink class is the building block for all of the list classes. It provides the link that's used to traverse the list elements. The doubly link classes use the WCSLink class to implement both links. Since no user data is stored directly with it, the WCSLink class should only be used as a base class to derive a user-defined class.

When creating a singly linked intrusive list, the WCSLink class is used to derive the user-defined class that holds the data to be inserted into the list.

The wclcom.h header file is included by the wclist.h header file. There's no need to include the wclcom.h header file explicitly, unless the wclist.h header file isn't included. No errors result if it's included unnecessarily.

The destructor is non-virtual, so that list elements are of minimum size. Objects created as a class derived from the WCSLink class, but destroyed while typed as a WCSLink object won't invoke the destructor of the derived class.

Public Member Functions

The following public member functions are declared:

WCSLink();
~WCSLink();

WCSLink::WCSLink()

create a WCSLink object

Synopsis:

#include <wclcom.h>
public:
WCSLink();

Semantics:

The public WCSLink constructor creates an WCSLink object. It's used implicitly by the compiler when it generates a constructor for a derived class.

Results:

The public WCSLink constructor produces an initialized WCSLink object.

WCSLink::~WCSLink()

destroy a WCSLink object

Synopsis:

#include <wclcom.h>
public:
~WCSLink();

Semantics:

The public WCSLink destructor doesn't do anything explicit. The call to it is inserted implicitly by the compiler at the point where the object derived from WCSLink goes out of scope.

Results:

The object derived from WCSLink is destroyed.

WCValDList<Type> and WCValSList<Type> Classes

Declared:

wclist.h

The WCValDList<Type> and WCValSList<Type> classes are the templated classes used to create objects that are singly or doubly linked lists. Values are copied into the list, which could be undesirable if the stored objects are complicated and copying is expensive. Value lists shouldn't be used to store objects of a base class if any derived types of different sizes would be stored in the list, or if the destructor for a derived class must be called.

In the description of each member function, the text Type is used to indicate the type value specified as the template parameter. Type is the type of the values stored in the list.

The WCExcept class is a base class of the WCValDList<Type> and WCValSList<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCValDList<Type> and WCValSList<Type> objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCValDList<Type> and WCValSList<Type> classes require Type to have:

A default constructor
```
    Type::Type()
    
```
A well defined copy constructor
```
    Type::Type( const Type & )
    
```

An equivalence operator with constant parameters

    Type::operator ==( const Type & ) const

Public Member Functions

The following member functions are declared in the public interface:

WCValSList();
WCValSList( void * (*)( size_t ), void (*)( void *, size_t ));
WCValSList( const WCValSList & );
~WCValSList();

WCValDList();
WCValDList( void * (*)( size_t ), void (*)( void *, size_t ));
WCValDList( const WCValDList & );
~WCValDList();

int append( const Type & );
void clear();
void clearAndDestroy();
int contains( const Type & ) const;
int entries() const;
Type find( int = 0 ) const;
Type findLast() const;
void forAll( void (*)( Type, void * ), void *) const;
Type get( int = 0 );
int index( const Type & ) const;
int insert( const Type & );
int isEmpty() const;

Public Member Operators

The following member operators are declared in the public interface:

WCValSList & WCValSList::operator =( const WCValSList & );
WCValDList & WCValDList::operator =( const WCValDList & );
int WCValSList::operator ==( const WCValSList & ) const;
int WCValDList::operator ==( const WCValDList & ) const;

Sample Program Using a Value List

#include <wclist.h>
#include <iostream.h>

static void test1( void );

void data_val_prt( int data, void * str ) {
    cout << (char *)str << "[" << data << "]\n";
}

void main() {
    try {
        test1();
    } catch( ... ) {
        cout << "we caught an unexpected exception\n";
    }
    cout.flush();
}

void test1 ( void ) {
    WCValDList<int>         list;

    list.append( 2 );
    list.append( 3 );
    list.append( 4 );

    list.insert( 1 );
    list.append( 5 );
    cout << "<value doubly linked list for int>\n";
    list.forAll( data_val_prt, "" );
    data_val_prt( list.find( 3 ), "<the fourth element>" );
    data_val_prt( list.get( 2 ), "<the third element>" );
    data_val_prt( list.get(), "<the first element>" );
    list.clear();
    cout.flush();
}

WCValSList<Type>::WCValSList()

create a WCValSList<Type> object

Synopsis:

#include <wclist.h>
public:
WCValSList();
WCValSList( void *(*allocator)( size_t ),
            void (*deallocator)( void *, 
                                 size_t ) );
void WCValSList( const WCValSList & );

Semantics:

There are three forms of the public WCValSList<Type> constructor:

The first form creates an empty WCValSList object.
The second form also creates an empty WCValSList<Type> object, but allows you to specify the allocator function to perform all memory allocations of the list elements, and the deallocator function to perform all freeing of the list elements' memory.
These functions provide the ability to control how the allocation and freeing of memory is performed, allowing for more efficient memory handling than the general purpose global operator new() and operator delete() can provide. Memory management optimizations may potentially be made through the allocator and deallocator functions, but aren't recommended until you understand memory management, and determine it to be worthwhile.
The allocator function shall return a pointer to allocated memory of at least the size at specified by the argument, or zero(0) if the allocation can't be performed. Initialization of the memory returned is performed by the WCValSList<Type> class.
The WCValSList<Type> class calls the deallocator function only on memory allocated by the allocator function. The deallocator shall free the memory pointed to by the first argument the size of which is given by the second argument. The size passed to the deallocator function is guaranteed to be the same size passed to the allocator function when the memory was allocated.
The allocator and deallocator functions may assume that for a list object instance, the allocator is always called with the same first argument (the size of the memory to be allocated). The WCValSListItemSize(Type)() macro returns the size of the elements that are allocated by the allocator function.
The third form of the public WCValSList<Type> constructor is the copy constructor for the singly linked list class. All of the list elements are copied to the new list, as well as the exception trap states, and any registered allocator and deallocator functions. Type's copy constructor is invoked to copy the values contained by the list elements.
If all of the elements can't be copied, and the out_of_memory is enabled in the list being copied, the exception is thrown. The new list is created in a valid state, even if all of the list elements can't be copied.

Results:

The public WCValSList<Type> constructor produces a WCValSList object.

WCValSList<Type>::~WCValSList()

destroy a WCValSList<Type> object

Synopsis:

#include <wclist.h>
public:
~WCValSList();

Semantics:

The public WCValSList<Type> destructor destroys the WCValSList object.

The call to the public WCValSList<Type> destructor is inserted implicitly by the compiler at the point where the WCValSList object goes out of scope.

Results:

The WCValSList object is destroyed.

WCValDList<Type>::WCValDList()

create a WCValDList<Type> object

Synopsis:

#include <wclist.h>
public:
WCValDList();
WCValDList( void *(*allocator)( size_t ),
         void (*deallocator)( void *, size_t ) );
WCValDList( const WCValDList & );

Semantics:

There are three forms of the public WCValDList<Type> constructor:

The first form creates an empty WCValDList object.
The second form also creates an empty WCValDList<Type> object, but allows you to specify the allocator function to perform all memory allocations of the list elements, and the deallocator function to perform all freeing of the list elements' memory.
These functions provide the ability to control how the allocation and freeing of memory is performed, allowing for more efficient memory handling than the general purpose global operator new() and operator delete() can provide. Memory management optimizations may potentially be made through the allocator and deallocator functions, but aren't recommended until you understand memory management, and determine it to be worthwhile.
The allocator function shall return a pointer to allocated memory of at least the size given by the argument, or zero(0) if the allocation can't be performed. Initialization of the memory returned is performed by the WCValDList<Type> class.
The WCValDList<Type> class calls the deallocator function only on memory allocated by the allocator function. The deallocator shall free the memory pointed to by the first argument which is of the size given by the second argument. The size passed to the deallocator function is guaranteed to be the same size passed to the allocator function when the memory was allocated.
The allocator and deallocator functions may assume that for a list object instance, the allocator is always called with the same first argument (that is, the size of the memory to be allocated). The WCValDListItemSize(Type)() macro returns the size of the elements that are allocated by the allocator function.
The third form of the public WCValDList<Type> constructor is the copy constructor for the doubly linked list class. All of the list elements are copied to the new list, as well as the exception trap states, and any registered allocator and deallocator functions. Type's copy constructor is invoked to copy the values contained by the list elements.
If all of the elements can't be copied and the out_of_memory exception is enabled in the list being copied, the exception is thrown. The new list is created in a valid state, even if all of the list elements can't be copied.

Results:

The public WCValDList<Type> constructor produces a WCValDList object.

WCValDList<Type>::~WCValDList()

destroy a WCValDList<Type> object

Synopsis:

#include <wclist.h>
public:
~WCValDList();

Semantics:

The public WCValDList<Type> destructor destroys the WCValDList object.

The call to the public WCValDList<Type> destructor is inserted implicitly by the compiler at the point where the WCValDList object goes out of scope.

Results:

The WCValDList object is destroyed.

WCValDList<Type>::append(), WCValSList<Type>::append()

append an element to the end of the list

Synopsis:

#include <wclist.h>
public:
int append( const Type & );

Semantics:

The append() public member function is used to append the data to the end of the list. The data stored in the list is a copy of the data passed as a parameter.

If the append fails, and the out_of_memory exception is enabled, the exception is thrown.

Results:

The data element is appended to the end of the list. A TRUE value (non-zero) is returned if the append is successful; FALSE (zero) is returned if it fails.

WCValDList<Type>::clear(), WCValSList<Type>::clear()

clear the list object

Synopsis:

#include <wclist.h>
public:
void clear();

Semantics:

The clear() public member function has the same sematics as the clearAndDestroy() member function.

Results:

The clear() public member function resets the list object to the state it was in immediately after its initial construction.

WCValDList<Type>::clearAndDestroy(), WCValSList<Type>::clearAndDestroy()

clear the list object

Synopsis:

#include <wclist.h>
public:
void clearAndDestroy();

Semantics:

Before the list object is re-initialized, the delete operator is called for each list element.

Results:

The clearAndDestroy() public member function resets the list object to the state it was in immediately after its initial construction.

WCValDList<Type>::contains(), WCValSList<Type>::contains()

determine whether or not a given element is in the list

Synopsis:

#include <wclist.h>
public:
int contains( const Type & ) const;

Semantics:

Results:

Zero(0) is returned if the passed list element object isn't found in the list. A non-zero result is returned if the element is found in the list.

WCValDList<Type>::entries(), WCValSList<Type>::entries()

count the entries in the list

Synopsis:

#include <wclist.h>
public:
int entries() const;

Semantics:

The entries() public member function is used to determine the number of list elements contained in the list object.

Results:

The number of entries stored in the list is returned.

WCValDList<Type>::find(), WCValSList<Type>::find()

find an element in the list

Synopsis:

#include <wclist.h>
public:
Type find( int = 0 ) const;

Semantics:

If the list is empty, and the empty_container exception is enabled, the exception is thrown. If the index_range exception is enabled, the exception is thrown if the index value is negative or is greater than the number of list entries minus one.

Results:

The value of the selected list element or the closest element is returned. If the index value is negative, the closest list element is the first element. The last element is the closest element if the index value is greater than the number of list entries minus one. A default initialized value is returned if there are no elements in the list.

WCValDList<Type>::findLast(), WCValSList<Type>::findLast()

find the last element in the list

Synopsis:

#include <wclist.h>
public:
Type findLast() const;

Semantics:

The findLast() public member function returns the value of the last list element in the list object.

If the list is empty, one of two exceptions can be thrown:

If the empty_container exception is enabled, it's thrown.
The index_range exception is thrown if it's enabled and the empty_container exception isn't.

Results:

The value of the last list element is returned. A default initialized value is returned if there are no elements in the list.

WCValDList<Type>::forAll(), WCValSList<Type>::forAll()

invoke a function for each element in the list

Synopsis:

#include <wclist.h>
public:
void forAll( void (*fn)( Type, void * ), 
             void *) const;

Semantics:

The forAll() public member function is used to cause the function fn to be invoked for each list element. The fn function should have the prototype:

    void (*fn)( Type, void * )

WCValDList<Type>::get(), WCValSList<Type>::get()

get a list element, removing it from the list

Synopsis:

#include <wclist.h>
public:
Type get( int = 0 );

Semantics:

Results:

The value of the selected list element or the closest element is removed and returned. If the index value is negative, the closest list element is the first element. The last element is the closest element if the index value is greater than the number of list entries minus one. A default initialized value is returned if there are no elements in the list.

WCValDList<Type>::index(), WCValSList<Type>::index()

determine the index of a given element

Synopsis:

#include <wclist.h>
public:
int index( const Type & ) const;

Semantics:

Results:

The index of the first element equivalent to the passed element is returned. If the passed element isn't in the list, negative one (-1) is returned.

WCValDList<Type>::insert(), WCValSList<Type>::insert()

insert an element at the beginning of the list

Synopsis:

#include <wclist.h>
public:
int insert( const Type & );

Semantics:

The insert() public member function is used to insert the data as the first element of the list. The data stored in the list is a copy of the data passed as a parameter.

If the out_of_memory exception is enabled, and the insertion fails, the exception is thrown.

Results:

The data element is inserted at the beginning of the list. A TRUE value (non-zero) is returned if the insert is successful. A FALSE (zero) result is returned if the insert fails.

WCValDList<Type>::isEmpty(), WCValSList<Type>::isEmpty()

determine whether or not the list is empty

Synopsis:

#include <wclist.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if a list object has any list elements in it.

Results:

A TRUE value (non-zero) is returned if the list object doesn't have any list elements in it. A FALSE (zero) result is returned if the list contains at least one element.

WCValDList<Type>::operator =(), WCValSList<Type>::operator =()

assign the value of one list to another

Synopsis:

#include <wclist.h>
public
WCValSList & WCValSList::operator =( 
    const WCValSList & );
WCValDList & WCValDList::operator =( 
    const WCValDList & );

Semantics:

Results:

The operator =() public member function assigns the right hand side to the left hand side, and returns a reference to the left hand side.

WCValDList<Type>::operator ==(), WCValSList<Type>::operator ==()

determine whether or not two lists are equivalent

Synopsis:

#include <wclist.h>
public:
int WCValSList::operator ==( 
    const WCValSList & ) const;
int WCValDList::operator ==( 
    const WCValDList & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCValDList<Type> and WCValSList<Type> classes. Two list objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side object and the right hand side objects are the same object. A FALSE (zero) value is returned otherwise.

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

Synopsis:

Semantics:

Results:

See also:

Synopsis: