An intelligent iterator for std::list

[John E]

typedef std::list<int> intList;
typedef intList::iterator myListIter;

intList myList;
myListIter iter = myList.begin();

while (1)
{
if (iter == myList.end())
{
myList.push_back(2);
myList.push_back(4);
myList.push_back(6);
}
}On the first time round the loop, myList is empty. On the second time round, 3 items have been added to the list. Therefore 'iter' is no longer at the list end. However, the test if (iter == myList.end()) passes, so 3 more ints get added to the list.

Is there a way to 'reset' an iterator (or to have some kind of intelligent iterator) so that, if items get added to (or removed from) the list, the iterator keeps track of the new begin() and end() ?

[laitinen]

An iterator is implemented as some kind of pointer to an element. It does not change when new items are added/deleted. The pointer is constant. YOu will have to assign new values to your iterator:iter = myList.begin();

Laitinen

[John E]

But surely myList.end() should be returning the modified end point - not the original end point. :confused:

Something's wrong here - either myList.end() is returning the wrong element or iter is somehow getting updated as elements get added.

What I need is an iterator that remembers where it was - even if new elements get added (which doesn't seem to be what's happening).

[treuss]

What I need is an iterator that remembers where it was - even if new elements get added (which doesn't seem to be what's happening).All iterators supplied by the standard library are are becoming invalid if new items are added. Using them is undefined behaviour (as you can see with your example, which might work different with different c++ compilers). If you want a different kind of iterator, you have to implement it yourself.

EDIT: Just some thought: I assume, the "surprising" results you get, are caused by the implementation returning a kind-a-null-pointer (TM) as list::end(). So list::begin() on an empty list will return list::end(), i.e. this kind-a-null-pointer. The push-back's do of course not affect this, so your check if the iterator is still pointing to end() will always be true. But as stated, this is just the undefined behaviour of your specific impelementation...

[jwbarton]

Originally Posted by treuss
All iterators supplied by the standard library are are becoming invalid if new items are added.


Actually, this isn't true for std::list. Inserting elements into an std::list never invalidates any iterators in the list (including the end() iterator).

It also isn't necessarily true for other containers, but the details depend on the container. However, for many of the standard containers, there are only limited cases where iterators remain valid after inserting an element.

Best regards,
John

[treuss]

Just for fun: A little modification of your code:
typedef std::list<int> intList;
typedef intList::iterator myListIter;

intList myList;
myListIter iter = myList.end();

while (1)
{
if (iter == myList.begin())
{
myList.push_back(2);
myList.push_back(4);
myList.push_back(6);
}
}Works as you would expect.

Thanks, jwbarton. I stand corrected.

[John E]

Thanks Treuss and John but this doesn't really get me any nearer to a solution. In my original example, the iterator apparently IS getting modified each time I add an element (in fact, I suspect that adding a new element resets the iterator - either to end() or to the newly added element).

[Edit...] Actually Treuss, I re-read your post and I suspect you might be right. A null end pointer will still be a null end pointer, even after adding new elements. This would also explain why your modified example worked but my original example didn't..!

Interestingly, for this code:-

if (iter == myList.end())
iter++;

if (iter == myList.end())
{
CallSomeFunc();
}'CallSomeFunc()' would actually get called - indicating that if the iterator is NULL, it doesn't get incremented any further.

[jwbarton]

