What is STL in C++?

The Standard Template Library or STL in C++ is a collection of template classes and template functions that provide a generic way of programming. It is a library of container classes, algorithms, and iterators.

It is commonly used for efficiently programming data structures, algorithms, and functions. Some built-in data structures include arrays, vectors, queues, etc.

Components of STL in C++

There are four major components of STL in C++:

1. Containers
2. Iterators
3. Algorithms
4. Function objects or Functors

In this article, we are mainly concerned about the first three components of C++ STL.

Containers

• A container is a holder object that stores other objects as elements. It is used to implement different data structures.
• They are implemented as class templates (templates use data types as parameters), allowing greater flexibility in the types supported as elements.
• The containers manage storage space for its elements and provide member functions to access them directly or through iterators.
• They replicate the most commonly used data structures like queues (queue), dynamic arrays (vector), stacks (stack), linked lists (list), queues (queue), heaps (priority_queue), trees (set), associative arrays (map), and many others.

There are 4 types of containers of STL in C++:

1. Sequence Containers - Array - Vector - Deque - List - Forward List

2. Associative Containers - Set - MultiSet - Map - Multimap

3. Unordered Associative Containers - Unordered Set - Unordered Multiset - Unordered Map - Unordered Multimap

4. Container Adapters - Stack - Queue - Priority Queue

You can also choose the most suitable C++ STL container that matches your needs. Different criteria used for the selection are:

• The functionality offered by the container.

• The efficiency of some members. It is especially true for sequence containers, which offer complex trade-offs between inserting/removing and accessing elements.

1. Sequence Containers

• Sequence containers implement data structures that can be accessed sequentially via their position.
• It preserves the insertion order of elements.
• These are internally implemented as arrays or linked lists.

The five sequence containers supported by STL are:

a. Array

Arrays are sequential homogeneous containers of fixed size. The elements are stored in contiguous memory locations.

Syntax:

b. Vector

Vectors are dynamic arrays, allowing the insertion and deletion of data from the end. They can grow or shrink as required. Hence their size is not fixed, unlike arrays.

Syntax:

c. Deque

Deque is double-ended queue that allows inserting and deleting from both ends. They are more efficient than vectors in case of insertion and deletion. Its size is also dynamic.

Syntax:

d. List

The list is a sequence container that allows insertions and deletions from anywhere. It is a doubly linked list. They allow non-contiguous memory allocation for the elements.

Syntax:

e. Forward List

Forward Lists are introduced from C++ 11. They are implemented as singly linked list in STL in C++. It uses less memory than lists and allows iteration in only a single direction.

Syntax:

2. Associative Containers

• Associative container is an ordered (sorted) container that provides a fast lookup of objects based on the keys, unlike a sequence container which uses position.
• A value is stored corresponding to each key.
• They are internally implemented as binary tree data structures. This results in logarithmic time operations -- $O(\log n)$.

Types of associative containers:

a. Set

The set is used to store unique elements. The data is stored in a particular order (increasing order, by default).

Syntax:

b. Map

The map contains elements in the form of unique key-value pairs. Each key can be associated with only one value. It establishes a one-to-one mapping. The key-value pairs are inserted in increasing order of the keys.

Syntax:

c. Multiset

Multiset is similar to a set but also allows duplicate values.

Syntax:

d. Multimap

Multimap is similar to a map but allows duplicate key-value pairs to be inserted. Ordering is again done based on keys.

Syntax:

3. Unordered Associative Containers

• Unordered Associative Container is an unsorted version of Associative Container.
• It is important to note that insertion order is not maintained. Elements are in random order.
• These are internally implemented as a hash table data structure. This results, on average, in constant time operations -- $O(1)$

a. Unordered Set

It is used to store unique elements.

Syntax:

b. Unordered Map

It is used to store unique key-value pairs.

Syntax:

c. Unordered Multiset

It is similar to an unordered set, but the elements need not be unique.

Syntax:

d. Unordered Multimap

It is similar to an unordered map, but the duplicate key-value pairs can be inserted here.

Syntax:

4. Container Adapters in C++

• STL in C++ also consists of a special type of container that adapts other containers to give a different interface with restricted functionality. Hence the name Container Adapters.
• The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adaptor independently of the underlying container class used.
• Unlike other containers, values are not directly initialized but with the help of other supported methods.

a. Stack

A Stack is a container that provides Last-In-First-Out (LIFO) access. All the operations occur at the same place called top of the stack. It is implemented on top of a deque by default.

