0

I understand that vectors get moved if you push more elements than it has capacity for, but what happens to std::list if one of it's elements get's moved for reasons unrelated to the list itself? For instance to make space for a vector? Will the list get invalidated because the elements around the moved element no longer point to it? Or is the list prepared for such eventuality?

If it is the later, what happens to pointers that point to the moved element?

For case application, i want to make a node map, which of course means that every node has to point to other nodes. But I also need to have a list of the nodes so I can search them easily. So i wanted to have a list where every object of the list will have pointers to some other elements of the same list (this is outside of the normal std::list back and forth pointers). But I got worried about how would std::list handle one of its elements getting moved, and how could i handle my own pointers in such eventuality.

I discarded vectors already because the documentation already states that if it gets moved all pointers and references to its elements will get invalidated. If my approach of using std::list can not work, my 2nd best would be to keep the list of nodes into a vector and make the nodes reference eachother through index number (which i can do because once built the vector won't change it's size)

11
  • 2
    They won't get "moved for reasons unrelated to the list itself". They'll get moved if you call a function that invalidates iterators. Read up on the functions you're working with and pay close attention to that annotation.
    – tadman
    Commented Nov 13, 2019 at 1:28
  • 2
    Remember only the container entry is invalidated, but if you're storing something like a reference or a shared pointer then those aren't invalidated. It sounds like you want to dynamically allocate the nodes you're persisting, then wrap a list around them as a way of iterating over them, etc.
    – tadman
    Commented Nov 13, 2019 at 1:29
  • 2
    Handy Reading: Iterator invalidation rules. You'll find that list is very forgiving. Commented Nov 13, 2019 at 1:30
  • Reading the documentation for vector was a good move, as you saw that pointers could become invalid. (You worded that strangely in your question, though.) Presumably your documentation source also covers list. What does that documentation say about when pointers can become invalid?
    – JaMiT
    Commented Nov 13, 2019 at 2:26
  • @tadman unless I assume the user will have an unlimited amount of memory, shouldn't I consider the posibility of memory being reallocated to make space for new elements (vectors for instance)?
    – Coyoteazul
    Commented Nov 13, 2019 at 3:08

1 Answer 1

3

but what happens to std::list if one of it's elements get's moved for reasons unrelated to the list itself?

In C++, the runtime environment is not allowed to unilaterally move objects in that way, for exactly the reason you imagine -- there is no reliable or efficient way to find all pointers to the object's old location and modify them to point to a new location, so any attempt to surreptitiously move an object would run the risk of creating dangling-pointers which would lead to undefined behavior. (btw this is one reason why garbage collectors don't work very well in C++)

So having your list-nodes objects moved behind your back is not something you need to worry about. Since your list-container has sole ownership of the nodes, the only way for this to happen would be if the list itself decided to explicitly move one of its nodes for some reason (and in general there's no general reason why it would need or want to do that).

2
  • Does that apply for too vectors? If i have a vector that won't change it's size after it's been constructed (lets suppose it's const, if it helps) can I safely make pointers to it's elements knowing that they won't get invalidated?
    – Coyoteazul
    Commented Nov 15, 2019 at 11:45
  • 1
    If you don’t do anything that would cause the vector to have to reallocate it’s underlying array, then pointers to items in the array will remain valid. Commented Nov 15, 2019 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.