partial_sort_at_most, nth_element_at_most

Contents

1. Revision history

1.1. Change since R0

• incorporate feedback from SG9
• changed the _n suffix to _at_most in accordance with SG9 recommendations; see §4.1. Naming
• added §4.2. Additional variants of partial_sort
• rebased §6. Wording on [N5014]
• removed stray <Size> template arguments in §6. Wording

2. Introduction

Algorithms such as std::ranges::partial_sort accept a "middle iterator" that must be in the range of iterators [begin(), end()]. For example, ranges::partial_sort is specified in [partial.sort] as follows:

There are problems with this interface, described below.

2.1. Middle iterators are unsafe

A common use case for partial_sort or nth_element is to sort the $N$ lowest elements or to obtain the $N^{\text{th}}$ lowest element, where $N$ is an integer that is constant, obtained from a config file, or otherwise independent of the range. This invites a common bug, which I have witnessed multiple times:

The underlying problem is that to use the algorithm, we need to offset the start iterator, and this can fall outside of the range of iterators [begin(), end()].

A possible safe alternative which would have prevented the bug above is

However, this is neither ergonomic nor does it address the cause of the bug. The bug was caused by the user not remembering that scores + n can be undefined, and by the interface encouraging them to write this expression. Why should we expect the user to know of and consistently use this workaround then?

Users generally prefer to use to "path of least resistance", and we should make that path safe:

2.2. Middle iterators are annoying

Since we need to obtain the middle iterator from the range but also provide the range to partial_sort, we may have to repeat ourselves.

Either options is somewhat annoying if it could theoretically be written as:

One key benefit of std::ranges is that we rarely have to work with iterators directly anymore. Requiring the user to provide middle iterators somewhat defeats this design strategy.

3. Scope

To address the problems above, I propose the following additional algorithms:

• partial_sort_at_most
• nth_element_at_most

These should exist both for the std::ranges:: and the std:: algorithms, as they provide a "safety/ergonomics hotfix" for anyone who has not migrated to these "new" algorithms yet, and is perhaps unable to because their iterators would not satisfy the std::ranges constraints.

While there are more algorithms that accept middle iterators, they do not exclusively operate on random access iterators, which results in different design concerns. There is also no proposed overload for partial_sort_copy because its result can already be specified as a range or iterator pair, so the concerns in §2.1. Middle iterators are unsafe do not apply.

4. Design

The design of the function signatures is essentially copied from shift_left. The proposed functions take either an iterator pair and a size, or a range and a size, just like shift_left and shift_right, and with similar interface. See [alg.shift].

4.1. Naming

The naming is novel. R0 of this paper proposed _n suffixes instead of _at_most, but this was unpopular in SG9. The issue with _n is that this suffix is used to mean "exactly N", not "at most" (with clamping/views::take-like) behavior.

A few possible candidates were discussed, and the currently proposed one is simply the most popular:

Approval of naming scheme:

Name	Votes
_n	1
_at_most	7
_up_to	5
_clamped	3
_safe	0

Attendance: 7

4.2. Additional variants of partial_sort

In addition to the "clamping" behavior of the proposed functions, SG9 also expressed interest in functions that detect misuses of partial_sort as a hardened precondition or by throwing an exception:

We want a variant of partial_sort/nth_element that takes a count n instead of an iterator mid and has a precondition/hardened precondition/erroneous behavior/throws an exception if n is too large.

SF	F	N	A	SA
0	5	0	2	0

Author: A
Attendance: 7
Consensus in favor.

However, just because there is interest, doesn't mean these functions need to be in this paper. Such new functions would have to be separate overload sets because adding additional "safer" overloads to partial_sort

• bloats the size of the overload set, and
• creates an ambiguity between passing a null pointer constant 0 (where the iterator is a pointer, for a contiguous range) and a 0 that is convertible to a difference_type, when 0 is passed as the size argument to the algorithm.

However, creating an entirely new overload set just to add a range check is novel and arguably overkill; I believe it would decrease consensus on this proposal.

5. Impact on existing code

No existing code should be affected because the proposed functions are all new. Existing overload sets are not modified.

6. Wording

The proposed changes are relative to [N5014].

In [version.syn], add two feature-test macros as follows:

In [algorithm.syn], change the synopsis of <algorithm> as follows:

In [partial.sort], append the following items at the end of the subclause:

In [alg.nth.element], append the following items at the end of the subclause:

7. References