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)

Coyoteazul
  • 123
  • 1
  • 9
  • 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 Nov 13 '19 at 01:28
  • 2
    Remember only the container entry is invalidated, but if you're storing something like a reference or a [shared pointer](https://en.cppreference.com/w/cpp/memory/shared_ptr) 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 Nov 13 '19 at 01:29
  • 2
    Handy Reading: [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules). You'll find that `list` is very forgiving. – user4581301 Nov 13 '19 at 01: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 Nov 13 '19 at 02: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 Nov 13 '19 at 03:08
  • @tadman shared pointer seem useful. I hadn't thought about ownership of the memory. Perhaps I'm missunderstanding how pointers work. I thought of them as strings that indicate coordinates on the memory – Coyoteazul Nov 13 '19 at 03:11
  • @user4581301 that was handy indeed. But as far as i see List is forgiving because the container is prepared to handle the reallocation when you use the container's methods. It doesn't state what happens when memory gets reallocated to make space for other objects, without intervention of the container's methods – Coyoteazul Nov 13 '19 at 03:12
  • @Coyoteazul You're not wrong, but a shared pointer handles memory management for you among other things. – tadman Nov 13 '19 at 03:26
  • @JaMit My documentation is simply google, I don't have a proper guide. For std I usually end up in cplusplus.com. It covers list, but doesn't state what happens if the elements get reallocated – Coyoteazul Nov 13 '19 at 03:35
  • C++ is a very complicated language. Probably the most complicated that you'll find in general use. You can learn it by trial and error, but the odds aren't good and it's going to be brutally slow going. A good set of references will get you started a lot faster and inoculate you against idiocy. Here is a [list of trusted books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to get you started. Without a book, my advice is to research the domain experts in what you want to learn and follow their tutorials or the tutorials they recommend. – user4581301 Nov 13 '19 at 05:59
  • @Coyoteazul Hmm... it looks like cplusplus.com scatters the relevant information across numerous pages. If you'll consider another site, there is a handy table under ["Iterator invalidation" at cppreference.com](https://en.cppreference.com/w/cpp/container#Iterator_invalidation). For more details, there is that SO FAQ entry to which user4581301 linked. Throw in Jeremy Friesner's answer, and your concerns should be addressed. Is there anything we missed from this question? – JaMiT Nov 13 '19 at 21:37

1 Answers1

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).

Jeremy Friesner
  • 70,199
  • 15
  • 131
  • 234
  • 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 Nov 15 '19 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. – Jeremy Friesner Nov 15 '19 at 14:43