Arthur O'Dwyer discovers that std::is_heap and std::is_heap_until unnecessarily require random_access_range when they could work with forward_range, analogous to how is_sorted only needs forward access. He demonstrates that libc++'s current implementation is also algorithmically inefficient, recomputing index arithmetic instead of simply advancing two iterators in lockstep. Benchmarks show the optimized forward-iterator approach is 11–41% faster across vector and deque containers of various sizes. He concludes that libc++ should adopt the faster implementation immediately, and that WG21 should relax the range constraint from random_access_range to forward_range, which would also force all three major STL vendors to adopt the faster algorithm.

4m read timeFrom quuxplusone.github.io
Post cover image
Table of contents
Benchmark it!Conclusions

Sort: