Input bidirectional custom iterator

Mateusz �oskot

Hi,

I know iterator categories as presented
by many authors: Stroustrup, Josuttis and Koenig&Moo:

Input <---|
|<--- Forward <--- Bidirectional <--- Random
Output <---|
Is it a requirement that Forward, Bidirectional and Random iterators
provide operations of both categories: Input and Output?

Here are my objectives:
1. I'd like to create custom iterator of Input
category - read-only access.
2. I'd also like to define my read-only access iterator to act as
bidirectional or random access (my sequence is random access compatible).

Last question, is it a valid and STL-compatible iterator which:
- enables user to travers both directions or even to get random access
- provides *only* read-only access?

Simply, it's a little cofusing me that i.e. Bidirectional iterator
is always assumed to provide read and write access but it is not assumed
to provide only read-only access.

Thanks for giving me some light on this subject.
Cheers
--
Mateusz �oskot
http://mateusz.loskot.net

Jan 3 '06 #1

Cy Edmunds

"Mateusz Loskot" <se****@signature.net> wrote in message
news:dp**********@inews.gazeta.pl...

Hi,

I know iterator categories as presented
by many authors: Stroustrup, Josuttis and Koenig&Moo:

Input <---|
|<--- Forward <--- Bidirectional <--- Random
Output <---|
Is it a requirement that Forward, Bidirectional and Random iterators
provide operations of both categories: Input and Output?

Here are my objectives:
1. I'd like to create custom iterator of Input
category - read-only access.
2. I'd also like to define my read-only access iterator to act as
bidirectional or random access (my sequence is random access compatible).

Last question, is it a valid and STL-compatible iterator which:
- enables user to travers both directions or even to get random access
- provides *only* read-only access?

Simply, it's a little cofusing me that i.e. Bidirectional iterator
is always assumed to provide read and write access but it is not assumed
to provide only read-only access.

Thanks for giving me some light on this subject.
Cheers
--
Mateusz Loskot
http://mateusz.loskot.net

The key thing to understand about iterator classifications is that they do
not represent inheritance. Actually, making a set of iterators which derive
from one another is dubious practice except for deriving an iterator from a
const_iterator. Otherwise it is generally better to derive all iterators
from std::iterator so they can be tagged appropriately. Of course the usual
techniques of composition and/or derivation from a common base class may be
applicable. HTH

Cy

Jan 3 '06 #2

Mateusz £oskot

Cy Edmunds wrote:

"Mateusz Loskot" <se****@signature.net> wrote in message:

Last question, is it a valid and STL-compatible iterator which: -
enables user to travers both directions or even to get random
access - provides *only* read-only access?

Simply, it's a little cofusing me that i.e. Bidirectional iterator
is always assumed to provide read and write access but it is not
assumed to provide only read-only access.

Thanks for giving me some light on this subject. Cheers -- Mateusz
Loskot http://mateusz.loskot.net

The key thing to understand about iterator classifications is that
they do not represent inheritance.

I know that. I did say nothing about inheritance.
Actually, making a set of iterators which derive from one another is
dubious practice except for deriving an iterator from a
const_iterator.
or std::iterator
Otherwise it is generally better to derive all iterators from
std::iterator so they can be tagged appropriately.
Yes
Of course the usual techniques of composition and/or derivation from
a common base class may be applicable. HTH

Hmm, I understand everything what you wrote but it does not apply to my
question at all.

I'm not asking about inheritance and how to define hierarchies of
iterators. I'm asking relation [1] between categories of iterators and
if some special cases [2] of custom iterators can be considered as valid
in terms of STL (usage in STL algorithms).

[1] relation as described by Stroustrup but not as inheritance; Forward
iterator relates to Input and Output in terms of Forward includes all
operations of Input and Output iterators.

[2] e.g. is read-only Forward iterator valid in terms of STL. As
Stroustrup explained Forward iterator is a combination of operations
provided by Input and Output. What if my Forward iterator won't offer
operations Output iterator category?

Cheers
--
Mateusz £oskot
http://mateusz.loskot.net

Jan 3 '06 #3

Neil Cerutti

On 2006-01-03, Mateusz £oskot <se****@signature.net> wrote:

"Mateusz Loskot" <se****@signature.net> wrote in message:

I'm not asking about inheritance and how to define hierarchies
of iterators. I'm asking relation [1] between categories of
iterators and if some special cases [2] of custom iterators can
be considered as valid in terms of STL (usage in STL
algorithms).

Yes. vector<int>::const_iterator is equivalent to the random
access, read-only iterator you are considering.

--
Neil Cerutti

Jan 3 '06 #4

Mateusz �oskot

Neil Cerutti wrote:

On 2006-01-03, Mateusz £oskot <se****@signature.net> wrote:

"Mateusz Loskot" <se****@signature.net> wrote in message:

I'm not asking about inheritance and how to define hierarchies of
iterators. I'm asking relation [1] between categories of iterators
and if some special cases [2] of custom iterators can be
considered as valid in terms of STL (usage in STL algorithms).

Yes. vector<int>::const_iterator is equivalent to the random access,
read-only iterator you are considering.

const_iterator says only about how value_type is accessed
(dereferenced): const T* and const T& as opposite to T* and T& in
non-const iterator.

I'm talking about iterator categories in terms of operations they provide.

Obviously, my english may be a limitation here.

