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:

operator=
T( const T&)
operator== defining an equivalence relation on T

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

An empty List has no elements.
A non-empty List has a first element and a last element.
For a List with one element, the first and last elements are identical.
A position designates the conceptual "space" between two elements.
A position may therefore have an element to its right and an element to its left.
Sometimes there is no element to the right or left of a given position.
In particular, the beginning of a List is the position with no element to the left and the end of a List is the position with no element to the right.
Note that for the empty List, the beginning and end designate the same position.
Every List may have iterators attached to it. Each iterator when attached to a List has an associated current position in the List. Many iterator operations that examine or modify List elements are specified with respect to the current position.
Different iterators represent different current positions in a List. When one iterator modifies List elements, the current position of other iterators is automatically updated.
With respect to the current position of an iterator, the element to the right (when it exists) is the next element, and the element to the left (when it exists) is the previous element.
Finally, each element has a nonnegative sequential index which starts at zero for the first element.

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:

While certain List<T>, Const_listiter<T>, and Listiter<T> operations return pointers to elements, the corresponding List_of_p<T>, Const_list_of_piter<T>, and List_of_piter<T> operations return the elements themselves; that is, they return T*, not T**, as might be expected.
List_of_p<T> elements are automatically dereferenced by the stream insertion operator.

References

Set(C++),