TThe Standard Template Library (STL) is a collection of template-based classes and functions provided by the C++ standard library. It provides commonly required data structures and algorithms, such as lists, stacks, arrays and sorting, without requiring the programmer to write them from scratch.
The STL is built around several main components:
- Containers – objects used to store collections of data, such as vector, list, stack and array.
- Iterators – objects used to access and move through the elements stored in containers.
- Algorithms – functions that perform operations on data, such as sorting, searching and copying.
These components are designed to work together. For example, an algorithm can use an iterator to access the elements stored in a container.
The STL therefore provides a collection of reusable, general-purpose components that can make C++ programs shorter, easier to develop and easier to maintain.
Containers
Containers are STL components used to store collections of objects. Each container provides functions for adding, removing, accessing and managing the objects it contains.
For example, a list provides operations for inserting and removing elements, while a stack provides operations such as push() and pop() for adding and removing elements according to the stack’s last-in, first-out (LIFO) structure.
The standard library provides several types of containers, which can be broadly divided into:
- Sequence containers
- Associative containers
- Container adapters
Sequence Containers
Sequence containers store elements in a linear sequence. The elements have a defined order, although the way that order is maintained depends on the particular container.
The STL provides five sequence container classes:
std::vector – The vector class implements a dynamic array and thus can grow as required. . Its elements are stored in contiguous memory, and individual elements can be accessed using the standard array subscript notation:
Vectors provide very fast direct access to their elements. Adding or removing elements at the end is generally very efficient, although inserting or removing elements elsewhere can require other elements to be moved. A vector is therefore particularly useful when fast random access is required and most insertions and removals occur at the end.
#include <iostream>
#include <forward_list>
int main()
{
std::forward_list<int> numbers;
numbers.push_front(30);
numbers.push_front(20);
numbers.push_front(10);
for (int number : numbers)
{
std::cout << number << '\n';//list contents of numbers
}
auto it = numbers.begin();
std::advance(it, 0);
numbers.erase_after(it);//erase 2nd element
numbers.pop_front();//erase 1 element
for (int number : numbers)
{
std::cout << number << '\n';//lists remaining contents of number
}
return 0;
}
std::deque – A deque (double-ended queue) provides fast access to individual elements and allows elements to be efficiently added or removed at both the beginning and the end. Unlike a vector, a deque does not require all of its elements to be stored in one contiguous block of memory. It nevertheless supports random access using the subscript operator. A deque is generally less efficient than a vector when elements need to be inserted or removed in the middle of the sequence.
#include <iostream>
#include <deque>
int main()
{
std::deque<int> numbers;
numbers.push_back(20);//add 20 to the end of the deque.
numbers.push_back(10);//add 10 to the end of the deque.
numbers.push_front(109);//add 109 to the beginning (front) of the deque.
numbers.insert(numbers.begin() + 2, 30);//insert at 2 places after start
for (int number : numbers)
{
std::cout << number << '\n';//display all values in numbers
}
numbers.pop_front();//removes last number added
std::cout << numbers.at(0) << '\n';
numbers.pop_back();//removes first number added
numbers.erase(numbers.begin() + 1);//remove value one place after start
std::cout << "After removing:\n";
for (int number : numbers)
{
std::cout << number << '\n';
}
return 0;
}
std::list – A list is a doubly linked list. Each element is connected to the previous and next elements, allowing the list to be traversed in either direction.
Insertion and removal can be performed in constant time when an iterator to the required position is already available. However, a list does not provide direct random access to an element by its position. Finding a particular position in the list can therefore require the elements to be traversed one at a time. They also consume some extra memory to keep the linking information associated with each element.
A list also requires additional memory for the links connecting its elements.
#include <iostream>
#include <list>
int main()
{
std::list<int> numbers;
numbers.push_back(20);
numbers.push_back(30);
numbers.push_front(10);
for (int number : numbers)
{
std::cout << number << '\n';//listv 3 values
}
numbers.pop_back();//remove the last element from the container.
std::cout << numbers.size() << '\n';//outputs number of elements left
auto it = numbers.begin();//creates an iterator called it that points to the first item in numbers.
std::advance(it, 1);//move the iterator it forward by 1 element.
std::cout << *it << '\n';//outputs iterator value
numbers.pop_front();//removes first element in container
std::cout << numbers.front() << '\n'; //returns first element in container
return 0;
}
std::forward_list – A forward_list is a singly linked list. Each element contains a link to the next element, allowing the list to be traversed in one direction only.
Like std::list, insertion and removal can be performed efficiently when the required position is already known. However, elements cannot be accessed directly by position, so finding an element may require the list to be traversed.
Because each element only needs a link to the next element, a forward_list uses less linking information than a std::list.
The main drawback of forward_lists is that like the standard list, they lack direct access to the elements by their position and consume extra resources to keep the linking information current.
#include <iostream>
#include <forward_list>
int main()
{
std::forward_list<int> numbers;
numbers.push_front(30);
numbers.push_front(20);
numbers.push_front(10);
for (int number : numbers)
{
std::cout << number << '\n';
}
auto it = numbers.begin();
// std::advance(it, 0);
numbers.erase_after(it);//removes the 2nd element from a std::forward_list.
numbers.pop_front();//removes the first element from a std::forward_list.
std::cout << "After removing first and third\n";
for (int number : numbers)
{
std::cout << number << '\n';
}
return 0;
}
std::array class – An array is a fixed-size container that stores its elements in contiguous memory. Unlike a built-in C++ array, std::array is a class template and provides standard container operations such as size(), begin() and end().
The size of a std::array is fixed when the type is declared and cannot be changed during the lifetime of the object. Unlike a built-in array, a std::array is an object rather than an array. This allows it to be copied, assigned and passed to functions as a normal C++ object while retaining information about its size.
#include <iostream>
#include <array>
int main()
{
std::array<int, 3> numbers = {10, 20, 30};
std::cout << numbers[0] << '\n';
std::cout << numbers[1] << '\n';
std::cout << numbers[2] << '\n';
return 0;
}
std::vector is a dynamic array that allows fast access by index and is usually the general-purpose choice; std::deque is similar but is efficient at adding and removing elements at both the front and back; std::list is a doubly linked list that does not support index access but allows efficient insertion and removal at known positions; std::forward_list is a simpler singly linked list that can only move forwards; and std::array is a fixed-size array that supports index access but cannot grow or shrink.
Associative Containers
Associative containers are designed to store data so that elements can be quickly found using a key or value. Some associative containers maintain their elements in sorted order, while others use a hash table and do not maintain any particular order. C++ associative containers can be divided into two groups:
- Ordered → elements are maintained in sorted order.
- Unordered → elements are not sorted and are organised using a hash table.
The ordered associative containers are: std::set, std::map, std::multiset,std::multimap
The ordered containers generally provide efficient searching, insertion, and deletion using a tree-based data structure. The unordered containers generally provide very fast searching, insertion, and deletion by using a hash table, although their elements are not kept in sorted order.
std::set – searches using the value itself as the key
#include <iostream>
#include <set>
int main()
{
std::set<int> numbers;
numbers.insert(30);
numbers.insert(10);
numbers.insert(20);
numbers.insert(20);//displicate value not inserted
auto it = numbers.find(10);//find value 19
if (it != numbers.end())
{
std::cout << *it << '\n';//display value 10
}
numbers.erase(it);//erase value 10
std::cout << "display remaining values" << '\n';//display remaining values
for (int number : numbers)
{
std::cout << number << '\n';//display remaining values
}
return 0;
std::map – searches using a key
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> ages;
// Add values
ages["John"] = 25;
ages["Mary"] = 30;
ages["Bob"] = 22;
// Access a value
std::cout << ages["Mary"] << std::endl;
//erase value
ages.erase("Mary");
// Loop through the map
for (const auto& item : ages) {
std::cout << item.first << " = "
<< item.second << std::endl;
}
return 0;
}
std::multiset – is like a std::set, except duplicate values are allowed.
#include <iostream>
#include <set>
int main() {
std::multiset<int> numbers;
numbers.insert(10);
numbers.insert(20);
numbers.insert(30);
numbers.insert(10);
for (int n : numbers) {
std::cout << n << " ";
}
return 0;
}
std::multimap – allows duplicate values/keys
#include <iostream>
#include <map>
using namespace std;
int main()
{
multimap<string, int> ages;
ages.insert({"John", 25});
ages.insert({"John", 30});
ages.insert({"Mary", 28});
ages.insert({"John", 35});
ages.insert({"Ann", 35});
auto range = ages.equal_range("John");
//delete value where john=30
for (auto it = range.first; it != range.second; ++it)
{
if (it->second == 30)
{
ages.erase(it);
break;
}
}
//display full range
for (auto item : ages)
{
cout << item.first << " = " << item.second << endl;
}
}
If you mainly need fast lookup and don’t care about order, an unordered container is often the most appropriate choice. The unordered associative containers are:
- std::unordered_set – Stores unique values using a hash table, with no particular order. Functionally similar to
std::set - std::unordered_map – Stores unique keys with associated values using a hash table, with no particular order. Functionally similar to
std::map - std::unordered_multiset – Stores values using a hash table and allows duplicates. Functionally similar to
std::multiset - std::unordered_multimap – Stores key/value pairs using a hash table and allows duplicate keys. Functionally similar to
std::multimap
Container Adapters
Container adapters provide a restricted interface to an underlying container and are designed for particular ways of organising and accessing elements. The main container adapters are:
std::stack — Stores elements in a LIFO (last-in-first-out) fashion. Elements are inserted (pushed) and removed (popped) from the top of the stack.
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);
cout << numbers.top() << endl; // 30
numbers.pop();
cout << numbers.top() << endl; // 20
}
std::queue — Stores elements in a FIFO (first-in-first-out) fashion. Elements are inserted at the back of the queue and removed from the front.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);
cout << numbers.front() << endl; // 10
numbers.pop();
cout << numbers.front() << endl; // 20
}
std::priority_queue — Stores elements so that the element with the highest priority is always available at the top of the queue. By default, the element with the highest value has the highest priority.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
priority_queue<string> q;
q.push("Apple");
q.push("Orange");
q.push("Banana");
cout << q.top() << endl; // Orange
}
Iterators
Iterators provide a way to access and move through the elements of a container. They work in a similar way to pointers, allowing you to move from one element to another and, where supported, read or modify the element being accessed.
There are five traditional categories of iterators:
Bidirectional iterator – Can read and modify elements and can move both forwards and backwards through a container.
#include <iostream>
#include <list>
using namespace std;
int main(){
list<int> numbers = {10, 20, 30, 40};
auto it = numbers.begin();
cout << *it << endl; // 10
++it;
cout << *it << endl; // 20
++it;
cout << *it << endl; // 30
--it;
cout << *it << endl; // 20
}
Forward iterator – Can read and modify elements and can move forwards through a container. It cannot move backwards.
#include <iostream>
#include <forward_list>
using namespace std;
int main()
{
forward_list<int> numbers = {10, 20, 30, 40};
auto it = numbers.begin();
cout << *it << endl; // 10
++it;
cout << *it << endl; // 20
++it;
cout << *it << endl; // 30
}
Input iterator – Can read elements and move forwards through a container. It cannot be used to modify the elements.
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
istream_iterator<int> it(cin);//enter character separated by white space
istream_iterator<int> end;
cout << *it << endl;
++it;
cout << *it << endl;
}
Output iterator – Can write elements and move forwards through a container. It cannot be used to read the elements.
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
ostream_iterator<int> output(cout, " ");
*output = 10;
++output;
*output = 20;
++output;
*output = 30;
}
Random access iterator – Can read and modify elements and can move forwards and backwards. It also allows elements to be accessed directly using an offset, much like an array.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> numbers = {10, 20, 30, 40, 50};
vector<int>::iterator it = numbers.begin();
cout << *it << endl; // 10
it += 3;
cout << *it << endl; // 40
it -= 2;
cout << *it << endl; // 20
cout << it[2] << endl; // 40
}
STL Algorithms
Algorithms provide functions for performing common operations on data stored in containers. Each container provides its own basic operations, but the standard algorithms library provides a much wider range of functionality.
STL algorithms are designed to work with different container types through iterators. This means that the same algorithm can often be used with different containers without having to write separate code for each container.
The algorithms provided by the STL cover a wide range of operations, including:
Sorting – arranging elements into a particular order.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> numbers = {50, 20, 40, 10, 30};
sort(numbers.begin(), numbers.end());
for (int n : numbers)
{
cout << n << " ";
}
}
Searching – finding elements that match a specified value or condition.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> numbers = {10, 20, 30, 40, 50};
auto it = find(numbers.begin(), numbers.end(), 30);
if (it != numbers.end())
cout << "Found: " << *it << endl;
else
cout << "Not found" << endl;
}
Modifying – changing, copying, moving, or rearranging elements.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> numbers = {10, 20, 30, 20, 40};
replace(numbers.begin(), numbers.end(), 20, 99);
for (int n : numbers)
cout << n << " ";
}
Non-modifying – examining or processing elements without changing them.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> numbers = {10, 20, 20, 30, 20};
int result = count(numbers.begin(), numbers.end(), 20);
cout << "20 appears " << result << " times";
}
Minimum and maximum – finding the smallest or largest element.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> numbers = {40, 10, 30, 50, 20};
auto min = min_element(numbers.begin(), numbers.end());
auto max = max_element(numbers.begin(), numbers.end());
cout << "Minimum: " << *min << endl;
cout << "Maximum: " << *max << endl;
}
Using the standard algorithms can save time and effort because many common operations are already implemented and tested as part of the C++ standard library.
The following code sample uses template lists to create and manipulate an int vector