6 ms·

Yeah I learned that the hard way when I found out that std::vector apparently feels free to move your objects around in memory for you, no matter if you point t

Yeah I learned that the hard way when I found out that std::vector apparently feels free to move your objects around in memory for you, no matter if you point to them from somewhere else. I mean in hindsight it's obvious, but still not exactly what I wanted to happen. For reference, what I did does actually work, temporarily.

tines 5y ago
> Yeah I learned that the hard way when I found out that std::vector apparently feels free to move your objects around in memory for you In standard terminology, this is described as "invalidating iterators". There are a bunch of member functions in std::vector that either do or don't invalidate iterators, e.g. push_back(...) does but size() doesn't. And as the name implies, if you call a function that invalidates iterators, all your existing iterators/pointers/references become invalid.
- Kranar 5y ago
  Iterator invalidation is different from this. Iterator invalidation, as the name suggests, only applies to iterators. The problem OP was having had to do with dangling references. Some containers guarantee references won't dangle on mutation such as unordered_map. An unordered_map may invalidate iterators if objects are added or removed, but will never result in dangling references (unless the object is removed). That is, it is safe to have a pointer to an object owned by an unordered_map and continue using that pointer even after an iterator to that same object is invalidated.
  - tines 5y ago
    Ah, interesting. Even within that dichotomy, I'd think that if references aren't invalidated on mutation, then dereferencing iterators would be valid, but incrementing them would not be.
  - einpoklum 5y ago
    Iterators are historically a generalization of pointers. A pointer is a kind of iterator. I mean, literally. The iterator of an std::vector<T> (not a bool vector) is a T*.
    - Kranar 5y ago
      This is a poor understanding of what an iterator is. For one, the iterator of a std::vector<T> is not a T*, it's a std::vector<T>::iterator and you are welcome to verify that the following assertion fails for all T: static_assert(std::is_same_v<T\*, std::vector<T>::iterator>) Link provided below for convenience [1]. Furthermore just like a cat is animal does not imply an animal is a cat, a pointer being an iterator does not imply that an iterator is a pointer and holding such a confusing thought is the source of many bugs and poor C++ code. An iterator not only represents a form of indirection to an object, it also represents traversal through a collection of values. unordered_map guarantees that the objects it stores will remain alive until the unordered_map is destroyed or the object is removed from the map. However, unordered_map, as the name once again suggests, does not provide any guarantee about the ordering of objects. Hence, if you have an iterator to an object owned by such a map, and you add or remove objects to that map, the iterator becomes invalid not because the object the iterator references gets destroyed, but because the iterator loses information about where it's located within the unordered collection. For further information, please review the following link [2], specifically the quote "References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.". [1] https://godbolt.org/z/Y5f4d74Kb https://godbolt.org/z/Y5f4d74Kb [2] https://en.cppreference.com/w/cpp/container/unordered_map https://en.cppreference.com/w/cpp/container/unordered_map
      - saagarjha 5y ago
        You're being far more patronizing than is necessary here, especially because the parent poster was correct in iterators originating out of a being a generalization over pointers, although not in their latter statement. But, while implementation defined, a vector iterator must behave identically to a pointer, and your assertion fails in both Clang and GCC not for any interesting reason but more because they wrap the pointer into a class for what I understand to be better encapsulation and earlier detection of nonportable code, not because pointers are somehow unfit to do the job of std::vector<T>::iterator. It so happens that iterators have become a useful way to generically iterate over noncontiguous containers as well, but it is very clear that they are "logically" meant to mirror the usage of a pointer (down to the operators you use to work with them) and suggesting that holding this opinion is a sign of inadequacy is condescending.
  - UncleMeat 5y ago
    This has its own problems. Pointer stability limits the internal implementation so much that unordered_map is embarrassingly slow given what we know about modern hashmap design. There is a good reason why the swisstables that Google built dropped this behavior.
daniel-levin 5y ago
I think if you come from the JVM / CLR world, you are so protected by the runtime’s patching up of references that it might not even occur to you that a (raw) pointer to a data structure’s internals can dangle after the data is moved around. The runtimes mentioned pause your code, move things around and even compact the heap and your references magically still point to what they did before!
- ncmncm 5y ago
  Except, it's not magic. It costs processing cycles, and latency, and invalidations of cache rows you were using, and memory bus traffic. Lots of all of them. Most of the costs are not counted as runtime for your process, so benchmarks invariably appear to show GC as costing less overhead than it does. Among the costs, as with all the myriad varieties of caching done in modern systems, is that GC makes it hard to know the costs of design choices you make. Many of the costs are in making the caches less effective.
