master

GGitHub [libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230)

a0662176创建于 2024年7月19日历史提交

文件	最后提交记录	最后更新时间
range.iter.ops.advance	[libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230) One-sided binary search, aka meta binary search, has been in the public domain for decades, and has the general advantage of being constant time in the best case, with the downside of executing at most 2*log(N) comparisons vs classic binary search's exact log(N). There are two scenarios in which it really shines: the first one is when operating over non-random-access iterators, because the classic algorithm requires knowing the container's size upfront, which adds N iterator increments to the complexity. The second one is when traversing the container in order, trying to fast-forward to the next value: in that case the classic algorithm requires at least O(N*log(N)) comparisons and, for non-random-access iterators, O(N^2) iterator increments, whereas the one-sided version will yield O(N) operations on both counts, with a best-case of O(log(N)) comparisons which is very common in practice.	1 年前
range.iter.ops.distance	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
range.iter.ops.next	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
range.iter.ops.prev	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
types.h	[libc++] Suppress -Wctad-maybe-unsupported on types w/o deduction guides There are a handful of standard library types that are intended to support CTAD but don't need any explicit deduction guides to do so. This patch adds a dummy deduction guide to those types to suppress -Wctad-maybe-unsupported (which gets emitted in user code). This is a re-application of the original patch by Eric Fiselier in fcd549a7d828 which had been reverted due to reasons lost at this point. I also added the macro to a few more types. Reviving this patch was prompted by the discussion on https://llvm.org/D133425. Differential Revision: https://reviews.llvm.org/D133535	3 年前