Valgrind memcheck is your friend.
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]
auto& r = *some_vector[0];From memory:
In MSVC, dequeue will allocate memory for every single element if your elements are > 8 bytes. This will never be changed, due to ABI compatibility.
Clang and gcc have batching sizes of 1K and 4K (i.e. you throw out a whole page of memory even if your dequeue contains only 1 element).
https://github.com/gcc-mirror/gcc/blob/47749c43acb460ac8f410...
Furthermore, depending on the size of T, the performance penalty of the extra heap allocations is amortized over the cost of resizing the vector. That is vector reallocation is significantly faster for a unique_ptr<T> than it is for T when T is large and almost all memory allocators are tuned to allocate objects close together in space when they are allocated close together in time, so you don't lose the cache locality or need to worry about memory fragmentation.
(Though it's still pretty brittle, so you may want to add a ton of comments to warn yourself in the future...)
I'm not going to pretend that I understand everything on that site (particularly anything about complex templates and things like SFINAE) but often there's comprehensible stuff in there. It can be really helpful.
If you write C++ it might be obvious what the problem is.
If you don't, this will absolutely ruin your entire day.
The worst part is, 95% of the time, it will probably work without issue.
But eventually, pushing a new item to the Vector will trigger a relocation of the whole vector, which will invalidate your reference and bring down production. Have fun debugging that.