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.