 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Andreas R.
Guest
|
 Posted: Fri Jan 21, 2005 10:24 am Post subject: Question about reverse iterators and its use of *(current-1) |
 |
|
On p. 557 of Bjarne Stroustrup's The C++ Programming Language is written,
that
"A reverse_iterator is implemented using an iterator called current. That
iterator can (only) point to the elements of its sequence plus its
one-past-the-end element. However, the reverse_iterator's one-past-the-end
elements is the original sequence's (inaccessible) one-before-the-beginning
element. Thus, to avoid access violations, current points to the element
after the one the reverse_iterator refers to."
I have problems to understand the reason following "Thus" (which then leads
to obscure implementation details, which must be thought about when you use
reverse iterators). Even if I had an iterator (pointer) pointing before the
first element of a container, how could this lead to a access violation, as
long as I do not dereference this iterator (pointer)?
(I wouldn't have problems to understand, if he just has stated that the
iterators are only supposed to be able to point to to [first, end] and
going to first-1 would possibly lead to problems with some iterator
implementations which e.g. would then through an exception, etc.
On the other hand, in this case I would ask if it wouldn't have been better
to avoid such restrictions for iterators.) (*)
Or does he mean by access violation the reason in (*) and not a
page/segmentation fault?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
msalters
Guest
|
| Posted: Sat Jan 22, 2005 5:01 am Post subject: Re: Question about reverse iterators and its use of *(curren |
|
|
Andreas R. wrote:
| Quote: | On p. 557 of Bjarne Stroustrup's The C++ Programming Language is
written,
that
"A reverse_iterator is implemented using an iterator called current.
That
iterator can (only) point to the elements of its sequence plus its
one-past-the-end element. However, the reverse_iterator's
one-past-the-end
elements is the original sequence's (inaccessible)
one-before-the-beginning
element. Thus, to avoid access violations, current points to the
element
after the one the reverse_iterator refers to."
I have problems to understand the reason following "Thus" (which then
leads
to obscure implementation details, which must be thought about when
you use
reverse iterators). Even if I had an iterator (pointer) pointing
before the
first element of a container, how could this lead to a access
violation, as
long as I do not dereference this iterator (pointer)?
|
Simple: you can create pointers to every element and immediately after,
but the compiler may cause an access violation when you create a
pointer
which points before the array. This can happen even if you do not
actually dereference that address.
Another case is with a linked list iterator. Such an iterator is simply
a wrapper around the pointer to the list node. When you decrement it,
you basically replace (*this) with *(this->prev). Now, the first node
has prev==0, and you see that an attempt to create an iterator pointing
before the first element of a linked list will fail.
| Quote: | (I wouldn't have problems to understand, if he just has stated that
the
iterators are only supposed to be able to point to to [first, end]
and
going to first-1 would possibly lead to problems with some iterator
implementations which e.g. would then through an exception, etc.
On the other hand, in this case I would ask if it wouldn't have been
better
to avoid such restrictions for iterators.) (*)
|
Yep, you're right. Iterators can point to [begin, end],
access [begin,end) and what happens beyond that is Unspeakably Bad,
in this group usually shortened to UB ;)
BTW, with linked list iterators you'll see that (iterator-1) is an
invalid expression. The reason is that you can't do random access
on an linked list. Only the pervious and next nodes are fast,
i.e. operator++ and operator--
HTH,
Michiel Salters
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Sat Jan 22, 2005 5:10 am Post subject: Re: Question about reverse iterators and its use of *(curren |
|
|
Andreas R. wrote:
| Quote: | On p. 557 of Bjarne Stroustrup's The C++ Programming Language
is written, that
"A reverse_iterator is implemented using an iterator called
current. That iterator can (only) point to the elements of its
sequence plus its one-past-the-end element. However, the
reverse_iterator's one-past-the-end elements is the original
sequence's (inaccessible) one-before-the-beginning
element. Thus, to avoid access violations, current points to
the element after the one the reverse_iterator refers to."
I have problems to understand the reason following "Thus"
(which then leads to obscure implementation details, which
must be thought about when you use reverse iterators). Even
if I had an iterator (pointer) pointing before the first
element of a container, how could this lead to a access
violation, as long as I do not dereference this iterator
(pointer)?
|
That depends on the iterator. Trying to position a pointer one
in front of the first element of a C style array is undefined
behavior. The STL adopted the same rule for its iterators.
| Quote: | (I wouldn't have problems to understand, if he just has stated
that the iterators are only supposed to be able to point to to
[first, end] and going to first-1 would possibly lead to
problems with some iterator implementations which e.g. would
then through an exception, etc. On the other hand, in this
case I would ask if it wouldn't have been better to avoid such
restrictions for iterators.) (*)
From what I understand, one of the goals in the design of the
STL is that a raw pointer into a C style array is a valid |
iterator.
It's a reasonable restriction for some user defined iterators as
well. Imagine a "safe" iterator into a vector:
| Quote: | template< typename T
class Iter
{
// ...
private:
std::vector
size_t myIndex ;
// @invariant myIndex <= myOwner->size()
} ;
|
The use of an unsigned type for the index is not without
consequences either.
--
James Kanze GABI Software http://www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thomas Maeder
Guest
|
| Posted: Sat Jan 22, 2005 5:36 am Post subject: Re: Question about reverse iterators and its use of *(curren |
|
|
"Andreas R." <newsgroupsREMOVE (AT) freenet (DOT) de> writes:
| Quote: | On p. 557 of Bjarne Stroustrup's The C++ Programming Language is written,
that
"A reverse_iterator is implemented using an iterator called current. That
iterator can (only) point to the elements of its sequence plus its
one-past-the-end element. However, the reverse_iterator's one-past-the-end
elements is the original sequence's (inaccessible) one-before-the-beginning
element. Thus, to avoid access violations, current points to the element
after the one the reverse_iterator refers to."
I have problems to understand the reason following "Thus" (which then leads
to obscure implementation details, which must be thought about when you use
reverse iterators). Even if I had an iterator (pointer) pointing before the
first element of a container, how could this lead to a access violation, as
long as I do not dereference this iterator (pointer)?
|
The ISO C and C++ Standards give us some guarantees.
Defined behavior for computing the address of one past the end of an
array is such a guarantee. Computing the address of one before the
start of an array isn't; this means that doing so has in undefined
behavior.
If this undefined behavior causes an access violation, or an E-mail
message, or nothing at all, isn't specified.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Bo Persson
Guest
|
| Posted: Sat Jan 22, 2005 11:34 am Post subject: Re: Question about reverse iterators and its use of *(curren |
|
|
"Andreas R." <newsgroupsREMOVE (AT) freenet (DOT) de> skrev i meddelandet
news:41f052b4$0$25910$9b622d9e (AT) news (DOT) freenet.de...
| Quote: | On p. 557 of Bjarne Stroustrup's The C++ Programming Language is
written,
that
"A reverse_iterator is implemented using an iterator called current.
That
iterator can (only) point to the elements of its sequence plus its
one-past-the-end element. However, the reverse_iterator's
one-past-the-end
elements is the original sequence's (inaccessible)
one-before-the-beginning
element. Thus, to avoid access violations, current points to the
element
after the one the reverse_iterator refers to."
I have problems to understand the reason following "Thus" (which then
leads
to obscure implementation details, which must be thought about when
you use
reverse iterators). Even if I had an iterator (pointer) pointing
before the
first element of a container, how could this lead to a access
violation, as
long as I do not dereference this iterator (pointer)?
(I wouldn't have problems to understand, if he just has stated that
the
iterators are only supposed to be able to point to to [first, end] and
going to first-1 would possibly lead to problems with some iterator
implementations which e.g. would then through an exception, etc.
On the other hand, in this case I would ask if it wouldn't have been
better
to avoid such restrictions for iterators.) (*)
Or does he mean by access violation the reason in (*) and not a
page/segmentation fault?
|
Is has to do with segmentation. On some architectures (like the 80268,
popular at the time this was written) you would always allocate a new
segment for each large object.
In that case first-1 might not exist!
Bo Persson
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dave Harris
Guest
|
| Posted: Sat Jan 22, 2005 6:41 pm Post subject: Re: Question about reverse iterators and its use of *(curren |
|
|
[email]newsgroupsREMOVE (AT) freenet (DOT) de[/email] (Andreas R.) wrote (abridged):
| Quote: | Even if I had an iterator (pointer) pointing before the
first element of a container, how could this lead to a access
violation, as long as I do not dereference this iterator (pointer)?
|
Some CPUs validate pointers when they are loaded into registers, rather
than waiting until they are dereferenced.
It's a hardware designer's choice. Perhaps because registers are rarely
loaded without being dereferenced at least once, and usually more than
once, so the validation gets done fewer times on average. Perhaps it's
just easier to lay out the chip that way. I don't know. It's just what
some real CPUs do and C++ has to deal with it.
| Quote: | (I wouldn't have problems to understand, if he just has stated that the
iterators are only supposed to be able to point to to [first, end] and
going to first-1 would possibly lead to problems with some iterator
implementations which e.g. would then through an exception, etc.
On the other hand, in this case I would ask if it wouldn't have been
better to avoid such restrictions for iterators.)
|
It turns out to be cheap to avoid the restriction at end, but not at
begin. To avoid it at end, you just need to allocate a byte or four which
the CPU will let you point to, and those bytes come just after the bytes
which are already allocated to the object, regardless of the size of the
object. You don't need to allocate another whole object.
To avoid it at begin, you would have to allocate enough space for a whole
object. Although in theory you only need a few bytes, those bytes have to
be located at the start of a nominal object, which means an object's
distance from the start of the array. You pretty much have to allocate all
the intervening bytes too. So you waste memory proportional to the size of
an object. If the object is large, the overhead becomes too great. (And
anyway the allocator might not know how big the object is.)
This asymmetry between restrictions at begin and end arises because
pointers point to the first bytes of objects rather than their last bytes.
-- Dave Harris, Nottingham, UK
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Andreas R.
Guest
|
| Posted: Sun Jan 23, 2005 2:48 am Post subject: Re: Question about reverse iterators and its use of *(curren |
|
|
Thanks to all for your answers.
msalters wrote:
[...]
| Quote: | Simple: you can create pointers to every element and immediately after,
but the compiler may cause an access violation when you create a
pointer
which points before the array. This can happen even if you do not
actually dereference that address.
Didn't think about the possibility that the compiler may cause such things |
in that context.
| Quote: | Another case is with a linked list iterator. Such an iterator is simply
a wrapper around the pointer to the list node. When you decrement it,
you basically replace (*this) with *(this->prev). Now, the first node
has prev==0, and you see that an attempt to create an iterator pointing
before the first element of a linked list will fail.
But this one is easy to work around. You just point to the "end" element |
(that you would need anyway) from your "begin" element. Just build it up
like a ring and you're fine :)
| Quote: |
(I wouldn't have problems to understand, if he just has stated that
the
iterators are only supposed to be able to point to to [first, end]
and
going to first-1 would possibly lead to problems with some iterator
implementations which e.g. would then through an exception, etc.
that was meant to be "throw" ^^^^^^^ |
[...]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
