Iterator implementation questions: copy constructor and postfixincrement

Discussion in 'C++' started by Scott Gifford, Sep 5, 2007.

  1. Hello,

    I'm working on an providing an iterator interface to a database. The
    basic thing I'm trying to accomplish is to have my iterator read rows
    from the database and return constructed objects. My goal here is to
    abstract away the database part, so that in the future these objects
    could be constructed from a data source on disk, across the network,
    etc. The interface I'm after is similar to the standard iterator
    interface for an "input iterator":

    DataSource source;
    for(DataSource::iterator iter = source.findAll(); iter++; iter != DataSource::end()) {
    /* ... */
    }

    The problem I'm running into is that this idiom requires that the
    iterator be constructed in findAll(), then copied into a local
    variable with the copy constructor. My constructor creates a database
    cursor object to read rows, so my copy constructor needs to make a
    copy of that cursor. However my database driver won't allow me to
    copy the cursor object, or even to create a new cursor object before
    the first cursor is destroyed.

    The solution I'm currently using is to store the cursor object in a
    pointer, then have a copy constructor which takes over ownership of
    the cursor, setting it to NULL in the copied object so it won't be
    destoyed in the destructor. This basically works, but seems very
    kludgey, and has some issues I'll address in another post,

    I'm having a similar problem implementing postfix increment
    (operator++(int)). I basically need to return a copy of the iterator
    at the previous position in the database, but again I can't copy the
    database cursor or construct a new cursor because of driver
    limitations.

    These seem like they would be common problems. Are there common
    solutions to them? Can anybody point me to a good reference for
    creating iterator interfaces?

    Thanks!

    ----ScottG.
     
    Scott Gifford, Sep 5, 2007
    #1
    1. Advertising

  2. Re: Iterator implementation questions: copy constructor and postfix increment

    Scott Gifford wrote:
    > I'm working on an providing an iterator interface to a database. The
    > basic thing I'm trying to accomplish is to have my iterator read rows
    > from the database and return constructed objects. My goal here is to
    > abstract away the database part, so that in the future these objects
    > could be constructed from a data source on disk, across the network,
    > etc. The interface I'm after is similar to the standard iterator
    > interface for an "input iterator":
    >
    > DataSource source;
    > for(DataSource::iterator iter = source.findAll(); iter++; iter !=
    > DataSource::end()) { /* ... */


    I believe you meant

    for (DataSource::iterator iter = source.findAll();
    iter != DataSource::end();
    ++iter)
    { /* ... */
    }

    (first compare, then increment)

    > The problem I'm running into is that this idiom requires that the
    > iterator be constructed in findAll(), then copied into a local
    > variable with the copy constructor. My constructor creates a database
    > cursor object to read rows, so my copy constructor needs to make a
    > copy of that cursor. However my database driver won't allow me to
    > copy the cursor object, or even to create a new cursor object before
    > the first cursor is destroyed.
    >
    > The solution I'm currently using is to store the cursor object in a
    > pointer, then have a copy constructor which takes over ownership of
    > the cursor, setting it to NULL in the copied object so it won't be
    > destoyed in the destructor. This basically works, but seems very
    > kludgey, and has some issues I'll address in another post,
    >
    > I'm having a similar problem implementing postfix increment
    > (operator++(int)). I basically need to return a copy of the iterator
    > at the previous position in the database, but again I can't copy the
    > database cursor or construct a new cursor because of driver
    > limitations.


    Don't implement post-increment. At all. Use pre-increment.

    > These seem like they would be common problems. Are there common
    > solutions to them? Can anybody point me to a good reference for
    > creating iterator interfaces?


    There are some pointers (so to speak) in "Effective STL" by Meyers,
    and in "The C++ Standard Library" by Josuttis. Otherwise, look on
    the web, search the archives of this newsgroup (and c.l.c++.moderated)
    for more recommendations.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Sep 5, 2007
    #2
    1. Advertising

  3. "Victor Bazarov" <> writes:

    > Scott Gifford wrote:


    [...]

    >> DataSource source;
    >> for(DataSource::iterator iter = source.findAll(); iter++; iter !=
    >> DataSource::end()) { /* ... */

    >
    > I believe you meant
    >
    > for (DataSource::iterator iter = source.findAll();
    > iter != DataSource::end();
    > ++iter)
    > { /* ... */
    > }
    >
    > (first compare, then increment)


    Yes, of course, thank you for the correction!

    [...]

    >> I'm having a similar problem implementing postfix increment
    >> (operator++(int)). I basically need to return a copy of the iterator
    >> at the previous position in the database, but again I can't copy the
    >> database cursor or construct a new cursor because of driver
    >> limitations.

    >
    > Don't implement post-increment. At all. Use pre-increment.


    That's what I've done so far, but I was concerned that it might not
    work with all of the standard algorithms without a post-increment
    operator, mostly because the docs at SGI say that an input iterator
    must implement post-increment:

    http://www.sgi.com/tech/stl/InputIterator.html

    Is it safe to assume that the standard algorithms that work with an
    input iterator all use pre-increment so I don't have to worry about
    this?

    >> These seem like they would be common problems. Are there common
    >> solutions to them? Can anybody point me to a good reference for
    >> creating iterator interfaces?

    >
    > There are some pointers (so to speak) in "Effective STL" by Meyers,
    > and in "The C++ Standard Library" by Josuttis. Otherwise, look on
    > the web, search the archives of this newsgroup (and c.l.c++.moderated)
    > for more recommendations.


    Thanks, I'll take a look!

    ----Scott.
     
    Scott Gifford, Sep 5, 2007
    #3
  4. Re: Iterator implementation questions: copy constructor and postfix increment

    Scott Gifford wrote:
    > "Victor Bazarov" <> writes:
    >> Scott Gifford wrote:

    > [...]
    >>> I'm having a similar problem implementing postfix increment
    >>> (operator++(int)). I basically need to return a copy of the
    >>> iterator at the previous position in the database, but again I
    >>> can't copy the database cursor or construct a new cursor because of
    >>> driver limitations.

    >>
    >> Don't implement post-increment. At all. Use pre-increment.

    >
    > That's what I've done so far, but I was concerned that it might not
    > work with all of the standard algorithms without a post-increment
    > operator, mostly because the docs at SGI say that an input iterator
    > must implement post-increment:
    >
    > http://www.sgi.com/tech/stl/InputIterator.html
    >
    > Is it safe to assume that the standard algorithms that work with an
    > input iterator all use pre-increment so I don't have to worry about
    > this?


    No, it's not safe at all. If you want to conform (and use standard
    algorithms), then you're stuck with post-increment.

    Sorry, I didn't realise you needed to strictly conform to the input
    iterator requirements set by the Standard. You said "similar"...

    The idea is that your operation

    *it++

    should give you the entry to the database. You shouldn't concern
    yourself with copying iterators, only with comparing them and with
    dereferencing them. What if every increment causes a fetch from
    the database and stores the fetched value (I am not versed in the
    database terminology to explain correctly what I mean). Could there
    be a "pointer" or a "reference" to the stored record? Could you
    make a copy of the record?

    Essentially your task in to provide the functioning operator*. You
    need to make sure that *it and *it++ do the same thing (return the
    same value for the same 'it').

    There are probably folks here who deal with databases and who better
    understand your "cannot copy the cursor" statement (and AFAIUI, your
    idea of sharing the cursor between all iterators may be the right
    path to take, what if instead of tranfer of ownership you just count
    the references?). If not, maybe asking in the newsgroup for DB
    development could prove fruitful?

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Sep 5, 2007
    #4
  5. "Victor Bazarov" <> writes:

    > Scott Gifford wrote:


    [...]

    >> Is it safe to assume that the standard algorithms that work with an
    >> input iterator all use pre-increment so I don't have to worry about
    >> this?

    >
    > No, it's not safe at all. If you want to conform (and use standard
    > algorithms), then you're stuck with post-increment.
    >
    > Sorry, I didn't realise you needed to strictly conform to the input
    > iterator requirements set by the Standard. You said "similar"...


    Well, I don't necessarily, I'd just like to be aware of the downsides
    of straying from the Standard so I can weigh that against
    implementation time and decide whether it's worth figuring this out,
    and of course to include any caveats in the documentation.

    [...]

    > Could there be a "pointer" or a "reference" to the stored record?
    > Could you make a copy of the record?


    Yes, I'm already keeping a copy of the record, so it would not be that
    hard to implement a "degenerate" iterator that just had held one
    record, and all operations besides dereference failed.

    [...]

    > There are probably folks here who deal with databases and who better
    > understand your "cannot copy the cursor" statement (and AFAIUI, your
    > idea of sharing the cursor between all iterators may be the right
    > path to take, what if instead of tranfer of ownership you just count
    > the references?).


    That might be a good idea, or at least a good excuse to learn about
    shared_ptr.

    Thanks again for your help!

    ----Scott.
     
    Scott Gifford, Sep 5, 2007
    #5
  6. Scott Gifford

    James Kanze Guest

    Re: Iterator implementation questions: copy constructor and postfix increment

    On Sep 5, 10:32 pm, Scott Gifford <> wrote:
    > I'm working on an providing an iterator interface to a database. The
    > basic thing I'm trying to accomplish is to have my iterator read rows
    > from the database and return constructed objects. My goal here is to
    > abstract away the database part, so that in the future these objects
    > could be constructed from a data source on disk, across the network,
    > etc. The interface I'm after is similar to the standard iterator
    > interface for an "input iterator":


    > DataSource source;
    > for(DataSource::iterator iter = source.findAll(); iter++; iter != DataSource::end()) {
    > /* ... */
    > }


    > The problem I'm running into is that this idiom requires that the
    > iterator be constructed in findAll(), then copied into a local
    > variable with the copy constructor. My constructor creates a database
    > cursor object to read rows, so my copy constructor needs to make a
    > copy of that cursor. However my database driver won't allow me to
    > copy the cursor object, or even to create a new cursor object before
    > the first cursor is destroyed.


    In practice, this means that you can only implement an input
    iterator; even a forward iterator is impossible, since it would
    require being able to copy the iterator, advance the original,
    and then use the copy to continue from where the iterator was
    when it was copied.

    I'm not sure just how useful this is. The functionality of most
    of the algorithms which accept input iterators (and a lot of
    those which require a higher order of iterators as well) is
    subsumed by the data base.

    If you do want an STL-like iterator, I think your model should
    be istream_iterator. With a little work, you should even be
    able to make it a template:

    std::vector< RowType > dest(
    (DataBaseIterator< DataSource, RowType > iter( source )),
    (DataBaseIterator< DataSource, RowType >() ) ;

    > The solution I'm currently using is to store the cursor object in a
    > pointer, then have a copy constructor which takes over ownership of
    > the cursor, setting it to NULL in the copied object so it won't be
    > destoyed in the destructor. This basically works, but seems very
    > kludgey, and has some issues I'll address in another post,


    It's not really guaranteed to work, although it might most of
    the time. This is one case where reference counting is
    appropriate: your iterator just contains a boost::shared_ptr to
    the actual, non-copiable iterator (with the cursor, etc.), and
    forward the dereference and incrementation requests to it. For
    the comparison, a simple implementation trick here is to set the
    pointer to null when you reach the end (effectively destructing
    the real iterator). Then the operator== function becomes
    simply:

    bool
    DataBaseIterator::eek:perator==(
    DataBaseIterator const& other ) const
    {
    return myImpl == other.myImpl ;
    }

    > I'm having a similar problem implementing postfix increment
    > (operator++(int)). I basically need to return a copy of the iterator
    > at the previous position in the database, but again I can't copy the
    > database cursor or construct a new cursor because of driver
    > limitations.


    Using the above technique, you simply use the standard
    implementation for postfix increment.

    > These seem like they would be common problems. Are there common
    > solutions to them? Can anybody point me to a good reference for
    > creating iterator interfaces?


    You should probably have a look at the Boost iterator
    components. The STL iterator requirements can be tricky at
    times, and the Boost wrappers allow you to write simply the
    behavioral parts, and not worry about all of the boiler plate.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Sep 6, 2007
    #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. Aire
    Replies:
    3
    Views:
    468
    Mike Wahler
    Jan 25, 2004
  2. Replies:
    26
    Views:
    2,120
    Roland Pibinger
    Sep 1, 2006
  3. ali
    Replies:
    4
    Views:
    579
    David Harmon
    Mar 5, 2007
  4. Generic Usenet Account
    Replies:
    10
    Views:
    2,245
  5. cinsk
    Replies:
    35
    Views:
    2,613
    James Kanze
    Oct 11, 2010
Loading...

Share This Page