Object Design in STL

The C++ standard template library (STL) is loaded with classes and functions that implement commonly used data structures (or containers) and algorithms. Among the former are vector, list, map, set, etc.; among the latter are functions for sorting, searching, finding minimum and maximum elements, etc. The usefulness of them are beyond doubt, as they reflect an old adage by Niklaus Wirth:

Algorithms + Data structures = Programs

The STL makes use of the C++ template construct. The containers are generic in the sense that they work with any type. Thus, 

    int a[] = {-3, 9, 3, 0, 5, -7, 3, 6, -6, 1};
    std::vector<int> v(a,a+10);
    double b[] = {-3.1, 9.2, 3.0, 0, 5.1, -7.3, 3.3, 6.5, -6.0, 1.1};
    std::vector<double> w(b,b+10);

puts ten integers into the vector v and ten doubles into the vector w. 

The algorithms in STL that work with the containers are also type generic, but with two additional constraints. 

First, the data type being processed by the algorithms must support the operation needed. For example, for a sorting algorithm to sort objects stored in a vector, the object type must support various comparison operators (e.g., >, >=, <, and <=).  

Second, each algorithm can only work with containers that support the required way to access data stored inside the containers. For example, sort works with vector but not list because it requires random access to data in the container. Access to data inside a container is provided through an iterator. For example,

    LONGS_EQUAL(-7, *std::find(v.begin(), v.end(), -7));
    CHECK(v.end() == std::find(v.begin(), v.end(), 8));

The find function accepts two iterators and the value it is looking for. The iterators, which mark the range of data inside the vector to look for the given value, are created through v.begin() and v.end(), where v is the vector of ten integers defined previously. The function find works with list as well, as follows:

    int a[] = {-3, 9, 3, 0, 5, -7, 3, 6, -6, 1};
    std::list<int> v(a,a+10);
    LONGS_EQUAL(-7, *std::find(v.begin(), v.end(), -7));
    CHECK(v.end() == std::find(v.begin(), v.end(), 8));

Impressive, isn't it? What makes this possible, in addition to the C++ template construct, is the Dependency Inversion Principle. Algorithms are made to work with iterators instead of containers, so they do not depend on the containers. On the other hand, containers are responsible for creating iterators for accessing the objects stored in them. In other words, both the algorithms and the containers depend on the iterators. Diagrammatically, the dependency relationships change as follows:

 Here's the take-away. 

• Look first in STL for data structures and algorithms you need.
• If you must code up an algorithm, make it work with existing STL containers through iterators.
• If you must code up a container, make it work with existing STL algorithms by having it create iterators for accessing data. 

© Y C Cheng, 2013, 2014. All rights reserved.

Polymorphism

Problem. A program is needed to print the properties of a number of shapes (e.g., Polygon, Circle, etc.) from an input file. The information includes
-- descriptive information (name of the shape, vertices in polygon, center and radius in circle)
-- area, and
-- perimeter.

Following the TDD convention of writing tests first, the following tests are written first:

C++ is strongly typed. Let's call the function printProperties and have it return a string of the properties given a shape object. We must still give the formal parameter of printProperties a type. So we can rephrase our problem as: 

• How to make printProperties accept both Polygon and Circle? Or, 
• How to treat Polygon and Circle as the same type so far as the required member functions are concerned?

C++ provides a way for you to do this. The basic idea is to create an interface between the function printProperties and the shapes that it will potentially accept.

1. Declare a class called Shape which has the required member function declared as virtual. Shape will be the interface that printProperties works with.

The declaration of each member function of Shape begins with the keyword "virtual" to indicate that it can be overridden by a derived class. Also, each member function declaration ends with " = 0" to indicate the the member function is not implemented in Shape. That is, Shape won't ever have an instance because these member functions are not implemented. Combining the meanings of both, Shape is an interface between the function printProperties and the classes Polygon, Circle, etc. In C++, Shape is called an abstract class.

2. Derive Polygon and Circle from shape.

We already have the Polygon class, so all we need to do to make it inherit or derive from Shape. Line 6 reflects this change. The inherited member functions are grouped in a newly added "public:" section (lines 7 - 10). Note that the member functions still begin with virtual (though this is optional) but the trailing " = 0" are now removed. The latter indicates that Polygon must provide the implementation of the three inherited member functions.

3. Use call by reference or call by value-pointer in properties. In the case of call by reference:

 

Doing the same for the class Circle, we obtain an output like this:

How it works

The fact that printProperties work with Polygon and Circle are the result of satisfying three conditions as explained above. The binding of a member function name (e.g., s.area()) with an implementation (e.g., Polygon::area() or Circle::area()) happens at execution time. This form of binding is called late binding or dynamic binding in contrast to static binding which takes place during compilation.

Late binding in C++ works approximately like this.

During compilation, the formal parameter s of printProperties is a reference to the type Shape. The three member functions called through s, including description(), area(), and perimeter(), are declared virtual. C++ compiler takes this as a request to delay binding the implementation until execution time.

During execution time, when the call

    Polygon p=createRegularPolygon(3);
    std::cout << printProperties(p); 
is executed, C++ looks up the implementation for the three member functions though the object p, which is passed by reference.

Late binding incurs an overhead in taking an extra step to look up the implementation of the member function. If you are using an OO language, you should assume that this run-time overhead can be ignored. 

The printProperties function is able to work with Polygon, Circle, and any other shape that derives from Shape. This achieves polymorphism, a corner stone feature of object-oriented languages. The design satisfies the Open/closed principle: 

"software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification"

Shape is open to extension since a new subclass (e.g., Ellipse) can be added without affecting the existing subclasses (e.g., Polygon and Circle) and the function printProperties. That is, Polygon, Circle, and  printProperties are closed for modification. 

Code can be found here.


© Y C Cheng, 2013, 2014. All rights reserved.