Iterating and removing from unordered collection - with stable code

help
1

I try to do simple thing: safely iterate over collection (it can be unordered), call element's method do_magic(&mut self) -> bool. If it returns false, remove element from collection.

I tried HashSet. It doesn't allow to use IterMut.

I tried LinkedList with cursors, but compiler denied it:
error[E0658]: use of unstable library feature 'linked_list_cursors'
Documentation says:
This is a nightly-only experimental API. (linked_list_cursors #58533)

I tried LinkedList.retain()
Documentation says:
This is a nightly-only experimental API. (linked_list_retain #114135)

What if I don't want to mess with unstable API and nightly builds?
I like Rust, but it's surprising that after 18 years of existence it has no stable API for LinkedList.

This problem was discussed in 2017:

Am I missing something?

2

If your elements are in a Vec, you should be able to use the Vec::retain_mut() method to keep just the elements where your magic method returns true.

4 Likes
3

Thanks a lot! Sounds good. For other adventurers, I'll copy-paste some code comments from Vec.retain_mut():

/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.

// It shifts unchecked elements to cover holes and `set_len` to the correct length.
4

It probably gets less love than other std types because linked lists, outside of some niche cases that probably need a custom implementation anyway, are a bad fit for Rust and for modern computers (where cache locality triumphs). "The collections person" at the time even tried to get it removed before stabilization,[1] as I understand it. I don't know that I've ever seen anyone use it; if I have, it's very rare.

  1. 9 years ago incidentally ↩︎

3 Likes
5

singly linked lists have some nice mathmatical properties, and segmented lists are quite useful for when a single allocation would be prohibitively large, but i'm not sure what doubly linked lists are good for besides wasting 8 bytes of memory.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.