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

pointer iterator interaction

P: n/a
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.. I thought of the following:

Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator;
modelIterator++;
return tmpEntry;
}
}

Unfortunately, this does not work, I get the error message:
error: cannot convert `
__gnu_cxx::__normal_iterator<Entry*, std::vector<Entry,
std::allocator<Entry> > >' to `Entry*' in assignment

I do not really understand this: As far as I understood it, an iterator
should be a pointer to the elements of the vector, and tmpEntry in the
mehtod above is nothing else than this..

How can I get a pointer to the element to which the iterator is
currently pointing?

Thanks a lot in advance
Tim

Jun 30 '06 #1
Share this Question
Share on Google+
18 Replies


P: n/a
silversurfer wrote:
Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator; [snipped] Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator; try:
tmpEntry = &(*modelIterator); modelIterator++;
return tmpEntry;
}
}
I do not really understand this: As far as I understood it, an iterator
should be a pointer to the elements of the vector, and tmpEntry in the
mehtod above is nothing else than this..

It behaves like one as in you can derference and increment etc.

Alan
Jun 30 '06 #2

P: n/a
silversurfer wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.. I thought of the following:

Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator;
modelIterator++;
return tmpEntry;
}
}

Unfortunately, this does not work, I get the error message:
error: cannot convert `
__gnu_cxx::__normal_iterator<Entry*, std::vector<Entry,
std::allocator<Entry> > >' to `Entry*' in assignment

I do not really understand this: As far as I understood it, an iterator
should be a pointer to the elements of the vector, and tmpEntry in the
mehtod above is nothing else than this..
No, it might be and in some implementation is is, but it doesn't have to be. How can I get a pointer to the element to which the iterator is
currently pointing?

&(*modelIterator);

should do it.

--
Ian Collins.
Jun 30 '06 #3

P: n/a
"silversurfer" <ki****@web.de> wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.
No you don't. Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.
I thought of the following:

Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator;
modelIterator++;
return tmpEntry;
}
}

Unfortunately, this does not work
Of course it doesn't work. The return type of your function is:

Entry*

but the type of tmpEntry is:

std::vector<Entry>::iterator

The two types are not even remotely similar.
I get the error message:
error: cannot convert `
__gnu_cxx::__normal_iterator<Entry*, std::vector<Entry,
std::allocator<Entry> > >' to `Entry*' in assignment
Yes, as I said, "not even remotely similar". You're asking the
compiler to convert apples to pipedreams. The compiler is
doubting your sanity, and rightly so.
I do not really understand this: As far as I understood it,
an iterator should be a pointer to the elements of the vector,
An iterator is not a pointer. It might (or might not) be
IMPLIMENTED in terms of a pointer, but unless you're writing
a compiler, that's none of your business.

An iterator can (and should) be USED LIKE a pointer, yes.
But it's not a pointer. It's an iterator. Think of it as
"one level higher of abstraction" compared to a pointer.
How can I get a pointer to the element to which the iterator
is currently pointing?


If you absolutely MUST do that, then you can, easily, like so:

Entry* DangerousPointer = &(*modelIterator);

But that is very dangerous. For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for.

Or use integer subscripting. With vectors, that's often easier than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.

--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net (put "[ciao]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/


Jun 30 '06 #4

P: n/a
silversurfer wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;
Pointers to objects in an array meet the definition of a random access
iterator. Vector iterators can be implemented as pointers, but they
are not necessarily done that way. Some compilers use pointers when
in optimized mode, but classes with more error checking implemented
for the various operators in debug mode. Unfortunately, this does not work, I get the error message:
error: cannot convert `
__gnu_cxx::__normal_iterator<Entry*, std::vector<Entry,
std::allocator<Entry> > >' to `Entry*' in assignment

I do not really understand this: As far as I understood it, an iterator
should be a pointer to the elements of the vector, and tmpEntry in the
mehtod above is nothing else than this..


Your understanding is WRONG. An iterator is an extraction of the
pointer concept. It may or may not actually be a pointer. It may
be a class. If you want to get the address of something an iterator
points at, you must dereference the iterator:
tmpEntry = &*modelIterator;
Note that the tmpEntry pointer now will NOT necessarily behave like
an iterator (it in fact must for vectors, but thats another story).
Jun 30 '06 #5

P: n/a
Thank you so much you guys,.. it seems that my understanding was a
little misleading (ok, I admit: it was simply wrong!)

Thanks Robbie for pointing out the fact about the re-structuring of
vectors, I did not think of this, before! Did I understand it right,
that using vector[] is safe in this respect? Why then bother and use
iterators at all? One could also run through the vector until size()
and return and access values by integer subscripting... (again, if I
understood this right).

One more thing: What was meant by "For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for."? Should I give back an
iterator-object instead of the object the iterator is pointing to?

Thanks once more,
Tim

Robbie Hatley schrieb:
"silversurfer" <ki****@web.de> wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.


No you don't. Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.
I thought of the following:

Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator;
modelIterator++;
return tmpEntry;
}
}

