Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++20 status.

2444. Inconsistent complexity forstd::sort_heap

Section: 26.8.8.5[sort.heap]Status:C++20Submitter: François DumontOpened: 2014-10-07Last modified: 2021-02-25

Priority:3

View all issues withC++20 status.

Discussion:

While creating complexity tests for the GNU libstdc++ implementationI stumbled across a surprising requirement for thestd::sort_heap algorithm.

In 26.8.8.5[sort.heap] p3 the Standard states:

Complexity: At mostN log(N) comparisons (whereN == last - first).

As stated on the libstdc++ mailing list by Marc Glissesort_heap can be implemented byN calls topop_heap. As max number of comparisons ofpop_heap is2 * log(N) thensort_heap max limit should be2 * log(1) + 2 * log(2) + .... + 2 * log(N) that is to say2 * log(N!). In terms oflog(N) we can also consider that this limit is also cap by2 *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 most2N 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.

1. In 26.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 most2N log(N) comparisons (whereN == last - first).