Quiz: Dynamic Arrays

The Background

In lecture we defined a Bag ADT using a dynamic array as its underlying data structure:

class Bag {
  public:
    typedef std::string value_type;
    typedef std::size_t size_type;

    Bag();    
    
    size_type size() const;
    void print(ostream&) const; // optional

    void add(const value_type& item);
    value_type remove_any() throw (underflow_error);
    // precondition: size() > 0

  private:
    static const int INITIAL_CAPACITY = 4;
    
    value_type* contents; // must be a dynamically allocated array
    size_type capacity; // must be the size of contents, must be > 0
    size_type count; // must be <= capacity

    void ensure_capacity(unsigned min); // postcondition: capcity >= min
};

The size() memeber function simply returns count. The implementation of print prints the values to the stream. It makes it easier to test bag functions. The add and remove_any implementations are only a few lines each:

void Bag::add(const value_type& item)
{
  ensure_capacity(count+1);
  contents[count] = item;
  ++count;
}
Bag::value_type Bag::remove_any() throw (underflow_error)
{
  if (count <= 0) throw underflow_error("nothing in bag");
  -count;
  return contents[count];
}

The Question

If we use the default implementation for operator=:

Bag& Bag::operator=(const Bag& other)
{
  contents = other.contents;
  capacity = other.capacity;
  count    = other.count;
  return *this;  // I forgot this line in lecture
}

Then if we execute:

Bag b;
b.add("ham");
b.add("carrots");
Bag b3;
b3.add("dill");
b3 = b;

Then b and b3 will both be pointing at the same array. This will cause things to go wrong. Continue the example and explain what unexpected things happen. Draw pictures.

Solution

b3.add("eggs");
b.add("flour");
cout << b3.remove_any();
// Expected output: eggs
// Actual output: flour

The actual output happens because the addition of ``flour'' uses b's count, which is unchanged at 2, and so overwrites the ``eggs.''

Alternatively, one could simply print out b3:

b3.add("eggs");
b.add("flour");
b3.print(cout); 
// Expected output: ham, carrots, eggs
// Actual output: ham, carrots, flour

Another, less satisfying solution is to have b3 in a nested scope, and close that scope and then print b. This would (probably) crash, because we would be accessing an array of destructed strings.

Incorrect solutions

The following attempts from actual quizzes won't work:

cout << b.remove_any(); // expected output: carrots
cout << b3.remove_any(); // expected output: carrots

Both will print "carrots" as expected. The reason why is that the remove_any function does not change the array, so there is no way to observe the fact that the array is shared.

b3.add("ginger");
b3.add("apples");
b3.add("ice cream");

This will add three new items to b3 which will cause the old array to be deleted and a new array allocated for b3. Now b is pointing to a deleted array. But the code above doesn't do anything with b. This would get full credit if we then printed b, which would probably cause the program to crash.

b3.add("pop");
b3.add("sugar");
cout << b3.remove_any();
b3.print(cout); // expected output: ham, carrots, pop

Again nothing strange will be observed. We will add the two new items to the array, and then b3's count will be reduced to 3, but still it will look fine. And even if we printed b at this point, it would still be fine.

b.add("onions");
b.add("cookies");
cout << b3.remove_any(); // expected output: carrots

Remember that b3's count is unaffected by b's additions. So b3's remove_any still returns the expected ``carrots.'' Furthermore, even if we printed b at this point, nothing strange would be observed, because remove_any does not change the array.

cout << b3.remove_any(); // expected output: carrots
b3.print(cout); // expected output: ham

An exercise for the reader: why does this not flush out the bug? Why is even printing b at this point useless?

b3.add("chicken");
(void) b3.remove_any();
(void) b3.remove_any();
cout << b.remove_any(); // expected output: carrots

Another exercise. Remember that remove_any doesn't change the array.