Tracking issue for Iterator::is_partitioned

[cuviper]

/// Checks if the elements of this iterator are partitioned according to the given predicate,
/// such that all those that return `true` precede all those that return `false`.
fn is_partitioned<P>(mut self, mut predicate: P) -> bool
where
    Self: Sized,
    P: FnMut(Self::Item) -> bool,

feature = "iter_is_partitioned"

ref: #62278

Unresolved questions

• Do we want this function at all? (Motivating use cases would be useful.)
• Would is_sorted_by_key already cover all use cases?

[TheWastl]

Is there anything blocking this from stabiilization?

[cuviper]

No blocker that I know of. There's some question about the related partition_in_place, but is_partitioned is straightforward.

[m-ou-se]

Comments from the stabilization PR:

I've looked at the various linked issues but didn't see any motivating use cases for this routine.

Thinking a bit more about this, I suppose that pretty much all use cases of this function are also covered by is_sorted_by_key.

I've added this as an unresolved question above.

[jayaddison]

(arrived here thanks to an initially unrelated curiosity re: iterator::partition (specifically, that it only provides binary partitions))

About use cases: one could be to aid (perhaps semi-automated) porting of existing C++ code that uses stdlib partition (which maps to partition_in_place in Rust, as I understand it?) in combination with stdlib is_partitioned.

I'm a very small Rustacean so I don't know if I understand correctly, but it does seem like all use cases for is_partitioned could theoretically be translated to an implementation in terms of is_sorted_by_key -- but that doing that could require careful sort order / partition function handling, and perhaps more care than automated porting tools could achieve easily / performantly. Basically I think they'd tend to rewrite it as a a check for is_sorted_by ( negation ( partition_func ) ) (because the left-side partition is the true values).

Current implementation notes: is_sorted_by_key performs a (lazy) map across the iterator whereas the current is_partitioned implementation short-circuits by applying all until failure, and then any for remaining elements. Those seem to both have O(n) worst-case?

[siebenHeaven]

Can this be extended to return an Option<usize> that would be Some(partition_point) if it is partitioned and None if it's not?

[evlogiy]

I conducted some testing, and the current implementation (which is quite neat in my opinion), iter.all(predicate) || !iter.any(predicate), is about 2.5 times faster than the implementation using iter.is_sorted_by_key(|x| !predicate(x)). I conducted this testing in response to @jayaddison's comment, although I must admit that I somewhat lost track of the original purpose in the process.

While I feel somewhat indifferent towards the is_partitioned() function, I would be interested in seeing something similar to what @siebenHeaven suggests implemented. However, I believe the function should be named differently; perhaps find_partition_index would be more suitable?

Is there a similar suggestion already in progress? If so, could you assist me in locating it? If not, would you be able to point me to how I can create a new one?