Unfortunately, this does not work


Of course it doesn't work. The return type of your function is:

Entry*

but the type of tmpEntry is:

std::vector<Entry>::iterator

The two types are not even remotely similar.
I get the error message:
error: cannot convert `
__gnu_cxx::__normal_iterator<Entry*, std::vector<Entry,
std::allocator<Entry> > >' to `Entry*' in assignment


Yes, as I said, "not even remotely similar". You're asking the
compiler to convert apples to pipedreams. The compiler is
doubting your sanity, and rightly so.
I do not really understand this: As far as I understood it,
an iterator should be a pointer to the elements of the vector,


An iterator is not a pointer. It might (or might not) be
IMPLIMENTED in terms of a pointer, but unless you're writing
a compiler, that's none of your business.

An iterator can (and should) be USED LIKE a pointer, yes.
But it's not a pointer. It's an iterator. Think of it as
"one level higher of abstraction" compared to a pointer.
How can I get a pointer to the element to which the iterator
is currently pointing?


If you absolutely MUST do that, then you can, easily, like so:

Entry* DangerousPointer = &(*modelIterator);

But that is very dangerous. For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for.

Or use integer subscripting. With vectors, that's often easier than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.

--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net (put "[ciao]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/


Jun 30 '06 #6

P: n/a
oh,.. I forgot:
Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.

The vector from which I am getting my elements shuffeled later on,.. is
it then even unsafer to use pointers to the elements in the vector or
should this not matter?

Thanks once more..
Tim

silversurfer schrieb:
Thank you so much you guys,.. it seems that my understanding was a
little misleading (ok, I admit: it was simply wrong!)

Thanks Robbie for pointing out the fact about the re-structuring of
vectors, I did not think of this, before! Did I understand it right,
that using vector[] is safe in this respect? Why then bother and use
iterators at all? One could also run through the vector until size()
and return and access values by integer subscripting... (again, if I
understood this right).

One more thing: What was meant by "For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for."? Should I give back an
iterator-object instead of the object the iterator is pointing to?

Thanks once more,
Tim

Robbie Hatley schrieb:
"silversurfer" <ki****@web.de> wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.


No you don't. Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.
I thought of the following:

Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator;
modelIterator++;
return tmpEntry;
}
}

Unfortunately, this does not work


Of course it doesn't work. The return type of your function is:

Entry*

but the type of tmpEntry is:

std::vector<Entry>::iterator

The two types are not even remotely similar.
I get the error message:
error: cannot convert `
__gnu_cxx::__normal_iterator<Entry*, std::vector<Entry,
std::allocator<Entry> > >' to `Entry*' in assignment


Yes, as I said, "not even remotely similar". You're asking the
compiler to convert apples to pipedreams. The compiler is
doubting your sanity, and rightly so.
I do not really understand this: As far as I understood it,
an iterator should be a pointer to the elements of the vector,


An iterator is not a pointer. It might (or might not) be
IMPLIMENTED in terms of a pointer, but unless you're writing
a compiler, that's none of your business.

An iterator can (and should) be USED LIKE a pointer, yes.
But it's not a pointer. It's an iterator. Think of it as
"one level higher of abstraction" compared to a pointer.
How can I get a pointer to the element to which the iterator
is currently pointing?


If you absolutely MUST do that, then you can, easily, like so:

Entry* DangerousPointer = &(*modelIterator);

But that is very dangerous. For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for.

