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

Web Accessibility