Today we will look at templates (again) and inheritance, two powerful mechanisms for code reuse in C++.
Most of the ADTs we will look at this semester have only minimal requirements on the data types they work with. For example, a bag of integers and a bag of strings are basically the same. All that is really required for the type of bag objects is that they can be copied (or moved) and there is a test for equality. Such types in C++ are called regular. It would be a waste to write a Bag class for each type from scratch, for example a BagOfInts and BagOfStrings, since most of the code would likely be the same-- that is, the code is generic. Fortunately C++ has a very efficient mechanism to do this using templates. Modern C++ uses templates extensively including throughout the standard library.
Templates elevate types to be generic, named but unspecifed, and can work with functions and classes. A simple example is a function to swap the contents of two variables (see std::swap):
template< typename T >
void swap(T& a, T & b)
{
T temp(b);
b = a;
a = temp;
}The symbol T acts like a variable, in fact it is a type variable. Defined this way swap is generic, I can use it on any type that can be copied. For example:
int a = 1;
int b = 2;
std::cout << a << ", " << b << std::endl;
swap(a,b);
std::cout << a << ", " << b << std::endl;
std::string A = "foo";
std::string B = "bar";
std::cout << A << ", " << B << std::endl;
swap(A,B);
std::cout << A << ", " << B << std::endl;When the above is compiled the swap function specific to int's and string's is generated and called automatically. If the type does not support a particular usage it generates a compile time error. For example suppose I wrote a class that explicitly does not allow copies
class NoCopy
{
public:
NoCopy() = default;
NoCopy(const NoCopy & x) = delete;
};and tried to use swap as
NoCopy x,y;
swap(x,y);My compiler complains
swapexample.cpp:7:5: error: call to deleted constructor of 'NoCopy'
T temp(b);Templates work with classes as well. However, one complication with templates is that it's definition and immplmentation cannot be in seperate compilation units. This is because a template itself cannot be compiled until the variable types are specified. This means that templates are usually defined and implemented in a header file. The definition and implmentation can stil be separated, and it is good style to do so, but it must be all available at the same time the compiler. For example, we might define and implement a tuple holding two different types (see std::pair) as
template <typename T1, typename T2>
class pair
{
public:
pair(const T1 & first, const T2 & second);
T1 first();
T2 second();
private:
T1 m_first;
T2 m_second;
};
template <typename T1, typename T2>
pair<T1,T2>::pair(const T1 & first, const T2 & second): m_first(first), m_second(second)
{}
template <typename T1, typename T2>
T1 pair<T1,T2>::first()
{
return m_first;
}
template <typename T1, typename T2>
T2 pair<T1,T2>::second()
{
return m_second;
}Notice that the implmentations defined outside the class require the full template specification, i.e. pair<T1,T2>::first() not just pair::first(). We might use it like so
pair<int,std::string> x(0, std::string("hi"));
std::cout << "First = " << x.first() << std::endl;
std::cout << "Second = " << x.second() << std::endl;C++ has several mechanisms to reuse code. One of them is polymorphism (many-form), where a class can inherit methods from one or more other classes. This has several uses, but the one that concerns us at the moment is specifying an interface, a class where the public methods are defined but not implemented. This defines the way client code can use a class that conforms to the interface. To define such a class you inherit from the interface, called a base class in C++, and implement the methods. There is a special way to declare methods so that they must be implemented and thus ensure the class can be used in the way the interface says.
The classic way to illustrate this is modeling shapes. Suppose we wanted to have classes that model closed 2D shapes. There are things that every 2D shape has, for example a prerimeter. We can ensure that any class that implements a specific 2D shape has an appropriate method by first defining a base class
class Shape2DBase
{
public:
virtual double perimeter() = 0;
};Note the use of the keyword virtual which means it can be redefined in subclasses and the = 0 syntax which says this class does not provide an implmentation on purpose. Defined this way we can't instantiate such a class -- the following will not compile
Shape2DBase shape;We can define and implement a setup of classes that conform to the base class using public inheritance (there are other kinds we are ignoring for now). For example we might define a Circle as
class Circle: public Shape2DBase
{
public:
Circle(double r): radius(r) {};
double perimeter()
{
return 2*M_PI*radius;
}
private:
const double radius;
};The statement class Circle: public Shape2DBase says to create a class that has the public methods of Shape2DBase. The implementation then overides the definition of perimeter, or in this case specifies one. If we fail to do so the compiler complains with an error. We might continue with classes for Square, Rectangle, Ellipse, etc. each inheriting from Shape2DBase and implementing the perimeter method appropriate to the shape they model.
This is handy because, while I can't instantiate the Shape2DBase, I can a pointer or a reference to one. So I could define a function that works for any subclass of Shape2DBase (lets say I want to show the perimeter) as
void show_perim(Shape2DBase & shape)
{
std::cout << "Perimeter = " << shape.perimeter() << std::endl;
}I can then pass a Circle, Square, etc to the function. Since it knows the classes have a perimeter method it can call it. Example
Circle c1(1.0);
show_perim(c1);You might have noticed this looks similar to templates. For example I could define Circle, Square, etc without inheiritance but till defining a perimeter method, then define the function as a template
template<typename T>
void show_perim(T & shape)
{
std::cout << "Perimeter = " << shape.perimeter() << std::endl;
}You are right! The difference is one between runtime and compile time, or dynamic versus static polymorphism. However, the approach using inhieritance can do some things the tempalte version cannot, for example we can create a vector of pointers to Shaep2DBase to collect different shapes into one data structure. On the other hand, the template solution is faster since the type sorting happens at compile time. Both are useful techniques. In this specific case the use of a base class makes the definition of the interface explicit. This can also be done with templates using something that goes by the crazy acronym SFINAE, but that is way beyond the scope of this course.
Now, supplied with templates and the notion of base classes we can create an interface for the Bag ADT and adapt our implementation of Bag to use this interface definition.
abstract_bag.hpp define a C++ interface for our Bag ADT.bag_simple.hpp and bag_simple.tpp to use this interfaceabstract_bag.hpp and modified bag_simple.hpp as a zip file via Canvas at the Assignment "Exercise for Meeting 4".