Iterator implementation questions: copy constructor and postfixincrement

[Scott Gifford]

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.

 

[Victor Bazarov]

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

 

[Scott Gifford]

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!

[...]

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?

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.

 

[Victor Bazarov]

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

 

[Scott Gifford]

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.

 

[James Kanze]

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 )),

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