Or use integer subscripting. With vectors, that's often easier than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.

--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net (put "[ciao]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/


Jun 30 '06 #7

P: n/a
Robbie Hatley wrote:
"silversurfer" <ki****@web.de> wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.
No you don't. Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.


The exact same is true for iterators into vectors.
I thought of the following:

Entry* MyObject::getNextEntry() {
Entry* tmpEntry;

if (modelIterator == models.end()) {
return NULL;
} else {
tmpEntry = modelIterator;
modelIterator++;
return tmpEntry;
}
}

Unfortunately, this does not work


Of course it doesn't work. The return type of your function is:

Entry*

but the type of tmpEntry is:

std::vector<Entry>::iterator

The two types are not even remotely similar.


They might actually be the same type, but it's implementation defined.
How can I get a pointer to the element to which the iterator
is currently pointing?


If you absolutely MUST do that, then you can, easily, like so:

Entry* DangerousPointer = &(*modelIterator);

But that is very dangerous. For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for.


In which way would an iterator be safer here?
Or use integer subscripting. With vectors, that's often easier than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.


Might be a bit slower though, but usually that can be ignored.

Jun 30 '06 #8

P: n/a

"silversurfer" <ki****@web.de> skrev i meddelandet
news:11*********************@y41g2000cwy.googlegro ups.com...
Thank you so much you guys,.. it seems that my understanding was a
little misleading (ok, I admit: it was simply wrong!)
A lot of people have been fooled by the fact that some popular
compilers used a pointer for vector::iterator. It works for
std::vector, but not for most other containers.

The thing is that a pointer is a kind of random-access iterator, but
not the other way round.

Thanks Robbie for pointing out the fact about the re-structuring of
vectors, I did not think of this, before! Did I understand it right,
that using vector[] is safe in this respect? Why then bother and use
iterators at all? One could also run through the vector until size()
and return and access values by integer subscripting... (again, if I
understood this right).
If you are using iterators, the code works even if the container is
not a std::vector. In fact, it works even if there is no container at
all - you just need a begin and an end iterator.

One more thing: What was meant by "For iterating through the
elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for."? Should I give back an
iterator-object instead of the object the iterator is pointing to?


It depends on what the return value is used for. What is the advantage
of having a raw pointer to the object? You access the value of the
object using either *p or *it.

Which one is the best? :-)
Bo Persson
> I thought of the following:
>
> Entry* MyObject::getNextEntry() {
> Entry* tmpEntry;
>
> if (modelIterator == models.end()) {
> return NULL;
> } else {
> tmpEntry = modelIterator;
> modelIterator++;
> return tmpEntry;
> }
> }
>
> Unfortunately, this does not work

Jun 30 '06 #9

P: n/a
"silversurfer" <ki****@web.de> wrote:
One more thing: What was meant by "For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for."? Should I give back an
iterator-object instead of the object the iterator is pointing to?


That depends much on what you're doing, and on whether this vector
is going to stay the same size always, or grow.

If the vector never changes size, it should occupy the same contiguous
block of memory always, and iterators to elements will always be valid.

But if the vector increases size, it may re-allocate itself, moving to
a new location in order to get a contiguous memory block of the required
size. According to the C++ standard, section 23.2.4.2, when a std::vector
reallocates itself, all references, pointers, and iterators referring to
the elements become invalid.

Also, if you insert or delete elements in the middle of a vector,
it will invalidate all pointers, iterators, and references to elements
after the point of insertion or deletion.

Therefore, it's best not to store copies of iterators to vector elements.
If you're going to pass a copy of an iterator from one function to another,
make sure you use it quickly before changes are made to the vector.

The usual way of iterating through a vector is like this:

std::vector<int> Splat;
// ... put a bunch of ints in Splat ...
std::vector<int>::iterator Iter;
for (Iter = Splat.begin(); Iter != Splat.end(); ++Iter)
{
(*Iter) += 17; // add 17 to each element of Splat
}

That way, Iter is always "fresh", unless you do something inside
the for loop which changes the size of Splat. So don't do that.
Instead, perform such operations outside of such "iterating" for
loops.

A simpler way of working with vectors, especially vectors with
fixed, known sizes, is by integer subscripting, like so:

