Get pointer to node in std::list or std::forward_list

Question

I am planning to use std::list in my code, I decided not to use std::forward_list, because for deletions (I figured) the whole list will have to traversed, O(N) complexity for std::forward_list (being a single link list). However, when I looked into the documentation I noticed both the stl containers have O(N) complexity to remove an item.

• http://www.cplusplus.com/reference/forward_list/forward_list/remove/
• http://www.cplusplus.com/reference/list/list/remove/

After some thinking I figured out why (I think). It's because in both cases, the whole list has to be scanned to find the node first, and then delete it. Is this right?

I then looked into the "erase" and "erase_after" methods, and their complexity is "Linear in the number of elements erased (destructions).". It's because, I am passing an iterator to the node (which is kind of like a "pointer"). However, I cannot (or prefer not to) pass this iterator around in my code to access the data in the node. I am not sure if this iterator will be valid if the list is modified? Thoughts?

My question is, is there a way I can get a pointer to the node in the list. That way, I know it will be valid throughout the lifetime of my program, pass it around. And I can just look into it to get access to my data.

Answer 1

However, I cannot (or prefer not to) pass this iterator around in my code to access the data in the node.

Why not? Iterators are easy to use and are quite lightweight. A pointer isn't better in any way.

I am not sure if this iterator will be valid if the list is modified?

For list, any iterator will remain valid, even if the list is modified. Except, of course, if you erase the particular element that is the iterator points to. But that's kind of obvious, you can' expect to have an iterator (or pointer) to something that doesn't exist any more.

(vector is more dangerous. One small change to a vector can invalidate all its iterators.)

You can take a pointer to any individual element in the list.

list<int> iterator it = find(l.begin(), l.end(), 7); // get an iterator
int * ptr = &*it; // get a pointer to the same element.

The pointer is similar to the iterator in many respects. But the iterator is a little more powerful. An iterator can be incremented or decremented, to access neighbouring elements in the list. And an iterator can be used to delete an element from the list. A pointer cannot do either of those things.

Both the iterator and pointer remain valid as long as that particular element isn't removed.

Answer 2

I am not sure if this iterator will be valid if the list is modified

Yeah, in the general case, storing iterators is risky unless you keep a close eye on the operations performed on your container.

Problem is, this is just the same for a pointer. In fact, for many containers, iterators are implemented as pointers.

So either store an iterator or a pointer if you like but, either way, keep an eye on the iterator invalidation rules:

• Iterator invalidation rules

Answer 3

For lists, an iterator is valid even if other items in the list are erased. It becomes garbage when that item the iterator references in the list is removed.

So, as long as you know the iterator you're passing around isn't being removed by some other piece of code, they're safe to hold onto. This seems fragile though.

Even if there was a construct outside of iterators to reference a node in the list, it would suffer from the same fragility.

However, you can have each node contain an std::shared_ptr to the data it stores instead of the object itself and then pass around std::weak_ptr's to those objects and check for expired before accessing those weak_ptr's.

eg

instead of

std::list<MyClass> foo;

you would have

std::list<std::shared_ptr<MyClass>> foo;

have a look here for info on weak_ptr's

Answer 4

is there a way I can get a pointer to the node in the list

Yes, in your particular implementation.

No, in a standard-compliant way.

If you look at the std::list documentation, there is not a single word about a node. While it is hard to imagine a different way to implement the std::list other than using a doubly linked list, there is nothing that prevents it.

You should almost never come into any contact with undocumented internals of libraries.

Answer 5

Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.

Source: https://en.cppreference.com/w/cpp/container/list

So a std::list<>::iterator is only invalidated when the corresponding element is deleted. So yes, as long as you make sure that the corresponding element exists (which you will anyway have to do in your scenario of storing/passing around a pointer to anything) you can save and/or pass around the iterator throughout the lifetime of your program.

Now, an iterator is nothing but a pointer in disguise. So, if you prefer to save/pass around the corresponding pointer instead of iterator, you can always first convert the iterator to the pointer as @Aaron McDaid suggested.

int * ptr = &*it; // get a pointer to the same element.