By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
444,058 Members | 1,209 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 444,058 IT Pros & Developers. It's quick & easy.

How to find out a if an iterator is pointing to the very last (end) node?

P: n/a
How do I do that?

The thing is, the only information I have about the iterator is the
iterator itself. No container it is belonging to or anything. Like

template<Iteratorvoid totally_isolated(Iterator& it)
{
//how do I find out if it points to the end node?
}

Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.

Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).

Instead of retrieving the referenced value, I want the function to do
something 'special' (like printing a message to the screen) whenever
the iterator is pointing to the end node.

Is there any trick?

Oct 5 '06 #1
Share this Question
Share on Google+
16 Replies


P: n/a
ma*******@googlemail.com wrote:

What is the sound of one hand clapping?

A pair of iterators designates a sequence of values. A single iterator,
without context, tells you nothing.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Oct 5 '06 #2

P: n/a
A pair of iterators designates a sequence of values. A single iterator,
without context, tells you nothing.
Pete, even if I had a pair of iterators, it would be no use. Would be
still the same problem.

Oct 5 '06 #3

P: n/a
ma*******@googlemail.com wrote:
>A pair of iterators designates a sequence of values. A single iterator,
without context, tells you nothing.

Pete, even if I had a pair of iterators, it would be no use. Would be
still the same problem.
If the two iterators in the pair are equal, the sequence is empty, and
the first iterator does not point to a valid element. If the two are not
equal, the first iterator points to a valid element.

It sounds like the actual problem is that the code is using iterators in
non-idiomatic ways. Don't do that.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Oct 5 '06 #4

P: n/a
In article <11**********************@c28g2000cwb.googlegroups .com>,
ma*******@googlemail.com wrote:
How do I do that?

The thing is, the only information I have about the iterator is the
iterator itself. No container it is belonging to or anything. Like

template<Iteratorvoid totally_isolated(Iterator& it)
{
//how do I find out if it points to the end node?
}

Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.

Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).

Instead of retrieving the referenced value, I want the function to do
something 'special' (like printing a message to the screen) whenever
the iterator is pointing to the end node.

Is there any trick?
SOP is to simply declare such an error as undefined. IE: 'it' must be a
valid iterator in a range.

If you are using an implementation that has checked iterators, they
would be able to notify you of the problem, but that's not part of the
language.

The only other thing I can think to do off hand is change your function
to take a container and iterator instead of just an iterator.

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer*have anyone to discuss your doubts with,
nor any ability to discuss them.
Oct 5 '06 #5

P: n/a

<ma*******@googlemail.comwrote in message
news:11**********************@c28g2000cwb.googlegr oups.com...
How do I do that?

The thing is, the only information I have about the iterator is the
iterator itself. No container it is belonging to or anything. Like

template<Iteratorvoid totally_isolated(Iterator& it)
{
//how do I find out if it points to the end node?
}
What's the "end node"? When an iterator is equal to mycontainer.end(), it's
pointing one PAST the last valid item in mycontainer. And without
mycontainer, there's not way to test for equality with mycontainer.end(),
obviously.
>
Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.
Iterators are not generic. How would you define a function that took just
any old iterator?
Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).
You can't access what an iterator points to without knowing the iterator
type in the first place. What code do you have that lets you do that?
>
Instead of retrieving the referenced value, I want the function to do
something 'special' (like printing a message to the screen) whenever
the iterator is pointing to the end node.

Is there any trick?
Yes. Don't do that. :-)

What problem are you trying to solve, that you need to pass a "generic"
iterator to, and get what it's pointing to? Probably, you shouldn't be
calling this function in the first place, if you're past the end of the
container. Are you in a loop? What's the code look like that could end up
trying to use an iterator which is equal to .end()?

We might be able to help you find a solution that doesn't cause this problem
for you, if we knew what the real problem was you were trying to solve.
Some code might be nice. :-)

-Howard

Oct 5 '06 #6

