2082. Misleading complexity requirements in <algorithm>

Section: 26 [algorithms] Status: NAD Submitter: Nicolai Josuttis Opened: 2011-09-02 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [algorithms].

View all other issues in [algorithms].

View all issues with NAD status.

Discussion:

The partition_point() algorithm is specified with:

Complexity: O(log(last - first)) applications of pred.

While this is correct, it gives the impression that this is a logarithmic algorithm. But unless random access iterators are used it is not logarithmic because for advancing the iterator we have last-first steps, which means that the complexity becomes linear here.

Shouldn't we clarify the complexity here to something like:

Complexity: logarithmic for random-access iterators and linear otherwise (in any case O(log(last - first)) applications of pred).

Or should we even require O(log(last - first) for random-access iterators only because for other iterators just iterating over all elements, while calling pred for each element, might often be faster.

Daniel Krügler:

I agree that especially this description is a bit misleading. I'm not convinced that this is a real defect, because the whole bunch of templates within <algorithm> document the complexity solely of applications* of predicates, assignment, or swaps, but never the complexity of traversal operations (e.g. increment or iterator equality tests). This means, the standard is consistent for this function template, even though it could say a bit more.

I would like to see a wording improvement, but I would rather think that the complexity of the predicate should be mentioned first (as in other algorithms) and that a non-normative note could be added for specifically this algorithm to point out that this does not imply a logarithmic traversal complexity. The note could give more details, by explicity pointing out the linear traversal complexity for non-random-Access iterators.

Howard Hinnant:

If we are going to make such improvements, they should be made across the board in <algorithm>, not to just partition_point. For example all 4 algorithms in 26.8.4 [alg.binary.search] have the same issue, and have since C++98.

stable_partition and inplace_merge should be inspected as well.

Perhaps a new paragraph in 26.1 [algorithms.general], similar to p12 would be a better place to address this issue.

[2012, Kona]

Move to NAD.

There was some concern that the issue, if it were to be addressed, is much larger than the couple of algorithms called out here, and applies across the whole library. There is no interest in looking at this or similar issues without a paper addressing the whole library. In fairness to anyone considering writing such a paper, it should be noted that there was not much interest in such a paper in the group, although no strong opposition either.

Proposed resolution: