Conor Hoekstra mentioned this talk in his algorithm talks and I'll admit this is a wonderful presentation. Just the way to present the idea and the vehicles to carry the presentation are so nice that you can't help but want to just dabble a tiny bit into algorithms, just to get a piece of the presentation's atmosphere. Very nice presentation!
24:00 if you can write your algorithm as a call to reduce, then you have made an nonsequential parallel algorithm. If you want to introduce yourself to multithreaded programming, this is the best place to start, as it is the fundamental algorithm for highly parallel code.
As someone who just started learning C++ and took a yt-course which only covered the syntax, this was very helpful and I'm excited to use it in my projects.
I somehow left lower_bound and upper_bound out of my notes, thought we might have missed it, so re-watched. Technically, the whole thing doesn't need to necessarily be fully sorted for a lower_bound call to work, as long as everything < val comes before the first element equal to val, and upper bound should be good as long as everything there onwards is > val. They both give correct answers for all val if the whole range is fully sorted, by far the neatest case.
Actually, I believe the entire functuon is redundant because you can use partition_point with the right predicate, which as you describe only demands that the range is partitioned with respect to this predicate.
Great talk! Few notes: 22:51 There is no such thing as is_partitioned_until in STL 51:51 C++17+: uninitialized_move, destroy, uninitialized_default_construct, uninitialized_default_construct
Thanks, Jonathan for the good talk, that was the most productive hour in my C++ learning history! 105 STL Algos in less an hour! Is your world map from a mindmap?
Very informative talk. Here are the obligatory flies in the ointment: 30:29 adjacent_find does not take a value and it does not return the first position where there are two adjacent occurrences of the value. Instead, adjacent_find returns the first position where ANY two adjacent and equal values appear. (You can use the overload with binary predicate to perform the operation described, but that's, I reckon, not a common use case, and requires extra typing at least.) 31:40 This is misleading, *all* of lower_bound, upper_bound, equal_range and binary_search do a binary search (the complexity guarantees practically mandate that). binary_search is just the only algorithm to carry the binary search in its name. (If you are extra pedantic, equal_range actually does two binary searches, one of which may be limited in scope.)
Interesting video. I will definitely be saving the slides and pdf offline for reference. *Edit: After reviewing the github link shared in the video description, Jonathan's talk is not among the presentations shown in CppCon2018 in the list in their README ~Wonders if they found him relevant enough for inclusion~ *
Really nice, but I wanted to see how the code will look like, so I did some exercises. Fun fact: for me std::copy (38:20) worked just fine and even produced the correct result! That's so weird. I think it's undefined behavior, though.
It would have been helpful to see the signatures of the functions. Also it would have been nice to mention lower_bound can be used if one wants binary search that finds an item. More (any) uses would have been great even if this makes the talk 105 minutes long.
Am I working with too many abbreviations if my first thought at IOTA - quite a funny name was that it is "increment over the array - why is that funny?"
if you have no idea how code works most likely when need arise you wouldn't realise which algorithm is the most appropriate. That's why big tech companies are so obsessed with Algorithms and tricky problems. If you pass them, it's most likely that you will solve any future problem with high efficiency.
I should have watched that video a year ago. wouldn't have solved my problems cause the requirements were just so strange but it might have made some of my constructs a little easier to read. remove-erase: In some situations you just want to remove the elements but not erase them. Does not happen often, but can be quit useful for example if you need a static memory footprint. Would be good if there was a "pure" erase too.
I wish there were "functional" equivalents for them all. Like list, vector, etc. should have a common base-class "container" (or so) that has a begin() and end() method. And then there should be inline for_each(container& c, f) etc. which does nothing other than call the other for_each(c.begin(), c.end(), f). The absence of these forces you to first construct the container and then pass it to the algorithm. Kevlin Henney calls such code "object-assembler" because of the "first X then Y" way of thinking. I would just prefer to do that in a nested way in one single expression, which I would consider a more "functional" way of doing it. In particular, it would allow you to compose the algorithms!
The reason you have to pass iterators to algorithms is that it promises that the algorithm will not modify the underlying container (save for giving a back_inserter to transform, generate, etc). This strong promise means that you are guaranteed that none of your other iterators will be invalidated after the algorithm ends.
Also, this would put more requirements on the container using the algorithm. You have to supply an overload for std::begin and std::end OR have a container.begin and container.end. By only requiring an iterator, you can pass raw pointers to algorithms, and provided they meet the criteria, they will function just as well as a vector.
Ranges will get you that sugar, in C++20, and much, much more. You also don't need a common base-class to write generic code - they have a common Concept - Container! It is easy to implement the `for_each` you want above :), or should I say the N versions of it, since you have quite a large design space for a functional for_each :)
But thats what for each does already? It works on anything with iterators ie any container you can dream up. Plus const_iterators exist, giving you the ability to trust algorithms to not have side effects on your data, which is about as "functional" as you practically often want to be.
It's great, and std algorithms are probably the best designed part of the C++ universe. Why do we need std::move, really? To create something in a function and then move it to a container? Or to "move it" out? It's a bit convoluted and unnecessary.
3:08 The perfect example of someone taking some horribly written code and turning into exponentially worse code albeit more terse code (the terseness isn't a good thing here, it just makes it worse)
4:20 "When we write for loops"... UB... And NO! Literally NOT everything can happen, only what is allowed by the law of physics can happen. But now I know not to trust anything you say. Well done. You lost my trust in the first 5 minutes. ;) "With the STL algorithms this doesn't happen they said"... int arr[3] = { 1,2,3 }; int sum; sum = accumulate(arr, arr+5, 0); /// Oh, NO, how could the STL algorithm fail us sum = 0; for (auto v : arr) sum += v; /// meanwhile the for loop is just fine sum = accumulate(begin(arr), end(arr), 0); /// to be fair we can make it safe with the STL, but did you notice how it is longer than the for loop? ... even without the std:: sum = std::accumulate(std::begin(arr), std::end(arr), 0); /// now it's "beautiful"! sum = 0; for (auto const& v : arr) sum += v; /// the for loop is still shorter even with const ref... "STL algorithms are used by" ... BS number ... and for loops are used orders of magnitude more... Just remember: for loops run the world
Haha. That world map. As nerdy as it gets.
Loving it.
What's amazing is that they work on things besides std::map !
Very clever. Not only will I remember the algorithms but I will remember the map too now :) Thanks for the good talk!
Conor Hoekstra mentioned this talk in his algorithm talks and I'll admit this is a wonderful presentation. Just the way to present the idea and the vehicles to carry the presentation are so nice that you can't help but want to just dabble a tiny bit into algorithms, just to get a piece of the presentation's atmosphere. Very nice presentation!
Can't like this video enough.
Clear, concise and entertained. Having been through all std algorithms at least once is absolutely educative.
I will remember your talk. Thanks man.
"std" I see what you did there
As a teacher of programming, I'm absolutely amazed and inspired about / by this map. A great educational tool.
Amazing presentation. Absolutely recommended for every STL beginners!
i am an STL beginner and i can confirm that.
OMG , It's not just a video , It's a movie. I never enjoyed that much before !!
Outstanding and I've learned quite a bit over the years by regularly visiting his web-site!
24:00 if you can write your algorithm as a call to reduce, then you have made an nonsequential parallel algorithm. If you want to introduce yourself to multithreaded programming, this is the best place to start, as it is the fundamental algorithm for highly parallel code.
Nice presentation. I was looking for a tutorial on the STL, and you did it very succinctly and well.
I'll be sure to check your blog out. Thanks.
That map was phenomenal !. Remarkable presentation!
As someone who just started learning C++ and took a yt-course which only covered the syntax, this was very helpful and I'm excited to use it in my projects.
I love how much effort went into this. Great talk
I somehow left lower_bound and upper_bound out of my notes, thought we might have missed it, so re-watched. Technically, the whole thing doesn't need to necessarily be fully sorted for a lower_bound call to work, as long as everything < val comes before the first element equal to val, and upper bound should be good as long as everything there onwards is > val. They both give correct answers for all val if the whole range is fully sorted, by far the neatest case.
Actually, I believe the entire functuon is redundant because you can use partition_point with the right predicate, which as you describe only demands that the range is partitioned with respect to this predicate.
I need to reread your slides. Great and innovative explanation!
Great talk! Few notes:
22:51 There is no such thing as is_partitioned_until in STL
51:51 C++17+: uninitialized_move, destroy, uninitialized_default_construct, uninitialized_default_construct
"There is no such thing as is_partitioned_until in STL" ... yet!
is partitioned until partition point xd
This is pure gold!
Awesome talk. Johnathon Boccara explains it beautifully! Acquired a few new tools :-)
Amazing presentation and glance of STL algorithms
clear presentation, recommended for me in the 2017
...and I thought my day wouldn't get any better!
Amazing talk!
Thanks, Jonathan for the good talk, that was the most productive hour in my C++ learning history! 105 STL Algos in less an hour! Is your world map from a mindmap?
Great content. Coming from learncpp!
Great presentation! Thanks!
Very welcome!
Excellent presentation. Concise and very informative.
Very informative talk. Here are the obligatory flies in the ointment:
30:29 adjacent_find does not take a value and it does not return the first position where there are two adjacent occurrences of the value. Instead, adjacent_find returns the first position where ANY two adjacent and equal values appear. (You can use the overload with binary predicate to perform the operation described, but that's, I reckon, not a common use case, and requires extra typing at least.)
31:40 This is misleading, *all* of lower_bound, upper_bound, equal_range and binary_search do a binary search (the complexity guarantees practically mandate that). binary_search is just the only algorithm to carry the binary search in its name. (If you are extra pedantic, equal_range actually does two binary searches, one of which may be limited in scope.)
Lovely talk, really good english and you look better on camera rather than google images
The map is AWESOME
9/10 talk, would listen again
Sry for the late reply... Please give me your 10/10 talk ;)
Thanks for the Amazing presentation !
Thank you too!
Interesting video. I will definitely be saving the slides and pdf offline for reference. *Edit: After reviewing the github link shared in the video description, Jonathan's talk is not among the presentations shown in CppCon2018 in the list in their README ~Wonders if they found him relevant enough for inclusion~ *
I found one. 2018.cppconf.ru/talks/day-1/track-a/3.pdf
Great talk
24:44 francais spotted, excellente vidéos
When the man pulled out the map of algorithms I knew I was on some nerd shit
Great talk! Any plans of updating it for C++20 (with ranges and other new algorithms)?
dude, not even c++17 is fully supported by major compiler vendors...
@darkee03 now it is :)
Great talk!
And now I want the map!
are there other videos on rest of the stl library ?
Really nice, but I wanted to see how the code will look like, so I did some exercises. Fun fact: for me std::copy (38:20) worked just fine and even produced the correct result! That's so weird. I think it's undefined behavior, though.
Thank you for the great explanation,
really helpful
Really great presentation
Are the posters no longer available? D:
Why didn't the committee overload functions like fill instead of writing new ones with _n like fill_n?
great presentation
Thank you for the talk
Great video, thanks
Glad you liked it!
Used only for std::sort until now.
Once you start using other algorithms you really can't go back. is still something I miss when writing other languages besides C++.
It would have been helpful to see the signatures of the functions. Also it would have been nice to mention lower_bound can be used if one wants binary search that finds an item. More (any) uses would have been great even if this makes the talk 105 minutes long.
Am I working with too many abbreviations if my first thought at IOTA - quite a funny name was that it is "increment over the array - why is that funny?"
i didnt get the each joke at 13:24 :(
The talk is awesome.
Superb. Kudos.
Still my interviewer ask me to write binary search tree using doubly linked list with raw pointer😣.
Did they want you to build a BST using the values from the doubly linked list?
if you have no idea how code works most likely when need arise you wouldn't realise which algorithm is the most appropriate.
That's why big tech companies are so obsessed with Algorithms and tricky problems. If you pass them, it's most likely that you will solve any future problem with high efficiency.
@@zuradzindzibadze8733 Even if you don't properly "pass" them, seeing how you go about solving a hard problem can outline your problem-solving skills.
Good job! I want that map, haha~
Yeah, this map needs to be in a museum, er, store. EDIT: As someone else pointed out: www.fluentcpp.com/getTheMap/
Reminded me a C++ map by Alena ;)
that was really amazing
Thank you very match!
I should have watched that video a year ago.
wouldn't have solved my problems cause the requirements were just so strange but it might have made some of my constructs a little easier to read.
remove-erase: In some situations you just want to remove the elements but not erase them. Does not happen often, but can be quit useful for example if you need a static memory footprint.
Would be good if there was a "pure" erase too.
I need that video which start at 7.55 😍
I want this map.
Once he said "use case", I split the scene soon after.
It's also for_every and for_any
Hmmm... he said that set_symetric_difference is the longest name, but I think uninitialized_default_construct_n is longer :D
amazing presentation , where can i find the presentation slides ? i didn't found them in the link that's in the description
I found one. 2018.cppconf.ru/talks/day-1/track-a/3.pdf
Now, this is what i am looking for.
13:20
greate talk, thanks a lot
24:44 C plüs plüs
Hi ayadi, rivez C++
What accent is that?
C++ FTW!!!!!! :D
I wish there were "functional" equivalents for them all. Like list, vector, etc. should have a common base-class "container" (or so) that has a begin() and end() method. And then there should be inline for_each(container& c, f) etc. which does nothing other than call the other for_each(c.begin(), c.end(), f). The absence of these forces you to first construct the container and then pass it to the algorithm. Kevlin Henney calls such code "object-assembler" because of the "first X then Y" way of thinking. I would just prefer to do that in a nested way in one single expression, which I would consider a more "functional" way of doing it. In particular, it would allow you to compose the algorithms!
The reason you have to pass iterators to algorithms is that it promises that the algorithm will not modify the underlying container (save for giving a back_inserter to transform, generate, etc). This strong promise means that you are guaranteed that none of your other iterators will be invalidated after the algorithm ends.
Also, this would put more requirements on the container using the algorithm. You have to supply an overload for std::begin and std::end OR have a container.begin and container.end. By only requiring an iterator, you can pass raw pointers to algorithms, and provided they meet the criteria, they will function just as well as a vector.
Ranges will get you that sugar, in C++20, and much, much more. You also don't need a common base-class to write generic code - they have a common Concept - Container! It is easy to implement the `for_each` you want above :), or should I say the N versions of it, since you have quite a large design space for a functional for_each :)
But thats what for each does already? It works on anything with iterators ie any container you can dream up. Plus const_iterators exist, giving you the ability to trust algorithms to not have side effects on your data, which is about as "functional" as you practically often want to be.
where can I get this map
www.fluentcpp.com/getTheMap/
56:44
WOW
It's great, and std algorithms are probably the best designed part of the C++ universe. Why do we need std::move, really? To create something in a function and then move it to a container? Or to "move it" out? It's a bit convoluted and unnecessary.
Well, to be honest, this presentation is useful but that's just reading a cpp STL docs...
3:08 The perfect example of someone taking some horribly written code and turning into exponentially worse code albeit more terse code (the terseness isn't a good thing here, it just makes it worse)
1.25x do yourself a favour
Jonathan is overly charismatic lol
i managed 15 minutes.
All these Algorithms deal with Sorting and Looking for,
Programmer need to dig in mathematics to change these situations.
4:20 "When we write for loops"... UB... And NO! Literally NOT everything can happen, only what is allowed by the law of physics can happen.
But now I know not to trust anything you say. Well done. You lost my trust in the first 5 minutes. ;)
"With the STL algorithms this doesn't happen they said"...
int arr[3] = { 1,2,3 }; int sum;
sum = accumulate(arr, arr+5, 0); /// Oh, NO, how could the STL algorithm fail us
sum = 0; for (auto v : arr) sum += v; /// meanwhile the for loop is just fine
sum = accumulate(begin(arr), end(arr), 0); /// to be fair we can make it safe with the STL, but did you notice how it is longer than the for loop? ... even without the std::
sum = std::accumulate(std::begin(arr), std::end(arr), 0); /// now it's "beautiful"!
sum = 0; for (auto const& v : arr) sum += v; /// the for loop is still shorter even with const ref...
"STL algorithms are used by" ... BS number ...
and for loops are used orders of magnitude more...
Just remember: for loops run the world
105 ways to make your code run even slower
@@Lunaticracy I feel sorry for the users of the code.