2 C++ Standard Library
2.1 Overview of the C++ Standard Library
The above image outlines some components of the C++ Standard Library (SL), including algorithms, iterators, atomic operations, ranges, coroutines, input/output, thread support, and containers. It is important to note that most components are provided by the C++17 standard, with two provided by the C++20 standard. For simplicity, we omit information about the C++17 standard. Additionally, we only showcase the components that will be used in this book. First, the container component provides the following data structures: unordered associative containers, associative containers, and sequence containers. In the current version of SL, maps and sets are provided as associative containers. As unordered associative containers, this book provides unordered sets and unordered maps. The most important containers in this book are sequence containers, such as vectors, lists, and arrays. The iterator component provides six iterators for handling sequences of values, such as lists or any container. Based on operations on value sequences, the following operations are defined: read or write access, random access, increment, or decrement. In the C++ standard, the iterator component will be extended with concept-based iterators, which differ from C++17 iterators. Furthermore, the ranges component will serve as an extension and generalization of existing C++ iterators. However, we have not yet utilized ranges, as not all mainstream C++ compilers support them. The second component that operates on containers is algorithms. We have carefully selected the algorithms that will be used in this book:
- Sorting: Sorting the sequence of values in order.
- Searching: Searching for a specific value in a sequence of values.
- Numerical algorithms: For example, calculating the sum of all values in a sequence.
- Min/Max operations: Finding the minimum or maximum value in a sequence.
- Generic iteration: Iterating over a sequence of values without using, for example, a for loop.
Note that there are more algorithms available, and all these algorithms are applicable to all containers. Coroutines, introduced in the C++20 standard, are stackless functions whose execution can be paused and resumed later. Concurrency support is introduced to avoid race conditions and deadlocks. We believe that the most important point from the introduction is: when looking at SL, if you cannot find the required container or algorithm, you should ask yourself if you really need it.
3.2 Containers
In this section, we will demonstrate the necessity of containers for storing data through an example. Suppose we want to calculate the average value a of n elements:
The implementation of the average calculation on page 20 uses the C++ Standard Library (SL) header file #include
%%cling
#include<iostream>
#include<vector>
//-----------------------------------------------------------------
double sum = 0;
size_t count = 0;
std::vector<double> vals = {1, 3, 7, 2.2, 1.8};
for (auto x : vals) {
sum += x;
++count;
}
std::cout << "Average: " << sum / count << std::endl;
Note that we do not need to store user input when calculating the average. However, to calculate the median, we need to store user input. The median is the middle value of a sorted list. To implement this calculation, we need a vector to store the list and an rt algorithm. Before exploring the algorithms in section 3.3, let’s first understand three commonly used containers.
3.2.1 Vector
From a mathematical perspective, the std::vector provided by the header file #include
Containers in C++ are homogeneous data structures that can only contain elements of the same type. Regarding the usage of vectors, let’s look at the calculation of the average.
%%cling
#include<numeric>
#include<iostream>
#include<vector>
//-----------------------------------------------------------------
size_t count = 0;
std::vector<double> values = {1.1, 2.3, 5.4, 3.2};
double sum = std::accumulate(values.begin(), values.end(), 0.0f);
std::cout << "Average: " << sum / values.size() << std::endl;
3.2.2 List
Another dynamically sized container is std::list, provided by the header file #include . From an API perspective, vectors and lists are the same in most cases; you can simply replace std::vector with std::list in the code. Therefore, we will not repeat the example of calculating the average for lists. However, we will create a new example for calculating the median, as we find some differences here.
%%cling
#include<iostream>
#include<list>
#include<algorithm>
typedefstd::list<double>::size_type list_size;
//-----------------------------------------------------------------
std::list<double> values = {2, 7.7, 3, 9.2, 1.4};
double x = 0;
values.sort();
list_size mid_index = values.size() / 2;
auto mid = values.begin();
std::advance(mid, mid_index);
double median = 0;
if (values.size() % 2 == 0) {
auto mid_one = values.begin();
std::advance(mid_one, mid_index + 1);
median = 0.5 * (*mid + *mid_one);
} else
median = *mid;
std::cout << "Median: " << median << std::endl;
std::sort requires random access iterators, so it does not work properly. Therefore, we use the member function std::list::sort. We calculate the index of the middle element in the list using values.size(), which is the same operation as for std::vector. For standard vectors, we can access the element at index i using the access operator values[i]; however, we lack the key property of random iterators, so we use values.begin() to get an iterator pointing to the first element of the list, and use std::advance to move the iterator to the middle element of the list, using the dereference operator *mid to access the value of the middle element.
3.2.3 List vs. Vector
Here, we will closely examine the differences in usage between vectors and lists. Choosing one over the other can have a significant impact on performance. When choosing between lists and vectors, consider the following points:
- For the same number of elements, vectors require less memory because they only store elements. Lists must store two pointers for each data element.
- Lists require less time to insert elements at arbitrary positions.
- Random data access speed is faster for vectors because elements are stored sequentially in memory. Lists can only be traversed sequentially in memory.
To study the time differences in calculations between these two data structures, the results shown in the figure below were obtained using gcc 12 on a single node, plotting the average of 10 runs for each number of elements. For all images, the number of elements in the list or vector ranges from 10, 102, 103 to 109.
3.2.4 Arrays
%%cling
#include<stdlib.h>
//-----------------------------------------------------------------
// Define the length of the array
constsize_t size = 6;
// Generate the array
double a[size];
// Fill the a
for (size_t i = 0; i < size; i++) {
a[i] = i;
}
// Print the a
for (size_t i = 0; i < size; i++) {
a[i] = i;
}
std::cout << "last element: " << a[size - 1] << std::endl;
For storing a fixed number of elements (which need to be determined at compile time), C++ provides two options. First, you can use language features, such as int* array = double[5];.
Using the container std::array is very similar to using language features, with the main difference being the use of algorithms.
%%cling
#include<algorithm>
#include<array>
#include<iostream>
#include<numeric>
//-----------------------------------------------------------------
// Define the length of the array
std::array<double, 6> a;
// Fill the array
std::iota(a.begin(), a.end(), 0);
// Print the array
std::for_each(a.begin(), a.end(), [](double value) {
std::cout << value << " ";
});
std::cout << std::endl;
3.2.5 Iterators
The C++ Standard Library (SL) provides iterators using the header file #include
(1) Output iterator type iterates forward on a container using the increment operator ++ and can only write elements once using the dereference operator *; (2) Input iterator type is read-only, iterates forward on a container using the increment operator ++, and can access elements multiple times using the dereference operator *; (3) Forward iterator type combines input and output iterator types; (4) Bidirectional iterator type is similar to forward iterator type but adds the — decrement operator, allowing iteration over the container in both directions; (5) Random access iterator type extends the random access capability of bidirectional iterator types by allowing programmers to add integers. Note that C++ pointer types are random access iterators.
Now, let’s look at an example of using iterators to print elements of std::list: Listing_3_6.cpp
#include<list>
#include<iostream>
//-----------------------------------------------------------------
intmain() {
std::list<int> values = {2, 7, 3, 9, 1};
// Accessing the iterator to the first element
std::list<int>::iterator it = std::begin(values);
for (; it != std::end(values); it++)
// Accessing the element using the dereference operator *
std::cout << *it << std::endl;
std::cout << "------" << std::endl;
for (constint value : values) {
std::cout << value << std::endl;
}
std::cout << "------" << std::endl;
for (int index = 0; constint value : values) {
std::cout << "Index=" << index << " Value= " << value
<< std::endl;
}
}
Compile and execute:
# g++ -std=c++20 -I . -o Listing_3_6 Listing_3_6.cpp -lpthread
# ./Listing_3_6
2
7
3
9
1
------
2
7
3
9
1
------
Index=0 Value= 2
Index=0 Value= 7
Index=0 Value= 3
Index=0 Value= 9
Index=0 Value= 1
The type of iterator significantly affects how we access container elements. For example, for std::vector or std::array, the subscript operator [] can be used to access elements by index, while this is not possible for std::list.
References
- Software testing quality book documentation download continuously updated https://github.com/china-testing/python-testing-examples Please like, thank you!
- The Python testing development libraries involved in this article Thank you for liking! https://github.com/china-testing/python_cn_resouce
- Download quality Python books https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
- Download quality Linux books https://www.cnblogs.com/testing-/p/17438558.html
- Python BaZi chart https://github.com/china-testing/bazi
- Contact: Ding or WeChat: pythontesting
3.3 Algorithms
In this section, we will explore the algorithms provided by the C++ Standard Library, as these algorithms form the basis of parallel algorithms. We will follow Sean Parent’s talk at the 2013 CppCon conference (which is worth watching), where he suggested avoiding “raw loops”. By using algorithms from the standard library, you can create shorter, more understandable, and maintainable code, and potentially more efficient. Additionally, it helps programmers develop the habit of reusing code rather than writing everything from scratch.
For example, Sean used the slide function. The slide function takes the range of elements specified by the first two parameters and moves them to the position specified by the third parameter. You might want to implement this algorithm by removing elements from the starting position and then inserting them at the terminating position.
%%cling
#include<vector>
template <typename T, typename V>
std::pair<T, T> slide1(V &v, T b, T e, T p) {
auto n = e - b;
typedef typename std::iterator_traits<T>::value_type e_type;
std::vector<e_type> v2;
for (auto i = 0; i != n; ++i) {
v2.push_back(*b);
v.erase(b);
}
T p2 = p;
for (auto i = 0; i != n; ++i) {
v.insert(p, v2.back());
v2.pop_back();
p2++;
}
return {p, p2};
}
The problem with this code is not that it is wrong (it is not wrong in itself). If using a std::list object, it might even be quite efficient. However, for std::vector, its efficiency is very low. Worse, it does not provide opportunities for parallelism.
On the other hand, if we realize that the sliding operation is just a subset of rotating value ranges, we can rewrite the slide function using the std::rotate algorithm without using loops.
%%cling
#include<algorithm>
//-----------------------------------------------------------------
template <typename T>
std::pair<T, T> slide2(T first, T last, T pos) {
if (pos < first) {
return {pos, std::rotate(pos, first, last)};
} else {
T hi = pos + (last - first);
return {std::rotate(first, last, hi), hi};
}
}
The new version of the code is about 50% shorter, does not require passing the container, and does not require allocating a vector. It turns out that algorithms for rotating container elements are difficult to implement efficiently, let alone parallelizing them. By rewriting the slide function to use the algorithm library, we can also gain these benefits.
The lesson is that programmers should be familiar with the algorithms available in the C++ Standard Library and use them whenever possible.
The second example is calculating the Taylor series for the natural logarithm ln. The Maclaurin series for the natural algorithm is:
%%cling
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
//-----------------------------------------------------------------
conststd::size_t n = 10;
constdouble x = .372;
std::vector<double> parts(n);
std::iota(parts.begin(), parts.end(), 1);
std::for_each(parts.begin(), parts.end(), [](double &e) {
e = std::pow(-1.0, e + 1) * std::pow(x, e) / (e);
});
double result = std::accumulate(parts.begin(), parts.end(), 0.);
In this example, we again avoid using raw for loops to make it easier to write parallel code using the parallel algorithms from chapter 1.