Standard Template Library in C++

Reading time: 10 minutes

Standard Template Library in C++ is a pre-defined generic implementation of most widely used data structures and algorithms. By generic implementation it means that there is a single implementation of various Classes and Functions which works with multiple datatypes by the use of templates.

STL at heart is mainly composed of 4 parts. These 4 parts are :

  • Algorithms : They are the operations or data manipulation schemes done on the data stored in the containers.
  • Functions : To allow the behavior of the associated function to be parameterized
  • Containers : They are the data-structures used to store data efficiently.
  • Iterators : They can be considered as tools which are used to access the data stored in the containers and also traverse them.

But the question which comes to our mind is why bother studying STL and is it useful? Well we will come to know about this within a few minutes.

STL in its entirety is too complex and its features are too many to be discussed in a single article. We will discuss the most widely used features here.

The best advantage of STL is that it can considerably save your time and effort and can lead to high quality programs. You do not have to reinvent the wheel and test it. The classes and functions implemented are already well-tested and what we do is basically "reuse" the well-written and well-tested components of the STL. Further they are very easy to use and provide fast, efficient and robust code.

Algorithms

A large number of algorithms to perform activities such as searching and sorting are provided in the STL, each implemented to require a certain level of iterator (and therefore will work on any container that provides an interface by iterators). Searching algorithms like binary_search and lower_bound use binary search and like sorting algorithms require that the type of data must implement comparison operator or custom comparator function must be specified; such comparison operator or comparator function must guarantee strict weak ordering. Apart from these, algorithms are provided for making heap from a range of elements, generating lexicographically ordered permutations of a range of elements, merge sorted ranges and perform union, intersection, difference of sorted ranges.

u00220020606KXS01_03-1

Functions

The STL includes classes that overload the function call operator (operator()). Instances of such classes are called functors or function objects. Functors allow the behavior of the associated function to be parameterized (e.g. through arguments passed to the functor's constructor) and can be used to keep associated per-functor state information along with the function. Since both functors and function pointers can be invoked using the syntax of a function call, they are interchangeable as arguments to templates when the corresponding parameter only appears in function call contexts.

A particularly common type of functor is the predicate. For example, algorithms like find_if take a unary predicate that operates on the elements of a sequence. Algorithms like sort, partial_sort, nth_element and all sorted containers use a binary predicate that must provide a strict weak ordering, that is, it must behave like a membership test on a transitive, non reflexive and asymmetric binary relation. If none is supplied, these algorithms and containers use less by default, which in turn calls the less-than-operator.

Container

Containers or container classes store objects and data. There are in total seven standard “first-class” container classes and three container adaptor classes and only seven header files that provide access to these containers or container adaptors.

u00220020606KXS01_01-1

  • Sequence Containers: implement data structures which can be accessed in a sequential manner such as:

    • vector
    • list
    • deque
    • arrays
    • forward_list( Introduced in C++11)
  • Container Adaptors : provide a different interface for sequential access

    • containers.
    • queue
    • priority_queue
    • stack
  • Associative Containers: implement sorted data structures that can be quickly searched (O(log n) complexity).

    • set
    • multiset
    • map
    • multimap

Iterators

  • The STL implements five different types of iterators. These are input iterators (that can only be used to read a sequence of values), output iterators (that can only be used to write a sequence of values), forward iterators (that can be read, written to, and move forward), bidirectional iterators (that are like forward iterators, but can also move backwards) and random access iterators (that can move freely any number of steps in one operation).

  • It is possible to have bidirectional iterators act like random access iterators, so moving forward ten steps could be done by simply moving forward a step at a time a total of ten times. However, having distinct random access iterators offers efficiency advantages. For example, a vector would have a random access iterator, but a list only a bidirectional iterator.

  • Iterators are the major feature that allow the generality of the STL. For example, an algorithm to reverse a sequence can be implemented using bidirectional iterators, and then the same implementation can be used on lists, vectors and deques. User-created containers only have to provide an iterator that implements one of the five standard iterator interfaces, and all the algorithms provided in the STL can be used on the container.

  • This generality also comes at a price at times. For example, performing a search on an associative container such as a map or set can be much slower using iterators than by calling member fu**nctions offered by the container itself. This is because an associative container's methods can take advantage of knowledge of the internal structure, which is opaque to algorithms using iterators.

u00220020606KXS01_02-1

Uses

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.

Take a look at this article for the most commonly used utilities in Standard Template Library in C++:

iq.opengenus.org/standard-template-library-cpp