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
teilten dies erneut
Ian Douglas Scott
Als Antwort auf Martin • • •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
Als Antwort auf Ian Douglas Scott • •Soso
Als Antwort auf Martin • • •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
Als Antwort auf 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
doc.rust-lang.orgMartin
Als Antwort auf Soso • •Vec::retain
create a whole new copy of the collection, i.e. I'll need twice the memory at that point?Soso
Als Antwort auf Martin • • •Martin
Als Antwort auf Soso • •I don't want to use Vec because:
Soso
Als Antwort auf Martin • • •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.
Soso
Als Antwort auf Soso • • •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..
George Macon
Als Antwort auf Martin • • •Martin mag das.
Martin
Als Antwort auf George Macon • •brettwitty
Als Antwort auf Martin • • •Martin
Als Antwort auf brettwitty • •brettwitty
Als Antwort auf Martin • • •Epic Eric :thinkhappy:
Als Antwort auf Martin • • •Vec in std::vec - Rust
doc.rust-lang.orgEpic Eric :thinkhappy:
Als Antwort auf Epic Eric :thinkhappy: • • •std::collections - Rust
doc.rust-lang.orgMartin
Als Antwort auf Epic Eric :thinkhappy: • •That guide explicitly says I should use a LinkedList when:
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
Als Antwort auf 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.