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 In standard terminolog

by 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.
      - Kranar 5y ago
        >because the parent poster was correct in iterators originating out of a being a generalization over pointers And an animal is a generalization of a cat, but that doesn't mean an animal is a cat. What is true of a particular doesn't have to be true of the general. > But, while implementation defined, a vector iterator must behave identically to a pointer No it does not. MSVC implements a vector iterator with additional runtime safety guarantees in DEBUG mode and while those guarantees are not mandatory as per the standard, they are fully in compliance, so saying they have to behave identically is patently false as MSVC's behavior is a superset of the behavior provided by a pointer. > suggesting that holding this opinion is a sign of inadequacy is condescending. If you care about writing correct code, then do not mix the very concept of pointers, arrays, references, and iterators with one another. They are all related to one another but have very important differences to the point that calling them literally identical to one another is a sign of inadequate understanding. It happens far too often and inevitably leads to poor code, bugs, and a fundamentally poor understanding of what these things represent conceptually.
        saagarjha 5y ago
        First of all, calm down. Consider that the people you are talking to may not be idiots. Second of all, nobody is saying that pointers, arrays, references, and iterators are identical in general. They are clearly related concepts but differ in fundamental ways. However, my point was that a vector iterator needs to behave like a pointer would and can in fact be implemented as a naked pointer. Pointing to MSVC's implementation having safety checks does not change that fact, because pointing to what an implementation does on undefined behavior is clearly out of scope when discussing specified behavior. I'm not going to bring address sanitizer into this discussion to show how pointers can actually be a superset of "pointer behavior" because that would just be irrelevant. The fact remains that iterators were originally meant to act like pointers, and in many cases still do. Believing this does not mean I have a poor understanding of the language.
- 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.

by tines 5y ago

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.
    - Kranar 5y ago
      >because the parent poster was correct in iterators originating out of a being a generalization over pointers And an animal is a generalization of a cat, but that doesn't mean an animal is a cat. What is true of a particular doesn't have to be true of the general. > But, while implementation defined, a vector iterator must behave identically to a pointer No it does not. MSVC implements a vector iterator with additional runtime safety guarantees in DEBUG mode and while those guarantees are not mandatory as per the standard, they are fully in compliance, so saying they have to behave identically is patently false as MSVC's behavior is a superset of the behavior provided by a pointer. > suggesting that holding this opinion is a sign of inadequacy is condescending. If you care about writing correct code, then do not mix the very concept of pointers, arrays, references, and iterators with one another. They are all related to one another but have very important differences to the point that calling them literally identical to one another is a sign of inadequate understanding. It happens far too often and inevitably leads to poor code, bugs, and a fundamentally poor understanding of what these things represent conceptually.
      - saagarjha 5y ago
        First of all, calm down. Consider that the people you are talking to may not be idiots. Second of all, nobody is saying that pointers, arrays, references, and iterators are identical in general. They are clearly related concepts but differ in fundamental ways. However, my point was that a vector iterator needs to behave like a pointer would and can in fact be implemented as a naked pointer. Pointing to MSVC's implementation having safety checks does not change that fact, because pointing to what an implementation does on undefined behavior is clearly out of scope when discussing specified behavior. I'm not going to bring address sanitizer into this discussion to show how pointers can actually be a superset of "pointer behavior" because that would just be irrelevant. The fact remains that iterators were originally meant to act like pointers, and in many cases still do. Believing this does not mean I have a poor understanding of the language.
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.