implement a IntStack with bridge pattern in C++

Question

This question was from "Thinking in C++" Vol-1, Chapter 5's exercise No.14:

Create a StackOfInt class (a stack that holds ints) using the “Cheshire cat” technique that hides the low-level data structure you use to store the elements in a class called StackImp. Implement two versions of StackImp: one that uses a fixed-length array of int, and one that uses a vector. Have a preset maximum size for the stack so you don’t have to worry about expanding the array in the first version. Note that the StackOfInt.h class doesn’t have to change with StackImp.

Here is the header file (StackOfInt.h) I created:

#ifndef STACKOFINT_H
#define STACKOFINT_H

class StackOfInt
{
    int size;
    int curr_idx;
    class StackImp;
    StackImp* head;
  public:
    void initialize(int max);
    void push(void* dat);
    void* peek();
    void* pop();
    void cleanup();
};
#endif

However, for the implementation, I'm confused about how to handle the difference between array and vector. Here is what I came up with so far:

#include "StackOfInt.h"
#include "require.h"
#include <vector>

class StackOfInt::StackImp
{
    int arrInt[50];
  public:
    void initialize()
    {
        for (int i = 0; i < 50; i++)
        {
            arrInt[i] = 0;
        }
    }
};

/*
class StackOfInt::StackImp
{
    std::vector<int> vecInt;
}
*/

void StackOfInt::initialize(int max)
{
    size = max;
    curr_idx = 0;
    head = 0;
    StackImp* newImp = new StackImp;
    newImp->initialize();
}

void StackOfInt::push(void* dat)
{
    *(head+curr_idx) = dat;
    curr_idx++;
}

void* Stack::peek(int idx)
{
    require(head != 0, "Stack empty");
    return head[idx];
}

void Stack::cleanup()
{
    require(head == 0, "Stack not empty");
} ///:~

I think I'm on the wrong tracks, could anyone give me some hints on how to solve this problem?

Answer 1

What the book author has in mind, is that the StackOfInt class should not contain any other members besides a pointer to the implementation class. The necessary data members, be it an array + count variable or a vector, should be members of the implementation class.

So in the header, you'd have

class StackOfInt {

    class StackImp;
    StackImp* impl;
public:
    void initialize();
    void push(int dat);
    int peek();
    int pop();
    void cleanup();
};

In the implementation file you'd have the implementation:

class StackOfInt::StackImp
{
public:
    int count;
    int array[100];
};

void StackOfInt::initialize()
{
    impl = new StackImp;
    impl->count = 0;
}

void StackOfInt::push(int dat)
{
    impl->array[impl->count++] = dat;
}

//and other methods

Write another cpp file that uses the StackOfImp class. Compile the project and run the program to make sure everything works nicely :)

Now you can completely rewrite the implementation file for the StackOfInt to use a vector as the underlying type. Recompile the project. Note that the user of StackOfImp (the test code) does not have to be recompiled because nothing was changed in the header.

To read more about the technique that the author calls "Cheshire cat": Opaque pointer

---

Note that I don't understand your usage of void pointer. A StackOfInt should take and return integers.

Calling the implementation pointer head also seems to indicate some misunderstanding. This represents a pointer to the object that will actually contain the necessary members to implement the stack.

Answer 2

One way of handling that is to make the "impl" class polymorphic and use a factory to select the implementation at construction time.

Answer 3

I think the expectation is that you will have two different implementations in two separate cpp files, and you would include one or the other in the project in order to use it.

StackImplArr.cpp

     class StackOfInt::StackImp
     {
       int arrInt[50];
     }

StackImplVec.cpp

     class StackOfInt::StackImp
     {
       std::vector<int> vecInt;
     }

A more advanced use would declare a base class and derive the two implementations from it, allowing the implementation to be selected at runtime:

     class StackOfInt::StackImp
     {
       virtual initialize() = 0;
     }

     class StackOfInt::StackImpArr : public StackOfInt::StackImp
     {
       int arrInt[50];
       virtual initialize() { ... }
     }

     class StackOfInt::StackImpVec : public StackOfInt::StackImp
     {
       std::vector<int> vecInt;
       virtual initialize() { ... }
     }

     void
     StackOfInt::initialize( int max) {
       head = condition ? new StackImpArr() : new StackImpVec();
     }