Syntax:

b. Queue

A queue is a container that provides First-In First-Out access. The insertion is done at the rear (back) position and deletion at the front. It is implemented on top of a deque by default.

Syntax:

c. Priority Queue

A priority Queue is similar to a queue, but every element has a priority value. This value decides what element is present at the top, which is, by default, the greatest element in the case of STL in C++. This is similar to the max heap data structure. It is implemented on top of the vector by default.

Syntax:

Iterators

• An Iterator is a pointer-like object that points to an element inside some container.
• You can use them to iterate over a container which means moving sequentially from one element to another.
• Iterators can also help you manipulate the data stored inside a container and connect algorithms to containers.
• Iterators provided by STL in C++ are analogous to using the cursor while typing some text. You can shift them to any position you want.

Iterators are classified into five categories depending on the functionalities offered. You can refer to the below diagram. Regarding functionality, the outermost iterator is the most powerful and the innermost the least powerful.

The common syntax to declare an iterator:

For example:

The two most commonly used iterators are returned by the following member functions of a container:

• begin() -- Returns an iterator to the first element of a container.
• end() -- Returns an iterator past the last element of a container.

These can be visualized in the case of a vector named v (which stores integers) as:

a. Iterator Categories

STL in C++ provides the following five iterators:

1. Input Iterator

• Input iterator is the weakest and simplest of all.
• It has limited functionality and is suitable for single-pass algorithms where you can access the elements in a container sequentially.
• It is a unidirectional iterator that only supports increment operation. Thus, it is a read-only iterator.

2. Output Iterator

• It is similar to the input iterator but works exactly the opposite.
• It is used for assignment operations that help you modify the values inside a container.
• It does not allow you to read elements from a container, i.e., it is a write-only iterator.

3. Forward Iterator

• Forward iterator is more powerful than input and output iterators.
• It combines the functionality of both the iterators (input and output).
• It permits you to access (read) and modify (write) the values of a container.
• It is also a unidirectional iterator, as the name suggests.

4. Bidirectional Iterator

• Bidirectional iterator has all the features of the forward iterator.
• It can move in both directions, i.e., backward and forward.
• So, you can use both increment (++) and decrement (--) operations.
• It does not permit the use of all relational operators.

5. Random Access Iterator

• It is the most powerful iterator.
• You can use it to access any random element inside a container.
• It supports all the functionality of the pointers, like addition and subtraction.
• It also gives you relational operator support.

b. Operation Supported by Iterators

Algorithms

• Algorithms in C++ STL define a collection of functions specially designed for use on a sequence of objects.
• These are standalone template functions, unlike member functions of a container.
• There are approximately 60 algorithm functions that help save our time and effort.
• To use algorithms, you must include the <algorithm> header file.
• They also allow you to work with multiple container types simultaneously.

STL in C++ algorithms can be broadly divided into 5 types:

1. Non-Manipulative Algorithms

• These are the non-modifying algorithms.
• They neither alter the containers' content nor change their order.
• They utilize forward iterators internally.

Some Examples: std::find -- Find value in a range std::search -- Search a range for subsequence std::count -- Count occurrences of an element in a given range

2. Manipulative Algorithms

• These are the modifying algorithms.
• They alter the contents of a container either by changing their values or modifying their order.

Some Examples: std::copy -- Copy a range of elements std::swap -- Exchange values of two objects/variables std::fill -- Fills a range with a certain value

3. Sorting Algorithms

These are modifying algorithms that are used to sort elements of a container.

Some Examples: std::sort -- Sort elements in a range std::stable_sort -- Sort elements in a range and keep the relative order of equivalent elements std::partial_sort -- Partially sort elements in a range

4. Set Algorithms

• These can improve the efficiency of a C++ program.
• These are generic set algorithms that are independent of the set container. They can also be used on any sorted STL container.
• Therefore, they are also called sorted range algorithms.

Some examples: std::merge -- Merge the sorted ranges std::includes -- Checks whether the sorted range includes another sorted range std::set_union -- Computes the set union of two sorted ranges

5. Relational Algorithms

• These are used to operate on numerical data.
• They perform some mathematical operation on all elements of a container.

Some Examples: std::equal -- Determines if two ranges of elements are equal std::lexicographical_compare -- Checks if the range is lexicographically less than another range of elements.

Learn More

To learn more about C++ STL, check out this link.