While C++ has traditionally been considered to be synonymous with object-oriented programming and object-oriented design, we sometimes tend to forget that C++ actually includes the first widely used modern implementation of a generic programming language. As I discussed in my first article, generic programming is a data structure-independent way of developing and delivering algorithms that need not be bound to a specific object.
Helping enable generic programming is the Standard Template Library (STL). This library of algorithms and containers uses templates to implement an efficient code base that is reusable and extensible. STL is one of the two major components in the Standard C++ Library as defined by the C++ standard.
STL can be described basically by three traditional categories: containers, iterators, and algorithms. These three concepts combined help produce an impressive library of algorithms and data types that greatly improve productivity. The STL library also helps the developer deliver fast, efficient, and robust code.
Containers are data structures with memory-management capabilities. In STL, there are two categories of containers, sequential containers and associative containers. Sequential containers have the data types of vector, deque, and list, while associate containers have map, multimap, set, and multiset. Various other containers exist in implementations of STL that extend the basic data types with slists, hash_set, and hash_map. Containers are objects that are specialized at compile time. They can be specialized with any type of class or data structure. They achieve this result because C++ templates implement them. Figure A outlines this information.
|Sequential container elements are in a sequential order; associative container elements are sorted against key value.|
Rather than move forward to a more academic treatment of containers, let us consider why you would use a container vs. a standard C or C++ data type. Let's take the common array. You must declare an array of static size at compile time or of dynamic size at run time. There is no way to extend the size of an array dynamically without explicitly doing so. This requires a lot of overhead code using C functions such as malloc or C++ operators such as new, along with memory-copying functions.
STL vectors are a great portable solution to this problem. They are easy to declare as an array and are dynamically resized on the fly. Listing A shows an interesting example of taking numbers from the standard input, sorting them, and printing them to the standard output. We'll discuss the sorting algorithm further on.
An interator is the logic that helps bind algorithms and containers together. While containers are merely glorified data structures that handle allocation and deallocation of memory, iterators provide a standard means of traversing the different types of containers.
A list is implemented as a doubly-linked list. A vector is implemented as a C type array. Each is traversed in a different manner, yet through the abstraction of an iterator, you can create a generic interface to traverse any type of container, whether it's implemented as an array, a linked list, or a binary tree.
Iterators are a pure abstraction. Any class that implements the methods of an iterator is an iterator. There are five types of iterators, which form a convenient hierarchy of attributes:
- · Input iterators
- · Output iterators
- · Forward iterators
- · Bidirectional iterators
- · Random access iterators
Each container implements a set of iterators. A vector would have no problems implementing a random access iterator, but a binary red-black tree might have issues implementing the random access iterator and therefore implements only bidirectional iterators. In this manner, containers implement the iterators that are most applicable to them. Figure B shows which containers implement which iterators. If a component implements a random access iterator, by definition, it will have implemented the other four iterators as well.
In Listing B, you can see how the most basic use of forward iterators affects the design of our application. Instead of using the random access iterator in the vector, we use the forward iterator to output the integers. Great care has been taken to make sure that iterators are backward compatible with C style pointers and that iterators function on existing C data types such as arrays. Listing C shows iterators functioning on existing data types.
Stream iterators are simply iterator interfaces to the iostream classes. STL created two types of stream iterators, istream_iterators, for obtaining data through an istream, and ostream_iterators, for outputting data through an ostream. Listing D shows an alternate method for reading, sorting, and outputting the data as described in Listings A and B.
Containers are independent of data structures, and iterators provide a means of accessing data from the containers in a uniform fashion. Algorithms work into the process by providing a procedural means of manipulating data exclusively through the iterator interface.
This allows you to develop powerful algorithms that will apply to all containers that implement a given iterator. Algorithms implemented in STL are usually more powerful then the algorithms that individual C++ programmers implement when solving a problem. The STL implementations of algorithms go so far as to provide a for_each loop. Some developers even argue that the for_each loop is more efficient then a standard for loop.
Algorithms can be broken down into seven major categories, which are described in Figure C. The sort algorithm we used to sort through the numbers obtained from the input in Listing A is an example of an STL-implemented algorithm.
Since we have just discussed the for_each loop, let's implement it and then see how it relates the C++ concept of functors. (More on functors in just a minute.) Listing E manipulates Listing B slightly to incorporate the for_each loop in a less-than-efficient manner. We can also use a function template to accomplish the same task, as illustrated in Listing F.
As you can see, the for_each loop condenses our for loop into a single line. This single line iterates through our vector and executes a function at every element within the vector. The function receives the element type the vector was specialized with at compile time. The function then does what it wants. In this case, it prints to the standard output.
So what's a functor, or function object? Essentially, it is a class declared with the () operator overloaded. First, we declare a class. Next, we overload the () operator with as many parameters as we want, and then we simply instantiate it. Why would we do something so complicated? Bjarne Stroustrup, the creator of C++, says that, "Function objects often execute faster." Since C++ was developed with robustness and efficiency in mind, the creators of STL felt that the use of functors would be an ideal way to maintain the performance for the algorithms implemented.
Listing Gshows how we would implement the previously discussed code using functors without templates. Listing H shows how we would implement functors using templates.
Putting it all together
Now that you've been introduced to the power of the STL, let's see what happens if we change the base container to a deque. This is usually implemented by using multiple arrays and is a lot more efficient at inserting objects at both ends of the queue than vectors are.
We will also add a binary predicate to the sorting algorithm that will allow the sort to take place in descending order. You can see the results of these actions in Listing I.
STL can dramatically change your programming style, allowing your code to be more reusable, solid, and robust. If you take advantage of STL, you can make your life efficient through simplicity. STL is also extensible, letting you add your own containers and algorithms.
Learning to use STL is no small task. The C++ standard has a wide range of concepts and methodologies that can be derived from the library. No article can replace the knowledge of a few good books, and a lot of implementation.
What other C++ topics do you want to see? Drop us an e-mail or post a comment below.