P: n/a
"Howard" <al*****@hotmail.comwrote:
<ma*******@googlemail.comwrote:
Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.

Iterators are not generic. How would you define a function that took just
any old iterator?
Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).

You can't access what an iterator points to without knowing the iterator
type in the first place. What code do you have that lets you do that?
What? Excepting input and output iterators, if you write code that works
with a forward iterator, then it might as well be generic because all
other iterators will work.

To access what an iterator points to, you simply dereference it.

I'm afraid your point is lost on me... :-/

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer*have anyone to discuss your doubts with,
nor any ability to discuss them.
Oct 5 '06 #7

P: n/a

"Daniel T." <da******@earthlink.netwrote in message
news:da****************************@news.west.eart hlink.net...
"Howard" <al*****@hotmail.comwrote:
><ma*******@googlemail.comwrote:
Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.

Iterators are not generic. How would you define a function that took
just
any old iterator?
Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).

You can't access what an iterator points to without knowing the iterator
type in the first place. What code do you have that lets you do that?

What? Excepting input and output iterators, if you write code that works
with a forward iterator, then it might as well be generic because all
other iterators will work.

To access what an iterator points to, you simply dereference it.

I'm afraid your point is lost on me... :-/
The OP seemed to imply that any old iterator could be used somehow, which to
me meant any old iterator which points to any old object. I may have
misinterpreted the OP's meaning there. I was wondering how you could _use_
an iterator which referenced an unkown type. Since you're writing code in
that function which actually _does_ something with that object, somebody has
to know what type of object it is, right? (Even template variables
eventually execute type-specific code.)

And taking that thought further, since you know what type of object you're
using (or at least you have a template variable of a generic type), then
instead of passing an iterator to the function, the OP should pass the
object itself, and put any controlling code (such as checking against
..end()) in the calling code, not in that function.

In any case, removing the iterator from the function entirely makes the
problem of checking against .end() move to where it should be: in the hands
of someone who is using the actual container! (It also allows one to use
any kind of iterator, whether it's forward, reverse, random-access or
whatever, because the iterator isn't passed to the function in the first
place.)

-Howard
Oct 5 '06 #8

P: n/a
Thanks for your help, folks. I appreciate it.

Howard wrote:
What's the "end node"? When an iterator is equal to mycontainer.end(), it's
pointing one PAST the last valid item in mycontainer. And without
mycontainer, there's not way to test for equality with mycontainer.end(),
obviously.
Yeah, with "end node" I mean the one that equals the node of
mycontainer.end(). Unfortunately (or fortunately) it's not legal to
dereference the mycontainer.end() iterator.
Iterators are not generic. How would you define a function that took just
any old iterator?
Well, as long as I presume that any iterator has these operators:

operator*
operator->
operator++
operator--

everything should be fine. I don't make use of operatoror operator<,
as not every iterator type supports them.

But in this case (the totally_isolated() function case), I only make
use of the *-operator. I don't even need to know the underlying type
the iterator operates on (see below.)
You can't access what an iterator points to without knowing the iterator
type in the first place. What code do you have that lets you do that?
In fact, the totally_isolated() function is a member of a class to
which the iterator type is actually known. Here is the class I am
talking about:
http://groups.google.com/group/comp....browse_thread/
thread/d908a39b187d60e6/42558e69440c1da1?lnk=gst&rnum=1#42558e69440c1da1

I'll try to explain the current problem, so you don't have to waste
your time examining the crappy code.

These Abstract Iterator classes wrap iterators. Once an Abstract
Iterator has "swallowed" an iterator, no one but itself knows what the
type of the wrapped iterator is (e.g. vector<...>::iterator,
list<...>::iterator, ...).

When it comes to comparing two Abstract Iterators, I can only pass an
abstract iterator in the shape of a base pointer to another abstract
iterator, which then tests (via dynamic_cast) if the passed base
pointer is pointing to an abstract iterator with the same underlying
iterator type. Then they can be compared. But I don't like the use of
dynamic cast, because once the wrong abstract iterator is passed, an
exception is thrown.

