Bobs Friends | Community

Martin 9 Stunden her friendica

I'm trying to get into #rustlang. I've already rewritten a small program and it was an okay experience but today, I hit something weird.

I have a LinkedList and need to iterate over it and, if I found any item that meets some criteria, I need to remove it from the list.

Using C++ iterators, this would be O(N).

Rust's linked_list has an issue open for more than 4 years (!) to add a remove function to linked lists. But even with that function, you'll need an index of the item to be removed and cannot (as far as I can tell) use the iterator you already have from scanning the list.

So in Rust I would need to spend O(N) to scan the list and an additional O(N) for each item I need removed.

Or is there a faster way to do that?

Tracking Issue for linked_list_remove · Issue #69210 · rust-lang/rust

#68705 adds a method in LinkedList to remove an element at a specified index. The feature gate for the issue is #![feature(linked_list_remove)].

^GitHub

#rustlang

Ian Douglas Scott 8 Stunden her • mastodon (AP)

Technically that's also O(n) (O(2n) = O(n)).

I don't see much Rust code using `LinkedList`. Probably its more common to just use `Vec`. Which in many cases will end up performing better overall, regardless of language.

Martin 15 Minuten her friendica

The List grows very dynamically, that's why I want to use LinkedList, because adding, removing and moving within the list is normally cheap with a LinkedList.

Soso 8 Stunden her • mastodon (AP)

I've been writing Rust for 5 years and professionally for 2 years, I've seen a linked list outside of some very specific use cases.

Yes, Rust Linked List are very limited and you will most likely fight the borrow checker.

Are you sure you need a linked list? In most cases a Vec will be more efficient, and you won't have as many borrow checking issue.

If the order of elements doesn't matter, you can even use Vec::swap_remove for O(1) removal of elements.

Soso 8 Stunden her • mastodon (AP)

if you want to remove all element that match a specific criteria, try using Vec::retain.

https://doc.rust-lang.org/stable/std/vec/struct.Vec.html#method.retain

https://doc.rust-lang.org/stable/std/vec/struct.Vec.html?search=retain#method.swap_remove

Vec in std::vec - Rust

A contiguous growable array type, written as `Vec`, short for ‘vector’.

^{doc.rust-lang.org}

Martin 6 Minuten her friendica

Doesn't Vec::retain create a whole new copy of the collection, i.e. I'll need twice the memory at that point?

Martin 8 Minuten her friendica

I don't want to use Vec because:

I don't want the collection to hog more memory than it actually needs.
I want to be able to cheaply extend the collection
I want to be able to cheaply remove items from arbitrary locations within the collection

George Macon 8 Stunden her • mastodon (AP)

You can do that with the (unfortunately unstable) cursor API, see LinkedList::cursor_front and LinkedList::cursor_back. The cursor API is more powerful than Iterator, but is specific to LinkedList AIUI.

Martin 5 Minuten her friendica

Yeah, I'm aware of that cursor API and even ChatGPT guided me towards that, but I don't want to do unstable at this point.

brettwitty 8 Stunden her • mastodon (AP)

Do you have to remove it from that list, or can you iterate and create the filtered list? I'm unsure if you can .collect() into a LinkedList (assuming you really want one)

Martin 4 Minuten her friendica

That sounds like a lote of unnecessary memory allocations to me.

Epic Eric :thinkhappy: 8 Stunden her • mastodon (AP)

The "faster way" depends on your exact use-case. If you intend to remove several items at once sporadically, then [Vec::retain()](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain) might be performant enough - especially if you're performing full reads of the resulting vector.

Vec in std::vec - Rust

A contiguous growable array type, written as `Vec`, short for ‘vector’.

^{doc.rust-lang.org}

Epic Eric :thinkhappy: 8 Stunden her • mastodon (AP)

In terms of which collection will best suit your needs, I recommend reading through the doc section "When Should You Use Which Collection?": https://doc.rust-lang.org/std/collections/#when-should-you-use-which-collection

std::collections - Rust

Collection types.

^{doc.rust-lang.org}

Martin 1 Minute her friendica

That guide explicitly says I should use a LinkedList when:

You want to efficiently split and append lists.

Which is exactly why I want to use a linked list. Vec seems like it would do a lot of unnecessary memory allocation for that.

Martin 9 Stunden her friendica

Ich liebe den Geruch von 🥦 zur Erntezeit.

Martin 1 Woche her friendica

Dude…

Someone on Reddit: Electric lamps inside a game uses real electricity to turn on. Someone else: Bro.