I'll try to explain it more clear.
Input iterator category is based on following set of operations
(from Josuttis' STL book):

*iter
++iter
iter++
iter1 == iter2
iter1 != iter2
TYPE(iter)

Output iterator category operations list:
*iter = value (assignment)
++iter
iter++
TYPE(iter)

Forward iterator category is a combination of both sets of operations above.

Now, I'm asking if I can define list of operations of my custom iterator
this way:

### Input ###
*iter
++iter
iter++
iter1 == iter2
iter1 != iter2
TYPE(iter)
### Bidirectional ###
--iter
iter++

As you can see, I've not applied set of operations from Output iterator
(or even from Forward iterator).
But Bidirectional iterator is assumed to provide those operations.
So, how about that?

Cheers
--
Mateusz �oskot
http://mateusz.loskot.net

Jan 3 '06 #5

Mateusz �oskot

Mateusz �oskot wrote:

### Bidirectional ###
--iter
iter++

Sorry, but here I did small typo:
Not iter++ but iter--, so:

### Bidirectional ###
--iter
iter--

Cheers
--
Mateusz �oskot
http://mateusz.loskot.net

Jan 3 '06 #6

Neil Cerutti

On 2006-01-03, Mateusz ?oskot <se****@signature.net> wrote:

Neil Cerutti wrote:

On 2006-01-03, Mateusz £oskot <se****@signature.net> wrote: I'm talking about iterator categories in terms of operations
they provide.

Obviously, my english may be a limitation here.

I'll try to explain it more clear.
Input iterator category is based on following set of operations
(from Josuttis' STL book):

*iter
++iter
iter++
iter1 == iter2
iter1 != iter2
TYPE(iter)

Output iterator category operations list:
*iter = value (assignment)
++iter
iter++
TYPE(iter)

Forward iterator category is a combination of both sets of
operations above.

Now, I'm asking if I can define list of operations of my custom
iterator this way:

### Input ###
*iter
++iter
iter++
iter1 == iter2
iter1 != iter2
TYPE(iter)
### Bidirectional ###
--iter
iter--

As you can see, I've not applied set of operations from Output
iterator (or even from Forward iterator). But Bidirectional
iterator is assumed to provide those operations. So, how about
that?

You need to support all the operations of Forward iterators in a
Bidirectional iterator, or it won't qualify as one, and might not
work with standard algorithms that require Bidirectional
iterators.

This quote is from the SGI docs:

The illustration below displays the five iterator categories
defined by the standard library, and shows their hierarchical
relationship. Because standard library iterator categories are
hierarchical, each category includes all the requirements of
the categories above it.

Requirements of Forward Iterators
<SNIP>

Requirements of Bidirectional Iterators
A bidirectional iterator must meet all the requirements for
forward iterators. In addition, the following expressions must
be valid
<SNIP>

If your design is the best type of iterator for your container,
then you'll have to tag it as an Input or Output iterator, which
happens to support a few more operations than normal. Clients
won't be able to use it as a Bidirectional iterator, despite that
it can go both ways.

--
Neil Cerutti

Jan 3 '06 #7

Mateusz �oskot

Neil Cerutti wrote:

On 2006-01-03, Mateusz ?oskot <se****@signature.net> wrote:

Neil Cerutti wrote:

On 2006-01-03, Mateusz £oskot <se****@signature.net> wrote:

I'm talking about iterator categories in terms of operations they
provide.

Obviously, my english may be a limitation here.

I'll try to explain it more clear. Input iterator category is based
on following set of operations (from Josuttis' STL book):

*iter ++iter iter++ iter1 == iter2 iter1 != iter2 TYPE(iter)

Output iterator category operations list: *iter = value
(assignment) ++iter iter++ TYPE(iter)

Forward iterator category is a combination of both sets of
operations above.

Now, I'm asking if I can define list of operations of my custom
iterator this way:

### Input ### *iter ++iter iter++ iter1 == iter2 iter1 != iter2
TYPE(iter) ### Bidirectional ### --iter iter--

As you can see, I've not applied set of operations from Output
iterator (or even from Forward iterator). But Bidirectional
iterator is assumed to provide those operations. So, how about
that?

You need to support all the operations of Forward iterators in a
Bidirectional iterator, or it won't qualify as one, and might not
work with standard algorithms that require Bidirectional iterators.

This quote is from the SGI docs:

[...]

That's asnwer I expected. I also know what SGI documentation says but
I just wanted to be sure and to get up-to-date answer.

Similarly, there is a definition of Sequence term in SGI docs.
In fact, (http://www.windevnet.com/documents/s...303a/0303a.htm)
user may define custom sequence which doesn't follow all SGI's Sequence
concept constraints but it still may be considered as "valid" sequence
in terms of STL iterators and algorithms (certainly, depending on
categories of those iterators).

Cheers
--
Mateusz �oskot
http://mateusz.loskot.net

Jan 3 '06 #8

Mateusz �oskot

Neil Cerutti wrote:

On 2006-01-03, Mateusz £oskot <se****@signature.net> wrote:

"Mateusz Loskot" <se****@signature.net> wrote in message:

I'm not asking about inheritance and how to define hierarchies
of iterators. I'm asking relation [1] between categories of
iterators and if some special cases [2] of custom iterators can
be considered as valid in terms of STL (usage in STL
algorithms).

Yes. vector<int>::const_iterator is equivalent to the random
access, read-only iterator you are considering.

One more note from my side, after I did some deeper analysis of
iterators for my better understanding of the subject.
T::const_iterator provides read-only access to single element of
sequence (container fits STL better).
But iterator itself may provide read-only, write-only or both accesses
to the whole sequence (e.g. traverse is immutable for sequence as a
whole, but re-order items, remove items is mutable).

There were lack of this understanding in my previous considerations.

Cheers
--
Mateusz �oskot
http://mateusz.loskot.net

Jan 4 '06 #9