Lecture Notes for SE 598, Data Structures and Algorithms

5 July 2000 - STL Lists

1. behavior

   1. lists are a sequential data type, but not like arrays, vectors, or dequeues

      1. lists do not have indexed access - no [] or at()

      2. lists do have arbitrary, efficient insert and delete

      3. lists have restricted iterators - bidirectional; no jumping

2. a list is a template class

   1. with template <class T, class Allocator = allocator>

3. list constructors

   1. the default constructor - list<T> l;

   2. the size and value constructor - list<T> l(n, v);

   3. the copy constructor - list<customer> line2(line1);

   4. the segment-copy constructor - list(start, end);

4. reading and writing values - no indexing via [] or at()

   1. iterator access only - front() and back()

5. growing and shrinking Lists

   1. size() and max_size() member functions

   2. no reserve() and capacity() member functions

   3. d.push_back(v), d.pop_back(), d.push_front(v), and d.pop_front() member functions

   4. insert(v) and erase()

      1. insert(i, v)

         1. insert the value v immediately before (just to the left of) the value referenced by the iterator i

         2. return an iterator to v

      2. insert(i, n, v)

         1. insert n copies of the value v immediately before (just to the left of) the value referenced by the iterator i

         2. return nothing

      3. insert(i, start, end)

         1. insert the values denoted by the iterator range start,end immediately before the value referenced by the iterator i

         2. return nothing

      4. erase(i) - delete the value referenced by the iterator i

      5. erase(s, e) - delete the values denoted by the iterator range s,e

   5. splicing - another form of insertion; lists only

      1. l1.splice(i, l2)

         1. insert the elements from list l2 immediately before the list l1 value referenced by iterator i

         2. l2 is empty after the splice - the elements are moved

         3. l1 and l2 must be different

      2. l1.splice(i1, l2, i2)

         1. insert the l2 value referenced by the iterator i2 immediately before the list l1 value referenced by iterator i1

         2. the value referenced by i2 is deleted from l2.

         3. l1 and l2 need not be different

      3. l1.splice(i1, l2, 2, e)

         1. insert the l2 values referenced by the iterator range (s, e) i2 immediately before the list l1 value referenced by iterator i1

         2. the values referenced by (s, e) are deleted from l2.

         3. l1 and l2 need not be different, but the iterator range may not contain i1

   6. l.remove(v) - delete from l all values equal to v; lists only

6. list relation operators - equality and less-than

7. iterators

   1. the usual types

   2. list iterators are bidirectional iterators

      1. no jumping around via +, -, +=, or -=

      2. no distance measurement via -

      3. no relations other than equality

      4. some generic algorithms don't work on lists - sorting

   3. the usual member functions

8. other member functions - make up for the loss of generic algorithms; have more efficient implementations

   1. l.sort() - sort l

   2. l.sort(c) - sort l using the comparison c

   3. unique() - replace consecutive runs of a value with one copy of the value

   4. unique(p) - replace consecutive runs with a single value using p to determine when adjacent values are equal

   5. l1.merge(l2), l1.merge(l2, c) - merge l2 into l1, using c; l2 is empty after

This page last modified on 4 July 2000.