A question about iterators

[hagai]

Hi,
I am doing all sorts of stuff with iterators, I am passing an iterator
to the start and end to generic functions. All iterators are at least
bi-directional.
My question is how do I get an iterator to the item before the end? I
am currently doing it like this:

_It itOneBeforeEnd = itEnd;
--itOneBeforeEnd;

This is not really comfortable, is there another short way of doing
it?

Thanks,
Hagai.

 

[Andrew Koenig]

My question is how do I get an iterator to the item before the end? I
am currently doing it like this:

_It itOneBeforeEnd = itEnd;
--itOneBeforeEnd;

This is not really comfortable, is there another short way of doing
it?

The real question is why you want to do this. Note in particular that it
will fail if the iterator refers to an empty container.

If you are trying to iterate backward through a container, it is tempting to
do this:

It = itEnd;
--It;
while (It != itBegin) {
// do something with *It
--It;
}

but this technique doesn't work -- not only does it fail immediately if the
container is empty, but it ultimately attempts to decrement a value equal to
itBegin, which will also fail if itBegin refers to the first element of a
nonempty container.

Here's the right way to step backward through a container:

It = itEnd;
while (It != itBegin) {
--It;
// do something with *It
}

General rule: Decrement before you use the iterator; increment after you use
it.

 

[James Kanze]

The real question is why you want to do this. Note in
particular that it will fail if the iterator refers to an
empty container.

If you are trying to iterate backward through a container, it
is tempting to do this:

It = itEnd;
--It;
while (It != itBegin) {
// do something with *It
--It;
}

but this technique doesn't work -- not only does it fail
immediately if the container is empty, but it ultimately
attempts to decrement a value equal to itBegin, which will
also fail if itBegin refers to the first element of a nonempty
container.

How's that? I think rather that it will never "do something"
with the first element in the container (which is probably not
what is wanted).

Here's the right way to step backward through a container:

It = itEnd;
while (It != itBegin) {
--It;
// do something with *It
}

General rule: Decrement before you use the iterator; increment
after you use it.

Or use a reverse iterator.

 

[Juha Nieminen]

iterator const next_to_last = advance(a_collection.end(), -1);

What's wrong with: iterator next_to_last = --a_collection.end(); ?

Or is operator--() UB for temporaries?

 

[Kai-Uwe Bux]

What's wrong with: iterator next_to_last = --a_collection.end(); ?

The method end() does not return an lvalue, the code would not compile if
the iterator happens to be a pointer. Generally, I would avoid code that
renders T* a non-model for a iterator to T. This way, I keep my code more
generic. Of course, there is no real harm in cases where you know that the
iterator is of class type.

Note: I am not sure what the correct answer would be from a standard point
of view. As far as I can tell, all iterator types for standard containers
are implementation defined. So, at least in principle, they could be magic
types that happen to be non-class types as far as the compiler is
concerned. In that case, the above might not compile (and one would not be
able to inherit from iterator types either). The iterator requirements in
the standard are worded so that T* is a model. Thus, the above is not
required to compile.

Or is operator--() UB for temporaries?

No. If it does compile (i.e., if the iterator is of class type), it invokes
the operator--() member function on the temporary. There is no undefined
behavior here.



Best

Kai-Uwe Bux

 

[James Kanze]

The method end() does not return an lvalue, the code would not
compile if the iterator happens to be a pointer.

Or if it's a classe type with a global operator-- (probably a
friend).

Generally, I would avoid code that renders T* a non-model for
a iterator to T. This way, I keep my code more generic. Of
course, there is no real harm in cases where you know that the
iterator is of class type.

That's not true, since the standard doesn't require operator--
to be a member. (If it's not a member, it rather obviously
takes a non-const reference, so you can't bind a temporary to
it.)

In general, I would argue that in a quality implementation,
overloaded operators which require lvalues should be
non-members, taking a non-const reference, so that the
overloaded operator also requires an lvalue. In practice,
however:

I think that this point has only been realized very, very
recently. All of the implementations of the standard
library I know date to well before I realized it, in any
case. So they don't follow this rule, and you can't fault
them for not following a guideline which didn't exist when
they were written.

The most frequent user defined operator which requires an
lvalue is simple assignment. And you can't make that one a
non-member. Given that you're already forced to compromize
in the most frequent case, I'm not sure that it's worth the
bother in the other cases. If it's no more effort to make
the operator a global function (and in the case of compound
assignment operators, it's often significantly less effort),
go ahead and do it, but it's not worth any significant extra
effort.

Note: I am not sure what the correct answer would be from a
standard point of view. As far as I can tell, all iterator
types for standard containers are implementation defined.

Yep. All that is required is that they support both prefix and
postfix ++ (and -- if they are bidirectional) on an lvalue.