Introduction to Standard Template Library(STL) in C++: A Complete Guide

👁️ : 4,821

In this lesson, you will learn.

Introduction to STL in C++
Why STL?
Component of STL
Containers
Algorithms
Iterators

1. Introduction to STL in C++

The Standard Template Library (STL) is a powerful set of C++ template classes and functions that provide ready-to-use data structures and algorithms.

It offers a wide range of containers, such as vectors, lists, and maps, along with algorithms for efficiently sorting, searching and manipulating data.

STL components are defined in the namespace std.

2. Why STL

The STL simplifies complex programming tasks, making code more concise, readable, and reusable.

By leveraging the STL, you can enhance your productivity, improve code quality, and focus on problem-solving rather than reinventing the wheel.

3. Component of STL

There are three key components of STL as shown in the below Figure.

Containers- Provide efficient ways to store and manage the data.

Algorithms- Provide algorithms for tasks like sorting, searching, and manipulating the data.

Iterators – Provide a uniform way to traverse and manipulate elements within containers.

4. Containers

The containers are objects that are used to store the data whether the data consists of built-in types such as int and float, or of class objects.

Now, containers are further classified into three categories and comprise 10 different containers (e.g. vector, list, set, etc.)

Why Many Containers Required?

Why not use C++ arrays in all data storage situations?

The answer is efficiency. An array is slow in many situations.

4.1. Sequence Container

A sequence container stores the elements in a linear order like a linked list or houses on a street.

The main sequence containers in C++ include:

Vector (std::vector):
- A dynamic array that automatically adjusts its size.
- Efficient for random access and appending elements at the end.
List (std::list):
- Doubly-linked list where each element contains a link to the next and previous elements.
- Efficient for insertion and deletion at any position.
Deque (std::deque):
- Double-ended queue that allows fast insertion and deletion at both ends.
- Implemented as a sequence of dynamically allocated fixed-size arrays.

Important Note!

An ordinary C++ array is an example of a sequence container.

Problems with Using an Array as a Container

Problem -1: You must specify the array size at compile time causing either waste space in memory by not filling the array or elicit an error message by running out of space.

Solution: Vector Container

Problem 2: If you now want to insert a new employee whose name starts with L in a sorted list based on their last name, you must move all the employees from M to Z to make room.

Solution: The STL provides the list container, which is based on the idea of a linked list, to solve this problem.

Here is the summary table of the Sequence Container

S.N	Container	Characteristics	Advantages/Disadvantages
1.	C++ Array	Fixed-Size	1. Quick random access (by index number). 2. Slow to insert or erase in the middle. 3. Size cannot be changed at runtime.
2.	Vector	Expandable Array	1. Same. 2. Same. 3. Quick to insert or erase at the end.
3.	List	Doubly Linked List	1. Quick to insert or delete at any location. 2. Quick access to both ends. 3. Slow random access
4.	Dequeue	Accessed from both ends	1. Same 2. Slow to insert or erase in the middle. 3. Quick insert or erase (push and pop) at either the beginning or the end.

4.2. Associative Container

An associative container is not sequential instead, it uses keys to access data.

The keys, typically numbers or strings, are used automatically by the container to arrange the stored elements in a specific order.

It’s like an ordinary English dictionary

Associative containers store data in a structure called a tree, which offers fast searching, insertion, and deletion.

The following are the four types of associative containers.

Set:

A set is a container that stores unique elements in a sorted order.
It does not allow duplicate elements, so each element in the set must be unique.
Elements are automatically sorted in ascending order based on their values.
Common operations on sets include insertion, deletion, and searching for an element.

Multiset:

A multiset is similar to a set but allows duplicate elements.
Elements are still sorted based on their values, but multiple elements with the same value are allowed.

Map:

A map is a container that stores key-value pairs in a sorted order based on the keys.
Each key must be unique, and associated with it is a value.
Like set, elements are automatically sorted based on the keys.
Common operations on maps include insertion, deletion, and searching for a key.

Multimap:

A multimap is similar to a map but allows multiple key-value pairs with the same key.
Elements are still sorted based on the keys.

Note: The difference is set is used to store only keys while a map is used to store key-value pairs.

Note: The map and set containers allow only one key of a given value to be stored. On the other hand, the multimap and multiset containers allow multiple keys.

4.3. Container Adapter

Container adapters are not standalone containers but adapt existing containers to provide a different interface also called a derived container.

Stack (std::stack):
- LIFO (Last In, First Out) data structure, typically implemented using a deque.
Queue (std::queue):
- FIFO (First In, First Out) data structure, typically implemented using a deque.
Priority Queue (std::priority_queue):
- Queue where elements have priorities and the element with the highest priority is served first.

5. Algorithms

An algorithm is a function that does something to the items in a container (or containers).

The following table shows the list of common algorithms.

S.N	Algorithms	Purpose
1.	find	Returns first element equivalent to a specified value
2.	count	Returns first element equivalent to a specified value
3.	equal	Compares the contents of two containers and returns true if all corresponding elements are equal
4.	search	Compares the contents of two containers and returns true if all corresponding elements are equal
5.	copy	Copies a sequence of values from one container to another (or to a different location in the same container)
6.	swap	Exchanges a value in one location with a value in another
7.	iter_swap	Exchanges a sequence of values in one location with a sequence of values in another location
8.	fill	Copies a value into a sequence of locations
9.	sort	Sorts the values in a container according to a specified ordering
10.	merge	Combines two sorted ranges of elements to make a larger sorted range
11.	accumulate	Returns the sum of the elements in a given range
12.	for_each	Executes a specified function for each element in the container

6. Iterators

Iterators are pointer-like entities that are used to access individual data items (which are usually called elements).

There are three major classes of iterators:

Forward Iterators

A forward iterator can only move forward through the container, one item at a time.

Its ++ operator accomplishes this and can’t move backward and it can’t be set to an arbitrary location in the middle of the container.

Bidirectional Iterators

A bidirectional iterator can move backward as well as forward, so both its ++ and — operators are defined.

Randon Access Iterators

A random access iterator, in addition to moving backward and forward, can jump to an arbitrary location.

There are also two specialized kinds of iterators.

An input iterator can “point to” an input device (cin or a file) to read sequential data items into a container, and an output iterator can “point to” an output device (cout or a file) and write elements from a container to the device.

The following table shows the characteristics of different iterators.

S.N.	Iterator Type	Read/Write	Iterator Saved?	Direction	Access
1.	Random Access	Read and Write	Yes	Forward and Back	Random
2.	Bidirectional	Read and Write	Yes	Forward and Back	Linear
3.	Forward	Read and Write	Yes	Forward Only	Linear
4.	Output	Write Only	No	Forward Only	Linear
5.	Input	Read Only	No	Forward Only	Linear