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

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

[m-ou-se]

Status update:

The stabilization PR was not merged. See #76505 (comment) and #76505 (comment) for the relevant feedback.

[clarfonthey]

I commented on #54279 about the weirdness of not finding this as an inherent method on slice; while after seeing the algorithm explained in the docs, it makes sense to me why this doesn't have to be a slice-specific method, it's not at all obvious before that explanation.

I understand that there are theoretical data structures that would not be represented internally as slices for which this could be implemented, but would said data structures expose a mutable iterator? Like, applying this to a binary tree would destroy the interior structure of the tree, for example, and it seems like this would only be done if you're destroying the structure and converting it to something else anyway.

Like, it seems like this would be useful as a slice method simply for the ability to combine it with a split_at_mut instead of returning an index, so, maybe that is enough to warrant just moving it to a slice-inherent method and maybe adding the iterator version if it's seen as useful later.

[cuviper]

LinkedList and VecDeque could plausibly want this via iter_mut() as well.

[clarfonthey]

...right, I dunno why I forgot the obvious ones.

Still, beyond those, I wonder whether it's that worth it to expose on Iterator instead of just offering the algorithm on those collections directly. And in the case of VecDeque, a lot of operations will just make_contiguous first anyway.

[orlp]

I think this function is misguided on Iterator and should be part of [T].