Need collection with insert and remove anywhere

Hello,

I need a list where I can insert elements anywhere (making the list longer) and remove elements anywhere (making the list shorter). Ideally, I also want to be able to replace a slice with a list of different length, potentially changing the length of the complete list.

Is there such a collection?

I see there is LinkedList, but I don't see an insert function and the remove function is unstable. And, there is no replace function. I'm surprised that these functions are not (stably) available, because I thought they are the whole point of having a doubly-linked list.

Thanks!

Best, Oliver

The LinkedList in std is quite limited and generally not particularly useful. Can you say more about your use-case?

Certainly a Vec can… technically… do all these operations, even though they might be slow, taking time on the order of the length of the whole vector, per operation. Are you aiming to do lots of such insert-anywhere or replace-slices operations, and hence looking for a particularly efficient datastructure?

1 Like

You can do this with Vec. Notably, the magic "can do anything" method is https://doc.rust-lang.org/std/vec/struct.Vec.html#method.splice.

4 Likes

I'm writing a parser where tokens are added to the end and then lots of slice-replacements according to given rules.

This looks like it gives you an iterator, from which I could construct a completely new Vec. Maybe I'll do this, but something more efficient would be nice.

Mostly replace-slices operations. Can Vec do these in place? How efficient would they be?

Oh, my bad. Vec::splice actually replaces in place, the iterator is for the removed items.

It replaces in-place, however it will have to move all the trailing end of the Vec’s data (everything to the right of the spliced portion) if the lengths of the removed part and its replacement don’t match. If you do this a lot with significantly long data, it might be slow.

However, keep in mind that a linked list does not let you jump to arbitrary indexes for free, so the operation would not be constant time for a linked list either.

If this was Haskell, I would suggest you try Data.Sequence – well… other (immutable) data structures can offer O(log n) splitting and appending (you can build your own splicing with that) as well as indexing, too: E.g. I know of im::Vector - Rust (or if you don’t need thread safety im_rc::Vector - Rust). I never tried using this crate, but it claims to be efficient.

Of course, this might not fit your use-case in case your tokens can’t be cloned cheaply… but if it does fit, an immutable data structure does offers the advantage that the whole thing, or parts of it, can be cheaply cloned. And if you do have unique access, then apparently modification still happens in-place.

1 Like

You might also consider VecDeque, which is implemented as a ring buffer. It may have better performance characteristics, depending on where you insert/remove elements (and the number of elements inserted/removed, and the size of your list, and other things too).

1 Like

In my case, the list will typically be not too long, and replacements will typically happen near the end, most often including the end itself, so I guess Vec.splice is fine. Thanks for the feedback!

Out of curiosity, why LinkedList is not more developed? Any not so obvious fundamental limitations?

Well, it's rather difficult to make a fully powerful API for a linked list that interacts well with the borrow checker. You would want the ability to have several handles into the list, but that is somewhat difficult if you also want mutable access to them.

And in general, linked lists are actually pretty useless in the real world. At least in any use-cases where you wouldn't be using unsafe regardless.

AFAIK, the standard library LinkedList is – in its current API (maybe with the Cursor API it gets some more use-cases?) – mainly useful if you need to append smaller lists into larger lists a lot, in an arbitrary manner, efficiently. With the goal to – in the end – iterate over everything once.

You can also split it, using split_off, which is not too expensive if your index is close to the end, so you could implement your own “splicing” by splitting and afterwards re-append-ing the list. But realistically, doing anything beyond just appending a lot might quickly run into the inefficiencies of storing every single element on its own in a separate allocation.

In addition to other comments, linked lists are notorious for poor cache hit rates and they are usually "intrusive" in C and C++ to turn T into a list of T (without the wrapper type). Intrusive linked lists are not easily done with Rust's ownership/borrowing model, and the implementation in the standard library is definitely not intrusive.

1 Like

Allocation-per-item is just typically a poor memory layout. That's also why Rust has a BTreeMap but not something like a RedBlackMap.

2 Likes

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.