So I have the abstract iterators return addresses of the objects their
wrapped iterators are pointing to so I can compare these addresses. The
functions that return the generic (void*) addresses are called
get_value_address(). It worked, until one of the wrapped iterators
happened to point to an end node. Here's the implementation of that
function that returns the generic address:

void const* get_value_address() const
{
return &*it;
}

That's why I need to dereference the iterator (actually, 'it' is a
member of the class rather than a parameter as shown in the
totally_isolated() function. Still, the whole Abstract Iterator concept
is ignorant about the iterator that is hold as a member. But it would
lose a lot of its elegance if I forced the user of the Abstract
Iterator to pass a reference to the container to an Abstract Iterator
object as well.

Anyway: I need to return the address of the object the 'it' iterator is
pointing to to compare two Abstract Iterators. (I am aware of other
ways to compare two Abstract Iterators, but they make use of
dynamic_cast, which is not so elegant. But I have to, if there's no way
to determine if 'it' is pointing to mycontainer.end().)

by and large, comparison is done this way:
// Instead of comparing two iterators the usual way like:
....
std::vector<int>::iterator i1 = vec.begin(), i2 = vec.begin();
i1 == i2;

// I have the iterators compared like this:

(&(*i1)) == (&(*i2))

But if either of these iterators happens to point to the end node, the
prorgam crashes.

I wished the C++ language stored "real" type information rather than
pseudo type_infos, which only contain lousy strings. So I could write

typeinfo iterator_type = typeid(std::vector<int>::iterator);
std::vector<int>::iterator& iter =
static_cast<iterator_type&>(disguised);

There would be no dynamic_cast whatsoever.

Oct 6 '06 #9

P: n/a
ma*******@googlemail.com wrote:
How do I do that?

The thing is, the only information I have about the iterator is the
iterator itself. No container it is belonging to or anything. Like

template<Iteratorvoid totally_isolated(Iterator& it)
{
//how do I find out if it points to the end node?
}
Ok, let's take the most basic iterator of all: int*.
It's the natural iterator for an int[10]. So, how do you know if an
int* points
to one after the int[10]?

HTH,
Michiel Salters

Oct 6 '06 #10

P: n/a

Mi*************@tomtom.com wrote:
Ok, let's take the most basic iterator of all: int*.
It's the natural iterator for an int[10]. So, how do you know if an
int* points
to one after the int[10]?
Luckily, I would not need to worry about that, as there's no "end node"
past int[9].

But vector<int>::iterators can indeed point to vector<int>::end(),
can't they?

Oct 6 '06 #11

P: n/a
Mi*************@tomtom.com wrote:
>Ok, let's take the most basic iterator of all: int*. It's the
natural iterator for an int[10]. So, how do you know if an int*
points to one after the int[10]?
ma*******@googlemail.com writes:
Luckily, I would not need to worry about that, as there's no "end node"
past int[9].
There is an "end node" after the last element of an array. I.e. a
pointer can point one past the end of an array.

Plus the problem is how function like `int foo(int*)` can tell if
passed pointer is valid.

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>--<jid:mina86*jabber.org>--ooO--(_)--Ooo--
Oct 6 '06 #12

P: n/a
Michal Nazarewicz wrote:
There is an "end node" after the last element of an array. I.e. a
pointer can point one past the end of an array.
There is? I didn't know. What does it look like? Isn't that the "begin
node" (index 0) of another int[] array? Then there's probably not just
one "end node", but many.

As far as I know, an int[10] array doesn't provide a special "end node"
like a vector does.

Oct 6 '06 #13

P: n/a
ma*******@googlemail.com wrote:
How do I do that?

The thing is, the only information I have about the iterator is the
iterator itself. No container it is belonging to or anything. Like

