Copy or Reference: Does the container keep copies of the original objects or refer to the original objects themselves.

class Vector{  //Copied Objects
     public:
     Vector(int capacity = 100) : index(0), size(capacity){
         buffer = new T[size];}
     ~Vector(){delete [] buffer;}
     void addElement(T & item) {if(index < size) buffer[index++] = item;}
     T elementAt(int i) {return buffer[i];}
      void removeLast() {if(index > 0) index--;}
     private:
      T * buffer;
      int size;
      int index;
};

class Vector{  //Original Objects
     public:
     Vector(int capacity = 100) : index(0),size(capacity){
          buffer = new T*[size];}
     ~Vector(){delete [] buffer;}
     void addElement(T & item) {if(index < size) buffer[index++] = &item;}
     T & elementAt(int i) {return *buffer[i];}
     void removeLast() {if(index > 0) index--;}
     private:
      T ** buffer;
      int size;
      int index;
};

Size: Is the container of a fixed size or does it grow or shrink as objects are added or removed?

class Vector{  //Fixed Size
     public:
     Vector(int n = 100) : index(0), size(n) {buffer = new T[n];}
     ~Vector() {delete [] buffer;}
     void addElement(T & item) {if(index < size) buffer[index++] = item;}
     T elementAt(int i) {return buffer[i];}
      void removeLast() {if (index > 0) index--;}
      private:
      T * buffer;
      int size;
      int index;
};

class Vector{  //Unbounded Container
     public:
     Vector(int n = 4) : index(0),size(n) {
         buffer = new T[n];}
     void addElement(T & item) {
         if(index == size) {  //grow the container
            cout << "growing\n";
            T * temp = buffer;
            buffer = new T[size*2];
            for(int i=0; i<size; i++) buffer[i] = temp[i];
            size = size *2;
            delete [] temp;
            }
      buffer[index++] = item;
     }
     T elementAt(int i) {return buffer[i];}
     void removeLast() {
         index--;
         if(index < size/2) {  //shrink the container
   cout << "shrinking\n";
            T * temp = buffer;
            buffer = new T[size/2];
            for(int i=0; i<index; i++) buffer[i] = temp[i];
            size = size/2;
            delete [] temp;
         }
     }
      private:
      T * buffer;
      int size;
      int index;
};

