-
Notifications
You must be signed in to change notification settings - Fork 13.6k
Open
Labels
A-collectionsArea: `std::collections`Area: `std::collections`A-iteratorsArea: IteratorsArea: IteratorsB-unstableBlocker: Implemented in the nightly compiler and unstable.Blocker: Implemented in the nightly compiler and unstable.C-tracking-issueCategory: An issue tracking the progress of sth. like the implementation of an RFCCategory: An issue tracking the progress of sth. like the implementation of an RFCLibs-TrackedLibs issues that are tracked on the team's project board.Libs issues that are tracked on the team's project board.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.Relevant to the library API team, which will review and decide on the PR/issue.
Description
This tracks the stabilization of BinaryHeap::into_iter_sorted
(binary_heap_into_iter_sorted
) and BinaryHeap::drain_sorted
(binary_heap_drain_sorted
) implemented in #65091.
EDIT much later:
- Stabilize feature(binary_heap_into_iter_sorted) #76234 looked at stabilizing part of this, but didn't come to a conclusion that it was ready-to-go as-is. The questions from there (such as consistency in order with
into_sorted_vec
) need to be addressed before a future attempt to stabilize.To pick up a draggable item, press the space bar. While dragging, use the arrow keys to move the item. Press space again to drop the item in its new position, or press escape to cancel.
Original feature request:
Currently, both BinaryHeap::into_iter
and BinaryHeap::drain
yield the heap elements in an arbitrary order. This seems counter-intuitive given the nature of a heap. Sadly, we can't simply change their behavior behind the scenes, as we would have to remove the implementation of DoubleEndedIterator
. Should we perhaps add into_ordered_iter
and drain_ordered
? The implementation is pretty straightforward so I'd be happy to submit a PR.
timvermeulen, codyps, sekineh, ryoqun, stanislav-tkach and 25 more
Metadata
Metadata
Assignees
Labels
A-collectionsArea: `std::collections`Area: `std::collections`A-iteratorsArea: IteratorsArea: IteratorsB-unstableBlocker: Implemented in the nightly compiler and unstable.Blocker: Implemented in the nightly compiler and unstable.C-tracking-issueCategory: An issue tracking the progress of sth. like the implementation of an RFCCategory: An issue tracking the progress of sth. like the implementation of an RFCLibs-TrackedLibs issues that are tracked on the team's project board.Libs issues that are tracked on the team's project board.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.Relevant to the library API team, which will review and decide on the PR/issue.
Type
Projects
Milestone
Relationships
Development
Select code repository
Activity
clarfonthey commentedon Mar 30, 2019
Isn't
into_sorted_vec().into_iter()
sufficient?scottmcm commentedon Apr 1, 2019
@clarfon No, because getting the largest
k
items from that isO(n lg n + k)
, whereas withinto_ordered_iter()
it would beO(k lg n)
.ckaran commentedon Apr 2, 2019
clarfonthey commentedon Apr 3, 2019
ckaran commentedon Apr 8, 2019
sekineh commentedon Oct 2, 2019
Hi,
I've implemented both API in the local rust tree.
I see some problems in the API and I'm proposing the better version at the bottom of this comment.
Any ideas?
Currently proposed API
.into_ordered_iter(self)
.drain_ordered(&mut self)
Problems I see
=> Edit:
BinaryHeap
doc example could be updated after this feature would be stabilized.=> @scottmcm: Both owning and borrowing versions are useful.
.drain()
inconsistency: The semantics of.drain_ordered()
is lazy. Other all .drain() method immediately removes elements.=> @scottmcm: I agree that drop(foo.drain_ordered()); should result in an empty foo. But that can be accomplished by just clearing in the iterator's drop (assuming it's safe so doesn't need to amplify).
Better API (Solution)Implement one method.into_ordered_iter(&mut self)
.This is the mix of above
.into_ordered_iter(self)
and.drain_ordered(&mut self)
. I picked more useful one and changed the name.Do not implement.drain_ordered()
method.->
Solves P2 and P3. Partially solves P1 (discoverability).scottmcm commentedon Oct 2, 2019
Both owning and borrowing versions are useful. I can't return a version that borrows from a local variable, but I can return the version that moves it.
That said, I agree that
drop(foo.drain_ordered());
should result in an emptyfoo
. But that can be accomplished by just clearing in the iterator's drop (assuming it's safe so doesn't need to amplify).(I'm not worried about discoverability here; people have presumably been taught about the difference in things like
Vec
, which also has.into_iter()
and.drain(..)
.)sekineh commentedon Oct 2, 2019
Thanks @scottmcm for the comment. I updated my comment accordingly.
@jonhoo, are you still working on PR for this?
jonhoo commentedon Oct 3, 2019
@sekineh nope, not currently working on a PR
24 remaining items