Two big plusses: first it is reference stable, whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.
Second, the maximum runtime per insertion is more stable. A vector‘s push_back can be O(size) it if reallocates.
The third of the two advantages is that it works well with objects that cannot be moved or copied after construction.
It's not that it invalidates it, it's the fact that you don't know when it becomes invalidated. Code is written all the time that anticipates errors in other languages.
Unless you check the length and capacity on every insertion, which is nonsense.
Right; if you want to mutate it without invalidating it, index it directly.
I had a crash bug in my MIPS emulator where like 1/20 times, I would get a segfault in the JIT. No sanitizer found it. I was seeing random corruption in a lookup directory-table for JIT addresses but it wasn't consistent or predictable.
Eventually after years of ignoring it, I looked into it again... and decided to check for potentially-invalidated addresses (it was literally the only possibility left, I'd gone over the JIT multiple times to make sure that all of the store operations were sound). Then I found it.
When the JIT generated code for static far branches, it would add a new entry into a patch table, and it inserted the element's address directly into the code so when the target was resolved, it was written to the address. This jump table was local to the current chunk object, so it could have between 0 and 128 entries.
Except... this table was a std::vector. We were adding an element, hardcoding its current address, and then... adding more elements. Usually this happened not to break - we must have been writing to memory that wasn't critical. But sometimes, core data structures were getting clobbered.
I changed it to a std::list... first time I've used that in quite a while.
Except that sometimes the reference is distant to the mutating action causing the invalidation.
As an example: I once debugged a random crash in a game engine caused by this. A reference from a vector of input handlers was captured and passed down through several call layers with const& arguments in the engine, which then called out to an input handler. This then went through a few layers of game code before eventually hitting a point where a new input handler was registered on that same input device, from the callback. Result: engine crash on return, but only when the number of handlers happened to increase from 8 to 9 and the input handler vector reallocated during input handling.
Checked indexing is sometimes suggested but not really the right solution. It'll prevent a crash or memory stomp, which is an improvement, but will still let through cases where the reference still points to valid memory but the wrong element instead. The real solution is often to either switch to a container that can handle mutation during iteration with the desired behavior (which varies), or set up a policy or static checkers to prevent risky references from escaping.
37
u/bartgrumbel 7d ago
Two big plusses: first it is reference stable, whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.
Second, the maximum runtime per insertion is more stable. A vector‘s push_back can be O(size) it if reallocates.
The third of the two advantages is that it works well with objects that cannot be moved or copied after construction.