Understanding Standard Template Libraries

C++ programmers have benefited from the Standard Template Library or STL, which is a collection of container classes, generic algorithms and related components that can greatly simplify many programming tasks in C++. The container classes, as you might surmise from the name, are classes used to hold objects of any particular type. Among the methods of the container classes are methods to add and remove elements, return elements and return iterators. Iterators are an abstraction of pointers. They provide a means to traverse containers and access objects within containers. Generic algorithms are a collection of routines that can be used to perform common operations on container classes, such as sorting, merging and finding. These are called generic because they are independent of the container class used and of the data type of the objects held in those container classes. Iterators are used to link a container with an algorithm. A container class has methods to return iterators that provide access to its contents. These iterators are provided, as arguments, to an algorithm. The algorithm can then traverse, access and manipulate the contents of the container.

STL provides container classes that can be used to hold objects; similar to the way an array can be used to hold objects. They can be used to store objects of intrinsic types, such as int or double, class objects defined by C++, e.g. string, or user-friendly objects, like instances of any user defined class. Container classes handle all sizing and memory allocation issues. You can't write past the end of a container class like you can with an array. Salient features of container classes include:

· Container classes are optimized for their intended use. Some allow constant time insertions at their end, while a few others allow this anywhere. Some are better in maintaining sorted lists and some for random access retrievals. We'll learn more on this as we proceed;
· They contain utility methods such as empty(), size() and clear() that can simplify programming;
· They contain other methods that perform insertion, deletion and copying;
· They have equality, inequality and assignment operators. You can directly compare two containers or assign one to another; and
· They provide iterators, which are an abstraction of pointers. They allow similar syntax and use, but also have some built-in methods and checks that increase their utility.

Container classes are implemented as class templates. It is not necessary to understand class templates to use STL, but if you want to understand more about the design of this library you'll need this information. This tutorial only briefly discusses the design of STL.
STL provides both sequence and associative containers. Sequence containers are meant to hold a collection of objects of one type in a linear sequence. This is similar to an array. STL provides three sequence containers:

· vector - The vector class provides random access retrievals of objects at any position in constant time. This is useful if your code needs to access elements in an unordered way. You need element 1, then element 5, then element 8752 and so on. The cost (CPU clocks or time needed) of getting element 8752 can be considered to be the same constant as the cost to retrieve element 1, for instance. Vector is optimized for insertions and deletions at its end. These are also done in constant time. Insertions or deletions at positions other than the end require linear time;

· deque - The deque (pronounces deck) class also provides random access retrievals of objects at any position in constant time. Insertions and deletions at both the front and end of a deque are optimized and occur in constant time. Insertions and deletions in the middle require linear time; and

· list - The list class does not support random access retrievals. Retrievals require linear time. This is because lists are implement with an underlying doubly linked-list structure. A linked-list is a series of nodes connected by previous and next pointers. The "previous" pointer gets you to the previous element and the next pointer to the next. Insertions and deletions at any point are efficient and occur in constant time. Insertion or deletion requires onlreassignmentnt of the next and previous pointers. No elements must be moved. Insertions and deletions in the middle of vectors and lists and at the beginning of vectors require other elements to be moved. This is why they require linear time.
In addition to the containers listed above, ordinary arrays and the string class can be considered sequence containers. As will be shown later, they can also be used with the generic algorithms that provide much of the usefulness of the STL. In addition, most STL implementations also provide stack, queue and priority queue container classes. These classes are created using container adapters and one of the core STL sequence containers. 

Associative Container

The second type of container in the STL is an associative container. These support the construction of hashes and sets. A set is a collection of keys. It can be used to determine whether a particular object is present or not. A hash is a collection of key, value pairs. Each value may be inserted by key and located by its key. All associative containers in the STL are sorted. That is, based on key, as elements are inserted, they are stored sorted. This allows fast retrieval. There are four associative containers that are part of STL. These classes are implemented as templates in the library.

· set - The set container holds unique keys of any type. It provides for fast retrieval of keys and tests for presence of particular keys;
· multiset - The multiset container also holds keys of any type, but they need not be unique. Multiple copies of each key may be stored. Moults also provide for fast key retrieval;
· map - A map is a hash. It stores objects of one type, the values, in a sorted order based on objects of another type, the keys. Maps are also optimized for fast retrieval of values by key; and
· multi map - Allows storage of values based on keys. The keys may be duplicated.
Some containers support only certain types of iterators. Each of the algorithms requires certain types of iterators. By matching a container providing the correct type of iterator with the iterator requirements of an algorithm, efficiency in the use of the library is maintained. Let's look at the different types of iterators:

