Repository navigation
Tracking issue for Iterator::partition_in_place #62543
Description
/// 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
Activity
PurpleMyst commentedon May 25, 2020
What's blocking this from stabilization?
cuviper commentedon May 26, 2020
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 commentedon May 26, 2020
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 commentedon Jun 2, 2020
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 commentedon Sep 9, 2020
Maybe a stupid question, but why is the method in the
Iteratortrait, and not in theDoubleEndedIteratortrait?cuviper commentedon Sep 9, 2020
It's a reasonable question. There's a little prior art in
Iterator::revandrposition, and the latter is especially weird given thatrfindis onDoubleEndedIterator.I guess the current
DoubleEndedIteratormethods are exclusively about traversing backwards. Withpartition_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 commentedon Sep 10, 2020
Naming thought: should this be
partition_unstable_in_place, following thesortvssort_unstabledistinction?cuviper commentedon Sep 10, 2020
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.
10 remaining items
clarfonthey commentedon Apr 16, 2022
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_mutinstead 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 commentedon Apr 17, 2022
LinkedListandVecDequecould plausibly want this viaiter_mut()as well.clarfonthey commentedon Apr 17, 2022
...right, I dunno why I forgot the obvious ones.
Still, beyond those, I wonder whether it's that worth it to expose on
Iteratorinstead of just offering the algorithm on those collections directly. And in the case ofVecDeque, a lot of operations will justmake_contiguousfirst anyway.orlp commentedon Dec 4, 2023
I think this function is misguided on
Iteratorand should be part of[T].AntoinePrv commentedon Nov 5, 2024
I'd like to see this applicable to iterators and not only on specific data structure. There are many data structures out there that would exposed a mutable iterator but cannot be a slice. I'm thinking of scientific libraries: a strided iterator on a matrix, a chunked array in Apache Arrow / Polars, ...
markg85 commentedon Sep 30, 2025
Hi,
I was just referred to this function by an LLM. Funny :)
Just a very small question/remark.
In sorting algorithms where equal elements are not guaranteed to maintain order the function is often suffixed by
_unstable. And when order is preserved there is no additional suffix.This function in it's docs currently has the mention:
The relative order of partitioned items is not maintained.Hence my question: Is there a reason why this is not suffixed with
_unstable?cuviper commentedon Sep 30, 2025
If you expand GitHub's hidden comments, you can see that "unstable" has come up before. My take remains that it only makes sense to name it that way if we think we might also offer a stable variant, and I don't think we would.
However,
select_nth_unstabledoesn't have a stable variant either, so... 🤷markg85 commentedon Sep 30, 2025
Sorry for that, i should've looked!
That's not really a scalable approach, is it? I don't disagree with your thinking but i also wouldn't do that. The reason i say that is for future new functions. If you don't suffix it now then a future version will have to be suffixed (or be a v2 or something). And you get naming inconsistencies where one algorithm is stable without a suffix and the other is unstable without a suffix.
But there's probably something to be said for either argument.
clarfonthey commentedon Sep 30, 2025
After encountering a potential use for this function, my opinion is… honestly, I still think it should be implemented directly on slices instead.
In particular, I think it should work closer to how
retaindoes, minus actually dropping anything. Maybe even a version that works likeretain_mut. In particular, the fact that those both retain stability of the items on at least one side of the partition is desirable, IMHO. Whereas this version basically can never be stable without some kind of trickery.The other benefit of implementing directly on slices is it can perform a
split_atfor you and directly return two slices, which seems kind of nice.LegionMammal978 commentedon Jan 17, 2026
Regarding the FIXME comment w.r.t. the count overflowing: we have precedent for this in
Iterator::count()andIterator::position(), which document that they either panic or produce a wrong answer depending on whether overflow checks are enabled. We could simply add a similar notice toIterator::partition_in_place(), and also note for clarity that if the increment, predicate, or iterator operations panic, then all elements remain, but the resulting order is unspecified.(Of course, this is moot if we specialize this function to slices and other containers instead of generic
&mut Titerators.)Also, this function could definitely have better visibility. I just went looking for this for a Gaussian-elimination routine, and I had lots of trouble finding it. One alternative: add it as a generic
Iteratormethod (or free function), and also add it as an inherent slice method. There is some precedent for this, with<[T]>::is_sorted_by_key()simply calling out toIterator::is_sorted_by_key().