Stefano Lusardi, Software Developer
What is an std::algorithm?
It is a functions designed to address general purpose problems that can be used on a range of elements.
Since the STL is just all about Containers, Iterators and Algorithms it is designed to have the best possible interaction between these components
Why do we need an algorithm library
(in Modern C++) ?
Expressive, Solid, and Reusable chunks of code.
Do you remember the initial example given in the first talk?
// 1. "Raw" for loop
int c = 0;
for (int i = 0; i < myVec.size(); ++i) {
myVec[i] == 5 && ++c;
}
// 2. Modern algorithm
int c = std::count(begin(myVec), end(myVec), 5);
A brief recap/comparison of the two approaches:
How does an algorithm work?
The algorithm is applied on a given container range, typically defined as: first, last.
According to the specific algorithm we are using we can have (or we can't have) several guarantees such as:
Modifying, Non-Modifying, Searching, Sorting...
Usually the pair begin(), end() iterators are used to define the sequence range, but there is no restriction set on the input range.
Iterators range. Any differences?
int c = std::count(begin(myVec), end(myVec), 5);
int c = std::count(myVec.begin(), myVec.end(), 5);
Single responsability principle
Note that even if algorithms and lambdas are an extreme powerful resource it is always better not to increase the code complexity and readability creating extremely complicated and nested logics.
Function still serves as functions!
std::algorithm with a predicate
Example: std::find and std::find_if
// Finds a given elem into myVec
int a = std::find(myVec.begin(), myVec.end(), /*elem*/);
// Finds an element which satisfies a given predicate
int b = std::find_if(myVec.begin(), myVec.end(), /*predicate*/);
A predicate can be a so-called Functor* (before C++11) or a Lambda Function
Example: std::find_if with a predicate
int f = std::find_if(myVec.begin(), myVec.end(),
[](const Foo& foo){ return foo.value == 42; });
More on predicates and iterators with std::algorithms
std::vector<std::string> strVec {"Not_Me", "Find_Me", "Not_You"};
int index = std::distance(strVec.begin(),
std::find_if(strVec.begin(), strVec.end()
[](const std::string& s)
{ return s.name == "Find_Me"; })
);
C++17 execution policies
Example:
std::vector<int> myVec { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// C++11 sequential sum using std::accumulate
// (can't be parallelized)
int sumSeq1 = std::accumulate(myVec.begin(), myVec.end(), 0);
// Equivalent using new C++17 algorithm std::reduce()
int sumSeq2 = std::reduce(myVec.begin(), myVec.end(), 0);
// C++17 parallel sum
int sumPar = std::reduce(
std::execution::par, myVec.begin(), myVec.end(), 0);
What is a Lambda Function?
A Lambda Function is an unnamed and callable object, able to capture variables from an enclosing scope.
Anatomy of a Lambda Function
[CaptureGroup](Parameters...) -> ReturnType { Body };
Capture Group
Capture Group example
int x = 4;
auto y = [&xRef = x, xCopy = x+1]() -> int
{
// xCopy is 5, global x is still 4
xRef += 2; // global x incremented by 2
return xCopy+2; // xCopy is incremented by 2
}();
// x = 6
// y = 7
Anatomy of a std::function object
std::function<R(Params...)>
Example: std::function declaration and usage
// wrap a free-function
void freeFunc(int i, std::string s, double d) { /*...*/ };
std::function<void(int, std::string, double)> myFunc
= freeFunc;
freeFunc(42, "hello world", 0.001); // invoke
// wrap a member function
class Foo {
void func(double d) { /*...*/ };
}
std::function<void(const Foo& foo, double)> myFooFunc
= &Foo::func();
myFooFunc(foo, 0.001); // invoke
Function objects and Lambdas
Since std::function
// Declaration:
std::function<void(int)> myPrint = [](int val) -> void
{ std::cout << "Printed value: " << val; };
// Usage:
myPrint(42); // "Printed value: 42"
A more functional style
Lambdas and functions objects enables a more functional approach to the Modern C++:
Using these tools it is now possible to declare a function in a local scope (i.e. inside another function) and use it at any time in the enclosing scope
Functional example:
void Foo::myFunction(const std::vector<int>& myVec)
{
/* ... */
std::function<void(int)> myPrint = [](int val) -> void
{ std::cout << "Printed value: " << val; };
/* ... */
for (auto e : myVec) myPrint(e);
}
Declare and invoke immediately
Lambdas can be declared and invoked directly in-place, after their declaration as:
// Declaration and immediate usage:
[](int val) -> void {
std::cout << "Printed value: " << val;
}(42); // "Printed value: 42"
Embrace more complex const correctness
bool something = ...
const int myVal;
if (something)
{
myVal = 42;
}
else
{
myVal = 0;
}
// This will not compile since myVal is
// declared const but not initialized
When the ternary operator (condition ? a : b) is not enough, lambdas are helpful:
bool something = ...
const int myVal = [something]() -> int
{
if (something) { return 42; }
return 0;
}();
auto ensures that the type of the variable that is being declared will be automatically deduced from its initializer.
auto takes exactly the type on the right-hand side removing const/volatile and &/&&.
auto foo1 = new Foo();
auto* foo2 = new Foo(); // equivalent, * is kept
auto bar1 = getBar();
auto& bar2 = getBar(); // different, & is removed
Can't forget variable initialization
Foo foo; // OK, but foo might not be initialized
auto bar; // Does not compile because initialization is missing
auto bar = Bar{ }; // OK, bar is initialized
Guarantees that no implicit conversions occur (including narrowing conversions)
int val = 42.f;
// OK, but float to int narrowing conversion kicks in
// Is that desired or is it a bug?
// If it is really desired why is it done like that?
auto val = 42.f; // OK
Avoid unnecessary temporary conversions
std::string getValue() { return "42"; }
// const char* to std::string conversion (1)
MyString val = getValue();
// std::string to MyString conversion (2)
auto val = getValue(); // OK
Keeps on using the correct type even if initialization is modified
Suppose that the previous getValue() function is changed as:
// std::string getValue() { return "42"; } // previous
int getValue() { return 42; } // new
std::string val = getValue(); // usage is unchanged
// Does not compile anymore after
// getValue() signature has changed
auto val = getValue(); // OK
// Keeps on working without changing client code
Hard to catch narrowing conversion
std::vector<int> myVec { /* ... */ };
for (int i = 0; i < myVec.size(); ++i){ /* ... */ }
// OK, but can easily overflow. Why?
// std::vector::size() returns size_t (can be 4 bytes),
// not an int (can be 2 bytes)
for (auto i = 0; i < myVec.size(); ++i){ /* ... */ } // OK
More on narrowing conversion
(unexpected side effects)
std::vector<float> myVec { 1.0, 2.0, 3.0 };
auto sumA = std::accumulate(myVec.begin(), myVec.end(), 0.0);
// OK, sumA is float as expected.
auto sumB = std::accumulate(myVec.begin(), myVec.end(), 0);
// OK, BUT sumB is int because the type of "0"
// in std::accumulate is set as the return type
Smart pointers "Heap-like" initialization
std::unique_ptr<Bar> b
= std::unique_ptr<Bar>(new Bar()); // OK
auto f = make_unique<Foo>(); // OK, better
Use of literal suffixes for uniform initialization
int x = 42; auto x = 42;
float x = 42.; auto x = 42.f;
unsigned long x = 42; auto x = 42ul;
using namespace std::string_literals; // C++14
std::string x = "42"; auto x = "42"s;
using namespace std::chrono_literals; // C++14
std::chrono::nanoseconds x{ 42 }; auto x = 42ns;
Template function with trailing return type
template <class T, class U>
auto getValue(const T& t, const U& u) -> decltype(T + U){
return t + u;
}
Member function with trailing return type
class Foo {
/* ... */
std::map<const std::string, std::shared_ptr<Bar>> mFooMap;
}
auto Foo::func(const std::string& id)
-> decltype(mFooMap)::iterator
{
return std::find_if(mFooMap.begin(), mFooMap.end(),
[id](const auto& pair) {return id == pair.first.name; });
}
And finally, less typing for the lazy ones
std::map<Foo::Bar, std::vector<T>>::const_iterator it
= myMap.begin(); // OK
auto it = myMap.begin(); // OK, lazy