Many newer object oriented languages such as Java and Swift have a dedicated interface type for defining the methods of a superclass. C++ does not. What C++ does provide is purely virtual classes, which function in essentially the same way.
In this post I will show how this is done in C++ by implementing an interface for a stack ADT, and then two different concrete implementations of that ADT, both of which can be used by any procedure that uses a stack. I know that last part sounds a little funny, but what I mean by it will become clear in a moment.
Purely Virtual Classes
A purely virtual class is a class in C++ is a class which has all of its member methods declared virtual, as the name would apply. These classes can not be instantiated directly, but they can be derived from. To declare a method virtual inside a class you use the following syntax:
virtual <return type> <method name>(method args) = 0;
So a purely virtual class for a stack would look like this:
template <class T>
class stack {
public:
virtual void push(T info) = 0;
virtual T pop() = 0;
virtual int size() = 0;
virtual bool empty() = 0;
};
As you can see, a purely virtual class has no code actual code. They only serve to declare what methods any class that derives from it MUST implement.
Concrete Derived Classes
As mentioned, on there own purely virtual classes are rather useless. In order to make use of them we still need am actual concrete implementation of the type being defined.
First I implemented an array based stack which inherits from the purely virtual stack class.
template <class T>
class ArrStack : public stack<T> {
private:
T* info;
int n;
int maxn;
void resize(); //code not shown for brevity.
public:
ArrStack(int maxsize = 5) {
maxn = maxsize;
n = 0;
info = new T[maxn];
}
ArrStack(const ArrStack& o); //code not shown for brevity.
~ArrStack();
void push(T i) {
if (n+1 == maxn) resize(2*maxn);
info[n++] = i;
}
T pop() {
if (n == maxn/2) resize(maxn - (maxn/4));
return info[--n];
}
int size() {
return n;
}
bool empty() {
return n == 0;
}
};
Next the same is done for a linked list based implementation:
template <class T>
class LinkedStack : public stack<T> {
private:
struct node {
T info;
node* next;
node(T i, node* n) {
info = i;
next = n;
}
};
node* head;
int n;
public:
LinkedStack() {
head = nullptr;
n = 0;
}
LinkedStack(const LinkedStack& o); //code omitted for brevity
~LinkedStack(); //code omitted for brevity
bool empty() {
return head == nullptr;
}
int size() {
return n;
}
void push(T info) {
head = new node(info, head);
n++;
}
T pop() {
T ret = head->info;
node* x = head;
head = head->next;
delete x;
n--;
return ret;
}
};
Liskov Substitution Principle
So what is exactly meant by “Any derived object can be substituted for it’s superclass without noticeable difference to the user”? It’s easier to demonstrate than explain. Consider the following method, clearStack() which expects a stack as one of it’s arguments and proceeds to empty the stack(i added the print statements for demonstration purposes). A useful operation which our classes do not internally implement.
template <class T>
void clearStack(stack<T>& sf) {
while (!sf.empty()) {
cout<<sf.pop()<<" ";
}
cout<<endl;
}
If our concrete classes did not derive from stack we would have to write a separate method for each stack implementation. But because of our use of an interface, our classes adhere to the Liskov substitution principle, so we can do the following:
template <class T>
void clearStack(stack<T>& sf) {
while (!sf.empty()) {
cout<<sf.pop()<<" ";
}
cout<<endl;
}
int main() {
ArrStack<int> as;
for (int i = 1; i < 10; i++)
as.push(i);
LinkedStack<char> ls;
string sed = "Liskov's substituion";
for (char c : sed)
ls.push(c);
clearStack(as);
clearStack(ls);
return 0;
}
And there you have it, implementing interfaces in C++ with purely virtual classes. Until next time, Happy Hacking!
Further Reading
- https://en.wikipedia.org/wiki/Liskov_substitution_principle