std::vector<int> Splat (800); // make a vector of 800 ints
// ... put a bunch of ints in Splat ...
for (int i = 0; i < 800; ++i)
{
Splat[i] += 17; // Add 17 to each element of Splat.
}

If you find yourself changing the size of a vector a lot, or sorting
it, or inserting elements in the middle, then consider using a
std::list instead. Lists can't be subscripted like vectors, but
they are much more efficient for insertions and deletions, and
iterators (or pointers) to elements never become invalid unless
the element they point to is deleted.

Or, if you're adding/removing elements mostly at the ends, try a
std::deque instead.

--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net (put "[ciao]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/

Jun 30 '06 #10

P: n/a

"Rolf Magnus" <ra******@t-online.de> skrev i meddelandet
news:e8*************@news.t-online.com...
Robbie Hatley wrote:

Or use integer subscripting. With vectors, that's often easier
than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.


Might be a bit slower though, but usually that can be ignored.


Also, in the case where modifying the vector invalidates the
iterators, how do we know what index to use next. Inserting or
deleting elements before v[i] also invalidates the use of i !
Bo Persson
Jun 30 '06 #11

P: n/a
Robbie Hatley wrote:
Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.


So do iterators. In fact, the iterators for vectors are invalidated in
precisely the same situations as their corresponding pointers.
(This is obviously because the standard was designed so vector
iterators can be implemented using a pointer)

HTH,
Michiel Salters

Jun 30 '06 #12

P: n/a
Bo Persson wrote:
"Rolf Magnus" <ra******@t-online.de> skrev i meddelandet
news:e8*************@news.t-online.com...
Robbie Hatley wrote:

Or use integer subscripting. With vectors, that's often easier
than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.

Might be a bit slower though, but usually that can be ignored.


Also, in the case where modifying the vector invalidates the
iterators, how do we know what index to use next. Inserting or
deleting elements before v[i] also invalidates the use of i !


But the problem is that inserting elements *after* v[i] (the more common
case) can also force reallocation. By using indices, you are insulated,
as v[i] still is the i-th element of the vector in that situation.
Jun 30 '06 #13

P: n/a

"Bo Persson" <bo*@gmb.dk> wrote:
In the case where modifying the vector invalidates the
iterators, how do we know what index to use next?


The "erase" member function of STL squence containers
returns an iterator to the element to the right of the
one which was erased.

The "insert" member function of STL squence containers
returns an iterator to the element which was inserted.

In either case, just set your iterator to the return value
in order to resume iterating.

As for "index", the valid range of indexes is always from
0 to size-1. If you insert an element at index i, the new
element will also have index i. If you delete an element
at index i, the index numbers of all the elements to its
right will decrease by one, so that the old Container[i+1]
now becomes Container[i]. Like so:

std::vector<int> Blat (6);
Blat[0] = 17; Blat[1] = 87; Blat[2] = 54;
Blat[3] = 33; Blat[4] = 49; Blat[5] = 97;
std::vector<int>::iterator Iter = Blat.begin();
++Iter; ++Iter; // Iter now points to the "54"
Blat.erase(Iter); // Erases the "54"; Blat.size() is now 5
// Blat[0] is now 17 // (same as before)
// Blat[1] is now 87 // (same as before)
// Blat[2] is now 33 // was Blat[3]
// Blat[3] is now 49 // was Blat[4]
// Blat[4] is now 97 // was Blat[5]

Hope that helps.
--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net (put "[ciao]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/
--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net (put "[ciao]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/

Jun 30 '06 #14

P: n/a
silversurfer wrote:
oh,.. I forgot:
Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.


The vector from which I am getting my elements shuffeled later on,.. is
it then even unsafer to use pointers to the elements in the vector or
should this not matter?

Both pointers and iterators are invalid when the "elements are shuffled."
Jun 30 '06 #15

P: n/a
Robbie Hatley wrote:
"silversurfer" <ki****@web.de> wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.
No you don't. Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.


Your reasoning is flawed, insofar as it creates no distinction between
a pointer-to-element and an iterator. Both will be invalidated under
the same conditions.

Furthermore, there may very well be a valid reason to take the address
of an element of a container. For example, one might wish to call a
function which uses a pointer type as an output parameter. I would not
advocate writing such a function, but in practice one frequently has
unpleasant interfaces foisted.
Of course it doesn't work. The return type of your function is:

Entry*

but the type of tmpEntry is:

std::vector<Entry>::iterator

The two types are not even remotely similar.
That's a bit of an overstatement. They support a nearly identical set
of operations, and one is a conceptual generalization of the other.
What is the case is that they are not convertible to one another.
I do not really understand this: As far as I understood it,
an iterator should be a pointer to the elements of the vector,


An iterator is not a pointer. It might (or might not) be
IMPLIMENTED in terms of a pointer, but unless you're writing
a compiler, that's none of your business.


But stating that "iterators are generalized pointers," with appropriate
follow-up explanation, can be a helpful way of explaining what
iterators are, how they work, and why they exist.
An iterator can (and should) be USED LIKE a pointer, yes.
In most ways, but not all. For example, it cannot be used as the
lvalue of an assignment statement taking a pointer rvalue.
How can I get a pointer to the element to which the iterator
is currently pointing?


If you absolutely MUST do that, then you can, easily, like so:

Entry* DangerousPointer = &(*modelIterator);

But that is very dangerous.


In what sense? As I've mentioned, an iterator will be invalidated just
as often as a pointer-to-element (I can't say this with 100% certainty
without referring to the standard, but I believe this is at least the
case in practice). I suppose you could try to delete it or something,
but I'd say the dangerous part is trying to delete a pointer you don't
own, not having the pointer in the first place.

What I *would* say is that it's inelegant and unlikely to be necessary.
Inelegance is the pain we feel so that we can notice design problems,
and unnecessary code is a good way to ask for trouble.
For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for.
Yes. Better yet, use standard algorithms such as std::for_each() most
of the time. The benefits of iterators compound and multiply the more
widely they're used. For example, a function which populates a
container will be more efficient if it takes an output iterator as a
parameter, rather than returning the container by value. It's just
good to establish habits like that.
Or use integer subscripting. With vectors, that's often easier than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.


I disagree with this suggestion, for two reasons.

First, it is inadvisable to couple oneself to a more restrictive
interface than one needs. If all you're doing is iterating across the
elements of a container in forward order, then all you need is for the
container to be a model of Forward Sequence. If you write code that
implements that iteration in terms of integer subscripting, you place
the additional requirement that the container be a model of Random
Access Sequence. That means you can't change your mind and use a
different Forward Sequence without changing all your looping code.

Second, even though it's safe in the context of a canonically-written
for-loop, std::vector::operator[]() is unsafe in general because it
does not check the validity of the index. The checked version,
std::vector::at(), is safer but of course incurs additional runtime
overhead, as well as throwing an exception. Such is the cost of random
access. The problem with using it even in a loop that's safe is that
maybe some day someone moves that code around and it's not safe
anymore, or they see you doing it and copy what you're doing without
understanding how to make it safe.

So, maybe it's easier to write, but it introduces too many potential
maintenance complications to justify such trivial expediency.
Iterators are more explicit, less dangerous, and less restrictive.

Luke

Jul 1 '06 #16

P: n/a
well, now I am a little confused: First you write that iterators are "
invalidated just as often as a pointer-to-element", and in the end you
write that they are less dangerous. So what should I do now?

The case I am concerned with is the following:
I will be adding elements or changing element-contents with the
container, but not remove elements. I need to iterate through the
containerin many situations (search for elements,...) and I often need
to access elements directly. Thus, a container which allows fast access
to specific members and good iteration through all of them would be
nice.

Together with all this, a standatd element, which is added to the
vector looks like this:
struct Entry{
int index;
FeatureVector* value;
int classname;
};

I thought of taking a map for representing all this, taking index as
key and a pair of classname and featurevector as map-entry. What would
be your suggestion? Is using a map reasonable here or is a vector
sufficient?

Thanks once more
Tim

Luke Meyerwells schrieb:
Robbie Hatley wrote:
"silversurfer" <ki****@web.de> wrote:
Ok, this should be fairly easy for most of you (at least I hope so),
but not for me:

Let us say we have got the following elements:
std::vector<Entry> models; //Entry is a struct
std::vector<Entry>::iterator modelIterator;

In a method, I am currently writing, I need to get a pointer to an
entry in the vector.


No you don't. Don't use pointers to elements in Vectors.
Pointers to elements in vectors tend to get "stale", because
vectors reallocate themselves if they grow, so you'd eventually
end up dereferencing wild pointers and crashing your program.


Your reasoning is flawed, insofar as it creates no distinction between
a pointer-to-element and an iterator. Both will be invalidated under
the same conditions.

Furthermore, there may very well be a valid reason to take the address
of an element of a container. For example, one might wish to call a
function which uses a pointer type as an output parameter. I would not
advocate writing such a function, but in practice one frequently has
unpleasant interfaces foisted.
Of course it doesn't work. The return type of your function is:

Entry*

but the type of tmpEntry is:

std::vector<Entry>::iterator

The two types are not even remotely similar.


That's a bit of an overstatement. They support a nearly identical set
of operations, and one is a conceptual generalization of the other.
What is the case is that they are not convertible to one another.
I do not really understand this: As far as I understood it,
an iterator should be a pointer to the elements of the vector,


An iterator is not a pointer. It might (or might not) be
IMPLIMENTED in terms of a pointer, but unless you're writing
a compiler, that's none of your business.


But stating that "iterators are generalized pointers," with appropriate
follow-up explanation, can be a helpful way of explaining what
iterators are, how they work, and why they exist.
An iterator can (and should) be USED LIKE a pointer, yes.


In most ways, but not all. For example, it cannot be used as the
lvalue of an assignment statement taking a pointer rvalue.
How can I get a pointer to the element to which the iterator
is currently pointing?


If you absolutely MUST do that, then you can, easily, like so:

Entry* DangerousPointer = &(*modelIterator);

But that is very dangerous.


In what sense? As I've mentioned, an iterator will be invalidated just
as often as a pointer-to-element (I can't say this with 100% certainty
without referring to the standard, but I believe this is at least the
case in practice). I suppose you could try to delete it or something,
but I'd say the dangerous part is trying to delete a pointer you don't
own, not having the pointer in the first place.

What I *would* say is that it's inelegant and unlikely to be necessary.
Inelegance is the pain we feel so that we can notice design problems,
and unnecessary code is a good way to ask for trouble.
For iterating through the elements
of a Vector, use real iterators. You can use iterators for (almost)
anything you could use pointers for.


Yes. Better yet, use standard algorithms such as std::for_each() most
of the time. The benefits of iterators compound and multiply the more
widely they're used. For example, a function which populates a
container will be more efficient if it takes an output iterator as a
parameter, rather than returning the container by value. It's just
good to establish habits like that.
Or use integer subscripting. With vectors, that's often easier than
using iterators, and you don't need to worry about whether an old
iterator still points to something valid.


I disagree with this suggestion, for two reasons.

First, it is inadvisable to couple oneself to a more restrictive
interface than one needs. If all you're doing is iterating across the
elements of a container in forward order, then all you need is for the
container to be a model of Forward Sequence. If you write code that
implements that iteration in terms of integer subscripting, you place
the additional requirement that the container be a model of Random
Access Sequence. That means you can't change your mind and use a
different Forward Sequence without changing all your looping code.

Second, even though it's safe in the context of a canonically-written
for-loop, std::vector::operator[]() is unsafe in general because it
does not check the validity of the index. The checked version,
std::vector::at(), is safer but of course incurs additional runtime
overhead, as well as throwing an exception. Such is the cost of random
access. The problem with using it even in a loop that's safe is that
maybe some day someone moves that code around and it's not safe
anymore, or they see you doing it and copy what you're doing without
understanding how to make it safe.

So, maybe it's easier to write, but it introduces too many potential
maintenance complications to justify such trivial expediency.
Iterators are more explicit, less dangerous, and less restrictive.

Luke


Jul 1 '06 #17

P: n/a
silversurfer wrote:
well, now I am a little confused: First you write that iterators are "
invalidated just as often as a pointer-to-element", and in the end you
write that they are less dangerous. So what should I do now?
Please don't top-post. Also, my surname is "Meyers," not "Meyerwells,"
as you had it for some reason.

What I wrote (sorry, I'm not fixing your quoting for you) is that
iterators are less dangerous than numeric indices, not than
pointers-to-element. Totally different contexts, and I thought quite
clearly indicated.
The case I am concerned with is the following:
I will be adding elements or changing element-contents with the
container, but not remove elements.
Where are you inserting the elements? This has a lot to do with your
container choice. If you need to insert into the middle, or at the
beginning, vector is a poor choice. If you can do all your insertions
at the end, it may be a good fit.
I need to iterate through the
containerin many situations (search for elements,...)
Linear search is very expensive. If you're doing a lot of searching,
you should make sure to design in a way that allows logarithmic-time
lookup. This could mean using e.g. std::map, or it could mean
maintaining your container in sorted order. It depends on your needs.
and I often need
to access elements directly.
What do you mean by "directly?" Do you mean random access by numeric
index? You may find that it's difficult to find a container type which
supports random access *and* all the other stuff you want -- I suggest
re-examining your requirements.
Thus, a container which allows fast access
to specific members and good iteration through all of them would be
nice.
Fast access based on what, is the key. Any container you choose will
support iterating across all elements. At least, any STL container or
other container with similar design -- they all support begin() and
end().
Together with all this, a standatd element, which is added to the
vector looks like this:
struct Entry{
int index;
FeatureVector* value;
int classname;
};

I thought of taking a map for representing all this, taking index as
key and a pair of classname and featurevector as map-entry. What would
be your suggestion? Is using a map reasonable here or is a vector
sufficient?
Based on my understanding and inferences about your requirements, I
suspect std::map is a better fit in terms of efficiency, particularly
for the lookups.

It's kind of weird that "index" is part of your struct, by the way --
if that's the same as the position within the vector, you've got the
same data in two places, which is bad.

Luke

Jul 2 '06 #18

P: n/a
Luke Meyers wrote:
silversurfer wrote:
well, now I am a little confused: First you write that iterators are "
invalidated just as often as a pointer-to-element", and in the end you
write that they are less dangerous. So what should I do now?

Please don't top-post. Also, my surname is "Meyers," not "Meyerwells,"
as you had it for some reason.
SOrry, I will now post within the message, if that is better...
What I wrote (sorry, I'm not fixing your quoting for you) is that
iterators are less dangerous than numeric indices, not than
pointers-to-element. Totally different contexts, and I thought quite
clearly indicated.
The case I am concerned with is the following:
I will be adding elements or changing element-contents with the
container, but not remove elements.

Where are you inserting the elements? This has a lot to do with your
container choice. If you need to insert into the middle, or at the
beginning, vector is a poor choice. If you can do all your insertions
at the end, it may be a good fit.
I need to iterate through the
containerin many situations (search for elements,...)

Linear search is very expensive. If you're doing a lot of searching,
you should make sure to design in a way that allows logarithmic-time
lookup. This could mean using e.g. std::map, or it could mean
maintaining your container in sorted order. It depends on your needs.
and I often need
to access elements directly.

What do you mean by "directly?" Do you mean random access by numeric
index? You may find that it's difficult to find a container type which
supports random access *and* all the other stuff you want -- I suggest
re-examining your requirements.
Thus, a container which allows fast access
to specific members and good iteration through all of them would be
nice.

Fast access based on what, is the key. Any container you choose will
support iterating across all elements. At least, any STL container or
other container with similar design -- they all support begin() and
end().
Together with all this, a standatd element, which is added to the
vector looks like this:
struct Entry{
int index;
FeatureVector* value;
int classname;
};

I thought of taking a map for representing all this, taking index as
key and a pair of classname and featurevector as map-entry. What would
be your suggestion? Is using a map reasonable here or is a vector
sufficient?

Based on my understanding and inferences about your requirements, I
suspect std::map is a better fit in terms of efficiency, particularly
for the lookups.
Thanks, I will change my code accordingly.
It's kind of weird that "index" is part of your struct, by the way --
if that's the same as the position within the vector, you've got the
same data in two places, which is bad.
index is a class name I am needing for other purposes, so it is not the
position in the vector or thelike...
Luke
Thanks
Tim

Jul 3 '06 #19

This discussion thread is closed

Replies have been disabled for this discussion.