template<Iteratorvoid totally_isolated(Iterator& it)
{
//how do I find out if it points to the end node?
}

Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.

Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).

Instead of retrieving the referenced value, I want the function to do
something 'special' (like printing a message to the screen) whenever
the iterator is pointing to the end node.

Is there any trick?
No.

Refering to the end of a given container is not a property of an iterator in
isolation, it is a relation of between the iterator and the container.
Thus, your iterator wrapper needs to store at least some information about
the container as well (e.g., a reference to it). There is no other way
since an iterator simply does not store enough information to tell. Thus,
there is no way to extract this information from the iterator. The iterator
simply does not know.

I should be more precise: the standard does not require the iterator to know
whether it points to a valid element. Most implementations use this license
to implement iterators in the most efficient way. For debugging purposes,
some libraries provide range-checking iterator implementations. In that
case, the iterator does know: but it won't tell you through the standard
interface.

For instance, an iterator to std::vector<intcan refer to the last valid
element, i.e., it points to the slot before end(). If you call pop_back()
on that vector, all of a sudden the iterator is invalidated. However, the
iterator has no chance of telling you. Anything you do to this iterator is
now undefined behavior. So even is the iterator would know internally
(e.g., if it is a special range-checking iterator), there is no way to ask
it using the standard interface: any operation on this iterator is
undefined behavior (and for a range-checking implementation the the
standard response would be an exception or an abort through a failed
assertion). You are just out of luck.
Best

Kai-Uwe Bux
Oct 6 '06 #14

P: n/a
ma*******@googlemail.com wrote:
Michal Nazarewicz wrote:
>There is an "end node" after the last element of an array. I.e. a
pointer can point one past the end of an array.

There is? I didn't know. What does it look like? Isn't that the "begin
node" (index 0) of another int[] array? Then there's probably not just
one "end node", but many.

As far as I know, an int[10] array doesn't provide a special "end node"
like a vector does.
It does. Suppose you have

int* i = new int [10];

then, i+10 serves as the past end pointer. It is legal to use this pointer,
in a restricted way. However, it is undefined behavior to dereference it.
The situation is exactly like for the end() iterator in a container: you
can use it in comparisons and assignments, but you cannot dereference it.

BTW: it is illegal to use i-1 or i+11 regardless of whether you try to
dereference them.
Best

Kai-Uwe Bux
Oct 6 '06 #15

P: n/a
Thank you very much, Kai-Uwe Bux (and thanks to all the others, of
course).

Now I will rewrite my wrapper class and make use of dynamic_cast. This
will be ugly, but forcing the programer to pass a reference to the
container would be even more ugly.

Also, thanks for explaining that there acutally is an end node in
int[10].

So long.

Oct 6 '06 #16

P: n/a
<ma*******@googlemail.comwrote in message
news:11**********************@c28g2000cwb.googlegr oups.com...
How do I do that?

The thing is, the only information I have about the iterator is the
iterator itself. No container it is belonging to or anything. Like

template<Iteratorvoid totally_isolated(Iterator& it)
{
//how do I find out if it points to the end node?
}

Iterators like std::vector::iterator, std::list::iterator and so on are
usually passed to the totally_isolated() function. User defined
iterators may indeed be passed to the function as well.

Is there any safe and portable solution? This is my goal: I want to
access the referenced value via the *-operator. I can't do this if if
the iterator is pointing to the very last node (if I did, an exception
would be thrown or an assertion would fail).

Instead of retrieving the referenced value, I want the function to do
something 'special' (like printing a message to the screen) whenever
the iterator is pointing to the end node.

Is there any trick?
Simples way, IMO, is to also pass into the function the .end() of the
container, then you have something to compare against.

template<Iteratorvoid totally_isolated( Iterator& it, Iterator& end )
{
if ( it == end )
// we're at end
}
Oct 7 '06 #17

This discussion thread is closed

Replies have been disabled for this discussion.