Simple iterator usage question...

[matthurne]

I am working through exercise 8-2 in Accelerated C++...I am
implementing the function equal(b, e, b2) where b is an iterator for
the first element in a container, e is an iterator pointing to one
past the last element in that same container, and b2 is an iterator
for the first element in the second container. Here's what I have:

template <class T>
bool equal(T begin, T end, T begin2) {
while (begin != end) {
if (*begin != *begin2) {
return false;
}
++begin;
++begin2;
}
return true;
}

This seems to work fine when the two containers are of the same size,
which is a precondition of the function. However, I noticed that the
equal method in the standard library returns false if two containers
of differing sizes are given to it. This makes complete sense, and I
want my function to behave that way as well. Right now it does
not...I keep getting back true if the containers have differing sizes.

So my questions then are: what happens when you increment an iterator
once it refers to one past the last element in the container? Does it
actually change or does it say put? If it changes, what happens when
you dereference an iterator that does not refer to a valid element?
And of course the big question: how can I write my function to behave
correctly and return false when two containers have different numbers
of elements?

Thanks!

 

[Victor Bazarov]

I am working through exercise 8-2 in Accelerated C++...I am
implementing the function equal(b, e, b2) where b is an iterator for
the first element in a container, e is an iterator pointing to one
past the last element in that same container, and b2 is an iterator
for the first element in the second container. Here's what I have:

template <class T>
bool equal(T begin, T end, T begin2) {
while (begin != end) {
if (*begin != *begin2) {
return false;
}
++begin;
++begin2;
}
return true;
}

This seems to work fine when the two containers are of the same size,
which is a precondition of the function. However, I noticed that the
equal method in the standard library returns false if two containers
of differing sizes are given to it. This makes complete sense, and I
want my function to behave that way as well. Right now it does
not...I keep getting back true if the containers have differing sizes.

So my questions then are: what happens when you increment an iterator
once it refers to one past the last element in the container?

You must not do that. If an iterator already refers to 'one past the
last', the result of incrementing it is undefined.

Does it
actually change or does it say put?
Undefined.

If it changes, what happens when
you dereference an iterator that does not refer to a valid element?

That's undefined too.

And of course the big question: how can I write my function to behave
correctly and return false when two containers have different numbers
of elements?

You need two pairs of iterators.

Victor

 

[matthurne]

You must not do that. If an iterator already refers to 'one past the
last', the result of incrementing it is undefined.


That's undefined too.


You need two pairs of iterators.

Victor

Ok...so if an iterator is one past the end of the container, what does
the program do when I try to increment it? You said I must not do so,
but what if I tried? Just curious about how this would likely be
handled. The same question applies to the other situations...my
program does not give me any kind of error or complaint if the second
container is smaller than the first, so if it actually iterates
through each element in the first container then ++begin2 is being
executed after the end of the second container as well. But the
program continues. Why? Does it just ignore the ++begin2?

You said I must have two pairs of iterators to have the function work
correctly. However, the library's implementation works correctly with
only a pair and the iterator for the beginning of the second
container. So then, there must be a way, yes?

And a more general iterator question. My college uses Java rather
than C++, so the first time I encountered iterators was this past
semester, in Java. Knowing how iterators work in Java has certainly
NOT helped me understand them in C++. Anyway, in Java an iterator is
one object whose position changes as it "moves over" the container.
One iterator, different states. How is this the same or different in
the standard library's iterators? The book I'm reading often says
things like "doing this will invalidate all the iterators after that
element in the container". For this to be the case, doesn't that mean
there has to be a separate iterator for each element in the container?
Wouldn't that be wasteful? With most other iterator operations, I
could see how it could work either the way I learned about them in
Java or by there being a separate iterator for each element. However,
that makes no sense...so I'm assuming that iterators in C++ work
internally in a similar way to those in Java, but I don't quite
understand how. And I really want to!

Thanks...

 

[Petec]

matthurne wrote:

Ok...so if an iterator is one past the end of the container, what does
the program do when I try to increment it? You said I must not do so,
but what if I tried? Just curious about how this would likely be
handled.