Protocol: What sort of access protocol does the container provide or enforce? (Stacks enforce a last in first out protocol; arrays allow random access to any part of the container.
 
 
 

Does the container allow client to access  it's memory or does the client simply request that objects be added or removed and leaves the memory management to the container's private affairs?

v[i] = object;    //v.operator[](i) = object;
v.addElement(object);
 
 

Does the container store values, references or pointers?

class Container{
   private:
   T elements[100];
};

class Container{
   private:
   T* elements[100];
};

class Container{
   private:
   T & elements[100]; //WRONG WRONG
};

class Node{
   public:
   Node * nextNode;
   T & element;
};

class List{
   private:
   Node * topOfList;
};
 
 

Does the container own  its elements? That is, if the container is distroyed must the elements also be distroyed.

class Container{  //Container does not own the elements
   public:
   Container(int n) :size(n) {buffer = new T*[n];}
   ~Container(void) { delete [] buffer;}
   private:
   T ** buffer;
   int size;
};

class Container{  //Container owns the elements
   public:
   Container(int n) :size(n) {buffer = new T*[n];}
   ~Container(void) {
      for(int i = 0; i< size; i++)
         delete buffer[i];
      delete [] buffer;}
   private:
   T ** buffer;
   int size
};
 

Sharing: Can objects be elements of more than one container at a time?

Does the container provide a mapping to elements. (e.g. arrays provide mapping from integers to elements)?

What sort of iteration is possible with a container?
 

Homogeneous vs. Heterogeneous: A homogeneous container holds only one type of element. A heterogeneous container can hold several different types of elements. A usual compromise is that the various types all inherit from a common superclass. A truly heterogeneous container is one that can store a variety of element types that have no relationship to each other.

How does container handle client violations of protocol? (e.g. Client pop()'s off an empty stack.)

class Stack{
   public:
   void push(T & element) {...}
   T & pop(void) {...}
};

//Client code
Stack s;
s.push(x); s.push(y);
cout << s.pop() << s.pop() << s.pop();

Iteration Strategies

Iteration provides a way to go through the elements of a container with limited knowledge of how the elements are stored

Often the same iteration protocol can be used to iterate over different types of containers
using the same protocol

Bad because it provides no encapsulation or a general scheme that works for all containers.
 
 

for (int i = 0; i<v.size(); i++)
    cout << v[i];
 

Simple, effective iteration, but limited control over start and order of elements

class Collection {
     public:
     T  someElement() { index++;
                        index = index % size;
                        return buffer[index]; }

     private:
       T * buffer;
       int size;
       int index; //current location
};
 

//client code
for(int i = 0; i< collection.size(); i++)
    cout << collection.someElement();

Avoid iteration problem by asking the container to do the work the client was planning to do with each element. (Uses function pointers)

class Collection {
     public:
     void apply( void (funcptr*)(const T & element) ){
         for(int i = 0; i<size; i++)
               funcptr(buffer[i]);
       }

     private:
       T * buffer;
       int size;

};

void print( const T & thing) {cout << thing;}

//client code
collection.apply(&print);
 

Container provides a way for clients to ask for elements without exposing its internal storage management

class Collection {
     public:
     void reset() {index = 0;}
     bool hasMore() {return index < size;}
     void advance() {index++;}
     T & element() const {return *buffer[index];
     private:
       T ** buffer;
       int size;
       int index;

};

//client code
for (v.reset(); v.hasMore(); v.advance() )
       cout << v.element();
 

External object keeps track of iterator location. This allows multiple iterators to work over the same collection

class Collection {
     friend class CollectionIterator;
     public:

     private:
       T ** buffer;
       int size;
};

class CollectionIterator{
  public:
     CollectionIterator(Collection & c) :col(c) {index = 0;}
     void reset() {index = 0;}
     bool hasMore() {return index < size;}
     void advance() {index++;}
     T & element() {return *(col.buffer[index]);
  private:
     Collection & col;
     int index;

};

//client code
Collection v;
CollectionIterator iter(v);

while (iter.hasMore() ) {
    cout << iter.element();
    iter.advance();
    }
 

//client code  --nested iterator
Collection v;
CollectionIterator iter1(v), iter2(v);

for(iter1.reset(); iter1.hasMore(); iter1.next())
  for(iter2.reset(); iter2.hasMore(); iter2.next() )
       cout << iter1.element() <<  iter2.element();
 

Container provides an iteration protocol but allows multiple clients at the same time. Each client returns their old element, which the container uses to select the next element to give the client. (Based on Mememto Programming Pattern)

class Collection {

     public:
     T & first() {return *buffer[0]; }
     bool hasMoreAfter(T & element) {
         for(int i = 0; i<size-1; i++)
             if(*buffer[i] == element) return true;
         return false;

     }
     T & nextAfter(T & element) {
         for(int i = 0; i<size; i++)
             if(*buffer[i] == element) return buffer[++i];
         return element;

     private:
       T ** buffer;
       int size;
};
 

//client code
Collection v;
 

for(T item = v.first(); v.hasMoreAfter(item); v.nextAfter(item))
   cout << item;

//client code --nested iteration

for(T item = v.first(); v.hasMoreAfter(item); v.nextAfter(item))
   for(T item2 = v.first(); v.hasMoreAfter(item2); v.nextAfter(item2))
       cout << item << item2;
 
 
 

The standard template library uses the idea to two iterators being moved towards each other.  The containers each provide a method begin() which returns an iterator pointing at the first element. The containers also provide a method end() which returns an iterator pointing "one position past the last element".
 

The iterators are advanced towards each other and when they collide the iteration has covered all to the elements. The iterator objects behave like pointers (They implement *,->,++ operators, so the client code can use them like pointers)

class Collection {
     friend class CollectionIterator;
     public:
     CollectionIterator begin() {return CollectionIterator(*this); }
     CollectionIterator end() {return CollectionIterator(*this, size) }

     private:
       T ** buffer;
       int size;
};

class CollectionIterator{
  public:

     CollectionIterator(Collection & c, int position = 0) :col(c) {index = position;}

     CollectionIterator & operator++ {index++; return *this;}
     T & operator*() {return *(col.buffer[index]);}
     T * operator->() {return col.buffer[index];}
     bool operator==(const CollectionIterator & iter) {
          return (col == iter.col) && (index == iter.index);
     }
     bool operator!=(const CollectionIterator & iter) {
         return !operator==(iter);
     }

  private:
     Collection & col;
     int index;

};

//client code
Collection v;
for(CollectionIterator iter = v.begin(); iter != v.end(); iter++)
   cout << *iter;

//client code --nested iteration

for(CollectionIterator iter = v.begin(); iter != v.end(); iter++)
  for(CollectionIterator iter2 = v.begin(); iter2 != v.end(); iter2++)
      cout << *iter  <<iter2->getName();