Introduce LinkedList::drain_filter #46262
Conversation
|
Thanks for the pull request, and welcome! The Rust team is excited to review your changes, and you should hear from @kennytm (or someone else) soon. If any changes to this PR are deemed necessary, please add them as extra commits. This ensures that the reviewer can see what has changed since they last reviewed the code. Due to the way GitHub handles out-of-date commits, this should also make it reasonably obvious what issues have or haven't been addressed. Large or tricky changes may require several passes of review and changes. Please see the contribution instructions for more information. |
kennytm
added
S-waiting-on-review
|
This PR introduces a new method. Deferring the decision to the libs team. r? @dtolnay |
There was a problem hiding this comment.
Vec::drain_filter is a much more general and equally efficient form of remove_if where the caller can do whatever they want with the removed values (building a new LinkedList of them, as with remove_if, seems like an uncommon use case). The equivalent of your example code would be:
let mut d = LinkedList::new();
d.push_back(1);
d.push_back(2);
d.push_back(3);
let mut removed = LinkedList::new();
for node in d.drain_filter(|v| *v < 3) {
removed.push_back(node);
}
assert_eq!(removed.len(), 2);
assert_eq!(d.len(), 1);I would prefer to be consistent by providing the same API for LinkedList.
|
@dtolnay will do, that also answers most of my questions. Thanks! |
|
Relates to rust-lang/rfcs#2140 |
Relates to rust-lang/rfcs#2140 - drain_filter for all collections `drain_filter` is implemented instead of `LinkedList::remove_if` based on review feedback.
|
I ported all the tests on All changes are now also associated with the |
udoprog
changed the title
|
Consistency is important. Note however that Linked List can do this kind of operation -- remove some elements during the scan and string them together a resulting linked list of the removed elements -- without any de/allocation of list nodes or even any moving of element values. It would be good to expose that functionality as well, but it is kind of its own kind of operation. |
|
The original patch did something like that. It could at some point be resurrected as a method on I'd be curious to see how well the optimizer deals with the example provided by @dtolnay. I wouldn't be surprised if specialized methods aren't needed. |
|
This could be covered with specialization. Imagine |
|
Since the extend approach is compatible with a draining iterator it can be introduced separately. @dtolnay With this in mind, can I get another round of review? |
|
@bors r+ |
|
📌 Commit 60aa834 has been approved by |
kennytm
added
S-waiting-on-bors
…olnay Introduce LinkedList::drain_filter This introduces `LinkedList::remove_if`. This operation embodies one of the use-cases where `LinkedList` would typically be preferred over `Vec`: random removal and retrieval. There are a number of considerations with this: Should there be two `remove_if` methods? One where elements are only removed, one which returns a collection of removed elements. Should this be implemented using a draining iterator pattern that covers both cases? I suspect that would incur a bit of overhead (moving the element into the iterator, then into a new collection). But I'm not sure. Maybe that's an acceptable compromise to maximize flexibility. I don't feel I've had enough exposure to unsafe programming in rust to be certain the implementation is correct. This relies quite heavily on moving around copies of Shared pointers to make the code reasonable. Please help me out :).
This introduces
LinkedList::remove_if.This operation embodies one of the use-cases where
LinkedListwould typically be preferred overVec: random removal and retrieval.There are a number of considerations with this:
Should there be two
remove_ifmethods? One where elements are only removed, one which returns a collection of removed elements.Should this be implemented using a draining iterator pattern that covers both cases? I suspect that would incur a bit of overhead (moving the element into the iterator, then into a new collection). But I'm not sure. Maybe that's an acceptable compromise to maximize flexibility.
I don't feel I've had enough exposure to unsafe programming in rust to be certain the implementation is correct. This relies quite heavily on moving around copies of Shared pointers to make the code reasonable. Please help me out :).