Here are some key terms that you may find useful for reading Standard Template Library (STL) literature and documentation.
A container is an object that stores objects as its elements. Normally, it’s implemented as a class template that has methods for traversing, storing, and removing elements. Examples of container classes are list and vector.
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 confined to a specific data type or a subset of types. Rather, it can store any built-in or a user-defined type. Such a container is said to be generic. A generic container provides a uniform interface regardless of the actual type of elements it stores. Note that a string, for instance, can only contain characters; therefore, it’s not generic. Genericity is perhaps the most important characteristic of STL.
A set of operations applied to an object or a sequence of object that accesses or manipulates the data therein in a specified manner and returns a result accordingly. Examples of algorithms are sort(), copy(), and remove(). STL algorithms are implemented as function templates that usually take iterators bound to a sequence of elements.
An iterator is an object that behaves like a generic pointer. Iterators are used for traversing, adding, and removing container elements. In many ways, they behave like ordinary pointers except that they are generic and safer. Iterators are classified into subcategories that characterize their capabilities. These subcategories include input iterators, forward iterators, bidirectional iterators, and more.
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 sort() algorithm, you can control whether the sorting order is descending or ascending. STL also defines several kinds of sequence adaptors, which transform a container to a different container with a more restricted interface. A stack, for instance, is built from a queue container 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 methods. An implementation is allowed to offer better performance but not worse. In other words, the limits express the worst case scenario. The Big Oh notation enables you to evaluate the efficiency of algorithms and containers for a given operation. For instance, an algorithm such as find(), that traverses every element is a sequence (in the worst case scenario) has the following notation:
T(n) = O(n). // a linear operation