Forward iterators and past-the-end iterator

Discussion in 'C++' started by Mark Stijnman, Jan 27, 2006.

  1. 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
    Mark Stijnman, Jan 27, 2006
    #1
    1. Advertising

  2. Mark Stijnman wrote:
    > 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
    Victor Bazarov, Jan 27, 2006
    #2
    1. Advertising

  3. Mark Stijnman

    Daniel T. Guest

    In article <>,
    "Mark Stijnman" <> wrote:

    > 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.
    Daniel T., Jan 27, 2006
    #3
  4. Mark Stijnman

    Pete Becker Guest

    Mark Stijnman wrote:

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

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
    Pete Becker, Jan 27, 2006
    #4
  5. Victor Bazarov wrote:
    > 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, Jan 28, 2006
    #5
  6. 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
    Mark Stijnman, Jan 28, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. James Aguilar
    Replies:
    4
    Views:
    3,640
    Lionel B
    May 9, 2005
  2. ozbear

    One-past-end-of-object pointers

    ozbear, Sep 1, 2004, in forum: C Programming
    Replies:
    3
    Views:
    476
  3. Matthias Kaeppler

    Dereferencing past-the-end iterators

    Matthias Kaeppler, Jul 22, 2005, in forum: C++
    Replies:
    2
    Views:
    428
    Matthias Kaeppler
    Jul 23, 2005
  4. Replies:
    7
    Views:
    367
  5. Nikos Chantziaras
    Replies:
    15
    Views:
    580
    Nikos Chantziaras
    Apr 14, 2011
Loading...

Share This Page