Lab 10: Containers

Abstraction

We use classes to create useful abstractions that combine data with functionality. Our BetterArray combines a normal array with the integer used to keep track of the number of values in it. Unlike a normal array, we don't allow the program to do just anything to a BetterArray object. Instead, we present a limited set of methods. This is called the API of the class (Application Programming Interface).

By limiting what you can do with a class (constraining it), you avoid unnecessary errors, optimize it for what it's good at, and simplify testing.

BetterArray is a type of container, in this case a linear sequential container because it stores items in a single sequence. There are many other useful containers, also known as data structures that are appropriate for different problems.

In this lab, you'll create two other containers that both combine a normal array and length to store information, but provide more constrained functionality than BetterArray.

Part I, Stack

The stack container is a common, simple data structure. Like a real-world stack of papers, it has a very simple set of functionality:

• Put something on the top of the stack
• Take the thing off the top of the stack

A stack is a linear sequence of items, so storing them in an array makes sense. But unlike a normal array, or even BetterArray, you aren't allowed to insert items or remove items in the middle. You can only add to the top (push) and remove from the top (pop).

Create a class Stack that makes this code work. Stack will holds strings. Note that to make it useful, we've added a couple other convenience methods beside push and pop.

Stack words;
words.push("anaconda");
words.push("parfait");
words.push("buttery");

// should print "I have 3 words in my stack."
cout << "I have " << words.count() << " words in my stack" << endl;

// should print "I got rid of buttery"
string next = words.pop();
cout << "I got rid of " << next << endl;

words.push("carnosaur");
words.push("peel");

// this should print the words as they are removed:
// peel
// carnosaur
// parfait
// anaconda
while (!words.empty()) {
  next = words.pop();
  cout << "Next word: " << next << endl;
}

// should print "I have 0 words in my stack."
cout << "I have " << words.count() << " words in my stack" << endl;

Part II, Sorted Set

A set is a container that holds only unique items. A sorted set guarantees that the items are kept in order. The API for a sorted set could be:

• Add a new item, put it in the right place to maintain sorting (ignore if a duplicate)
• Return true if an item is in the set
• Remove an item (by specifying it's value, not it's position)

Create a class SortedSet that makes this code work. SortedSet will hold chars. Again, we've added a couple other convenience methods.

SortedSet letters;
letters.add('t');
letters.add('h');
letters.add('d');
letters.add('k');
letters.print(); // should show: (d, h, k, t)

letters.add('k');
letters.print(); // should still show: (d, h, k, t)

// positive check, does contain h
if (letters.contains('h')) { 
  cout << "My set contains h" << endl;
} else { 
  cout << "My set does not contain h" << endl;
}

// negative check, does not contain q
if (letters.contains('q')) { 
  cout << "My set contains q" << endl;
} else { 
  cout << "My set does not contain q" << endl;
}

letters.remove('h');
letters.print(); // should show: (d, k, t)