Part 9: The C++ Standard Library
By design C++ provides only the basic mechanisms to convert our ideas into machine executable actions. There are no built-in functions that perform tasks as reading keyboard input or producing any form of output. All these tasks are completed with libraries.
In the beginning the library that came along with the language was extremely limited and C++ relied a lot on its compatibility with C. The nature of the language encouraged many developers to create libraries of classes that were covering many disciplines.
In 1993 Alexander Stepanov presented a new library, based on generic programming. This library was initially called Standard Template Library or STL for short and was adopted by the ISO standardization committee in 1994. Years later its name was changed to Standard Library.
The C++ Standard Library is an excessively big topic that cannot be covered in a few lines. Dedicated books with thousands of pages have been written about it. Our aim here is to cover the basics required to understand the development of an application.
Introduction and general concepts
By the time if this writing the latest official standard of the language is C++23. The C++26 standard is in-progress. The most supported version by the compilers is C++17. C++20 is supported but not an all platforms. Only GCC and MSVC support all the features of the standard.
Standardization is a hard and slow process. Adapting to the changes in the standard is even slower.
The C++ standard library relays heavily on generic programming. It is implemented in header files, and you do not need to link your code with external libraries. All the identifiers of the library are members of the std namespace:
#include <iostream>
int main() {
std::cout << "This is the C++ Standard Library";
}
Containers
Containers in C++ are objects used to store collections of other objects. They are implemented as templates which give them the ability to adapt and store any data type.
Types of containers
There are several types of containers:
- Sequential Containers: Used to store ordered collections of objects. These include std::array, std::vector, std::deque, std::forward_list, and std::list. These containers maintain the order of insertion and can be accessed sequentially.
- Associative Containers: Implement sorted data structures that can be quickly searched. These include std::set, std::multiset, std::map, and std::multimap. They are optimized for fast search and retrieval and maintain their elements in a sorted order.
- Unordered Associative Containers: They were introduced in C++11, these containers store elements using hash tables allowing for fast access to individual elements based on their keys. This group includes std::unordered_set, std::unordered_multiset, std::unordered_map, and std::unordered_multimap.
- Container Adapters: These provide a different interface for sequential containers suited for specific tasks. They include std::stack, std::queue and std::priority_queue.
Sequential containers
Here is a brief description of the sequential containers.
std::array
This is an alternative to the C-style arrays we saw in Part 3. C++ arrays are self-aware, they know their size which is fixed and are more robust.
#include <array>
void arrays() {
std::array<int, 3> ar = { 1,2,3 };
for (int i = 0; i < 3; i++)
std::cout << ar[i] << "\n";
}
std::vector
Vectors can be considered as dynamic arrays. They have the ability to resize the memory they occupy when we insert elements. They occupy contiguous storage. They are optimized to insert and remove objects at the end of their storage. They also support adding and removing at random locations, but they are very inefficient, and they should be avoided.
#include <vector>
void vectors() {
std::vector<int> v = { 1,2,3 };
size_t s = v.size();
for (int i = 0; i < s; i++) {
std::cout << v[i] << "\n";
}
}
std::forward_list
std::forward_list is a container that implements the singly-linked list data structure. In this data structure every object ‘knows’ the one that comes after it. They do not require contiguous memory thus they are very fast and efficient in insert and remove operations anywhere in the list. It can only be searched or iterated from start to end, aka forward only, and not backward.
std::forward_list cannot be accessed with index like a vector or an array. So, we introduce a C++ feature that allows us to iterate over the objects within a container. The for loop allows us to iterate over a container like this: for (auto var_name : container) {…}. Here it is in action:
#include <forward_list>
void forw_list() {
std::forward_list<int> l;
l.assign({ 1,2,3 });
// iterate over the contents of the list
for (int i : l) {
std::cout << i << "\n";
}
}
std::list
The list container implements the double-linked list data structure. They do not require contiguous memory as well and are also very efficient in insert and remove operations. They require a little more memory than std::forward_list in order to support walking up and down the list.
#include <list>
void list_s() {
std::list<int> l;
l.assign({ 1,2,3 });
for (int i : l) {
std::cout << i << "\n";
}
}
std::dequeue
std::dequeue stands for double-ended queue. It is a sequential container specifically designed and optimize for fast insertion and removal at both ends. It is not guaranteed to store the data in contiguous memory so accessing them with index is not allowed.
#include <deque>
void dequeue_s() {
std::deque<int> d;
d.push_back(1);
d.push_front(2);
for (int i : d) {
std::cout << i << "\n";
}
}
Associative containers
Here is the list of the associative containers:
std::set
std::set is a container that stores unique elements in a specific order. The order is determined by the less operator (<). The default operator defined by C++ is used to sort the items unless define a custom operator for our objects.
#include <set>
void set_s() {
std::set<int> s;
s.insert(1);
s.insert(1); // will be rejected, duplicate
s.insert(2);
for (int i : s) {
std::cout << i << "\n";
}
}
std::multiset
std::multiset is similar to std::set, only this allows duplicate values.
#include <set>
void multiset_s() {
std::multiset<int> s;
s.insert(1);
s.insert(1); // duplicates are accepted
s.insert(2);
for (int i : s) {
std::cout << i << "\n";
}
}
std::map
std::map is a very powerful associative container that stores data in key-value pairs. Here are the key characteristics of maps:
- Sorted: std::map maintains its elements sorted based on the keys. The less operator is the default for sorting but we can customize it.
- Unique keys: duplicate keys are not allowed in maps.
We can access elements in a map using the bracket operator [].
Here are some common operations on maps.
- Insert: m.insert(std::pair
- Remove: m.erase(key);
- Lookup: m.find(key); or m.count(key);
std::multimap
std::multimap is similar to the std::map, only this allows for multiple values under the same key. Another difference is the bracket operator is not supported for multimaps.
#include <map>
void multimap_s() {
std::multimap<int, int> m;
m.insert(std::pair<int, int>(2, 1));
m.insert(std::pair<int, int>(3, 10));
m.insert(std::pair<int, int>(1, 11));
m.insert(std::pair<int, int>(1, 17));
for (auto e : m) {
std::cout << e.first << "," << e.second << "\n";
}
}
Unordered associative containers
Keeping the associative containers ordered costs in insert and remove efficiency. To compensate for that in cases we do need the elements to be ordered but we have many insert and remove operations we can use the unordered associative containers.
std::unordered_set
std::unordered_set is used to store unique elements in no particular order.
#include <unordered_set>
void unordered_set_s() {
std::unordered_set<int> s;
s.insert(2);
s.insert(1);
s.insert(1); // will be rejected, duplicate
s.insert(6);
s.insert(4);
for (int i : s) {
std::cout << i << "\n";
}
}
std::unordered_multiset
std::unordered_multiset is like std::unordered_set only this one allows for duplicate entries.
#include <unordered_set>
void unordered_multiset_s() {
std::unordered_multiset<int> s;
s.insert(2);
s.insert(1);
s.insert(1); // will be rejected, duplicate
s.insert(6);
s.insert(4);
for (int i : s) {
std::cout << i << "\n";
}
}
std::unordered_map
std::unordered_map is the unordered counterpart of std::map. It sacrifices retrieval speed (only by a margin) and order for faster insert and removal. It maintains the unique feature of the keys and ease of use of std::map.
#include <unordered_map>
void unordered_map_s() {
std::unordered_map<int, int> m;
m.insert(std::pair<int, int>(2, 1));
m.insert(std::pair<int, int>(3, 10));
m.insert(std::pair<int, int>(3, 15)); // will fail previous, no duplicates
m.insert(std::pair<int, int>(1, 11));
m[2] = 16; // will replace previous, no duplicates
for (auto i : m) {
std::cout << i.first << ", " << i.second << "\n";
}
}
std::unordered_multimap
std::unordered_multimap is similar to std::unordered_map with he exception that this allows duplicate entries. The bracket operator is not supported like std::multimap.
#include <unordered_map>
void unordered_multimap_s() {
std::unordered_multimap<int, int> m;
m.insert(std::pair<int, int>(2, 1));
m.insert(std::pair<int, int>(3, 10));
m.insert(std::pair<int, int>(3, 15));
m.insert(std::pair<int, int>(1, 11));
for (auto i : m) {
std::cout << i.first << ", " << i.second << "\n";
}
}
Container Adapters
Sequential and associative containers have all the functionality we need. Unordered associative containers add the efficiency we may need in some cases. There are times we need to have some containers that put some constraints. These are the container adapters. They are based on container already defined and they enforce the restrictions we need. These container adapters are stack, queue and priority_queue. They are meant for storage and retrieval only and do not allow iterators or random access.
std::stack
std::stack implements the classic stack data structure. The last item inserted is the first retrieved (Last-In-First-Out or LIFO).
#include <stack>
void stack_s() {
std::stack<int> s;
s.push(2);
s.push(3);
s.push(1);
while (!s.empty()) {
// retrieve last element
std::cout << s.top() << "\n";
// and remove it
s.pop();
}
}
std::queue
std::queue implements the queue data structure. In this the first element inserted is the first retrieved (First-In-First-Out or FIFO).
#include <queue>
void queue_s() {
std::queue<int> s;
s.push(2);
s.push(3);
s.push(1);
while (!s.empty()) {
// retrieve first element
std::cout << s.front() << "\n";
// and remove it
s.pop();
}
}
std::priority_queue
std::priority_queue is almost the same as std::queue only this one keeps elements ordered, hence the priority in the name.
void priority_queue_s() {
std::priority_queue<int> s;
s.push(-1);
s.push(2);
s.push(3);
s.push(1);
s.push(9);
while (!s.empty()) {
// retrieve first element
std::cout << s.top() << "\n";
// and remove it
s.pop();
}
}
Iterators
The iterators are objects that help us traverse through the elements of a container and access them.Types of iterators
Iterators are classified based on their functionality.
Input Iterators: These are used to read elements from a container in a single-pass algorithm.
Output Iterators: These are used to write elements to a container in a single-pass algorithm.
Forward Iterators: These can read and write elements and can move forward through the container.
Bidirectional Iterators: These are like forward iterators, plus they can move backward through the container.
Random-Access Iterators: These are the most powerful iterators, allowing direct access to any element in the container, similar to a pointer.
Basic usage
Iterators are based on the container they access. Here is how we declare an iterator to a vector:
std::vector<int> v={ 1,4,5,3,8,7,6 };
std::vector<int>::iterator it;
The container provides methods to initialize the iterator, in the case of the std::vector we have the v.begin(), which returns an iterator to the first element.
The iterator marches using the increment operator ++. We can check if we have reached the end of the vector using the v.end() member function. This returns one past the last element. Here is how we go through the element of the vector.
void iterators_s() {
std::vector<int> v={ 1,4,5,3,8,7,6 };
for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
std::cout << *it << "\n";
}
Benefits of Iterators
Convenience: Iterators abstract the details of the container, making it easier to write generic algorithms.
Flexibility: They allow algorithms to work with different types of containers without modification.
Safety: Iterators provide bounds checking, reducing the risk of accessing invalid memory.
Algorithms
C++ offers a rich set of algorithms through the Standard Library, which provides functions for sorting, searching, and manipulating data structures like arrays and vectors. This gives us the benefit of standard code that is highly optimized and debugged. We can focus on our problems and be sure that the tools we use are of the highest quality.
What sets the C++ algorithms apart from other language implementations is that they operate on iterators and not on containers. As long as your data storage implements iterators correctly the algorithms can be used.
The algorithms library relies heavily on function objects. That is our chance to inject our logic and modify the behavior of the algorithms.
Here are some commonly used algorithms:
Sorting
This group of algorithms sorts a given range of values, based on the iterators we pass.
std::sort
The first and most basic sorting algorithm in the library. It comes in two flavors. The first compares two objects using the less (<) operator, and the second uses a compare function object we provide:
template <class Iterator>
void sort(Iterator first, Iterator last);
template <class Iterator, class Compare>
void sort(Iterator first, Iterator last, Compare comp);
Here is an example:
#include <algorithm>
#include <vector>
void sort_s() {
std::vector v = { 1,4,8,2,-3,7,9,-5,5,20,6 };
// the lambda function determines ascending or descending order
std::sort(v.begin(), v.end(), [](int a, int b) {return a < b; });
for (auto i : v) {
std::cout << i << "\n";
}
}
std::stable_sort
This is almost the same as sort. The only difference is that if two elements are equivalent it does not swap them.
std::partial_sort
This function can sort only a part of the container. Here is the definition of the algorithm:
template <class Iterator>
void partial_sort(Iterator first, Iterator middle, Iterator last);
template <class Iterator, class Compare>
void partial_sort(Iterator first, Iterator middle, Iterator last, Compare comp);
It affects the range [first, last) iterator. It puts in the range up to middle the smallest elements in ascending order, and from middle to last the remaining elements in no particular order.
first: the start of the range to affect.
last: the end of the range.
middle: the element within the range [first, last) that is used for the upper boundary of the sort.
The algorithm starts sorting in ascending order the elements in the [first, last) range until it has sorted the elements up the middle iterator.
In the following sample partial_sort will sort the elements of the vector until it has reached the third element, the sorted elements will be [first, middle).
void partial_sort_s()
{
std::vector<int> v = { 10, 8, 5, 4, 3, 19, 0, 9, 7 };
std::partial_sort(v.begin(), v.begin() + 3, v.end());
for (auto i:v)
std::cout << i << ", ";
std::cout << "\n";
}
Searching algorithms
Searching and retrieving information is one of the basic functions we do with containers. Here we will look at some fundamental and common search algorithms.
std::find
std::find searches a given range in a container to find the first occurrence of a value. It returns an iterator at its position if found and the iterator marking the end of the search range if not found.
std::find_if and std::find_if_not
std::find_if and std::find_if_not are similar functions only they give us the opportunity to define a condition in the search instead of value.
void find_if_s() {
std::vector<int> v = { 10, 8, 5, 4, 3, 19, 0, 9, 7 };
// find the first number bigger than 15
auto f = std::find_if(v.begin(), v.end(), [](int i) { return i >= 15; });
if (f == v.end()) // the end of the range reached
std::cout << "not found\n";
else
std::cout << "found:" << *f << " at position:" << f - v.begin() << "\n";
}
std::find_if_not is the same with inverted logic (NOT). In simple cases like this lambda functions are useful.
std::find_first_of
std::find_first_of compares two containers. Its purpose is to find the first occurrence of any element of the second container in the first.
void find_first_of_s() {
std::vector<int> v = { 10, 8, 5, 4, 3, 19, 0, 9, 7 };
std::vector<int> s = { 1, -2, 9 };
auto f = std::find_first_of(v.begin(), v.end(), s.begin(), s.end());
if (f == v.end()) // the end of the range reached
std::cout << "not found\n";
else
std::cout << "found:" << *f << " at position:" << f - v.begin() << "\n";
}
std::binary_search
std::binary_search is another search algorithm designed to work on sorted containers. It actually uses the binary search algorithm which works on sorted data. The simple std::find algorithm searches the data sequentially and it is slow on big datasets, so for std::map, std::set and other sorted containers we prefer std::binary_search which is faster.
void binary_search_s() {
std::set<int> v = { 10, 8, 5, 4, 3, 19, 0, 9, 7 };
auto f = std::binary_search(v.begin(), v.end(), 19);
if (!f) // the end of the range reached
std::cout << "not found\n";
else
std::cout << "found\n";
}
std::lower_bound & std::upper_bound
std::lower_bound and std::upper_bound are used in sorted containers that allow for multiple entries of the key like std::multiset and std::multimap or sorted vectors and lists. They return:
std::lower_bound: an iterator an iterator to the first occurrence of the search key.
std::upper_bound: an iterator one position past the last occurrence of the search key.
void bounds_s() {
std::vector<int> v = { 1,2,3,4,4,4,4,5,6,7,8,9,10 };
// find first occurrence of 4
auto lb = std::lower_bound(v.begin(), v.end(), 4);
// find last occurrence of 4
auto ub = std::upper_bound(v.begin(), v.end(), 4);
for (auto i=lb; i<ub; ++i)
std::cout << *i << " ";
std::cout << "\n";
}
Copy, move & remove algorithms
These algorithms provide efficient copy, move and remove operations for elements in containers.
std::copy and std::copy_if
These algorithms copy a range of data to a new location. The std::copy_if allows us to define a condition that will determine if a copy is allowed or not:
void copy_s() {
std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };
std::vector<int> l = { 21,22,23,24 };
std::copy(l.begin(), l.end(), v.begin() + 2);
for (auto i : v)
std::cout << i << " ";
std::cout << "\n";
}
void copy_if_s() {
std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };
std::vector<int> l = { 21,22,23,24 };
std::copy_if(l.begin(), l.end(), v.begin() + 2, [](int i) { return (i%2)==0; });
for (auto i : v)
std::cout << i << " ";
std::cout << "\n";
}
std::remove & std::remove_if
std::remove and std::remove_if remove elements from a container. std::remove removes all occurrences of a certain value within a range. std::remove_if removes all elements that fulfill a given condition. The functions cannot modify the length of the container so instead of deleting elements they shift them towards the start and return an iterator to the new end of the container. Here is an example:
void remove_s() {
std::vector<int> v = { 1,2,3,4,5,6,4,7,8,9,10 };
auto it = std::remove(v.begin(), v.end(), 4);
std::cout << "last after removal (0 based!):" << it - v.begin() << "\n";
for (auto i : v)
std::cout << i << " ";
std::cout << "\n";
}
void remove_if_s() {
std::vector<int> v = { 1,22,31,40,5,6,7,8,9,10 };
auto it = std::remove_if(v.begin(), v.end(), [](int i) { return (i % 2) == 1; });
std::cout << "last after removal (0 based!):" << it - v.begin() << "\n";
for (auto i : v)
std::cout << i << " ";
std::cout << "\n";
}
Compile and run these samples to see the shift in the elements within the vector.
std::merge
std::merge merges two sorted containers in a new sorted container. Destination container must have enough space allocated for the operation.
void merge_s() {
std::vector<int> v1 = { 1,3,5,7,9 };
std::vector<int> v2 = { 2,4,6,8,10 };
std::vector<int> v3(v1.size() + v2.size()); // preallocate space!!
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for (auto i : v3)
std::cout << i << " ";
std::cout << "\n";
}
std::min and std::max
std::min and std::max return the minimum and maximum values in a container or a list of elements. It uses the less operator (<) but a custom comparison function can be given to customize the algorithm.
void min_max_s() {
auto mn = std::min({ 1,3,9,4,6,10,5,8,7 });
std::cout << "min:" << mn << "\n";
// using a custom comparison we can get the opposite result!
auto mx = std::min({ 1,3,9,4,6,10,5,8,7 }, [](int i, int j) { return (i > j); });
std::cout << "max:" << mx << "\n";
auto mx2 = std::max({ 1,3,9,4,6,10,5,8,7 });
std::cout << "max:" << mx2 << "\n";
}
Summary
In this part we were introduced to the C++ Standard Library. We have seen:
- Containers
- Iterators
- Algorithms