Rust: Tracking issue for Iterator::partition_in_place

[cuviper]

/// Reorder the elements of this iterator *in-place* according to the given predicate,
/// such that all those that return `true` precede all those that return `false`.
/// Returns the number of `true` elements found.
fn partition_in_place<'a, T: 'a, P>(mut self, ref mut predicate: P) -> usize
where
    Self: Sized + DoubleEndedIterator<Item = &'a mut T>,
    P: FnMut(&T) -> bool,

feature = "iter_partition_in_place"

ref: #62278

[PurpleMyst]

What's blocking this from stabilization?

[cuviper]

There's no blocker as far as I know. It would be nice to see some real use for experience, e.g. in the compiler or standard library itself, but I don't think that's required.

[PurpleMyst]

I've rewritten exactly this function before to avoid depending on nightly features. Is there any way we can put this up for stabilization?

[cuviper]

There's a documented process for stabilizing language features, but I'm not aware of anything special for libraries. AFAIK, you can just open a pull request with the change, and the libs team will put the proposal through FCP. For example, #71886 stabilized a couple numeric methods.

[ogoffart]

Maybe a stupid question, but why is the method in the Iterator trait, and not in the DoubleEndedIterator trait?

[cuviper]

why is the method in the Iterator trait, and not in the DoubleEndedIterator trait?

It's a reasonable question. There's a little prior art in Iterator::rev and rposition, and the latter is especially weird given that rfind is on DoubleEndedIterator.

I guess the current DoubleEndedIterator methods are _exclusively_ about traversing backwards. With partition_in_place, it's reading both ends, but the traversal order is not the main point of the method.

But that's pretty loose justification, and I think it would also be reasonable to move it. :shrug:

[scottmcm]

Naming thought: should this be partition_unstable_in_place, following the sort vs sort_unstable distinction?

[cuviper]

IMO, "unstable" is only useful if we think there might be a stable variant, but you would need a side buffer of displaced items to manage that. The documentation does say that relative order is not maintained.

[PurpleMyst]

Well, Iterator::partition is stable, isn't it?

[cuviper]

True, partition is stable into new collections.

[sanmai-NL]

@cuviper Would it be possible to also offer an partition_unstable_in_place that accepts the item type’s natural ordering (Ord), rather than a predicate?

[cuviper]

@sanmai-NL partitioning is a binary decision on each individual item, which we can do in a linear sweep. Asking for Ord sounds like you want a full sort, which is quite a different algorithm.

[sanmai-NL]

@cuviper I agree, but I had another application in mind. I was using it to implement Quicksort, and would like be able to control the sorting order through the predicate function. Since it got hairy with all the lifetimes in combination with recursion and mutable references in to the (sub)arrays, I was wondering whether I could use the natural ordering or some Ordering value directly.

But otherwise, how would I pass the predicate from the caller for use here? It's probably easy, but the docs/signature wasn't helpful enough for me.

[cuviper]

@sanmai-NL So right now you have this, which already uses PartialOrd for the < operator:

            .partition_in_place(|&element| element < pivot)

If you have a custom parameter cmp: impl FnMut(i16, i16) -> Ordering, then you can use:

            .partition_in_place(|&element| matches!(cmp(element, pivot), Ordering::Less))

Or you might have a parameter lt: impl FnMut(i16, i16) -> bool without full ordering, then:

            .partition_in_place(|&element| lt(element, pivot))

[Ignition]

Wouldn't returning a pair of iterators be better? ATM you return an index in reference to the where the partition happened, then you likely have to use that index to constuct iterators again.

let mut a = [1, 2, 3, 4, 5, 6, 7];
let offset = 2;
let i = a[offset..].iter_mut().partition_in_place(|&n| n % 2 == 0);
assert!(a[offset..i+offset].iter().all(|&n| n % 2 == 0)); // evens
assert!(a[i+offset..].iter().all(|&n| n % 2 == 1)); // odds

vs

let mut a = [1, 2, 3, 4, 5, 6, 7];
let offset = 2;
let (bottom, top) = a[offset..].iter_mut().partition_in_place(|&n| n % 2 == 0);
assert!(bottom.all(|&n| n % 2 == 0)); // evens
assert!(top.all(|&n| n % 2 == 1)); // odds

(forgive me for any mistakes, coming from C++, learning Rust ATM)

[cuviper]

@Ignition that's not possible with an arbitrary Iterator input. Once we step to an item, there's no going back. If we implemented this only as a slice method instead, then yes we could return a pair of slices.

For your C++ background, it may help to think of C++ iterators as _cursors_, whereas Rust iterators are more like _ranges_ that shrink each time an item is retrieved.