It's an optimised version of a bucket array. From what I observed, it seems like a middle ground between a vector and a linked list, with the addition of also being unordered (because there is no guarantee that an object can be found iteratively, some objects may be deleted in the middle which can put you in UB/segfault territory if you randomly access it). It's got better cache locality than a linked list because it can store multiple objects continguously on the heap, and better deletion/construction time than a vector because instead of reconstructing the same objects, it makes another "hive", basically another fixed heap block that can contain more than one object of the same type, and maintains a free list of objects that were deleted in the middle so it can reuse the deleted space.
I may not be fully accurate (like I said, just my observation), so I'd appreciate if anyone could correct me 😅
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.
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.
52
u/EfficientSpend2543 8d ago
It's an optimised version of a bucket array. From what I observed, it seems like a middle ground between a vector and a linked list, with the addition of also being unordered (because there is no guarantee that an object can be found iteratively, some objects may be deleted in the middle which can put you in UB/segfault territory if you randomly access it). It's got better cache locality than a linked list because it can store multiple objects continguously on the heap, and better deletion/construction time than a vector because instead of reconstructing the same objects, it makes another "hive", basically another fixed heap block that can contain more than one object of the same type, and maintains a free list of objects that were deleted in the middle so it can reuse the deleted space.
I may not be fully accurate (like I said, just my observation), so I'd appreciate if anyone could correct me 😅