friends.mbober.de
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?
#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
A contiguous growable array type, written as `Vec`, short for ‘vector’.doc.rust-lang.org
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.
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.
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.
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.
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.orgVec::retaincreate a whole new copy of the collection, i.e. I'll need twice the memory at that point?I don't want to use Vec because:
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.
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..