next up previous contents
Next: 3.4 Generators Up: 3 Primitive Data Structures Previous: 3.2 Sequences

3.3 Lists and Tuples

 

The most commonly used collections are L ist and T uple; you may also encounter B ag, O rdered_Bag and M ap (which is not derived from Collection ), although no public functions return these types.

List s are sequences with access time for the element. They add the following operations to those of class Sequence :

template<class T> class List : public Sequence<T> {
public:
         int length() const;
         int empty() const;

           T &front();

// insertion/deletion on a list invalidates any iterators
// that are on/after the element added/removed

           T remove_front();       
        void prepend(const T &item);
        void append(const T &item);
        void ins_after(List_Iterator<T> i, const T &item);
        void del_front();
        void del_after(List_Iterator<T> i);
        void clear();

        void join(List<T> &consumed);
};

Tuples are essentially re-sizable arrays: they provide time access to elements. They provide bounds checking.

template <class T> class Tuple : public Sequence<T> {  
public:
    Tuple<T>& operator=(const Tuple<T>&);

    int length() const;
    int  empty() const;

    void delete_last(); 
    void append(const Tuple<T> &);
    void append(const T &);
    void join(Tuple<T> &consumed);
    void clear();
};

These classes have associated iterator classes: List_Iterator

and Tuple_Iterator , which can be initialized with a List or Tuple to be iterated over, allowing iteration without the overhead of heap allocation that is incurred when we use the more general new_iterator or any_iterator functions:

        int sum(List<int> &l)
            {
            int s = 0;

            for (List_Iterator<int> i = l; i; i++)
                s += *i;

            return s;
            }



omega@cs.umd.edu