partial_sort_n, nth_element_n

Contents

1. 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.

1.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:

1.2. Middle iterators are annoying

Since we need to obtain the middle iterator from the range but also provide the range to partial_sort_n, 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.

2. Scope

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

• partial_sort_n
• nth_element_n

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 §1.1. Middle iterators are unsafe do not apply.

3. Design

While the names follow the scheme of copy_n, the design is essentially copied from shift_left, which is the _n counterpart to rotate. copy_n takes an iterator and the size of the range, without an end iterator, and thus without any safety benefits.

The proposed functions would 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. Impact on existing code

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

5. Wording

The proposed changes are relative to [N5008].

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:

6. References