This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++20 status.
std::sort_heap
Section: 27.8.8.5 [sort.heap] Status: C++20 Submitter: François Dumont Opened: 2014-10-07 Last modified: 2021-02-25
Priority: 3
View all issues with C++20 status.
Discussion:
While creating complexity tests for the GNU libstdc++ implementation I
stumbled across a surprising requirement for the std::sort_heap
algorithm.
In 27.8.8.5 [sort.heap] p3 the Standard states:
Complexity: At most
N log(N)
comparisons (whereN == last - first
).
As stated on the libstdc++ mailing list by Marc Glisse sort_heap
can be implemented by N
calls to
pop_heap
. As max number of comparisons of pop_heap
is 2 * log(N)
then sort_heap
max limit should be 2 * log(1) + 2 * log(2) + .... + 2 * log(N)
that is to say 2 * log(N!)
.
In terms of log(N)
we can also consider that this limit is also cap by 2 * N * log(N)
which is surely what the Standard wanted to set as a limit.
This is why I would like to propose to replace paragraph 3 by:
Complexity: At most
2N log(N)
comparisons (whereN == last - first
).
[2015-02 Cologne]
Marshall will research the maths and report back in Lenexa.
[2015-05-06 Lenexa]
STL: I dislike exact complexity requirements, they prevent one or two extra checks in debug mode. Would it be better to say O(N log(N)) not at most?
[2017-03-04, Kona]
Move to Tentatively Ready. STL may write a paper (with Thomas & Robert) offering guidance about Big-O notation vs. exact requirements.
Proposed resolution:
This wording is relative to N3936.
In 27.8.8.5 [sort.heap] p3 the Standard states:
template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);[…]
-3- Complexity: At most
2N log(N)
comparisons (whereN == last - first
).