- deleted 5y ago
  [deleted]
- contravariant 5y ago
  Well it's not so much being protected by patching up references, but more that C++ is (as far as I know) the only language that doesn't complain when you create a reference to an object that can move away. Most languages either don't have the concept of classes or ensure that invalidating references is an explicit operation (such as calling the destructor).
_huayra_ 5y ago
This is why things like std::list still have value: iterator stability. You even get this in most map/sets too. But vector is usually what one should reach for unless one has a good reason not to. The only danger really comes when the lifetime of iterators and the thing they point to become a bit decoupled, even due to insertion!
- einpoklum 5y ago
  You can also use an offset instead of a pointer (or a pointer to the object and and an offset into its heap storage, or whatever).
  - _huayra_ 5y ago
    This is actually on my list of "neat utilities to write": an iterator that encapsulates this "offset" for vector. If anyone is looking to write a custom iterator, I definitely recommend Boost's new stl interfaces: https://github.com/boostorg/stl_interfaces https://github.com/boostorg/stl_interfaces
    - nly 5y ago
      Or you could just use Boost stable_vector and save yourself the trouble https://www.boost.org/doc/libs/1_76_0/doc/html/boost/container/stable_vector.html https://www.boost.org/doc/libs/1_76_0/doc/html/boost/contain...
- gpderetta 5y ago
  deque is also good for reference stability when doing push_backs (but of course not when inserting in the middle).
rualca 5y ago
> Yeah I learned that the hard way when I found out that std::vector apparently feels free to move your objects around in memory for you, no matter if you point to them from somewhere else. It's not as much as "feeling free" as it is having to reallocate the array because you added elements beyond it's capacity and they had to be stored somewhere.
- contravariant 5y ago
  Well the problem I had was that I apparently didn't forbid it from using the move constructor, after I changed that it correctly failed to compile. So in my case the problem was very much that it took the liberty of doing something I wasn't expecting it to.
gpderetta 5y ago
Interestingly, the dangers of reference invalidation is actually one of the reasons why auto doesn't deduce references by default: vector<int> v = {42}; ... auto x = v[0] v.clear(); // if x was deduced as reference, using x at this point // would be UB std::cout<< x;

tines 5y ago

> Yeah I learned that the hard way when I found out that std::vector apparently feels free to move your objects around in memory for you In standard terminology, this is described as "invalidating iterators". There are a bunch of member functions in std::vector that either do or don't invalidate iterators, e.g. push_back(...) does but size() doesn't. And as the name implies, if you call a function that invalidates iterators, all your existing iterators/pointers/references become invalid.

Kranar 5y ago
Iterator invalidation is different from this. Iterator invalidation, as the name suggests, only applies to iterators. The problem OP was having had to do with dangling references. Some containers guarantee references won't dangle on mutation such as unordered_map. An unordered_map may invalidate iterators if objects are added or removed, but will never result in dangling references (unless the object is removed). That is, it is safe to have a pointer to an object owned by an unordered_map and continue using that pointer even after an iterator to that same object is invalidated.
- tines 5y ago
  Ah, interesting. Even within that dichotomy, I'd think that if references aren't invalidated on mutation, then dereferencing iterators would be valid, but incrementing them would not be.
