Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Input bidirectional custom iterator

Reply
Thread Tools

Input bidirectional custom iterator

 
 
=?UTF-8?B?TWF0ZXVzeiDFgW9za290?=
Guest
Posts: n/a
 
      01-03-2006
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
 
Reply With Quote
 
 
 
 
Cy Edmunds
Guest
Posts: n/a
 
      01-03-2006
"Mateusz Loskot" <(E-Mail Removed)> wrote in message
news:dpeak3$pee$(E-Mail Removed)...
> 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


 
Reply With Quote
 
 
 
 
=?ISO-8859-2?Q?Mateusz_=A3oskot?=
Guest
Posts: n/a
 
      01-03-2006
Cy Edmunds wrote:
> "Mateusz Loskot" <(E-Mail Removed)> 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
 
Reply With Quote
 
Neil Cerutti
Guest
Posts: n/a
 
      01-03-2006
On 2006-01-03, Mateusz Łoskot <(E-Mail Removed)> wrote:
>> "Mateusz Loskot" <(E-Mail Removed)> 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
 
Reply With Quote
 
=?UTF-8?B?TWF0ZXVzeiDFgW9za290?=
Guest
Posts: n/a
 
      01-03-2006
Neil Cerutti wrote:
> On 2006-01-03, Mateusz ÂŁoskot <(E-Mail Removed)> wrote:
>
>>> "Mateusz Loskot" <(E-Mail Removed)> 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
 
Reply With Quote
 
=?UTF-8?B?TWF0ZXVzeiDFgW9za290?=
Guest
Posts: n/a
 
      01-03-2006
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
 
Reply With Quote
 
Neil Cerutti
Guest
Posts: n/a
 
      01-03-2006
On 2006-01-03, Mateusz ?oskot <(E-Mail Removed)> wrote:
> Neil Cerutti wrote:
>> On 2006-01-03, Mateusz Łoskot <(E-Mail Removed)> 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
 
Reply With Quote
 
=?UTF-8?B?TWF0ZXVzeiDFgW9za290?=
Guest
Posts: n/a
 
      01-03-2006
Neil Cerutti wrote:
> On 2006-01-03, Mateusz ?oskot <(E-Mail Removed)> wrote:
>> Neil Cerutti wrote:
>>> On 2006-01-03, Mateusz ÂŁoskot <(E-Mail Removed)> 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
 
Reply With Quote
 
=?UTF-8?B?TWF0ZXVzeiDFgW9za290?=
Guest
Posts: n/a
 
      01-04-2006
Neil Cerutti wrote:
> On 2006-01-03, Mateusz ÂŁoskot <(E-Mail Removed)> wrote:
>
>>>"Mateusz Loskot" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Use different input & output in bidirectional lines nicx82 VHDL 0 01-27-2010 09:41 AM
bidirectional connection between two bidirectional ports Manfred Balik VHDL 12 09-10-2006 08:53 PM
Difference between Java iterator and iterator in Gang of Four Hendrik Maryns Java 18 12-22-2005 05:14 AM
[ann] bidirectional iterator 0.8 Simon Strandgaard Ruby 2 06-02-2004 07:24 PM
Iterator doubts, Decision on Iterator usage greg C++ 6 07-17-2003 01:26 PM



Advertisments