- Hi, I'm Jonathan Boccara.
I write on the blog Fluent C++.
It's a blog about expressive code in C++
with an article every Tuesday and Friday,
and I work at Murex.
I am a team leader of a C++ developer software,
software developer team. (audience grumbling)
I'm sorry? - Do you have a microphone?
- It's not working.
Oh, it's, okay.
Just let me put that up.
Hi, hi, everyone hears me?
Right, so I was Jonathan Boccara.
I was on Fluent C++ writing twice a week
about expressive code in C++,
and I'm still working at Murex as a team leader
of a C++ software developer team.
What we're gonna talk about today is the STL algorithms.
We're gonna start off this talk with a question to you.
Who in this room is aware of the fact
that it's a good thing to know the STL algorithms?
Just raise your hand if you're aware of that fact.
Pretty much everyone, hands rising.
That's pretty cool.
Second question, who knows them all?
Go on, raise your hand.
Go on, then.
That's pretty much, that's actually no one.
No one's hand's rising now.
That's exactly the purpose of this talk.
When you walk out of that room,
you will know every single thing
that's in the STL algorithms library.
To do that, I suggest that we start
with a brief chat about why it's important
to know them and what to learn in them,
and then we dive in the STL algorithms themselves.
So, there's this thing that's been popularized
across the C++ community over the past few years
that's we need to know all the STL algorithms
and we need to know them well, very well.
Well, for one thing, they can make
our code more expressive,
and they do that by raising levels of abstraction,
which means that they allow to express
what we want to do as opposed to how we want to execute it,
and I think that raising the levels of abstraction
is one of the most efficient way to write expressive code.
And it can be sometimes spectacular.
Like, if you've seen that talk a couple of years back,
by Sean Parent, which was called C++ Seasoning,
in that talk, Sean took a chunk of code
that was a bit hard to understand
and he refactored it into a more concise
and expressive piece of code,
just by picking the right STL algorithm.
That's not the only reason
If we write ourselves our manipulations
on collections, then we have to have, to write somehow,
the traversal of a collection,
and we have to write a for-loop if we don't resort
to using STL algorithms, and when we write for-loops,
there are things that can go wrong,
like for example, we need to be sure
that the traversal doesn't go past the ends,
like, we have to run that mental check,
run the loop in our head to make sure,
and even then, there's a risk,
and if we go past the end of a collection in C++,
then we get into undefined behavior,
and from that point on, anything can happen.
Literally, anything can happen,
and that's allowed by the standard.
What's happening on the screen right now,
is absolutely legal C++,
even though it's probably more likely
that you get a crash than a clown popping up next to you
but still, the clown is legal by the standard.
Another kind of mistake is dealing with the case
of an empty loop, and that's the same thing,
we have to run it in our head, have a risk
of it going wrong sometimes,
and then going to undefined behavior all over again.
With the STL algorithms, this doesn't happen,
so that's one more reason to use them.
Another case of mistake we can make
when writing our own for-loops is about complexity.
Some algorithms that they can be implemented naively,
in quadratic complexity, and in a more astute manner,
in a linear complexity.
We go back to an example later with algorithms on sets.
Also, STL algorithms are used
by billions of people every day.
Well, maybe not billions of people every day,
but quite a lot of people fairly often.
(laughing) More seriously, they are parts
of standard C++ which means that you should not be afraid
to use them and think that maybe
somebody's not gonna be able to understand them
because they don't know them.
I think we should level up to the STL algorithms
and not the other way around.
So this is the common, this is part
of the common vocabulary of C++
just as much as int or if or whatever the language is.
And it's so, so standard
that even if you're running an older C++ version,
you can still get most of the STL algorithms,
like for example, if you're in C++03 for example,
and you want to use like all of or any of or none of,
which appeared in C++11,
well, you can just grab that code
and copy it into your codebase and just start using them,
so most of them are within your reach,
whichever version of C++ you're on right now.
Right, so, now, let's say that you want
to go to the STL algorithms, you want to take that path.
Well, there's a trap that's lying
just at the beginning of that path,
and this is called for_each.
For_each is one of the STL algorithms.
It's nothing, there's nothing wrong with it.
It has a use case we'll see a bit later,
but the trap that it represents is that,
it looks like a for-loop, right,
because it takes a begin and an end,
and some code that it will execute
on every element of the collection, just like a for-loop.
So, you might be tempted to think
that you can replace all your for-loops by for_each,
and that you'd be done,
that you'd be using the STL algorithms.
And that's not quite the spirit,
because there's much more than for_each
in the STL algorithms library.
There's many more, many more algorithms
that let you express more nuance when you write your code.
I'm going to show you something to illustrate the fact
that there's much more than for_each
in the STL algorithms library.
(moderate orchestral music)
(dramatic orchestral music)
(intense orchestral music)
Ladies and gentlemen, I present to you
the world of the STL algorithms.
On this map, I've placed all the STL algorithms
as of C++17,
and I've grouped them by region,
according to the logical relationship they have, right?
The rest of this talk will consist in exploring that world,
but before diving in,
we can note a few things while looking at it from afar.
The first thing we can note is that,
for_each is just one of them on one island,
lost on the middle of the ocean,
so it's just one of them.
What we can note, also, is where most of them are.
You can observe that the largest region
on that world is over here,
and that's the lands of queries.
Call that queries because all those algorithms
that live here,
they just read into the collection
and extract some piece of information,
and they don't actually modify it.
I don't know what you think, but I would have thought
that most algorithm would somehow change the collection,
like sort or partition or whatever.
They are there, as well, but most of them,
they're just read-only operations.
I suggest that we start our journey
by the other end of the world from for_each,
down here on the algorithms on heaps.
So, what is a heap to begin with?
A heap is a data structure
that looks like a tree, but that has a property.
It's that every node must be smaller
than its children.
I think it's called that because it kind of like,
looks like a heap in real life,
like, the small ones are at the top
and the bigger one at the bottom.
It's better having a heap.
That you can observe, that the heap on the right
of the picture is the other way around, right?
The biggest element is at the top
and every element is bigger by its children.
That's a C++ heap, it's called a max heap.
The relationship between the parent and its children
is the parent is bigger, right?
So it's the other way around from the heap from real life,
but, you know, we developer don't really live
in real life anyway, so, does it really matter?
Don't think so.
So, one interesting property of a heap
is that we can squash it down into a range like that.
One more time, more slowly.
To squash down a heap into a range,
we take the first row, which is just the root of the tree
and then the second row, and then the third row,
and so on and so forth, and when we do this,
there's this nice property that it's a range,
so we can represent it with a vector, for example,
which is quite convenient to work with, and also,
to go from a node to its left child,
it's essentially taking its index
and multiplying it by twos, nearly that.
So it's a way to represent a tree into a range.
If we have a range, we have a beginning and an end
and we can use STL algorithms.
So, the first thing we can do
is taking values that are not particularly a heap,
and rearrange them so that they respect the heap property.
To make a heap, to make a heap, we use std::make_heap
with a begin and an end, and that rearranges
the element inside of a collection.
That's our first algorithm of the day.
That's one down, 104 to go.
I forgot to mention,
it's 105 STL Algorithms In Less Than an Hour, Each.
Just making sure we've got the same understanding here,
No, I'm joking.
Don't worry, well, either way, you'll find out.
Let's move on, what we can do with a heap
is add something to it, independently from C++,
to add something to a heap, we put the new thing
right at the end and it might not be its right position
because it may be smaller than its father,
and the way to add it to the heap is to swap it
with its parent until it reaches its final position.
All right, now, to do that in C++,
we can squash down the heap, right,
to represent it as a range.
Say that it's a vector, we add something to the end
and then we need something to make it bubble its way up
to its final position, and that's push_heap.
Now, push_heap just does the same thing
within, with the tree version, but in range version.
Now, to remove something from a heap,
or this thing with heap, why do we use heaps
in the first place, is to be able to get the maximum value
of the collection in not too much time,
and count it on time.
In fact, the heap, the max element of the collection
is just the front, so this is where we access
and this is also what we allow to remove.
To do that, we swap it with the last one.
That's what pop_heap does.
At this point, the range in yellow is probably not a heap
because there's the one at the end
that was probably one of the smallest ones,
that was at the beginning,
so we need to make it bubble its way down
to its final position, and that's what pop_heap does.
And if we want to remove, to actually remove that value,
we pop it back from the vector.
Now, if we don't pop it back from the vector,
but leave it here and do that again,
for the part in yellow, the shrinking heap,
if we do that over and over,
at the end, we'll get, can someone see
what we'll get at the end?
Yeah, right, a sorted collection.
So that's a way to sort the collection,
and that's what sort_heap,
Talking about sorting, this is the region around the corner,
the shore of sorting.
So, let's see how to sort with the STL.
The simplest way probably is std::sort.
That takes a collection, begin, end, and rearranges them
so that they're in sorted order, okay.
Now, if we only want to sort the beginning of a collection,
as we saw in depth in Fred's talk,
we can just partial sort the things.
A partial sort takes a begin and an end,
and sort of like a middle,
something inside of the collection,
and sorts the collection from the beginning to that point
and the rest is in unspecified order, right.
So the left-hand side of the collection
is what would be there if it was completely sorted.
Now, to sort just one element,
that's nth_element, which takes a begin, an end,
and something inside of the collection,
and puts at that position inside of the collection
the element that would be there
if the whole thing were sorted.
And for the rest, everything that's on the left is smaller,
and everything that's on the right is not smaller.
There's sort_heap, which we've mentioned
with repeatedly calling pop_heap,
and there's inplace_merge, inplace_merge
is the incremental step in a merge sort,
so we've got a collection that we can mentally think of
as two halves,
and merge sort, so the two halves are sorted
and merge sort combines the whole thing
into a sorted collection.
So that's about sorting with the STL.
Just further up the shore,
there's the region of partitioning.
So, what's partitioning in the first place?
To partition a collection is to look at it
through a predicate, something that returns a Boolean.
Here, our predicate is being blue.
To partition a collection is putting all the blue ones
at the beginning, and other not-blue ones at the end.
Of course, it works for blue and red and yellow
and actually every, any predicate, all right.
The border between the blue ones and the not-blue ones
is called a partition point, that's the end
of the blue range and that's also the begin
of the not-blue range, can you see that?
Okay, that's called partition_point
and to retrieve from a partition collection,
Right, if we take a step back on that part of the world,
that was the land of permutation,
the place where elements move around the collection
even if they don't change value.
We've seen heaps, sort, partition,
and there are a few others that we'll go through quickly.
There's this permutation that takes the element
at the end and put it at the bottom,
put them at the beginning, sorry.
Another way to change the order of the element collection
is to do that randomly, and that's what std::shuffle does.
So std::shuffle takes a collection with elements
in a certain order, and takes something
that generates random numbers,
and rearranges the collection in random order.
There is an order we can define on permutations.
Given a set of object, given a collection of object,
we can order them, order all their possible arrangements,
and an intuitive way to see that is thinking
about an alphabetical order, right?
So, in this collection, one, two, three,
all the way to nine, the smallest one
if those were in a dictionary,
would be that first one, one, all the way to nine.
And the one just after would be the same thing,
with the nine and an eight, swapped together, right?
And so on, and the largest one would be the one
at the bottom here, from nine down to one, right?
If you have a collection in a given order,
any order between the smallest and the biggest one,
next_permutation which takes a beginning and an end
would rearrange it so that it goes to the order
that's just after it, and prev_permutation
to the order that's just before it.
That's interesting if you'd like to do something
for every possible arrangement of a collection,
we can repeatedly call next_permutation
until you've cycled back to the beginning.
And finally, the last one is reverse,
that reverses the element collection.
Right, so we've been all around the lands of permutation.
Just in the corner of the map here
are the secret runes.
The secret runes are things that you can combine
with other algorithms to generate new algorithms.
I call them runes because it's like,
it's like going to see runes to augment your powers
and also because I find that kind of cool as a name.
So let's call them that for purpose of this presentation.
We've seen all the algorithm that go
with the stable rune, so stable,
when you tack it onto an algorithm,
it does what this algorithm does,
but keep the relative order.
Think about partition for example.
It put all the blue ones at the beginning, that's for sure,
but maybe in the process, some of them got swapped around.
With stable_partition, they all keep
the same relative order, same thing with stable_sort.
The is rune checks for a predicate on the collection.
We know what sort, partition, heap, means,
or is_sorted, is_partitioned, is_heap returns a Boolean
to say, to indicate whether it's a sorted,
a partition or a heap that we're looking at.
An is until returns an iterator
that's the first position where that predicate
doesn't hold anymore.
All right, so for example, if we have a sorted collection,
and then we call is_sorted_until,
we'll get the end of that collection.
All right, let's take a step back.
So we've been down there in the lands of permutation.
Let's now focus on the largest part
of the world, the lands of queries.
There are quite a few of them in there,
but we'll go through them quite quickly.
So, one thing you can extract out of a collection
is some sort of value.
For example, the simplest one is probably count
that takes begin and an end and a value
and returns how many times this value occurs
in the collection.
There's accumulate, that makes the sum
of the element of the collection calling operator plus,
or any custom function you'd pass it.
In C++17, there's reduce that appeared,
that does practically the same thing as accumulate,
except it has a slightly different interface.
It can accept to take no initial value,
and it can also be run in parallel,
but essentially, it's the same as accumulate,
and transform_reduce takes a function
and applies that function to the element of the collection
before calling the reduce.
Partial_sum, well, it sums the,
all the elements starting from the beginning
to the current point of the collection,
so here, partial_sum would return a collection
with, in the first position, what was in the first position
of the original collection,
and in the second one would be the first one
plus the second one, in the third one
would be the first plus the second plus the third,
so on and so forth.
there's inclusive_scan, exclusive_scan,
transform inclusive_scan, transform exclusive_scan,
which have interesting names, let's say.
Or inclusive_scan is the same thing as partial_sum,
except it can be run in parallel.
Exclusive_scan is the same thing as inclusive_scan,
except it doesn't include the current element,
so for example, with exclusive_scan,
the second element would be equal
to the first element of the original collection,
the third one would be one plus two,
the fourth one would be one plus two plus three,
and so on and so forth,
and the transform versions of those two guys
take a function, apply it to the collection,
and then perform the inclusive slash exclusive scan.
Inner_product makes the inner product of the collection
which is a multiplication
of the counterpart elements
and then summing that whole thing.
Adjacent difference makes the difference
between every two neighbors in the collection,
and sample, appearing in C++17,
takes something that can return some,
that can generate random numbers,
and it takes a number,
say n, and it produces n element
of that collection, selected randomly.
Apart from querying a value, we can query a property.
There's all_of, any_of and none_of,
which are really useful in everyday code.
All_of takes collection and a predicate,
returns if all of the elements satisfy that predicate,
any_of if at least one element satisfy that predicate,
and none_of if no element satisfy that predicate.
Now, what do you think all_of return,
returns with an empty collection?
What do you think, Fred?
Does everyone, everyone agrees with Fred?
Yeah, that's true.
Any_of on an empty collection?
Come on, there's only two possible answers.
Yeah, true, absolutely.
That was querying a property on one range.
We can also query a property on two ranges,
which is essentially different ways of comparing them.
The simplest way to compare two ranges
is to see if they have the exact same contents,
so the element would be equal two by two
and it would have the same size
and that's what std::equal returns, it returns a Boolean.
Now, if we'd like to know if the two collections
contain the same elements but not necessarily
in the same order, that's is_permutation,
also returning a Boolean.
Now, we can also compare ranges
and say which one is smaller than the other one.
To define smaller, we could go with size.
That's not very precise, there's another way to do that,
is going back to the alphabetical,
lexicographical ordering, all right.
In this example, I've used characters,
but that can be with any type
that has a comparison operator.
You can see on this example that,
the left collection is smaller
than the second one, than the right one.
If it was in, if they were in a dictionary, right,
even though it's longer in terms of size,
it would come before in a dictionary,
and that's what lexicographical_compare returns
in the form of a Boolean.
Now, the last way to compare two collection
is to traverse them both
and stop whenever they start to differ.
That's what mismatch has, std::mismatch,
and it returns a pair of iterators
pointing to the respective position
of where they start to differ in the two collections.
Now, a classic thing to extract
in a collection is a position,
like looking for something,
or to look for something in a collection now,
essentially, two ways to do that.
It depends on whether the collection is sorted
or not sorted.
If it's sorted, we can use a binary search.
It's not sorted, we'll have to go all the way through
from the beginning.
Let's start with a not sorted case
because it has the lower number of algorithms.
Well, the simplest one, and very famous one,
is find, std::find takes a value,
takes, sorry, begin and end and value,
and returns the iterator where,
pointing to that value.
Now, or end, if that value is not found.
Now, it has a sort of like twin brother
that's much less famous, but quite useful as well
and it's called adjacent_find,
and that returns the first position
where two adjacent value occur
and are equal to the value search,
so adjacent_find takes a beginning and an end and a value
and returns the first position where two of those values
appear in a row.
On the sorted side, we are not really looking for a value,
because searching for a given value could,
it could be at several places, and since it's sorted,
they would be lumped together,
all right, so in this example,
if we're searching for orange,
we're actually looking for a sub range
that could be empty for orange is not there at all,
and that's what equal_range returns.
Search in a sorted collection will use equal_range.
There are other algorithms that sort of like,
look like it, lower_bound and upper_bound,
and that only indicate positions to insert elements.
Like, if I were to insert a new orange
at the left of the existing orange, I would use lower_bound,
and at the right of the existing orange,
I would use upper_bound, and there's this guy, binary_search
that returns a Boolean, just appear, unexpected,
because it takes a beginning and end and a value
and only tells you whether it's there or not,
but doesn't tell you where it found it,
and it uses a binary search, which is a good thing. (laughs)
Now, we've been looking for one value in a collection
like orange, we can also look for a range of value
in a collection, like, looking for the first occurrence
of the sub range in a big range,
like looking for that range on the left in the big range.
To do that, there's an algorithm
that has a very bizarre name,
because it's called search.
I don't know what you think, but for me,
search is almost the same as find,
except find says that it will find it, right,
and search says it will try to find it,
but search has nothing to do with find.
It searches a sub range into a range.
That's not the best name.
The best, I think the most curious name
in the whole STL library is what follows,
which is looking for a sub range but starting from the end.
It's called find_end.
That's good to know, isn't it?
And what we can search in a sub range
is any of the value in the little range
finding its first occurrence in the big range
and that's find_first_of.
And finally, we can search for a relative value
which is the largest one or the smallest one.
That's max_element or min_element, or both,
minmax_element, that returns a pair of iterators
pointing to the max and the min element,
sorry, the min and the max element.
Right, we've been around the largest part of the world.
Now we're going to move in my favorite place.
It's the glorious county of the algorithms on sets,
because they're glorious.
Well, what's a set to begin with?
It includes std::set but not only.
In C++, what we call a set is any sorted collection,
so a std::set is sorted and is a set,
but a sorted vector, for the purpose of the STL algorithms,
is also considered as a set.
Set_difference, which is my favorite algorithm,
takes two sets and returns
the elements that are in the first one
but not in the second one,
and its end phase is like that,
it produces this output via an output iterator.
I like it so much because it's useful all the time,
and it's also in linear complexity,
and it would be easy to implement in quadratic complexity
but it's in linear complexity because it uses the fact
that the input that's sorted,
and also its output is sorted.
Set_difference has siblings, set_intersection,
that returns the element that are both in A and in B,
set_union that returns element that are in A or in B,
set_symmetric_difference, which is, I think,
the longest name yet, it's the longest name
in the whole library, fun fact.
That returns the elements that are in A and not in B,
and those that are in B and not in A,
includes, that returns a Boolean, that indicates
whether all the elements of B are also in A,
and merge, that takes two sorted collection
and puts them together into one big sorted collection.
Oh, that's it, that was too short.
Okay, let's take a step back.
We've been in the most populated regions of the world,
all over here, we now have just
these parts, small parts, to cover,
so maybe we'll take an hour after all.
So let's go to this place that, the place of movers,
so movers are algorithms that move things around.
The simplest way to move things around
is probably to copy them, and so std::copy,
it will be the simplest algorithm in the whole library.
Takes two collection, or takes one collection
with a begin and an end, and the output iterator
of a second collection or a back inserter
or stream iterator or whatever,
and copies every element of the first collection
into this output iterator.
There's also std::move.
Like, we know std::move like std::move,
but there's also std::move, the algorithm,
and it takes a begin and an end
and our output iterator just like std::copy,
and it calls the usual std::move on every element
of the input collection, so after std::move the algorithm,
all the elements of the input collection are moved,
and to swap the contents of two ranges, there's swap ranges
and they all obviously have to be the same size.
Now, a little exercise.
Let's say that we've got a collection at the top,
one, two, three, all the way up to 10,
and we would like to write some code
and use an algorithm that we've seen
from the beginning of our talk up until now,
to turn it into the collection at the bottom,
so we want to copy the first five elements
four positions down.
Which algorithm do you think we could use to do that?
Come on, there's less than 105 possible answers.
Yeah. - Copy.
- Copy, absolutely.
So, we'll use copy.
I thought to use copy as well,
and then it, I think it crashed when I used it.
So let's see what happens, what's happening.
So, the first thing copy does
is to copy the first element, right, to the output,
so I don't know if you are thinking
about that, but I put as an output iterator,
begin, plus four, or plus, sorry, plus three.
And then we've lost a value, we've lost four, right?
Which is annoying.
What we would like to do is to copy,
but starting from the last one, right?
Because we don't care about the eight
that used to be there, and then move all the way back up,
yeah, so what we would really like to do
is to copy, but backwards.
That's what we're gonna say, right?
- Reverse copy. - Yeah, copy backwards.
Pretty much the same, hey.
And there's also move backwards
that does the same thing, but moves.
Right, so that's the movers.
Now, just down around the corner,
there's the value modifiers, which I would have expected
to be more more numerous, but there's just four of them
in a quite large piece of land.
So, those guys actually change the values
inside of a collection, so, how can we change the values
inside of a collection?
One easy way to do that is to put the same value everywhere.
That's what fill does, it takes a begin, an end and a value
and copies that values all the way through.
Another way that's a bit similar in spirit
is to use a function that can be called
with no argument, and we call that function once
for every element of the collection.
Another way to fill a collection that's quite useful
to have, like, I don't know, a unit test, stuff like that,
to have quickly a sequence of values,
is iota, which has a funny name, I think.
It takes begin, an end, a value,
put that value at the beginning,
and then increment it and increment it,
until it fills the whole collection with increments.
And finally, there's replace,
that quite expectedly
replaces the values in a collection,
like replace 42, 43 will replace every 42 by a 43
in a collection of ints.
Right, now, jumping above the water,
there's this island of the structure changers.
What I call the structure changers, is the algorithms
that after they've done their job,
the collection doesn't look the same even from afar.
So, there are two of them, remove and unique.
Remove is used
to remove values, but it has something peculiar with it.
Since STL algorithms only act as the iterators
of a collection and not the collections themselves,
they can't change the size for example of a collection.
They can't perform an erase in a collection.
All they can do is to change the values
between the begin and the end,
so what remove, std::remove does,
is to pull up the collection
by leaving only those that should not be removed,
so if we want to remove the 99s,
we use std::remove, begin, end, 99,
and it will pull up everything that's left without the 99
and what's at the end is not specified.
We can't rely on it, it could be the element
that were there before, it could be the 99s,
it could be anything else.
It could change, it could vary from compiler to compiler,
from version to version, so we can't rely on that.
And to actually remove those element
from, say, a vector, we have to call a method
on the container, like erase on a vector.
We'd like to erase all the element that are crossed out,
and to do that, remove returns an iterator
that points to the first element that's here crossed out,
so we have to erase between what remove returns
and the end,
which is quite of a mouthful of code
to remove the 99 in the collection, isn't it?
I think that we should not use that code,
and we should drop it into a function with a nicer name,
and use this in our everyday code.
I reckon that's been a proposal by STL,
Mr. STL, the guy, to add those functions to the standard,
but it hasn't been accepted yet, so until it is,
if it is, we should just wrap this function,
it's quite an easy thing to do.
If you want to grab the code, it's been published
on Fluent C++ last week, I reckon.
Unique does something quite similar.
It removes the duplicates in a collection,
or more precisely the adjacent duplicates in a collection.
Right, so if we do unique here,
this collection has several 99s,
and it will remove only the adjacent 99,
because it has a linear complexity,
it will only traverse the collection once,
and unique will also pull up the values
that are to be left and return an iterator to the values,
to the, yeah, the values that are crossed out.
Those value, we can't rely on them, just like remove,
and we have to erase them, quite a bit of code,
from not much, and we should package that into a function
with a better name.
Whether unique is a better name, I'm not sure,
but we should at least package that into a function.
Have we got a question there?
Sorry, I couldn't hear that.
- [Man] Sorry, one was not removed.
- Indeed, one was not removed.
That's a good observation, and it's not removed
because there's no adjacent ones in the collection.
Thanks for that.
We've unlocked a new rune, copy.
We've seen all the algorithms that are combined with copy
in the STL algorithms library,
so, copy, you can tack it on an algorithm
like those algorithms and it creates new algorithms
that do the same thing but in a new collection,
so like remove or unique or replace or whatever,
they operate in place.
Those guys, they leave the collection untouched
and they take an output iterator
and they produce the output to that output iterator.
We've also unlocked if.
That, as a predicate, so, where,
say, find, for example was taking a value,
find_if takes a predicate
but does essentially the same thing.
And we're going to go to that part
we started the talk with, the lonely islands,
with for_each and transform.
Let's start with transform.
There's nothing wrong with for_each or transform.
The reason why I put them on lonely islands
is because I couldn't see in what family they would belong.
I think they sort of like, separate,
even though it's not a problem in itself.
So, transform, essentially it applies a function
to the elements of a collection,
so it takes a collection, begin, end,
a function, f, and an output, like an output iterator,
such as this back_inserter here.
And it produces the, well, the application
of that function to every element of the collection.
What's a bit less famous about transform
is its other overload.
The one that takes two collections
and a function that takes two parameters, all right.
It applies that function just like transform
with one input collection to the two collection
by feeding the two collection into f
for each element and producing the output.
Yeah, like for example, if you'd like to sum
the elements of two collection two by two,
you can do that with one line of coding with transform
and f would be std::plus.
And there's for_each, and for_each, if we think
about what it does, the for_each takes a begin,
an end, and some piece of code, a function,
it could be a Lambda for example, or a regular function,
and it applies that function to every element.
What's interesting to note is that it doesn't care
about what f returns,
so, for the purpose of for_each,
f might as well return void.
Now, what does a function
that returns void do?
Anyone, an idea?
- [Man] It makes side-effects.
- Yeah, exactly, side-effects.
For_each is made to perform side-effects.
Now, are side-effects a good thing or a bad thing
is absolutely not the purpose of that talk,
even thought I think that some case are useful,
with side-effects, but for-each is made
for doing side-effects.
That could be side-effects on the elements themselves,
modifying the elements of a collection,
or that could be side-effect in the more general sense
of sending stuff to the logger or whatever,
right, but the for_each is made for side-effects.
Using for_each for making anything else
such as a partition or a find or whatever,
is not the right usage of for_each,
there are algorithms that are more appropriate
than for_each, and if there's no algorithm more appropriate
than for_each in the STL algorithms,
then the algorithms outside of the STL algorithm,
we briefly talk about them in a minute.
Okay, so, we've been literally
all around the world.
We've started down there, we've been in land of queries,
the glorious county of algorithm on sets,
movers, the value modifiers, and the structure changers,
and even up there.
There's only one place we haven't been yet,
the raw memory.
So we're gonna finish up with that one.
What does that mean, algorithms in the raw memory?
Well, if you think back to fill
and copy and move, they have one thing in common.
Does anyone see what they have in common?
It's that they use the assignment operator.
For_each assigns a 42, I'm sorry.
Fill assigns a 42, copy assigns with the copy assignment,
move assigns with the move assignment.
They all use an assignment.
Now, if we use an assignment operator,
it means that the object has been constructed,
and hopefully that's true.
But, in some rarer cases,
we have objects that are not constructed yet
if we have just the memory, just chunks of memory
that we got from somewhere, and we'd like to construct
instead of calling the assignment operator,
we'd like to call constructor on those chunks of memory.
For that, we use the uninitialized counterpart,
uninitialized_fill, uninitialized_copy, uninitialized_move,
and these use constructors, so this takes,
this is the constructor that takes a value,
this is a copy constructor, this is a move constructor.
So, in practice, you get a chunk of memory from somewhere,
like shared memory or wherever,
and you'd like to fill it with values
but you can't call fill because you can't call
the assignment operator because there is just raw memory,
right, it hasn't been initialized yet.
So, we need to call the constructor.
This is what uninitialized_fill does, right,
it takes the two pointers for at the beginning and the end
and calls the value constructor,
leading to an initialization
of that chunk of memory.
Now, once we're done with it, we want to call the destructor
of those guys because we've been in charge
of the constructor, we're probably also in charge
of calling the destructor,
and that's what std::destroy does.
Kind of like, sounds familiar, right.
Destroy, but we don't really use it on a day-to-day basis,
but that's what it does,
so, destroy will destroy the,
calls the destructor of all the elements in that collection
and if we'd like to call the other kinds of constructor,
such as default constructor or value constructor,
what value initialization goes in it,
and we've unlocked our final rune, the underscore n,
that changes a little the interface
like instead of taking a begin and an end,
it takes a begin and a size.
Let's take an example.
So, still using fill, so fill takes a begin,
an end, value, put that value all the way through,
fill_n takes a begin and a size, okay,
and a value and it fills the first five elements
starting from begin, it fills them with the 42s.
Now, what do you think this line of,
this third line of code does?
Imagine that collection is a vector,
an empty vector, for example.
What do you think is in collection after executing
that third line of code?
Say that a little louder.
- [Man] Insert five elements equal to 42.
That would insert five elements equal to 42,
right, because it would assign
through the back_inserter operator, five times.
Right, this time we've been around the world, everywhere.
You know everything in the STL algorithms library.
Well, for one thing, you can use them in your codes
to make it more expressive, all right.
You can think about if you want to write a for-loop,
think about if you could use an algorithm instead
or if you could replace existing for-loops
that are like a bit of a problem in your code,
by an STL algorithm to make it smoother to work with,
and if you'd like a second pair of eyes,
I always like to read code, so you can reach out to me
and show me your code, then I can have a look
and think about which algorithm with you
we can put in your code,
I'd be more than happy to look at code.
If you'd like to see more algorithms,
there are some outside of the STL
and the library nextdoor is Boost.
There's those Boost.Algorithms,
which contains all the algorithms are in the same spirit
as the algorithms of the STL.
Soon I will publish on Fluent C++ a series of articles
going all through all these guys.
To go further, it's a good thing to understand
in depth, the STL algorithms.
I think it's a good investment of our time
about their complexity, about prerequisite,
think about sorted collections for example,
and see how they're implemented,
and that's often quite instructive.
And finally, if you use them on a day-to-day basis,
you can get inspired.
You can have a better intuition
of what abstractions work well,
and that's fundamental for writing good code
and that intuition, you can use that in your own code.
And once you're familiar enough,
you can start thinking about writing your own algorithms
so what sort of algorithm can we write?
Well, we can combine an algorithm, an existing algorithm
with an existing rune to create a new combination
like sort_copy doesn't exist, for example,
or we could add a city on the map.
If I were to add something, I think I would add something
to the algorithm on sets, do something like an algorithm
that would have three outputs,
those that are in A not in B, B not in A,
and both in A and B, all in a single pass, I think.
I don't know.
If you think about things to add,
I'm happy to hear about that, too,
or start a new family.
If you'd like to get the map, you can download it
and there you can also order the poster
that you can hang in your homes and offices,
and for the people in the room,
if you'd like to acquire a poster right now,
like this one, I've got a bunch of them with me
so you can come and see me after the talk.
If you'd like to get in touch,
you can find me on Twitter, @JoBaccara
and if you're interested in reading about the STL
or about expressive code in general,
then check out fluentcpp.com, Fluent C++
with a new post every Tuesday and every Friday,
about expressive code in C++.