CppCon 2018: Jonathan Boccara “105 STL Algorithms in Less Than an Hour”
ฝัง
- เผยแพร่เมื่อ 15 มิ.ย. 2024
- CppCon.org
-
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2018
-
We are all aware that we should know the STL algorithms. Including them in our designs allows us to make our code more expressive and more robust. And sometimes, in a spectacular way.
But do you know your STL algorithms?
In this presentation, you’ll see the 105 algorithms that the STL currently has, including those added in C++11 and C++17. But more than just a listing, the point of this presentation is to highlight the different groups of algorithms, the patterns they form in the STL, and how the algorithms relate together. And all this in an entertaining way.
This kind of big picture is the best way I know to actually remember them all, and constitute a toolbox chock-full of ways to make our code more expressive and more robust.
-
Jonathan Boccara, Murex
Jonathan Boccara is a Principal Engineering Lead at Murex where he works on large codebases in C++.
His primary focus is searching how to make code more expressive. He has dedicated his blog, Fluent C++, to writing expressive code in C++.
He also gives internal trainings on C++ every day, in the short format called "Dailies".
-
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/registration/
*-----*
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!
Amazing presentation. Absolutely recommended for every STL beginners!
i am an STL beginner and i can confirm that.
As a teacher of programming, I'm absolutely amazed and inspired about / by this map. A great educational tool.
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
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!
OMG , It's not just a video , It's a movie. I never enjoyed that much before !!
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.
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.
Outstanding and I've learned quite a bit over the years by regularly visiting his web-site!
I need to reread your slides. Great and innovative explanation!
Amazing presentation and glance of STL algorithms
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?
Excellent presentation. Concise and very informative.
That map was phenomenal !. Remarkable presentation!
I love how much effort went into this. Great talk
Awesome talk. Johnathon Boccara explains it beautifully! Acquired a few new tools :-)
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.
...and I thought my day wouldn't get any better!
Amazing talk!
One of the best talks of all time on cppcon.
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.)
Thank you for the great explanation,
really helpful
clear presentation, recommended for me in the 2017
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
Really great presentation
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...
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
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 ;)
Great content. Coming from learncpp!
Can't like this video enough.
Great presentation! Thanks!
Very welcome!
This is pure gold!
Thanks for the Amazing presentation !
Thank you too!
And now I want the map!
great presentation
Thank you for the talk
Thank you very match!
Superb. Kudos.
24:44 francais spotted, excellente vidéos
Great talk!
Great video, thanks
Glad you liked it!
Great talk
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 😍
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.
Reminded me a C++ map by Alena ;)
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/
The talk is awesome.
that was really amazing
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++.
are there other videos on rest of the stl library ?
Are the posters no longer available? D:
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?"
greate talk, thanks a lot
When the man pulled out the map of algorithms I knew I was on some nerd shit
Why didn't the committee overload functions like fill instead of writing new ones with _n like fill_n?
Hmmm... he said that set_symetric_difference is the longest name, but I think uninitialized_default_construct_n is longer :D
Now, this is what i am looking for.
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
It's also for_every and for_any
I want this map.
WOW
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.
C++ FTW!!!!!! :D
13:20
Once he said "use case", I split the scene soon after.
i didnt get the each joke at 13:24 :(
where can I get this map
www.fluentcpp.com/getTheMap/
56:44
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.
What accent is that?
24:44 C plüs plüs
Well, to be honest, this presentation is useful but that's just reading a cpp STL docs...
i managed 15 minutes.
Jonathan is overly charismatic lol
1.25x do yourself a favour
All these Algorithms deal with Sorting and Looking for,
Programmer need to dig in mathematics to change these situations.
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)
105 ways to make your code run even slower
@@Lunaticracy I feel sorry for the users of the code.
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