In your original example, the iterator is set to begin() on an empty list, which is the same as end(). When you insert elements into the list, it still maintains the value of end() (it doesn't change, and is still the valid value of the end() iterator).

No insert operation on a list is going to change the value of a separate variable. You have to provide this logic yourself. The standard library doesn't provide any iterators which have this kind of functionality.

Best regards,
John

[John E]

Sorry John - I re-edited my post while you were typing. Does that explain why my second example also works?

[treuss]

'CallSomeFunc()' would actually get called - indicating that if the iterator is NULL, it doesn't get incremented any further.Incremeanting an end pointer is, I believe, once again undefined behaviour. I would have to check the details, but I believe that it could even crash, as incremeanting a list iterator usually requires dereferencing. Not sure though and don't have the standard at hand...

[jwbarton]

It isn't valid to increment an iterator which has the end() value (as treuss said - undefined behavior).

My compiler (Visual C++ 2008) gives diagnostic messages in debug mode when attempting this.

Running it in debug mode with iterator debugging turned on (the default mode), I get a diagnostic:
Expression: list iterator not incrementable

If I turn off iterator debugging, I still get an assert in debug mode on the increment of the iterator.


You also shouldn't think of the end iterator as a NULL value. It is a special value indicating the end of the list. Since an iterator isn't a pointer, this value isn't NULL. It might be implemented as NULL internally on some compilers, but this is not something to rely upon.

Best regards,
John

[exterminator]

Incremeanting an end pointer is, I believe, once again undefined behaviour. I would have to check the details, but I believe that it could even crash, as incremeanting a list iterator usually requires dereferencing. Not sure though and don't have the standard at hand...Did a quick scan but couldn't find anything relevant. Don't know for sure, but I recall that dereferencing end() is UB. And as you rightly mentioned that you cannot go to ++end() for a list iterator without dereferencing end(), it is UB as well.

[exterminator]

But surely myList.end() should be returning the modified end point - not the original end point. :confused:

Something's wrong here - either myList.end() is returning the wrong element or iter is somehow getting updated as elements get added.

What I need is an iterator that remembers where it was - even if new elements get added (which doesn't seem to be what's happening).What should it remember? When you do something like this:

std::list<int>::iterator it = myList.begin();
and then later add up stuff into the list, how does the variable it know what it was initialized with? begin() or end() or may be some other already existing element? And once a value is inserted or let's say the element pointed to by it is removed where should "it" now point to? One ahead or one behind? It is just too much documentation to have some behaviour of that kind and probably would be inefficient too!

.end() call will always give you one past the last element. That is by definition. That is not the culprit here. The culprit is "iter" object. As a boundary condition, when the list is empty begin() == end() but that is just a special case for the boundary condition since there is no element for begin() to point to and there is no element for end() to point beyond of!

.begin() will always return the beginning element of the sequence (except for when empty). If you want your iterators to move on inserts and push backs, you will need to do that manually or take use of return value of insert (overload taking position). If you are doing push_back then to get iterator to this push_backed element, you can do --myList.end(). That is, you will need to code to handle to iterator movements.

What is it that you are trying to achieve?

[John E]

What is it that you are trying to achieve?Basically, I'm iterating through a long list and (as I go along) I might want to add new elements to the list. The new elements will always be added using either push_back() or insert() - but either way, they'll always be inserted at a later position than the current iterator pos. I just want to be sure that this won't upset the iterator because (ideally) I don't want to have to keep resetting it back to the beginning after each new addition.

My understanding of std::list is patchy but according to MSDN, end() returns:-

a bidirectional iterator that addresses the location succeeding the last element in a list. If the list is empty, then list::end == list::begin.This is why I was surprised that, after adding elements to an empty list, list::end() was apparently still returning list::begin()

(or, to put it another way, it was still returning the same thing it returned when the list was empty).

[exterminator]

This is why I was surprised that, after adding elements to an empty list, list::end() was apparently still returning list::begin()

(or, to put it another way, it was still returning the same thing it returned when the list was empty).No! begin() will always return the first element and end() will always return one past the last element (that could be anything from a NULL pointer to any custom node having some identification of not being part of the list).

The problem is with empty lists - the boundary condition - then begin() and end() need to return true on equality comparison. But this will not happen in any other scenario.

The problem you are facing is because you cached the begin iterator and due to the specific implementation's way of representing begin() and end() when empty, you get that begin() initialized iterator to be always same as what end() returns. Do not cache that value and you should be okay. Your iterators you fetch from begin (which you get for a non-empty list) will always remain intact if you don't push an element at the beginning. Even then that just changes the definition of that iterator. That is no longer a begin() iterator since something got inserted before it but you can use the iterator or a reference to that element without any issues. You can do op-- to reach to the newly inserted element at the head (you can do op-- and op++ to list iterators shows that the iterator is bidirectional).

All iterators would remain valid as long as they are not removed. But again, note the boundary condition as above.

If this doesn't help, can you show some code as to what you are doing and what you want that code to do exactly?

[John E]

Thanks exterminator. My code is actually working fine but my original confusion arose because (according to MSDN) std::list::end() returns "a location". I couldn't understand why that location was apparently the same - even after I'd added 3 new elements to the list. I now realise that std::list::end() (at least in VC++) must return something akin to NULL - and that explains why it was the same as the cached iterator, even after adding extra elements.

[exterminator]

I now realise that std::list::end() (at least in VC++) must return something akin to NULL - and that explains why it was the same as the cached iterator, even after adding extra elements.No, it is not necessarily NULL. Particularly for the STL list with VS2005, end() is actually valid node : _Myhead which is initialized in the function _Buynode(). It is such that the next and prev for it are same as that node itself when the list is empty. Try putting a break point on to that function defined in <list> and see. It could be just about anything by which the library author wants to identify the end().

[treuss]

No! begin() will always return the first element and end() will always return one past the last element...I think, this describes the original mistake that John E. had in his thinking. begin() will not always return the first element, it will only return the first element for non-empty lists. For empty lists, begin() will return the virtual "one past the last" element, just like end().

A list iterator pointing to the first element will remain pointing to the first element when new elements are added to the list. Likewise a list iterator pointing to the virtual one-past-the-last element, will continue pointing to that element when new elements are added to the list. So, list iterators do remember their position just like they should.

The problem with the original code is that you were expecting the iterator to change from pointing to the one-past-the-last element to pointing to the first element, just because you received the iterator through a call to begin(). Once you understood that begin() does not always return an iterator pointing to the first element, it's easy to realize the code works as expected (and not at all undefined like I stated previously :blush: ).

[John E]

I think, this describes the original mistake that John E. had in his thinking. begin() will not always return the first element, it will only return the first element for non-empty lists. For empty lists, begin() will return the virtual "one past the last" element, just like end().Yes, I think that's part of the explanation but it's more true to say that I assumed myList.end() would return something different as new elements get added to the list. This seems not to be the case (at least for VC++).