Forward iterators and past-the-end iterator

[Mark Stijnman]

I have a question about forward iterators and what one should do or not
do with them. I'm planning on writing a container that, when all boils
down to it, stores a sequence of strings. I want threads to be able to
read this sequence from start to end, and when they reach the end, wait
until new data is added to the end. If so, it should pick up reading
where it left off. The question is, is it valid and moral to do
something like this from a reader thread (synchronization code is left
out here for brevity/clarity):

MyContainer::const_iterator ReadIter; // a forward iterator
MyContainer ReadThis; // a container

for (ReadIter = ReadThis.begin(); ReadIter!=ReadThis.end(); ++ReadIter)
cout << *ReadIter << endl;

// at the end of the loop ReadIter is the past-the-end iterator
returned by the last end() call.

// Thread waits for ReadThis to have one more more items added.
WaitForItemsAddedSignal(...);

// Here's the catch: assume ReadIter is now no longer the past-the-end
iterator, but is now
// referencing the next unread string, so we can just pick up where we
left off like so:
for ( ; ReadIter!=ReadThis.end(); ++ReadIter)
cout << *ReadIter << endl;

So, a Forward iterator that used to store the past-the-end iterator,
returned from a previous call to end(), now suddenly references an
actual item. It is clearly possible to implement something like this,
but is it a good idea? It might be somewhat confusing: It assumes
something about the iterator (or the container?) that 'normal' forward
iterators don't guarantee. Of course I could specificly mention this in
the description of MyContainer that I give this guarantee, but should I
go this route to begin with? Or should I use another way of keeping
track of the "last read" item?

Thanks for any insights,

regards Mark

 

[Victor Bazarov]

I have a question about forward iterators and what one should do or not
do with them. I'm planning on writing a container that, when all boils
down to it, stores a sequence of strings. I want threads to be able to
read this sequence from start to end, and when they reach the end, wait
until new data is added to the end. If so, it should pick up reading
where it left off. The question is, is it valid and moral to do
something like this from a reader thread (synchronization code is left
out here for brevity/clarity):

MyContainer::const_iterator ReadIter; // a forward iterator
MyContainer ReadThis; // a container

for (ReadIter = ReadThis.begin(); ReadIter!=ReadThis.end(); ++ReadIter)
cout << *ReadIter << endl;

// at the end of the loop ReadIter is the past-the-end iterator
returned by the last end() call.

// Thread waits for ReadThis to have one more more items added.
WaitForItemsAddedSignal(...);

// Here's the catch: assume ReadIter is now no longer the past-the-end
iterator, but is now
// referencing the next unread string, so we can just pick up where we
left off like so:
for ( ; ReadIter!=ReadThis.end(); ++ReadIter)
cout << *ReadIter << endl;

So, a Forward iterator that used to store the past-the-end iterator,
returned from a previous call to end(), now suddenly references an
actual item. It is clearly possible to implement something like this,
but is it a good idea? It might be somewhat confusing: It assumes
something about the iterator (or the container?) that 'normal' forward
iterators don't guarantee. Of course I could specificly mention this in
the description of MyContainer that I give this guarantee, but should I
go this route to begin with? Or should I use another way of keeping
track of the "last read" item?

I think the dilemma is solved not by providing the documentation, but
rather by examining the possibility of somebody (even yourself) using
the code with any other container rather than your own with its special
iterator.

What happens here is that after the signal arrives, the first thing you
are going to be doing is dereferencing the iterator, then incrementing it
in the last loop. Both operations are definitely invalid for iterators
from 'std::list', for example.

Generally speaking, once the iterator got the value "one after the last"
it should be impossible for any code outside the thread that owns that
iterator object to change its meaning (by somehow changing its value).

Store the iterator to the "last" element and increment it after you get
the signal:

MyContainer ReadThis; // a container
MyContainer::const_iterator ReadIter = ReadThis.begin(), RT;

for (RT = ReadIter; RT != ReadThis.end(); ReadIter = RT++)
cout << *RT << endl;

// at the end of the loop ReadIter is the iterator to the last read.

// Thread waits for ReadThis to have one more more items added.
WaitForItemsAddedSignal(...);

++ReadIter; // now it points to the next to read

for (RT = ReadIter; RT != ReadThis.end(); ReadIter = RT++)
cout << *RT << endl;

V

 

[Daniel T.]

