Iuri Chaer comments

Results 11 comments of


                                            Iuri Chaer

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

Hi Mark, thanks for your reply! Strictly speaking, yes, that is true: the number of comparisons may violate the requirement of there being at most log(last - first) + O(1)...

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

OK, that's fair. How about I just stop exposing one-sided lower bound through std::lower_bound, and just use it for std::set_intersection, where all complexity guarantees are preserved, would that be OK?

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

SGTM! I'll amend my submission, thanks!

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

Cool, thanks :). Just for context, this code is actually being used in production out there. I work for Splunk, and we've implemented this outside of the standard library to...

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

Sounds good to me! I'll be out on holiday for a couple of weeks and should be able to update this PR in early January. Thanks for your feedback so...

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

Sorry for all the noise, I'll work through the CI failures in a private PR... I thought I had a good handle on the tests being executed, but clearly I...

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

@philnik777, I'm convinced that the one test failure I got is unrelated, and, from the looks of it, a likely flaky test (`std/thread/thread.semaphore/timed.pass.cpp`, in the `mingw-dll-i686` job). Could you please...

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

@philnik777, I'd love to hear your thoughts about the change :)

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

@philnik777, any more feedback?

[libc++] Introduce one-sided binary search for set_intersection so that it can be completed in sub-linear time for a large class of inputs.

@philnik777, what do you think? Any more feedback?