It does. Some collections have a "collection.retain" method.
collection.retain(|v| true_if_we_want_to_keep(v))
which goes through the collection in linear time and deletes any items for which the test is false. This is O(N).Some collections ("multi_map", which isn't used much, comes to mind) don't have that. You have to make a read pass over the collection, construct a list of things to delete, then go through the delete list and delete those items. Can't read and change with the same iterator. That's slower. But sound.
I'm OK with that. It avoids subtle bugs.
struct OrderedSet {
deque<string> storage;
set<string_view> vals;
}
The deque holds the string contents, and the set holds views of those contents. This is safe because the deque has iterator stability, and it's pleasant because the `vals` set can just be a regular set.As you say Rust does not allow this; its answer is IndexSet, and it is implemented differently, like:
struct OrderedSet {
Vec<String> buckets;
RawTable<usize> hashToBucketIndex;
}
RawTable is a hash table that doesn't know how to compute a hash or determine equality. Instead, you provide it with closures to do those tasks, but at the call site (not construction time).Basically Rust achieves the same thing through a layer of indirection involving indexes, which is a common pattern.
If you wanted to do the same in Rust it would be Vec<Box<T>>. Mutating the collection won't invalidate the pointers.
Rust still won't let you mutate a Vec<Box<T>> while you hold a &T or &mut T borrowed from the Vec.
Perhaps it would be sound to do so unsafely; Rust would let you mutate a Vec<Rc<T>> while you hold a Rc<T> cloned from the Vec. But I'm not clear on whether Stacked Borrows allows moving the Box while you have a &mut T pointing to the same memory as the Box points to. It definitely does not allow dereferencing the Box. (I heard Stacked Borrows will be updated to make self-referential types sound, and I don't know if it will affect this situation.)
In the case of Rc<T>, cloning the Rc creates a second owner of the heap allocation, so the Vec dropping its copy won't deallocate. Though I believe one complication to this would be that the lifetime any references created through the Vec's copy of the Rc will be linked specifically to that copy, so would result in a borrow check error when it's dropped.
If the Vec is storing references, you can borrow the thing behind the reference and still mutate the Vec because that reference stays valid even if mutating the Vec drops its reference to the item.
let (a, b, c, d) = (1, 2, 3, 4);
let mut v = vec![&a, &b, &c, &d];
// If you change the type here to &&u32, or let the compiler infer the type
// then you'll get a borrow check error because the outer reference
// borrows the Vec.
let borrowed_b: &u32 = &v[1];
v.remove(1);
println!("{}", borrowed_b);
println!("{:?}", v);
https://play.rust-lang.org/?version=stable&mode=debug&editio...[1]