[C/C++] - Tips for STL

The Standard Template Library (STL) has revolutionized the way C++ programmers write code. It brings code reuse to new levels of productivity and it saves huge amounts of time that would have otherwise been spent on reinventing wheels. Yet, it's a full-blown framework, with a peculiar jargon and intricate rules that you have to master in order to learn how to use it effectively. To shed some light on certain aspects of STL, I decided to include no less than six tips under this category.

Naturally, the first tip describes the basic constituents of STL and some of its key terms.

The next tip deals with template definitions. As you probably know, templates are the building bricks of STL containers and algorithms. The following three tips describe techniques of using the std::vector container—the most widely-used STL container. We will learn how to properly store pointers to objects in a vector and how to avoid common pitfalls; we will see how to treat a vector object as if it were a built-in array. The fifth tip in this category will show you how to use vectors to imitate a multidimensional array. Finally, the closing tip in this category teaches a very important lesson about the interaction of std::auto_ptr and STL.

Tip 14: Useful STL Terminology

Here are some key terms that you may find useful when reading Standard Template Library (STL) literature and documentation.

Container

A container is an object that stores objects as its elements. Normally, it's implemented as a class template that has member functions for traversing, storing and removing elements. Examples of container classes are std::list and std::vector.

Genericity

The quality of being generic, or type-independent. The above definition of the term container is too loose because it may apply to strings, arrays and structs, which also store objects. However, a real container isn't limited to a specific data type or a set of types. Rather, it can store any built-in and user-defined type. Such a container is said to be generic. Note that a string can only contain characters. Genericity is perhaps the most important characteristic of STL. The third tip presents the standard base classes for function objects. Since function objects are one of the constituents of generic programming, adhering to standard conventions in their design and implementation will save you a lot of difficulties.

Algorithm

A set of operations applied to a sequence of objects. Examples of algorithms are std::sort(), std::copy(), and std::remove(). STL algorithms are implemented as function templates taking iterators.

Adaptor

An adaptor is a special object that can be plugged to an exiting class or function to change its behavior. For example, by plugging a special adaptor to the std::sort() algorithm, you can control whether the sorting order is descending or ascending. STL defines several kinds of sequence adaptors, which transform a container to a different container with a more restricted interface. A stack, for instance, is often formed from queue”“ and an adaptor that provides the necessary push() and pop() operations.

Big Oh Notation

A special notation used in performance measurements of algorithms. The STL specification imposes minimum performance limits on the operations of its algorithms and container operations. An implementation may offer better performance but not worse. The Big Oh notation enables you to evaluate the efficiency of algorithms and containers for a given operation and data structure. An algorithm such as std::find(), which traverses every element is a sequence (in the worst case scenario) has the following notation:

T(n) = O(n). /* linear complexity */

Iterator

An iterator is an object that functions as a generic pointer. Iterators are used for traversing, adding and removing container elements. STL defines five major categories of iterators:

input iterators and output iterators
forward iterators
bidirectional iterators
random access iterators

Note that this list doesn't represent inheritance relationships; it merely describes the iterator categories and their interfaces. Each lower category is a superset of the category above it. For instance, a bidirectional iterator provides all the functionality of a forward iterators plus additional functionality. Here is a brief summary of the functionality and interfaces for these categories:

· Input iterators allow an algorithm to advance the iterator and offer read-only access to an element.

· Output iterators allow an algorithm to advance the iterator and offer write-only access to an element.

· Forward iterators support both read and write access, but traversal is permitted only in one direction.

· Bidirectional iterators allow the user to traverse the sequence in both directions.

· Random access iterators support random jumps and "pointer arithmetic" operations, for example:

string::iterator it = s.begin();

char c = *(it+5); /* assign sixth char to c*/