It's completly undefined; it could print "Hi there, something funny
happened" or it could format your hard drive. Usually it just does about the
same thing as dereferencing an invalid pointer.

The same question applies to the other situations...my
program does not give me any kind of error or complaint if the second
container is smaller than the first, so if it actually iterates
through each element in the first container then ++begin2 is being
executed after the end of the second container as well. But the
program continues. Why? Does it just ignore the ++begin2?

Nope, it's completly undefined what will happen.

Thanks...

- Pete

 

[Buster]

Ok...so if an iterator is one past the end of the container, what does
the program do when I try to increment it?

You must not do that.

You said I must not do so, but what if I tried?
Don't.

Just curious about how this would likely be handled.

An iterator can just be a pointer - in that case you already know what
happens when you increment it past the end. If a certain iterator type
is implemented as a user-defined type, however, it is impossible to
'handle it correctly' when a user increments a past-the-end iterator. If
you really want to know what it is that happens then, go into your
debugger and look - compare vector, list, deque and map iterators.

The same question applies to the other situations...my
program does not give me any kind of error or complaint if the second
container is smaller than the first, so if it actually iterates
through each element in the first container then ++begin2 is being
executed after the end of the second container as well. But the
program continues. Why? Does it just ignore the ++begin2?

It's not the compiler's job to check iterator validity for you. Imagine
if it were, and consider the following code:

#include <vector>

int g ();

void f ()
{
std::vector <int> v (10);
for (std::vector <int>::iterator iter (v.begin ());
iter != v.end ();
++ iter) // check the iterator is valid and not past-the-end first
{
* iter = g (); // check again
}
}

That's 20 totally redundant checks (40 pointer comparisons, if you're
lucky). Instead, you, the programmer, have to know when iterators are
going to be invalidated, and what to do about it.

You said I must have two pairs of iterators to have the function work
correctly. However, the library's implementation works correctly with
only a pair and the iterator for the beginning of the second
container. So then, there must be a way, yes?

No. For the standard library function template "equals" you specify two
ranges using three iterators, but both must be valid ranges, or the
behaviour is undefined.

And a more general iterator question. My college uses Java rather
than C++, so the first time I encountered iterators was this past
semester, in Java. Knowing how iterators work in Java has certainly
NOT helped me understand them in C++. Anyway, in Java an iterator is
one object whose position changes as it "moves over" the container.
One iterator, different states. How is this the same or different in
the standard library's iterators?

There is a big difference in philosophy between Java and C++. Part of
it is the emphasis on identity (and pass by reference) in Java versus
equality (and pass by value) in C++.

In Java, = means reseat (make this reference refer to that object), and
== means identical (these two references refer to the same object). In
C++, = and == mean whatever you want them to mean, but typically, =
means assign (modify this object to be "equal" to that one) and == means
equal (these two objects have interchangeable values). (I haven't said
what I mean by "value": that's what a programmer is saying when she
writes the = and == operators.)

So in Java you have one Iterator object, which changes to represent the
position in a sequence. In C++ there is still generally one main, named
iterator object that gets incremented and compared and so on -- it's
just that if the main iterator gets changed by (for example) making a
copy to pass it into a function, incrementing it inside the function,
copying the copy back into the return value, and finally copying the
return value back into the main iterator, then that's just as good as
incrementing the main iterator directly with ++, because the value ends
up the same.

The book I'm reading often says
things like "doing this will invalidate all the iterators after that
element in the container". For this to be the case, doesn't that mean
there has to be a separate iterator for each element in the container?

Um. No. It means that if there is an iterator which points to one of
those elements, then after "doing this", that iterator will be invalid.
This can be for several different reasons, for example:

If std::vector's iterators are implemented as pointers, and you cause a
reallocation by increasing the size of a vector, then the pointers point
to the previous location, not the new location, so they're no use.

The iterators for an std::deque can carry extra information about the
underlying block structure of the data, perhaps in the form of a pointer
into an array of pointers-to-blocks. If a new block is added because of
an insertion, that array may no longer be big enough and may have to be
reallocated. Then the pointer into the array will be invalid, so the
iterator can't be used.