A major reason people describe the "rabbit hole" they're in is Stack Overflow closes questions without sufficient effort behind them, and people downvote any question like that as well.
36:00 Alexander Stepanov (STL inventor) actually discusses this second-smallest problem and shows the minimal N+logN comparison solution in one of his A9 lectures: ruclips.net/video/lWSYE-hRw0s/видео.html
Justin Meiners has written up some great course notes of Stepanov's A9 lectures - "Efficient Programming with Components". Chapter 10 is about the 'second-smallest' problem and the O(N+logN) solution.
Second problem: I would definitely use an explicit cast to unsigned char. And write a specific test for this. Else some developer after me could "auto everything" during some upgrade refactoring and break the code.
Funny, seeing the "better than nth_element" solution to the first problem with the "first_two" algorithm: that's how somebody that doesn't know the std algorithms would likely solve it. So "know your algorithms" is not only "know they exist" but also "know their weaknesses", because they're not always the best solution?
It's not surprising that nth_element does a lot more work. It loosely sorts the entire sequence because it matters what's left and right of the nth element. Partial sort does not have that overhead since it only moves a few elements to the beginning after a linear iteration
How do you mean that it "loosely sorts" the entire sequence in nth_element? The only requirement from nth_element is that values to the left are less than the pivot, and values to the right are greater. Partial sort means that elements to the left are less than, but also specifically sorted, while elements to the right are greater (but not in any specific order). Partial sort would seem to have specifically less entropy than nth_element and would seem to need more work to achieve that.
46:28 - I may be wrong about this, but I'm pretty sure you can pass _any_ char value to ispunct and it will always work. UB comes if you pass it values like 512, which cannot be converted to an unsigned char. If your platforms characters are signed, -5 can still be converted to an unsigned character, and it will usually (8 bit char, two's complement representation) get you the value 251.
You are incorrect, passing any negative char values to ispunct will not work. If the segment before the start of the table is not mapped to the process, you will get a segfault; if it is, you will get random garbage as a result. This happens because promotion to int happens before the function is even called; the char is loaded into a register, sign-extended to an int, and pushed into the stack for the call. Regarding the casting from char to int: implementations are not allowed to convert the (signed) char to unsigned char before promoting to int because this changes the value (in your example, from -5 to 251). The promotion must preserve the value, because otherwise, the semantics becomes different: for example, adding 5 to -5 gives 0, but adding 5 to 251 gives 256.
From a stackoverflow answer it seems like there is no UB in case of char overflow. It will simply take the modulo of the number (512 % 256 == 0). Also in cppreference it is emphasized that static_cast should be used on char type before invoking ispunct.
For the 2nd problem, I am really confused why the following approach works (my own walk-around but was not covered in this talk): Add "using namespace std;" and use ::ispunct instead of ispunt. Then the code will compile and run as expected. Please note that neither std::ispunct nor ispunct (without a scope ::) would work. Only ::ispunct works. What really confuses me is that given that I already added "using namespace std", what's the difference between ::ispunct and std::ispunct (or ispunct without a scope)?
A major reason people describe the "rabbit hole" they're in is Stack Overflow closes questions without sufficient effort behind them, and people downvote any question like that as well.
Really interesting concept for a talk!
I would gladly watch a whole RUclips series riffing on this idea :)
18:40 - and that's why I'm in love with Computer Science for the past three decades...
36:00 Alexander Stepanov (STL inventor) actually discusses this second-smallest problem and shows the minimal N+logN comparison solution in one of his A9 lectures: ruclips.net/video/lWSYE-hRw0s/видео.html
Justin Meiners has written up some great course notes of Stepanov's A9 lectures - "Efficient Programming with Components". Chapter 10 is about the 'second-smallest' problem and the O(N+logN) solution.
Second problem: I would definitely use an explicit cast to unsigned char. And write a specific test for this. Else some developer after me could "auto everything" during some upgrade refactoring and break the code.
Funny, seeing the "better than nth_element" solution to the first problem with the "first_two" algorithm: that's how somebody that doesn't know the std algorithms would likely solve it. So "know your algorithms" is not only "know they exist" but also "know their weaknesses", because they're not always the best solution?
It's not surprising that nth_element does a lot more work.
It loosely sorts the entire sequence because it matters what's left and right of the nth element.
Partial sort does not have that overhead since it only moves a few elements to the beginning after a linear iteration
How do you mean that it "loosely sorts" the entire sequence in nth_element? The only requirement from nth_element is that values to the left are less than the pivot, and values to the right are greater. Partial sort means that elements to the left are less than, but also specifically sorted, while elements to the right are greater (but not in any specific order). Partial sort would seem to have specifically less entropy than nth_element and would seem to need more work to achieve that.
rubber duck debugging for the win.
46:28 - I may be wrong about this, but I'm pretty sure you can pass _any_ char value to ispunct and it will always work. UB comes if you pass it values like 512, which cannot be converted to an unsigned char. If your platforms characters are signed, -5 can still be converted to an unsigned character, and it will usually (8 bit char, two's complement representation) get you the value 251.
You are incorrect, passing any negative char values to ispunct will not work. If the segment before the start of the table is not mapped to the process, you will get a segfault; if it is, you will get random garbage as a result. This happens because promotion to int happens before the function is even called; the char is loaded into a register, sign-extended to an int, and pushed into the stack for the call.
Regarding the casting from char to int: implementations are not allowed to convert the (signed) char to unsigned char before promoting to int because this changes the value (in your example, from -5 to 251). The promotion must preserve the value, because otherwise, the semantics becomes different: for example, adding 5 to -5 gives 0, but adding 5 to 251 gives 256.
From a stackoverflow answer it seems like there is no UB in case of char overflow. It will simply take the modulo of the number (512 % 256 == 0).
Also in cppreference it is emphasized that static_cast should be used on char type before invoking ispunct.
For the 2nd problem, I am really confused why the following approach works (my own walk-around but was not covered in this talk):
Add "using namespace std;" and use ::ispunct instead of ispunt. Then the code will compile and run as expected. Please note that neither std::ispunct nor ispunct (without a scope ::) would work. Only ::ispunct works. What really confuses me is that given that I already added "using namespace std", what's the difference between ::ispunct and std::ispunct (or ispunct without a scope)?