I have a question about forward iterators and what one should do or not
do with them. I'm planning on writing a container that, when all boils
down to it, stores a sequence of strings. I want threads to be able to
read this sequence from start to end, and when they reach the end, wait
until new data is added to the end. If so, it should pick up reading
where it left off. The question is, is it valid and moral to do
something like this from a reader thread (synchronization code is left
out here for brevity/clarity):

MyContainer::const_iterator ReadIter; // a forward iterator
MyContainer ReadThis; // a container

for (ReadIter = ReadThis.begin(); ReadIter!=ReadThis.end(); ++ReadIter)
cout << *ReadIter << endl;

// at the end of the loop ReadIter is the past-the-end iterator
returned by the last end() call.

// Thread waits for ReadThis to have one more more items added.
WaitForItemsAddedSignal(...);

// Here's the catch: assume ReadIter is now no longer the past-the-end
iterator, but is now
// referencing the next unread string, so we can just pick up where we
left off like so:
for ( ; ReadIter!=ReadThis.end(); ++ReadIter)
cout << *ReadIter << endl;

So, a Forward iterator that used to store the past-the-end iterator,
returned from a previous call to end(), now suddenly references an
actual item. It is clearly possible to implement something like this,
but is it a good idea? It might be somewhat confusing: It assumes
something about the iterator (or the container?) that 'normal' forward
iterators don't guarantee. Of course I could specificly mention this in
the description of MyContainer that I give this guarantee, but should I
go this route to begin with? Or should I use another way of keeping
track of the "last read" item?

Thanks for any insights,

I would create an iterator class that always returns something when
incremented, even if it has to wait for data. However, there must be
*some* way to determine that it has hit the end of the data...

MyContainer::const_iterator readIter = readThis.begin();
while ( *readIter != eof ) {
cout << *readIter << '\n';
++readIter; // will wait for more data if it has to.
}

Or you could have readIter throw an exception when it comes to the
*real* end.

 

[Pete Becker]

I have a question about forward iterators and what one should do or not
do with them. I'm planning on writing a container that, when all boils
down to it, stores a sequence of strings. I want threads to be able to
read this sequence from start to end, and when they reach the end, wait
until new data is added to the end. If so, it should pick up reading
where it left off. The question is, is it valid and moral to do
something like this from a reader thread (synchronization code is left
out here for brevity/clarity):

If your iterator's increment blocks until there's a new element
available, then it looks a lot like a stream iterator reading from the
standard input stream. The only time the iterator compares equal to the
end iterator is when there's not going to be anything further, such as
when you press whatever magic key combination tells the input system
that it's at end of file.

 

[Mark Stijnman]

I think the dilemma is solved not by providing the documentation, but
rather by examining the possibility of somebody (even yourself) using
the code with any other container rather than your own with its special
iterator.

What happens here is that after the signal arrives, the first thing you
are going to be doing is dereferencing the iterator, then incrementing it
in the last loop. Both operations are definitely invalid for iterators
from 'std::list', for example.

Generally speaking, once the iterator got the value "one after the last"
it should be impossible for any code outside the thread that owns that
iterator object to change its meaning (by somehow changing its value).

Store the iterator to the "last" element and increment it after you get
the signal:

MyContainer ReadThis; // a container
MyContainer::const_iterator ReadIter = ReadThis.begin(), RT;

for (RT = ReadIter; RT != ReadThis.end(); ReadIter = RT++)
cout << *RT << endl;

// at the end of the loop ReadIter is the iterator to the last read.

// Thread waits for ReadThis to have one more more items added.
WaitForItemsAddedSignal(...);

++ReadIter; // now it points to the next to read

for (RT = ReadIter; RT != ReadThis.end(); ReadIter = RT++)
cout << *RT << endl;

V

Thanks, that was the insight I was looking for. It does indeed seem
more logical that a past-the-end iterator will remain a
non-dereferenceable iterator, and not magically turn itself into a
dereferenceable iterator when you are not looking. Also, like you
pointed out, your approach makes it work with all other containers that
support forward iterators.

best regards Mark

 

[Mark Stijnman]

Thanks for your suggestion, it definitely has its merits - the most
important that I see is that the details of having the thread wait for
the "new items available" signal is hidden inside the iterator. It also
defines a mechanism to alert the reading threads of the fact that there
will be no more new data. The one disadvantage I see is that it might
make the thread irresponsive to other events. In my case, one or more
of the threads will more than likely be doing network communication as
well. I will have to think whether this is a real problem though.

best regards Mark