plain iterators and reverse iterators on vector

[subramanian100in]

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

 

[Victor Bazarov]

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

 

[Michael Doubez]

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).

 

[James Kanze]

Probably.

Certainly. It is required by the standard.

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]

On 6 août, 14:35, "(e-mail address removed), India"

[Re operator- on reverse iterators...]

<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.

 

[subramanian100in]

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

 

[Michael Doubez]

On 6 août, 14:35, "(e-mail address removed), India"

    [Re operator- on reverse iterators...]

<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

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

 

[Michael Doubez]

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 Doubez]

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.

 

[Victor Bazarov]

Certainly. It is required by the standard.



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

 

[James Kanze]

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>.