plain iterators and reverse iterators on vector

Discussion in 'C++' started by subramanian100in@yahoo.com, India, Aug 6, 2009.

  1. , India

    , India Guest

    Consider the following program x.cpp:

    #include <cstdlib>
    #include <iostream>
    #include <vector>

    using namespace std;

    int main()
    {
    vector<int> c;

    for (int i = 0; i != 10; ++i)
    c.push_back(i);

    cout << c.end() - c.begin() << endl;
    cout << c.rend() - c.rbegin() << endl;

    return EXIT_SUCCESS;
    }

    I compiled with g++3.4.3 as
    g++ -std=c++98 -pedantic -Wall -Wextra x.cpp

    When I ran it, it produced the output
    10
    10

    The first 10 in the output is fine. It corresponds to c.end() - c.begin
    ().
    Shouldn't the second 10 in the output be -10 because I am using
    reverse iterators in calculating c.rend() - c.rbegin() ie isn't this
    expression equivalent to c.begin() - c.end() in which case -10 would
    be printed? Is my understanding wrong ?

    Is the difference operator-() between the RandomAccessIterators
    defined in <iterator> ? If so, how does the program compile even when
    I do not #include <iterator> ?

    Kindly clarify.

    Thanks
    V.Subramanian
    , India, Aug 6, 2009
    #1
    1. Advertising

  2. , India wrote:
    > Consider the following program x.cpp:
    >
    > #include <cstdlib>
    > #include <iostream>
    > #include <vector>
    >
    > using namespace std;
    >
    > int main()
    > {
    > vector<int> c;
    >
    > for (int i = 0; i != 10; ++i)
    > c.push_back(i);
    >
    > cout << c.end() - c.begin() << endl;
    > cout << c.rend() - c.rbegin() << endl;
    >
    > return EXIT_SUCCESS;
    > }
    >
    > I compiled with g++3.4.3 as
    > g++ -std=c++98 -pedantic -Wall -Wextra x.cpp
    >
    > When I ran it, it produced the output
    > 10
    > 10
    >
    > The first 10 in the output is fine. It corresponds to c.end() - c.begin
    > ().
    > Shouldn't the second 10 in the output be -10 because I am using
    > reverse iterators in calculating c.rend() - c.rbegin() ie isn't this
    > expression equivalent to c.begin() - c.end() in which case -10 would
    > be printed? Is my understanding wrong ?


    It would seem that you misunderstand the iterator operations.

    To move from a "start" iterator (whether it's returned by 'begin()' or
    'rbegin()') to the "finish" iterator (whether it's return by 'end()' or
    'rend()') you need to *increment* the iterator (use the ++ operator).
    That means that the "finish" iterator is "greater" than the "start".
    That, it turn means (for 'std::vector' only, since its iterators are
    random-access) that when you subtract "start" from "finish", you should
    get a positive value.

    > Is the difference operator-() between the RandomAccessIterators
    > defined in <iterator> ?


    Probably.

    > If so, how does the program compile even when
    > I do not #include <iterator> ?


    It must be included for you by <vector> or maybe <iostream>. Who knows?
    If you need to be explicit, include it yourself, there's no harm in that.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Aug 6, 2009
    #2
    1. Advertising

  3. On 6 août, 14:35, ", India"
    <> wrote:
    > Consider the following program x.cpp:
    >
    > #include <cstdlib>
    > #include <iostream>
    > #include <vector>
    >
    > using namespace std;
    >
    > int main()
    > {
    >         vector<int> c;
    >
    >         for (int i = 0; i != 10; ++i)
    >                 c.push_back(i);
    >
    >         cout << c.end() - c.begin() << endl;
    >         cout << c.rend() - c.rbegin() << endl;
    >
    >         return EXIT_SUCCESS;
    >
    > }
    >
    > I compiled with g++3.4.3 as
    > g++ -std=c++98 -pedantic -Wall -Wextra x.cpp
    >
    > When I ran it, it produced the output
    > 10
    > 10
    >
    > The first 10 in the output is fine. It corresponds to c.end() - c.begin
    > ().
    > Shouldn't the second 10 in the output be -10 because I am using
    > reverse iterators in calculating c.rend() - c.rbegin() ie isn't this
    > expression equivalent to c.begin() - c.end() in which case -10 would
    > be printed?


    It is not

    > Is my understanding wrong ?


    It is.

    operator-() computes the distance between two iterators not the
    difference between pointers.
    Example:
    distance = it2 - it1
    means that
    it2 == it1 + distance

    In the case of reverse iterator:
    distance = rend() - rbegin()
    rend() == rbegin() + size()

    > Is the difference operator-() between the RandomAccessIterators
    > defined in <iterator> ?


    RandomAccessIterators is not a type, it is a concept, each iterator
    type which are RandomAccessIterators will define their own operator-
    ().

    > If so, how does the program compile even when
    > I do not #include <iterator> ?


    <vector> may define it, you are guaranteed that it works without
    additional header (vector may include <iterator> and I guess it does
    for reverse_iterator).

    --
    Michael
    Michael Doubez, Aug 6, 2009
    #3
  4. , India

    James Kanze Guest

    On Aug 6, 3:01 pm, Victor Bazarov <> wrote:
    > , India wrote:
    > > Is the difference operator-() between the
    > > RandomAccessIterators defined in <iterator> ?


    > Probably.


    Certainly. It is required by the standard.

    > > If so, how does the program compile even when


    > > I do not #include <iterator> ?


    > It must be included for you by <vector> or maybe <iostream>.
    > Who knows? If you need to be explicit, include it yourself,
    > there's no harm in that.


    If you aren't explicit, it is formally undefined behavior.
    Given that vector can return a reverse iterator, however, and
    that reverse iterators are defined in <iterator>, it's hard to
    imagine how an implementation could implement <vector> without
    including <iterator>.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Aug 7, 2009
    #4
  5. , India

    James Kanze Guest

    On Aug 6, 3:02 pm, Michael Doubez <> wrote:
    > On 6 août, 14:35, ", India"


    [Re operator- on reverse iterators...]
    > > If so, how does the program compile even when
    > > I do not #include <iterator> ?


    > <vector> may define it, you are guaranteed that it works
    > without additional header (vector may include <iterator> and I
    > guess it does for reverse_iterator).


    That's an interesting question. The standard requires that the
    reverse iterator type for vector be std::reverse_iterator<
    std::vector<>::iterator >. A priori, I don't think it requires
    that the operators for std::reverse_iterator be made available;
    <vector> could use some sort of special forward declaration of
    the type, or some sort of compiler magic, to allow <vector> to
    compile without including <iterator>, and without making the
    subtraction operator available. In practice, that would mean a
    lot of work for not much benefit, and probably wouldn't be
    possible at all unless the compiler supported export, so I don't
    think you really have to worry about it. Formally, I think it's
    in some way "cleaner" to include <iterator>, since you are using
    types and operators from it, but it's not something I'd worry
    about if I forgot.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Aug 7, 2009
    #5
  6. , India

    , India Guest

    The following question is for learning purpose only.

    I am not sure if the following question is related to this newsgroup.
    If it is not related to this newsgroup, kindly reply as to which
    newsgroup I should post this question.

    This is regarding operator-() between vector<T> or deque<T> iterators:

    I want to understand how this difference operator is implemented.

    Consider the program x.cpp :

    #include <cstdlib>
    #include <iostream>
    #include <deque>
    #include <iterator>

    using namespace std;

    int main()
    {
    deque<int> c;

    for (int i = 0; i != 10; ++i)
    c.push_back(i);

    cout << c.end() - c.begin() << endl;

    cout << c.begin() - c.end() << endl;

    return EXIT_SUCCESS;
    }

    I compiled with g++3.4.3 as
    g++ -std=c++98 -pedantic -Wall -Wextra x.cpp

    When I ran it, it produced the output
    10
    -10

    I want to learn how the implementation of the operator-() function
    knows whether we pass 'start' iterator minus the 'finish' iterator(in
    which case it prints -10) or the 'finish' iterator minus the 'start'
    iterator(in which case it prints 10) - that is, how the operator-()
    function knows whether we pass 'finish' iterator argument followed by
    'start' iterator argument or we pass 'start' iterator argument
    followed by 'finish' iterator argument ?

    I am unable to locate the implementation of operator-() between
    iterators in g++3.4.3 which I am using. That is why I am posting this
    question.

    Kindly provide the information.

    Thanks
    V.Subramanian
    , India, Aug 7, 2009
    #6
  7. On 7 août, 10:16, James Kanze <> wrote:
    > On Aug 6, 3:02 pm, Michael Doubez <> wrote:
    >
    > > On 6 août, 14:35, ", India"

    >
    >     [Re operator- on reverse iterators...]
    >
    > > > If so, how does the program compile even when
    > > > I do not #include <iterator> ?

    > > <vector> may define it, you are guaranteed that it works
    > > without additional header (vector may include <iterator> and I
    > > guess it does for reverse_iterator).

    >
    > That's an interesting question.  The standard requires that the
    > reverse iterator type for vector be std::reverse_iterator<
    > std::vector<>::iterator >.  A priori, I don't think it requires
    > that the operators for std::reverse_iterator be made available;
    > <vector> could use some sort of special forward declaration of
    > the type, or some sort of compiler magic, to allow <vector> to
    > compile without including <iterator>, and without making the
    > subtraction operator available.


    True, it could simply make it an incomplete type until instantiation
    time (i.e. use of rbegin() or rend()).

    But I was rather thinking it could provide a specialisation of
    std::reverse_iterator<> for its iterator.

    > In practice, that would mean a
    > lot of work for not much benefit, and probably wouldn't be
    > possible at all unless the compiler supported export, so I don't
    > think you really have to worry about it.


    That depends, if it is legal on the architecture to address space
    before begin(), it could use a simpler form of reverse_iterator<>:
    rbegin as a pointer to last() and rend() a pointer to one before begin
    (with correct operations).

    And the standard requires §24.4.1.2/2 that global operator-() be
    defined for reverse_operator<> of RandomAccessIterator.

    > Formally, I think it's
    > in some way "cleaner" to include <iterator>, since you are using
    > types and operators from it, but it's not something I'd worry
    > about if I forgot.



    --
    Michael
    Michael Doubez, Aug 7, 2009
    #7
  8. On 7 août, 10:59, ", India"
    <> wrote:
    > The following question is for learning purpose only.

    [snip]
    > I want to learn how the implementation of the operator-() function
    > knows whether we pass 'start' iterator minus the 'finish' iterator(in
    > which case it prints -10) or the 'finish' iterator minus the 'start'
    > iterator(in which case it prints 10) - that is, how the operator-()
    > function knows whether we pass 'finish' iterator argument followed by
    > 'start' iterator argument or we pass 'start' iterator argument
    > followed by 'finish' iterator argument ?


    For vector, the iterators have underlying pointer representation. It
    makes a diff between the pointerss.

    > I am unable to locate the implementation of operator-() between
    > iterators in g++3.4.3 which I am using. That is why I am posting this
    > question.
    >
    > Kindly provide the information.


    Line 89 of bits/stl_iterator_base_funcs.h in the header files of c++
    for g++3.4.3:

    --
    Michael
    Michael Doubez, Aug 7, 2009
    #8
  9. On 7 août, 11:59, Michael Doubez <> wrote:
    > On 7 août, 10:16, James Kanze <> wrote:

    [snip]
    > > That's an interesting question.  The standard requires that the
    > > reverse iterator type for vector be std::reverse_iterator<
    > > std::vector<>::iterator >.  A priori, I don't think it requires
    > > that the operators for std::reverse_iterator be made available;
    > > <vector> could use some sort of special forward declaration of
    > > the type, or some sort of compiler magic, to allow <vector> to
    > > compile without including <iterator>, and without making the
    > > subtraction operator available.

    >
    > True, it could simply make it an incomplete type until instantiation
    > time (i.e. use of  rbegin() or rend()).


    Oups, I guess it would work on older compiler that doesn't check non
    dependant name at definition time.

    --
    Michael
    Michael Doubez, Aug 7, 2009
    #9
  10. James Kanze wrote:
    > On Aug 6, 3:01 pm, Victor Bazarov <> wrote:
    >> , India wrote:
    >>> Is the difference operator-() between the
    >>> RandomAccessIterators defined in <iterator> ?

    >
    >> Probably.

    >
    > Certainly. It is required by the standard.
    >
    >> > If so, how does the program compile even when

    >
    >>> I do not #include <iterator> ?

    >
    >> It must be included for you by <vector> or maybe <iostream>.
    >> Who knows? If you need to be explicit, include it yourself,
    >> there's no harm in that.

    >
    > If you aren't explicit, it is formally undefined behavior.
    > Given that vector can return a reverse iterator, however, and
    > that reverse iterators are defined in <iterator>, it's hard to
    > imagine how an implementation could implement <vector> without
    > including <iterator>.


    Hard to imagine? I would think the simplest explanation is that
    'reverse_iterator' is defined in some <reverse_iterator> header and both
    <vector> and <iterator> include it. There is no need for <vector> to
    include <iterator> if that's only to get 'reverse_iterator'...

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Aug 7, 2009
    #10
  11. , India

    James Kanze Guest

    On Aug 7, 12:30 pm, Michael Doubez <> wrote:
    > On 7 août, 11:59, Michael Doubez <> wrote:


    > > On 7 août, 10:16, James Kanze <> wrote:

    > [snip]
    > > > That's an interesting question. The standard requires
    > > > that the reverse iterator type for vector be
    > > > std::reverse_iterator< std::vector<>::iterator >. A
    > > > priori, I don't think it requires that the operators for
    > > > std::reverse_iterator be made available; <vector> could
    > > > use some sort of special forward declaration of the type,
    > > > or some sort of compiler magic, to allow <vector> to
    > > > compile without including <iterator>, and without making
    > > > the subtraction operator available.


    > > True, it could simply make it an incomplete type until
    > > instantiation time (i.e. use of rbegin() or rend()).


    > Oups, I guess it would work on older compiler that doesn't
    > check non dependant name at definition time.


    Or a compiler which implemented export, with a suitable
    incomplete definition in the <vector> header. Your suggestion
    concerning an explicit specialization, or rather a partitial
    specialization, of reverse_iterator for vector is interesting
    too, but I don't think it would change things. The key is
    export: if the implementation exports the class template vector,
    then it only requires an incomplete type in the header file, and
    can include <iterator> only in the implementation file, which
    isn't visible in the context of client code.)

    BTW: there was some discussion at one point of standardizing
    that some headers must include others---it's hard to imagine
    <vector> not including <memory>, for example, because it needs
    to know about the default allocator. I don't know if anything
    came of this discussion, but if so, I would rather expect that
    <vector> would be required to include <iterator>.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Aug 8, 2009
    #11
    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. dogbite
    Replies:
    4
    Views:
    682
    osmium
    Oct 10, 2003
  2. pmatos
    Replies:
    6
    Views:
    23,735
  3. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    478
    Kai-Uwe Bux
    May 8, 2005
  4. David Crawford

    Question on vector of vector iterators

    David Crawford, Dec 15, 2005, in forum: C++
    Replies:
    3
    Views:
    471
  5. Replies:
    8
    Views:
    1,896
    Csaba
    Feb 18, 2006
Loading...

Share This Page