Input bidirectional custom iterator

Discussion in 'C++' started by =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=, Jan 3, 2006.

  1. 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
     
    =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=, Jan 3, 2006
    #1
    1. Advertising

  2. =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=

    Cy Edmunds Guest

    "Mateusz Loskot" <> wrote in message
    news:dpeak3$pee$...
    > 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
     
    Cy Edmunds, Jan 3, 2006
    #2
    1. Advertising

  3. Cy Edmunds wrote:
    > "Mateusz Loskot" <> 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
     
    =?ISO-8859-2?Q?Mateusz_=A3oskot?=, Jan 3, 2006
    #3
  4. =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=

    Neil Cerutti Guest

    On 2006-01-03, Mateusz £oskot <> wrote:
    >> "Mateusz Loskot" <> 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
     
    Neil Cerutti, Jan 3, 2006
    #4
  5. Neil Cerutti wrote:
    > On 2006-01-03, Mateusz £oskot <> wrote:
    >
    >>> "Mateusz Loskot" <> 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
     
    =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=, Jan 3, 2006
    #5
  6. 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
     
    =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=, Jan 3, 2006
    #6
  7. =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=

    Neil Cerutti Guest

    On 2006-01-03, Mateusz ?oskot <> wrote:
    > Neil Cerutti wrote:
    >> On 2006-01-03, Mateusz £oskot <> 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
     
    Neil Cerutti, Jan 3, 2006
    #7
  8. Neil Cerutti wrote:
    > On 2006-01-03, Mateusz ?oskot <> wrote:
    >> Neil Cerutti wrote:
    >>> On 2006-01-03, Mateusz £oskot <> 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=7545/win0303a/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
     
    =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=, Jan 3, 2006
    #8
  9. Neil Cerutti wrote:
    > On 2006-01-03, Mateusz £oskot <> wrote:
    >
    >>>"Mateusz Loskot" <> 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
     
    =?UTF-8?B?TWF0ZXVzeiDFgW9za290?=, Jan 4, 2006
    #9
    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. Hendrik Maryns
    Replies:
    18
    Views:
    1,452
  2. greg
    Replies:
    6
    Views:
    475
    Dietmar Kuehl
    Jul 17, 2003
  3. Manfred Balik
    Replies:
    12
    Views:
    6,672
    Marc Guardiani
    Sep 10, 2006
  4. nicx82
    Replies:
    0
    Views:
    521
    nicx82
    Jan 27, 2010
  5. Simon Strandgaard

    [ann] bidirectional iterator 0.8

    Simon Strandgaard, Jun 2, 2004, in forum: Ruby
    Replies:
    2
    Views:
    136
    Simon Strandgaard
    Jun 2, 2004
Loading...

Share This Page