Review: Copying Files

Linked Lists

Problem

In some situations random insertion in and removal from a sequence is more common than random access. These operations are very inefficient for vectors.

Solution

Unlike arrays, structs, and vectors; linked lists decouple physical and logical order. The data in a linked list are not stored in consecutive memory locations. Instead, a linked list is a collection of cells or nodes. Each cell contains a single data item, plus pointers to its logical neighbors. Here's how the sequence ( 22 32 42 52 ) is represented as a doubly linked lists:

There are other styles of linked lists including singly linked lists, circularly linked lists, lists with header nodes, and sorted linked lists (these are useful for priority queues).

Static Structure

Our implementation provides iterators and allocators:

Implementation

We'll try to reverse engineer STL lists as much as possible (and/or desirable). Here's the general structure of list.h:

#ifndef LIST_H
#define LIST_H

#include <stdexcept>
using namespace std;
#include "alloc.h"

// etc.

#endif

Magic Memory Idiom: Allocators (alloc.h)

An allocator encapsulates a heap and provides methods for allocating and deallocating items from the heap. Allocators are only needed if the system heap (allocator<Type>) is unsatisfactory for a particular application. For example, a custom allocator might use a best-fit rather than a first-fit strategy, or it may implement garbage collection. More commonly, allocators are used when a fixed size block of memory is frequently needed.

Here's the structure of alloc.h:

#ifndef ALLOC_H
#define ALLOC_H

#include <stdexcept>
using namespace std;
// etc.

#endif

My allocator maintains a list of free cells. A free cell can contain an item or a pointer to the next free cell on the list.

template <class Type>
class Allocator
{
public:
   enum { NCELL = 100 };
   union FreeCell
   {
      // WARNING: Union members can't have a
      // programmer-defined constructors in VC++
      Type item;
      FreeCell* next;
   };

   Allocator(int n = NCELL);
   Type* allocate();
   void deallocate(Type* c);

private:
   FreeCell* freelist;
};

template <class Type>
Allocator<Type>::Allocator(int n /* = 100 */)
{
   freelist = new FreeCell[n];
   // initialize pointers
   for(FreeCell* p = freelist; p < freelist + n - 1; p++)
      p->next = p + 1;
   p->next = 0;
}

template <class Type>
Type* Allocator<Type>::allocate()
{
   if (!freelist) // temporarily out of heap
   {
      freelist = new FreeCell[NCELL];
      if (!freelist) throw runtime_error("Out of memory"); // Yikes!
      // initialize pointers
      for(FreeCell* p = freelist; p < freelist + NCELL - 1; p++)
         p->next = p + 1;
      p->next = 0;
   }

   FreeCell* f = freelist;
   freelist = freelist->next;
   return (Type*) f;
}

template <class Type>
void Allocator<Type>::deallocate(Type* c)
{
   FreeCell* f = (FreeCell*)c;
   f->next = freelist;
   freelist = f;
}

List<Item>

List<Item> is a template. To maintain consistent use of the template parameter, Cell and Iterator are declared as inner classes. Naturally, the orthodox canonical form pattern is used:

template <class Item>
class List
{
public:
   // OCF stuff
   List() { first = last = 0; }
   List(const List<Item>& l) { copy(l); }
   ~List() { free(); }
   List<Item>& operator=(const List<Item>& l);

   // inner classes
   class Iterator; // forward reference
   class Cell; // forward reference
   typedef Allocator<Cell> Allocator; // see alloc.h
   class Cell { /* see below */ };
   class Iterator { /* see below */ };

   // member functions
   void erase(Iterator p);
   void insert(Iterator p, const Item i);
   void push_front(const Item i);
   void push_back(Item i);
   Iterator begin() { return Iterator(first); }
   Iterator end() { return Iterator(); }
   bool empty() { return first == 0; }
   Item& front()
   {
      if (!first) throw logic_error("List is empty");
      return first->data;
   }

private:
   Cell *first, *last;
   void free();
   void copy(const List<Item>& l);
};

Cells

Remember, Cell is an inner class of List<Item>, which identifies all references to Item in Cell with the template parameter of the outer class. Because the outer class is a template, it seems all inner class member functions must be inline in VC++. Note that new and delete are redefined to allocate and deallocate from a static allocator member:

class Cell
{
   // Cell(Item i) { data = i; prev = next = 0; } NO!
   // unions can't have members with constructors in VC++!
   // use this instead:
   void init(Item i, Cell* cp = 0, Cell* cn = 0)
   {
      data = i;
      next = cn;
      prev = cp;
   }

   friend class List<Item>;
   friend class Iterator;

   Item data;
   Cell* next;
   Cell* prev;

   void* operator new(size_t bytes) // size_t defined in <stddef.h>
   {
      if (bytes != sizeof(Cell))
         throw logic_error("Wrong size!");
      return myHeap->allocate();
   }

   void operator delete(void* p)
   {
      myHeap->deallocate((Cell*) p);
   }

   static Allocator* myHeap; // must be a pointer
};

Iterators

Remember, Iterator is an inner class of List<Item>, which identifies all references to Item in Iterator with the template parameter of the outer class. Iterators are abstract pointers.

class Iterator
{
public:

   Iterator(Cell* c = 0) { cell = c; }

   friend class List<Item>;

   Item& operator*()
   {
      if (!cell) throw runtime_error("Invalid iterator");
      return cell->data;
   }

