A question about iterators
hagai
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.
Pete Becker
No, that's it. If you had a random access iterator you could use itEnd
- 1, but for bidirectional iterators all you can do is increment and
decrement.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
Jeff Schwab
Well, you could get that onto one line with something like:
iterator const next_to_last = advance(a_collection.end(), -1);
std::advance is in <iterator>. A better alternative might be a little
utility function:
template<class Iterator>
Iterator prior(Iterator i) {
return --i;
}
iterator const next_to_last = prior(a_collection.end());
Of course, these both assume the collection is large enough for "one
before the end" to make sense. You might prefer a next_to_last function
template that accepts the collection, rather than just its end-iterator,
in order to detect out-of-range errors.
iterator const next_to_last = penultimate(a_collection);
One other thing you might want to consider is changing your naming
convention. Any identifier beginning with and underscore and a capital
letter is supposed to be reserved for use in system libraries. There
are other restrictions on leading underscores (and double underscores),
as well.
Andrew Koenig
news:6eef8841-03b9-45b6...@35g2000pry.googlegroups.com...
> 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
> "hagai" <hagai.s...@gmail.com> wrote in message
> news:6eef8841-03b9-45b6...@35g2000pry.googlegroups.com...
> > 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.
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.
--
James Kanze
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
> Jeff Schwab wrote:
>> iterator const next_to_last = advance(a_collection.end(), -1);
>
> 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
> Juha Nieminen wrote:
> > Jeff Schwab wrote:
> >> iterator const next_to_last = advance(a_collection.end(), -1);
> > 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.
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.
--
James Kanze