- einpoklum 5y ago
  Iterators are historically a generalization of pointers. A pointer is a kind of iterator. I mean, literally. The iterator of an std::vector<T> (not a bool vector) is a T*.
  - Kranar 5y ago
    This is a poor understanding of what an iterator is. For one, the iterator of a std::vector<T> is not a T*, it's a std::vector<T>::iterator and you are welcome to verify that the following assertion fails for all T: static_assert(std::is_same_v<T\*, std::vector<T>::iterator>) Link provided below for convenience [1]. Furthermore just like a cat is animal does not imply an animal is a cat, a pointer being an iterator does not imply that an iterator is a pointer and holding such a confusing thought is the source of many bugs and poor C++ code. An iterator not only represents a form of indirection to an object, it also represents traversal through a collection of values. unordered_map guarantees that the objects it stores will remain alive until the unordered_map is destroyed or the object is removed from the map. However, unordered_map, as the name once again suggests, does not provide any guarantee about the ordering of objects. Hence, if you have an iterator to an object owned by such a map, and you add or remove objects to that map, the iterator becomes invalid not because the object the iterator references gets destroyed, but because the iterator loses information about where it's located within the unordered collection. For further information, please review the following link [2], specifically the quote "References and pointers to either key or data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.". [1] https://godbolt.org/z/Y5f4d74Kb https://godbolt.org/z/Y5f4d74Kb [2] https://en.cppreference.com/w/cpp/container/unordered_map https://en.cppreference.com/w/cpp/container/unordered_map
    - saagarjha 5y ago
      You're being far more patronizing than is necessary here, especially because the parent poster was correct in iterators originating out of a being a generalization over pointers, although not in their latter statement. But, while implementation defined, a vector iterator must behave identically to a pointer, and your assertion fails in both Clang and GCC not for any interesting reason but more because they wrap the pointer into a class for what I understand to be better encapsulation and earlier detection of nonportable code, not because pointers are somehow unfit to do the job of std::vector<T>::iterator. It so happens that iterators have become a useful way to generically iterate over noncontiguous containers as well, but it is very clear that they are "logically" meant to mirror the usage of a pointer (down to the operators you use to work with them) and suggesting that holding this opinion is a sign of inadequacy is condescending.
- UncleMeat 5y ago
  This has its own problems. Pointer stability limits the internal implementation so much that unordered_map is embarrassingly slow given what we know about modern hashmap design. There is a good reason why the swisstables that Google built dropped this behavior.

daniel-levin 5y ago

I think if you come from the JVM / CLR world, you are so protected by the runtime’s patching up of references that it might not even occur to you that a (raw) pointer to a data structure’s internals can dangle after the data is moved around. The runtimes mentioned pause your code, move things around and even compact the heap and your references magically still point to what they did before!

ncmncm 5y ago
Except, it's not magic. It costs processing cycles, and latency, and invalidations of cache rows you were using, and memory bus traffic. Lots of all of them. Most of the costs are not counted as runtime for your process, so benchmarks invariably appear to show GC as costing less overhead than it does. Among the costs, as with all the myriad varieties of caching done in modern systems, is that GC makes it hard to know the costs of design choices you make. Many of the costs are in making the caches less effective.
deleted 5y ago
[deleted]
contravariant 5y ago
Well it's not so much being protected by patching up references, but more that C++ is (as far as I know) the only language that doesn't complain when you create a reference to an object that can move away. Most languages either don't have the concept of classes or ensure that invalidating references is an explicit operation (such as calling the destructor).

_huayra_ 5y ago

This is why things like std::list still have value: iterator stability. You even get this in most map/sets too. But vector is usually what one should reach for unless one has a good reason not to. The only danger really comes when the lifetime of iterators and the thing they point to become a bit decoupled, even due to insertion!

einpoklum 5y ago
You can also use an offset instead of a pointer (or a pointer to the object and and an offset into its heap storage, or whatever).
- _huayra_ 5y ago
  This is actually on my list of "neat utilities to write": an iterator that encapsulates this "offset" for vector. If anyone is looking to write a custom iterator, I definitely recommend Boost's new stl interfaces: https://github.com/boostorg/stl_interfaces https://github.com/boostorg/stl_interfaces
  - nly 5y ago
    Or you could just use Boost stable_vector and save yourself the trouble https://www.boost.org/doc/libs/1_76_0/doc/html/boost/container/stable_vector.html https://www.boost.org/doc/libs/1_76_0/doc/html/boost/contain...
gpderetta 5y ago
deque is also good for reference stability when doing push_backs (but of course not when inserting in the middle).

rualca 5y ago

> Yeah I learned that the hard way when I found out that std::vector apparently feels free to move your objects around in memory for you, no matter if you point to them from somewhere else. It's not as much as "feeling free" as it is having to reallocate the array because you added elements beyond it's capacity and they had to be stored somewhere.

contravariant 5y ago
Well the problem I had was that I apparently didn't forbid it from using the move constructor, after I changed that it correctly failed to compile. So in my case the problem was very much that it took the liberty of doing something I wasn't expecting it to.

gpderetta 5y ago

Interestingly, the dangers of reference invalidation is actually one of the reasons why auto doesn't deduce references by default: vector<int> v = {42}; ... auto x = v[0] v.clear(); // if x was deduced as reference, using x at this point // would be UB std::cout<< x;