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