DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 

List(C++)


List, List_of_p -- parameterized variable-length sequences

Synopsis

   #include <List.h>
   #include <Listio.h>
   namespace SCO_SC {
   

template <class T> class List { public:

// Constructors, destructor List( ); List(const T& t1); List(const T& t1,const T& t2); List(const T& t1,const T& t2,const T& t3); List(const T& t1,const T& t2,const T& t3, const T& t4); ~List( );

// Copy and assign List(const List<T>& x); List<T>& operator=(const List<T>& x);

// Length int length( )const; operator void*( ) const;

// Relations int operator==(const List<T>& x)const; int operator!=(const List<T>& x)const;

// Concatenation List<T> operator+(const T& t); List<T> operator+(const List<T>& x);

// Queue operations T* head( )const; T* tail( )const; List<T>& put(const T& t); List<T>& put(const List<T>& x); T unput( ); int unput(T& t); T get( ); int get(T& t); List<T>& unget(const T& t); List<T>& unget(const List<T>& x);

// Array operations T& operator[ ](unsigned i); const T& operator[](unsigned i) const; // Sort void sort(int (*f)(const T&, const T&); };

// Stream insertion template <class T> ostream& operator<<(ostream& os, const List<T>& x); template <class T> class Const_listiter { public:

// Constructors, destructor Const_listiter(const List<T>& x); ~Const_listiter( ); // Copy and assign Const_listiter(const Const_listiter<T>& it); Const_listiter<T>& operator=( const Const_listiter<T>& it);

// Relations int operator==(const Const_listiter<T>& it) const; int operator!=(const Const_listiter<T>& it) const;

// Check the attachment const List<T>* the_list( );

// Current element int at_head( ) const; int at_end( ) const; ~Listiter( );

// Copy and assign Listiter(const Listiter<T>& it); Listiter<T>& operator=( const Listiter<T>& it);

// Relations int operator==(const Listiter<T>& it)const; int operator!=(const Listiter<T>& it)const;

// Check the attachment List<T>* the_list( );

// Inherited Const_listiter operations Current element Changing current position Examining next and previous elements

// Changing next and previous elements void insert_next(const T& t); void insert_prev(const T& t); int replace_next(const T& t); int replace_prev(const T& t); int remove_next( ); int remove_prev( ); int remove_next(T& t); int remove_prev(T& t); };

typedef voidP void*; template <class T> class List_of_p : public List<voidP>{...}; template <class T> class Const_list_of_piter : public Listiter<voidP>{...}; template <class T> class List_of_piter : public Const_list_of_piter<voidP>{...}; template <class T> ostream& operator<<(ostream& os, const List_of_p<T>& x); template <class T> ostream& operator<<(ostream& os, const List_of_p<T>* x); }

Description

A List<T> is a variable-length sequence whose elements are objects type T. T can be any type having:

A List_of_p<T>, also known as a pointer list, is a sequence whose elements are uninterpreted pointers to objects of type T; that is, the objects pointed to are not involved in pointer list operations. For example, if an object pointed to by a pointer list element is deleted, the pointer list operations will continue to function as if nothing had happened. List_of_p<T> offers a more efficient implementation of pointer lists than List<T> when T is a pointer type. Each of these two classes has a companion iterator class, whose instances may be used for iterating over elements.

The following notions are needed to explain the behavior of Lists ("List" in normal font can mean either List<T> or List_of_p<T>).

List<T>

Constructors, destructor

List();

List(const T& t1);

List(const T& t1,const T& t2);

List(const T& t1,const T& t2,const T& t3);

List(const T& t1,const T& t2,const T& t3, const T& t4); Constructors for Lists of zero, one, two, three, or four elements, respectively. The current position is at the beginning of the List. Runs in O(1).

~List(); Destructor. All iterators currently attached to this List will be informed that this List has been destroyed (see Listiter(T)::the_list()). Runs in O(max(length(), #iterators)).

Copy and assign

Copying or assigning a List<T> creates a copy of its value.

List(const List<T>& x); Copy constructor. The current position is the same as that of x. Runs in O(x.length()).

List<T>& operator=(const List<T>& x); Assignment. All iterators currently attached to the List will be reset to the beginning of the List. Runs in O(length()+x.length()).

Length

int length()const; The number of elements. Runs in O(1).

operator void*()const; Returns zero if and only if the List is empty. Most useful as an implicit conversion in contexts like while(x). Runs in O(1).

Relations

int operator==(const List<T>& x)const;

int operator!=(const List<T>& x)const; The usual equality and inequality relations. Only the elements (not the current positions) are compared. Runs in O(min(length(),x.length())).

Concatenation

List<T> operator+(const T& t); Returns a List consisting of the elements of this List followed by the single element t. Runs in O(length()).

List<T> operator+(const List<T>& x); Returns a List containing a copy of the elements in this List followed by a copy of the elements in x. Runs in O(length()+x.length()).

Queue operations

These operations manipulate the List as a double-ended queue (that is, they access the ends of the List but not the middle).

T* head()const; Returns the pointer to the first element. Runs in O(1). Zero will be returned if the List is empty.

T* tail()const; Returns the pointer to the last element. Runs in O(1). Zero will be returned if the List is empty.

List<T>& put(const T& t); Makes t the last element. Does not affect the current position. Runs in O(1).

List<T>& put(const List<T>& x); Appends the elements of x to the end of the List. Does not affect the current position. Runs in O(x.length()).

T unput(); Removes and returns the last element. If the current position is at the end of the List, it is decremented; otherwise, the current position remains unchanged. Updates all iterators currently attached to this List. Runs in O(#iterators). Preconditions: The List is not empty.

int unput(T& t); Attempts to remove the last element and returns non-zero if the removal succeeded. If the removal succeeded, the removed element is assigned to t. If the removal failed, the value of t is undefined. If the current position is at the end of the List, it is decremented by 1; otherwise, the current position is unchanged. Updates all iterators currently attached to this List. Runs in O(#iterators).

T get(); Removes and returns the first element. If the current position is at the beginning of the List, it remains unchanged; otherwise, the current position is decremented by 1. Updates all iterators currently attached to this List. Runs in O(#iterators). Preconditions: The List is not empty.

int get(T& t); Attempts to remove the first element and returns non-zero if the removal succeeded. If the removal succeeded, the first element is assigned to t. If the removal failed, the value of t is undefined. If the current position is at the beginning of the List, it remains unchanged; otherwise, the current position is decremented by 1. Updates all iterators currently attached to this List. Runs in O(#iterators).

List<T>& unget(const T& t); Makes t the first element of the List. Increments the current position by 1. Updates all iterators currently attached to the List. Runs in O(#iterators).

List<T>& unget(const List<T>& x); Prepends the elements of x to this List. Increments the current position by x.length(). Updates all iterators currently attached to this List. Runs in O(#iterators).

Array operations

These operations manipulate Lists as if they were randomly accessible arrays.

T& operator[](unsigned i); Returns a reference to the element with index i. Runs in O(length()). Preconditions: i is a valid index in this List.

const T& operator[](unsigned i) const; Returns a const reference to the element with index i. Same performance and preconditions as the regular operator[]. This operator can work on constant lists.

Sort

void sort(int (*f)(const T&,const T&)); Sorts the List in place using a user-defined "less than" function f to define a total order relation on T. This function is expected to return a nonzero integer if its first argument is less than its second, and 0 otherwise. Resets the current position and the position of all iterators to the beginning of the List. Runs in O(NlnN), where N=length().

Stream insertion

ostream& operator<<(ostream& os,const List<T>& x); Inserts an ASCII representation of x into os. Runs in O(x.length()).

Const_listiter<T>, Listiter<T>

For certain List applications, a single current position is inadequate (think of trying to reverse a List in place). To keep track of additional positions, one or more iterators may be created. Any number of iterators may be attached to the same List concurrently, and each keeps track of a single position in that List.

Const_listiter provides all the operations of Listiter except for those that change the List to which the iterator is attached. It can be used to iterate over a constant List.

The behavior of all iterator operations except the_list() is undefined when the List to which the iterator is attached ceases to exist.

Constructors, destructor

Listiter(const List<T>& x); Creates an iterator attached to List x whose position is at the beginning of x. Runs in O(1).

~Listiter(); Destructor. Runs in O(#iterators).

Copy and assign

Copying or assigning a Listiter creates a copy of its value.

Listiter(const Listiter<T>& it); Copy constructor. Runs in O(1).

Listiter(T)& operator=(const Listiter<T>& it); Assignment. Runs in O(#iterators).

Relations

int operator==(const Listiter<T>& it)const;

int operator!=(const Listiter<T>& it)const; Equality and inequality. Two iterators are equal if (1) they are both attached to the same List and (2) they both have the same position within that List. Runs in O(1).

Check the attachment

List<T>* the_list(); Returns a pointer to the List to which this iterator is attached, or 0 if there is no such List (this can happen if the List is destroyed).

List operation analogues

For each List<T> operation that is defined with respect to the current position, Listiter<T> has an operation with identical syntax. The semantics of these operations differ in that iterator operations are defined with respect to the iterator's own private position, rather than the List's current position The effect of a change made through an iterator is well-defined with respect to the List and all other iterators currently attached to the List. Runs in O(1).

Current element

int at_head()const;

int at_end()const; Returns non-zero if the current position is at the beginning (end) of the List. Runs in O(1).

int position()const; Returns the index of the next element. Runs in O(1).

Changing current position

void reset(unsigned i = 0); Moves the current position to the left of the element with index i. If i>=length(), the current position is moved to the end of the List. Runs in O(length()).

void end_reset(unsigned i = 0); Moves the current position to the left of the element with index length()-i. If i>=length(), the current position is moved to the beginning of the List. Runs in O(length()).

int find_next(const T& t); Scans rightward from the current position until either (1) an element with the value t is found, or (2) the end of the List is reached. Returns non-zero if the search succeeded. If the search fails, the current position remains unchanged. If the search succeeds, the current position is changed so that it is immediately to the left of the element; that is, the element will be the next element. Note that if the next element has the value t, the search will succeed but the current position will remain unchanged. Runs in O(the_list().length()).

int find_prev(const T& t); Like find_next(const T& t), except that the scan moves leftward from the current position. Note that if the previous element has the value t, the search will succeed but the current position will remain unchanged. Runs in O(the_list().length()).

int step_next();

int step_prev(); Increments (decrements) the current position. Has no effect if the current position cannot be incremented (decremented). Returns non-zero if the current position changed. Runs in O(1).

Examining next and previous elements

int peek_next(T& t)const;

int peek_prev(T& t)const; Assigns the value of the next (previous) element to t. The value of t is undefined if there is no next (previous) element. Returns non-zero if the value of t is defined. Does not affect the current position. Runs in O(1).

int peek_next(T*& p);

int peek_prev(T*& p); Assigns a pointer to the next (previous) element to p. The value of p is undefined if there is no next (previous) element. Returns non-zero if the value of p is defined. Does not affect the current position. Runs in O(1).

T* peek_next()const;

T* peek_prev()const; Returns the value of the next (previous) element, without affecting the current position. Runs in O(1). Preconditions: There is a next (previous) element.

int next(T& t);

int prev(T& t); Like int peek_next(T& t) (int peek_prev(T& t)) except that the current position is moved to the right (left) by one element. Runs in O(1).

int next(T*& p);

int prev(T*& p); Like peek_next(T*& p) (peek_prev(T*& p)) except that the current position is moved to the right (left) by one element. Runs in O(1).

T* next();

T* prev(); Like peek_next() (peek_prev()) except that the current position is moved to the right (left) by one element.

Changing next and previous elements

void insert_next(const T& t);

void insert_prev(const T& t); Inserts t to the right (left) of the current position. Updates all iterators currently attached to this List. Runs in O(#iterators).

int replace_next(const T& t);

int replace_prev(const T& t); Replaces the next (previous) element by t. Has no effect if the element to be replaced does not exist. Returns non-zero if replacement occurred. Runs in O(1).

int remove_next();

int remove_prev(); Attempts to remove the next (previous) element and returns non-zero if removal occurred. Updates all iterators currently attached to this List. Runs in O(#iterators).

int remove_next(T& t);

int remove_prev(T& t); Like remove_next() (remove_prev()) except that the removed value is assigned to t. Runs in O(#iterators).

List_of_p<T>, Const_list_of_piter<T>, List_of_piter<T>

The above description holds, mutatis mutandis, for List_of_p<T>, Const_list_of_piter<T>, and List_of_piter<T>, with the following exceptions:

References

Set(C++),
© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 - 01 June 2005