   Iterator operator++(int) // post inc
   {
      if (cell)
         cell = cell->next;
      return *this;
   }

   Iterator operator--() // pre dec
   {
      if (cell)
         cell = cell->prev;
      return *this;
   }

   bool operator==(const Iterator& p) const
   {
      return cell == p.cell;
   }

   bool operator!=(const Iterator& p) const
   {
      return cell != p.cell;
   }

private:
   Cell* cell; // my cursor
};

Putting stuff in the list

template <class Item>
void List<Item>::push_front(const Item i)
{
   Cell* c = new Cell;
   c->init(i, 0, first);
   if (first)
      first->prev = c;
   first = c;
   if (!last) last = c;
}

template <class Item>
void List<Item>::push_back(Item i)
{
   Cell* c = new Cell;
   c->init(i, last, 0);
   if (!first) first = c;
   if (last)
      last->next = c;
   last = c;
}

template <class Item>
void List<Item>::insert(Iterator p, const Item i)
{
   if (p.cell)
   {
      Cell* c = new Cell();
      c->init(i, p.cell, p.cell->next);
      p.cell->next = c;
      if (last == p.cell) last = c;
   }
}

erase()

template <class Item>
void List<Item>::erase(Iterator p)
{
   if (p.cell)
   {
      Cell* c = p.cell->prev;
      if (c) c->next = p.cell->next;
      c = p.cell->next;
      if (c) c->prev = p.cell->prev;
      if (first == p.cell) first = c;
      if (last == p.cell) last = p.cell->prev;
      delete p.cell;
   }
}

OCF Implementations

template <class Item>
void List<Item>::copy(const List<Item>& l)
{
   Cell *curr = l.first;
   if (curr)
   {
      Cell* c = new Cell();
      c->init(curr->data);
      first = c;
      curr = curr->next;
      while(curr)
      {
         last = c;
         c->next = new Cell();
         c->next->init(curr->data, c);
         c = c->next;
         curr = curr->next;
      }
   }
   else
   {
      first = 0;
      last = 0;
   }
}

template <class Item>
void List<Item>::free()
{
   Cell *curr, *next;
   if (first)
   {
      curr = first;
      next = curr->next;

      while(next)
      {
         delete curr;
         curr = next;
         next = next->next;
      }

      if (curr) delete curr;
   }
}

template <class Item>
List<Item>& List<Item>::operator=(const List<Item>& l)
{
   if (this != &l)
   {
      free();
      copy(l);
   }
   return *this;
}

A list writing utility

template <class Item>
ostream& operator<<(ostream& os, List<Item>& vals)
{
   List<Item>::Iterator p;
   os << "( ";
   for(p = vals.begin(); p != vals.end(); p++)
      os << *p << ' ';
   os << ")\n";
   return os;
}

Adaptors (queue.h)

Stacks and queues are just lists with a different interface. Queue uses the inheritance adapter patter, while stack uses the delegation adapter pattern:

#include "list.h"

template <class Item>
class Queue: List<Item> // private inheritance
{
public:

   void enqueue(Item i)
   {
      push_back(i);
   }

   void dequeue()
   {
      Iterator p = begin();
      erase(p);
   }

   Item& front() { return List<Item>::front(); }
};

template <class Item>
class Stack
{
public:

   Stack() { elems = new List<Item>(); }

   void push(Item i)
   {
      elems->push_front(i);
   }

   void pop()
   {
      List<Item>::Iterator p = elems->begin();
      elems->erase(p);
   }

   Item& top() { return elems->front(); }

private:
   List<Item>* elems; // my delegate
};

Example

Here are the includes we will need:

#include "list.h"
#include "queue.h"
#include <iostream>
#include <string>
using namespace std;

The only thing scarey about using lists is initializing the static heap. A macro can make this less painful:

List<int>::Allocator* List<int>::Cell::myHeap
= new List<int>::Allocator();

Here's main:

int main()
{
   List<int> vals;
   List<int> nums;

   nums.push_back(32);
   nums.push_back(42);
   nums.push_back(52);
   nums.push_front(10);

   cout << nums;
   vals = nums;
   cout << vals;

   List<int>::Iterator p;
   p = vals.begin();
   p++;
   vals.erase(p);
   cout << vals;
   cout << nums;

   p = nums.begin();
   p++;
   *p = 20000;
   p++;
   nums.insert(p, 100);
   cout << nums;

   Queue<int> q;
   q.enqueue(10);
   q.enqueue(50);
   q.enqueue(60);
   cout << q.front() << '\n';
   q.dequeue();
   cout << q.front() << '\n';
   q.dequeue();
   cout << q.front() << '\n';

   return 0;
}

Program Output

Here's the program output:

( 10 32 42 52 )
( 10 32 42 52 )
( 10 42 52 )
( 10 32 42 52 )
( 10 20000 42 100 52 )
10
50
60

Project

The Vector class implemented in the Handle-Body chapter needs iterators, too. Define and test an inner iterator class for vector. The inner class encapsulates an index to the "current element" of the vals array, but provides the same pointer-type operations as the iterator inner class for lists defined above:

template <class Storable>
class Vector
{
public:

   class Iterator
   {
   public:
      // etc.
   private:
      int curr; // vals[curr] = current element
   }; // Iterator

   friend class Iterator;

   // etc.

private:
   Storable *vals; // = the heap array
   int _size; // = number of storables in vals
   int capacity; // = length of vals
   // etc.
};