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

[Cy Edmunds]

Re: Input bidirectional custom iterator

"Mateusz Loskot" <see.my@signatu re.net> wrote in message
news:dpeak3$pee $1@inews.gazeta .pl...[color=blue]
> 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[/color]

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

[Mateusz £oskot]

Re: Input bidirectional custom iterator

Cy Edmunds wrote:[color=blue]
> "Mateusz Loskot" <see.my@signatu re.net> wrote in message:[color=green]
>>
>> 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[/color]
>
>
> The key thing to understand about iterator classifications is that
> they do not represent inheritance.[/color]

I know that. I did say nothing about inheritance.
[color=blue]
> Actually, making a set of iterators which derive from one another is
> dubious practice except for deriving an iterator from a
> const_iterator.[/color]

or std::iterator
[color=blue]
> Otherwise it is generally better to derive all iterators from
> std::iterator so they can be tagged appropriately.[/color]

Yes
[color=blue]
> Of course the usual techniques of composition and/or derivation from
> a common base class may be applicable. HTH[/color]

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

[Neil Cerutti]

Re: Input bidirectional custom iterator

On 2006-01-03, Mateusz £oskot <see.my@signatu re.net> wrote:[color=blue][color=green]
>> "Mateusz Loskot" <see.my@signatu re.net> wrote in message:[/color]
> 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).[/color]

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

--
Neil Cerutti

[Mateusz Łoskot]

Re: Input bidirectional custom iterator

Neil Cerutti wrote:[color=blue]
> On 2006-01-03, Mateusz £oskot <see.my@signatu re.net> wrote:
>[color=green][color=darkred]
>>> "Mateusz Loskot" <see.my@signatu re.net> wrote in message:[/color]
>>
>> 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).[/color]
>
>
> Yes. vector<int>::co nst_iterator is equivalent to the random access,
> read-only iterator you are considering.
>[/color]

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

[Mateusz Łoskot]

Re: Input bidirectional custom iterator

Mateusz Łoskot wrote:[color=blue]
>
> ### Bidirectional ###
> --iter
> iter++[/color]

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

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

Cheers
--
Mateusz Łoskot

http://mateusz.loskot.net

[Neil Cerutti]

Re: Input bidirectional custom iterator

On 2006-01-03, Mateusz ?oskot <see.my@signatu re.net> wrote:[color=blue]
> Neil Cerutti wrote:[color=green]
>> On 2006-01-03, Mateusz £oskot <see.my@signatu re.net> wrote:[/color]
> 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:[/color]
[color=blue]
> ### 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?[/color]

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

[Mateusz Łoskot]

Re: Input bidirectional custom iterator

Neil Cerutti wrote:[color=blue]
> On 2006-01-03, Mateusz ?oskot <see.my@signatu re.net> wrote:[color=green]
>> Neil Cerutti wrote:[color=darkred]
>>> On 2006-01-03, Mateusz £oskot <see.my@signatu re.net> wrote:[/color]
>>
>> 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:[/color]
>
>[color=green]
>> ### 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?[/color]
>
>
> 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:
>
> [...][/color]

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

[Mateusz Łoskot]

Re: Input bidirectional custom iterator

Neil Cerutti wrote:[color=blue]
> On 2006-01-03, Mateusz £oskot <see.my@signatu re.net> wrote:
>[color=green][color=darkred]
>>>"Mateusz Loskot" <see.my@signatu re.net> wrote in message:[/color]
>>
>>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) .[/color]
>
>
> Yes. vector<int>::co nst_iterator is equivalent to the random
> access, read-only iterator you are considering.[/color]

One more note from my side, after I did some deeper analysis of
iterators for my better understanding of the subject.
T::const_iterat or 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