· Input Iterator: This iterator is read-only, i.e. it cannot be assigned to. It must support *, ==, =- and ++ operations.
· Output Iterator: This iterator is write-only. It cannot be read. It must support * and ++ operators;
· Forward Iterator: Read/Write iterator. It must support *, ==, =- and ++ operations;
· Bi-directional Iterator: Read/Write iterator. It must support *, ==, =-, ++ and – operations; and
· Random Access Iterator: Read/Write iterator. It must support *, ==, =-, ++, --, +, +=, -, -=, <, <=, > and >= operations.

Note that the iterators are actually part of an inheritance hierarchy. A random access iterator is a bidirectional iterator. A bidirectional iterator is a forward iterator.

Now, let's look at a simple example that shows how iterator requirements of the algorithms and the iterator capabilities of the containers shape the choice of both container and algorithm in our code. Let's assume that we have a sequence of numbers that must be stored and sorted. The prototype of the sort algorithm is as follows.

template<class RandomAccessIterator>
void sort(RandomAccessIterator _First, RandomAccessIterator _Last);

Sort is implemented as a template and it requires a random access iterator. To use sort we must choose a container that provides random access iterators. Vector and deque satisfy this requirement, but list does not. List only provides bidirectional iterators, as a result of its underlying doubly linked-list implementation. You cannot randomly access elements in a linked list. You must traverse the list to get to a particular element. Again, this matching of containers and algorithms helps to maintain efficiency.

Generic algorithms

The generic algorithms provide functions that implement many common programming tasks in an efficient manner. We'll explore these algorithms in detail later in the tutorial. For now, I'll just list them so that you can see the wide range of algorithms available. Many of the algorithms have overloaded function signatures. That is, they have versions that take different numbers and/or types of arguments. Here is a list of the algorithms. You can surmise their use from their names. The suffix "if" on some of the method name indicates that the method takes a function object as an argument. We'll see more on this shortly. The suffix "copy" indicates that the method copies its results into a destination container.
The point to take away is that there are many algorithms available and before writing code, check to see if an existing algorithm can suffice.
Many of the generic algorithms perform some type of comparison or test as they execute. For instance, count function returns the number of elements equal to some value. The find function returns an iterator containing the location of the first element equal to some value. If this were the limit to the flexibility of these algorithms they would still be useful, but STL was designed to make the algorithms significantly more flexible and useful. Many of the algorithms have versions that take a function or function object as a parameter. Function objects are classes that have the function operator, (), overloaded. These functions or function objects usually take one or two parameters and return a Boolean, or true/false value. A function that returns a Boolean value is also called a predicate. Let's see how a predicate can be used to extend the functionality of the count algorithm. See code 1.

Code-1.

OUTPUT:
2 elements equal to 25
1 elements less than 25
2 elements greater than 23 

Notice how the behavior of count is modified when a predicate, such as the functions less or more, is provided as a parameter. Instead of a simple function (as shown in this example) a class that overloads the function operator, (), could also be used. We will see the benefits of this in a later lesson. Also, please note that STL provides built-in function objects via the functional include file. This will be covered in a later lesson.

Adapters

Adapters modify the interface or the behavior of other STL components. Adapters can be used to modify iterators, containers or function objects. For example, an iterator can be modified into a reverse iterator that traverses a container in the opposite direction. A vector can be modified into a stack using a container adapter. Function adapters can change the behavior and interface of function objects. Let's redo the last example using two binary predicates that are part of STL, less and greater. Less compares two values and returns true if the first is less than the second. Greater returns true if the second is greater than the first. In the previous page, we counted values in a vector less that 25 and greater than 25. We want to use these predicates with the "second" value hard coded to 25. To do this using the STL provided less and greater function objects, we need to use an adapter, bind2nd, which binds the second value in these function objects to 25. For now, you only need to see how adapters can greatly extend the usefulness of other STL components. We'll handle all the details in later lessons. Check out code 2.

Code 2

OUTPUT:
2 elements equal to 25
1 elements less than 25
2 elements greater than 23