Could someone explain to me in a clear and high level fashion what exactly pointer stability (or pointer instability for that regards) entails? I've watched some of the cppcon talks on the google hashtable implementation [0] and in that talk Matt Kulukundis also mentioned it affecting the adoption rate, but I always failed to really grasp the concept and its implications. Google searches also ended up rather fruitless to be honest.
An operation maintains Pointer Stability means if you take a pointer to an element in a data structure and then execute that operation, the pointer is still valid and pointing to the same data.
Think about how vector would be implemented under the hood. What happens if you delete an element? Does it shift down all of the elements after it? If you do that, the objects have literally moved in memory. Any pointer that points into those memory locations is now invalid. That's a problem if you wanted to hold onto pointer to elements. But if you declare that your interface has certain pointer stability guarantees then suddenly your implementation is massively constrained. Now your vector implementation will have big gaps that you need to deal with and will waste a ton of memory if you add and remove many elements.
Pointer instability means that it is undefined behaviour to:
1) store (both on stack and heap) the pointer address to a value element outside of its respective container
2) then modify the container's content
3) then thereafter use the stored pointer address
This implies that:
- containers without pointer stability require pass-by-value (or a pointer to a temp copy) to be used for its values after accessing them OR
- containers without pointer stability require absolute immutibility of the container to guarantee runtime safety OR
- containers without pointer stability require "relative" immutability during the existence of a pointer to a value element to guarantee runtime safety. Note that I think this last option is a bad idea, because it requires multithreaded blocking/synchronization of the container and is also easy to encapsulate wrongly, leading to UB.
... with a specific set of mutating operations that (may) alter the container's structure (eg, element insertions and removals).
Altering the value of one element of the container doesn't invalidate iterators or references to any element. You can make as many mutating passes over a std::vector as you like without invalidating anything.
Things only start to get dicey when you push_back(), insert(), erase(), etc.
If you allocate your objects inline in your internal table, rehashing will invalidate existing references to those objects as they will need to be copied into the new, larger, table.
Allocating every object separately in its own node as used in chaining implementations guarantee that the object ___location is stable (i.e doesn't change), but in addition to making iteration slower it requires separate allocation for each object.
[0]: https://youtube.com/watch?v=ncHmEUmJZf4