Zum Inhalt der Seite gehen

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

teilten dies erneut

Als Antwort auf Martin

Ian Douglas Scott
Ian Douglas Scott
• •

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.

Als Antwort auf Ian Douglas Scott

Martin
Martin
•
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.
Als Antwort auf Martin

Soso
Soso
• •

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.

Als Antwort auf Soso

Soso
Soso
• •

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
Als Antwort auf Soso

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

Soso
Soso
• •
No, retain does not re-allocate. It modifies the Vec in place.
Als Antwort auf Soso

Martin
Martin
•

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
Als Antwort auf Martin

Soso
Soso
• •

LinkedList will likely use more memory. Each LinkedList element needs:

2 additional pointers,
Additional metadata for the allocation (size depends on the allocator)

Pushing an element to a vec is faster than to a LinkedList because it doesn't always need to allocate..
Removing from arbitrary locations can be done through swap_remove. But even remove is likely to be faster than linked list due to not needing to reallocate.

Als Antwort auf Soso

Soso
Soso
• •
There are very few algorithms that need a linked list for performance.
And most of the time they need specific properties from a specific linked list implementation, so they end up implementing their own, so the standard library version never got much attention, which is a bit disappointing for algorithms that actually need it..
Als Antwort auf Martin

George Macon
George Macon
• •
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.
Als Antwort auf George Macon

Martin
Martin
•
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.
Als Antwort auf Martin

brettwitty
brettwitty
• •
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)
Als Antwort auf brettwitty

Martin
Martin
•
That sounds like a lote of unnecessary memory allocations to me.
Als Antwort auf Martin

brettwitty
brettwitty
• •
Possibly! Depends on the context. Try and see, you might be surprised. The costs of these things can be a lot more complicated under the hood than a napkin calculation. Good luck!
Als Antwort auf Martin

Epic Eric :thinkhappy:
Epic Eric :thinkhappy:
• •
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
Als Antwort auf Epic Eric :thinkhappy:

Epic Eric :thinkhappy:
Epic Eric :thinkhappy:
• •
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
Als Antwort auf Epic Eric :thinkhappy:

Martin
Martin
•

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.

Als Antwort auf Martin

Martin
Martin
•

BTW what I want to do is a cache that stores a key/value pair (both are strings). When an entry is hit, I want to move it to the front of the list.

When there is no hit, a network request is issued to fetch the value for the key. The key/value pair is then emplaced at the front of the list. If the list is then over the maximum capacity, the item at the back shall be removed.

⇧