Non-pointer iterators....

[fungus]

I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of problems cropping
up in the code thanks to this change.

a) With pointer-iterators you could set an iterator
to null to mark it as invalid, you can't do that
any more.

b) You can't use const_cast with iterators.

I can hack (b) by using "thing.begin()+n"
to make a new iterator but dealing with (a) is
a real pain. Unless there's a hack for this
I'm going to have to have a flag associated
with the iterator to mark it as valid/invalid.

So...what's the rationale behind changing from
simple pointers to fancy iterator objects? Was
there a good reason for doing this? To me it
seems that pointers are a much more natural
(and useful) choice.


Also, something I've been meaning to ask for
a while: Why is the default access for a class
"private"? Surely "public" makes much more sense.

--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[Greg]

I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of problems cropping
up in the code thanks to this change.

a) With pointer-iterators you could set an iterator
to null to mark it as invalid, you can't do that
any more.

Being able to assign NULL to an iterator - was merely a byproduct of
the iterator being implemented as a pointer. There is nothing in the
Standard that requires an iterator to support such assignments, so a
program should not rely on them.

b) You can't use const_cast with iterators.

I can hack (b) by using "thing.begin()+n"
to make a new iterator but dealing with (a) is
a real pain. Unless there's a hack for this
I'm going to have to have a flag associated
with the iterator to mark it as valid/invalid.

So...what's the rationale behind changing from
simple pointers to fancy iterator objects? Was
there a good reason for doing this? To me it
seems that pointers are a much more natural
(and useful) choice.

One advantage of a non-pointer implementation is to eliminate those
qualities of pointer behavior (such as assigning NULL to one) that are
not part of the concept of iterators and which an implementation is not
required to support in the first place. In reality, the Standard has
always specified iterators as "fancy" objects - objects whose class has
pointer-like semantics but not necessarily, a pointer-based
implementation.

Also, something I've been meaning to ask for
a while: Why is the default access for a class
"private"? Surely "public" makes much more sense.

Look at this way: if I came across some information about you - say in
the form of photos, videos, journal entries. And further assume that I
had no idea how you would like me to treat this information. So what
would you prefer that I do: a) place this information on a public
website, assuming that you wish this information to available to all or
b) not share the information with others under the assumption that you
wish to keep it private. I know that I would have a strong preference
for one of these options over the other - if the roles were reversed.
And apparently most class designers share that same preference.

Greg

 

[Alan Johnson]

I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of problems cropping
up in the code thanks to this change.

a) With pointer-iterators you could set an iterator
to null to mark it as invalid, you can't do that
any more.

An iterator by itself is largely useless. It needs to be paired with
another iterator to form a range. Then you can set the first iterator
to the second to indicate an empty range.

Alternatively, it could be paired with the container from which it
originates, and you could set it to the containers end() to indicate
invalid.

b) You can't use const_cast with iterators.

Can you give an example of when you might want to? If you need to
modify the value an iterator "points" to, then the iterator shouldn't
have been a const_iterator to begin with, so the correct solution is to
change its type.

I can hack (b) by using "thing.begin()+n"
to make a new iterator but dealing with (a) is
a real pain. Unless there's a hack for this
I'm going to have to have a flag associated
with the iterator to mark it as valid/invalid.

So...what's the rationale behind changing from
simple pointers to fancy iterator objects? Was
there a good reason for doing this? To me it
seems that pointers are a much more natural
(and useful) choice.

I don't know what rationale the developers of your platform had, but, as
you've seen, you should never rely on the underlying type of an
iterator. Each iterator concept has a very specific set of expressions
for which it has valid semantics. If you use them in any expression not
in that set, your program ceases to be valid C++, and may or may not
compile on a given platform.

If you don't have a copy of the standard handy, the following URL has a
good discussion of the five iterator concepts supported in C++:
http://www.sgi.com/tech/stl/Iterators.html

Also, something I've been meaning to ask for
a while: Why is the default access for a class
"private"? Surely "public" makes much more sense.

This sounds suspiciously trollish, but I'll answer anyway.

Object oriented programming is all about interfaces, not
implementations. How the data in an object is stored is an
implementation detail that clients of that object should not have to
worry about.

Consider the standard library containers, as an example. They all have
a size() method to tell you how many elements they contain. Is the size
stored internally as a variable, or is it computed when you ask for it?
The correct answer is, you don't know and shouldn't have to care.
With either implementation, the interface stays the same, and you could
even change the implementation without having to change client code.

But, if you REALLY want the default to be public, use a struct. Other
than default accessibility of their members, there is no difference
between a class and a struct.

 

[fungus]

Being able to assign NULL to an iterator - was merely a byproduct of
the iterator being implemented as a pointer.

I realize that...

One advantage of a non-pointer implementation is to eliminate those
qualities of pointer behavior (such as assigning NULL to one) that are
not part of the concept of iterators and which an implementation is not
required to support in the first place.

So it's the work of the Code-Nazis, no real reason?



--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[P.J. Plauger]

I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of problems cropping
up in the code thanks to this change.

a) With pointer-iterators you could set an iterator
to null to mark it as invalid, you can't do that
any more.

But you can set an iterator to its default constructed value,
which is invalid.

b) You can't use const_cast with iterators.

But you have both iterators and const_iterators for all
containers, and you can implicitly convert the former to
the latter.

I can hack (b) by using "thing.begin()+n"
to make a new iterator but dealing with (a) is
a real pain. Unless there's a hack for this
I'm going to have to have a flag associated
with the iterator to mark it as valid/invalid.

Luckily for you, that's probably not necessary.

So...what's the rationale behind changing from
simple pointers to fancy iterator objects? Was
there a good reason for doing this? To me it
seems that pointers are a much more natural
(and useful) choice.

With iterators implemented as classes, it's much easier
to provide additional safety checks, such as dereferencing
an invalid iterator, or incrementing it beyond its valid
range. Yet with modern compilers, normal operations on
iterators generate the same code as pointer arithmetic.

Also, something I've been meaning to ask for
a while: Why is the default access for a class
"private"? Surely "public" makes much more sense.

Only if your philosophy is "stay outa my way, unless I
*ask* for your help".

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[P.J. Plauger]

I realize that...


So it's the work of the Code-Nazis, no real reason?

You've been given several good reasons, but now you're being
deliberately provocative. I suggest you stick with C, or
perhaps go back to Dartmouth Basic, for raw unbridled power.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Rolf Magnus]

But you can set an iterator to its default constructed value,
which is invalid.

Hmm. You'd always have to explicictly default-initialize it then. After all,
if you only write:

std::vector<int>::iterator it;

and the iterator is just a pointer, its value is indeterminate and might
accidentally be a valid address of a member of the container.

But you have both iterators and const_iterators for all
containers, and you can implicitly convert the former to
the latter.

But not the other way round. After all, const_cast is there to cast _away_
constness.

Only if your philosophy is "stay outa my way, unless I
*ask* for your help".

Well, I agree with fungus here. For me, the "natural" order for a class
defintion is public members first, then protected, and at the end, the
private members. So generally, my classes always start with 'public:'.

 

[Rolf Magnus]

I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of problems cropping
up in the code thanks to this change.

It's rather thanks to you relying on implementation details that are not
required/defined by the C++ standard.

So...what's the rationale behind changing from
simple pointers to fancy iterator objects?

Probably so that it offers a clean iterator interface without the stuff that
isn't supposed to be part of the iterator concept.
Btw: Iterators for any other standard container have always been classes and
not raw pointers. Making vector iterators classes as well is more
consistent.

Was there a good reason for doing this? To me it
seems that pointers are a much more natural
(and useful) choice.

Well, if you want pointers, you can still use them. They are just not hidden
behind an iterator typedef in vector. If you want a pointer, ask for one,
not for an iterator.

Also, something I've been meaning to ask for
a while: Why is the default access for a class
"private"? Surely "public" makes much more sense.

Agreed. It seems many people see private as a more natural choice, because
class members should "by default" be private, and only those that are
needed from the outside should be exposed. I guess for a similar reason,
class inheritance is private by default too.

 

[fungus]

>This sounds suspiciously trollish, but I'll answer anyway.

Does it? It wasn't meant to be.

Object oriented programming is all about interfaces, not
implementations. How the data in an object is stored is an
implementation detail that clients of that object should
> not have to worry about.

I fully grok encapsulation, interfaces, etc.,
I was asking about the *default*.

Let me see if I can put it another way:

If I look through all my code I'll find classes
with both public and private contents, classes
with only public contents ("interfaces"), but
not one single class with *only* private contents.

Therefore it doesn't make sense to me to make
the default access "public". QED.

if you REALLY want the default to be public, use a struct. Other
than default accessibility of their members, there is no difference
between a class and a struct.

I know that, too... but as a former C programmer
it just feels wrong to put functions in a struct.
Silly, I know.


--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

So it's the work of the Code-Nazis, no real reason?

The work of the code-no-morons is to learn by reading and practicing, not by
insulting others to try to force him to write "for dummies" explanations
for you.

 

[Evan]

Can you give an example of when you might want to? If you need to
modify the value an iterator "points" to, then the iterator shouldn't
have been a const_iterator to begin with, so the correct solution is to
change its type.

There's an example in "A problem with typedef". The following is
invalid:
container.erase(citer);
because erase takes an iterator and citer is a const_iterator.

This is inconsistent with being able to delete a const pointer:
int const * p = new int;
delete p;

The only way around it that anyone has offered is to change to using
iterators from const_iterator and use std::distance to calculate how
far it is into the sequence then form a new iterator from that
distance, which is not only ugly but if you're using a list will turn
O(1) algorithms into O(n), O(n) into O(n^2), etc.

Evan

 

[Andrew Koenig]

a) With pointer-iterators you could set an iterator
to null to mark it as invalid, you can't do that
any more.

I can hack (b) by using "thing.begin()+n"
to make a new iterator but dealing with (a) is
a real pain. Unless there's a hack for this
I'm going to have to have a flag associated
with the iterator to mark it as valid/invalid.

Create a singleton container that contains a single object of the given type
and use an iterator that refers to that object as your null marker.

 

[Clark S. Cox III]

Create a singleton container that contains a single object of the given type
and use an iterator that refers to that object as your null marker.

No need for it to even contain a single object; just use that
container's "end" iterator.

 

[Clark S. Cox III]

I mentioned earlier to day that I was moving some code
from VC++6 to VC++2005 and having trouble with the
new iterators. There's all sorts of problems cropping
up in the code thanks to this change.
[snip]


So...what's the rationale behind changing from
simple pointers to fancy iterator objects?

The weren't really changed, iterators were always specified in terms of
the operations that one could perform on them; it just happens that the
operations that you can perform on pointers is a superset of those
operations.

Was
there a good reason for doing this? To me it
seems that pointers are a much more natural
(and useful) choice.

If iterators were all pointers, then how would someone implement the
iterators for std::set, std::map, std::list, etc.? Or how would someone
implement back_insert_iterator's or insert_iterators, etc.

Additionally, using objects as iterators provides many places to add
range-checking and other debugging code in debug builds, which can catch
invalid uses of iterators much earlier in the development cycle.

 

[fungus]

Create a singleton container that contains a single object of the given type
and use an iterator that refers to that object as your null marker.

I did that....It compiled fine but when I ran the
program I hit an assert in the STL - "incompatible
iterator" or something like that. Poking around the
source of the STL it seems like they check *everything"
these days.


--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[fungus]

No need for it to even contain a single object; just use that
container's "end" iterator.

I could do that with some of the code but
not all of it. Some of the code was working
on a subset of data so I don't know where
container.end() is.


--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[fungus]

You've been given several good reasons, but now you're being
deliberately provocative.

The point is that it broke code (and I suspect
not just mine). I'd expect more of a reason
than it's "more correct to do it that way".


--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[P.J. Plauger]

The point is that it broke code (and I suspect
not just mine). I'd expect more of a reason
than it's "more correct to do it that way".

About 40-odd years ago, Princeton University upgraded their
IBM 7090 to an IBM 7094, which added a divide-check trap.
Where the 7090 treated a zero divide like division by 1.0,
the 7094 terminated execution. Within the first week of
turning on this feature, a significant fraction of all
Fortran programs regularly trapped out. Some of these had
been working for years and doing mildly important things
like plotting spacecraft trajectories and analyzing cancer
data.

By the second week, the community was unanimous in
demanding that the damned thing be turned off. They
*liked* the erroneous answers they had been getting.

My personal taste has drifted, over the decades, in the
direction of greater safety and reliability in writing
and running computer programs. YMMV.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Bo Persson]

The point is that it broke code (and I suspect
not just mine). I'd expect more of a reason
than it's "more correct to do it that way".

The code was broken all along, it just happened to work on one specific
implementation.

The standard allows a vector::iterator to be a pointer, but it does not
require it. Most other iterators cannot be pointers.


Henry Ford once thought all cars should be black (because it simplified his
Model T implementation). We shouldn't base our code on such an assumption
always being valid.


Bo Persson

 

[Rolf Magnus]

The point is that it broke code (and I suspect not just mine).

No, the code was already broken. I already told you: If you want something
that behaves like a pointer, then just use a pointer. If you use an
iterator, don't assume it offers anything else than the standard iterator
interface. Assumptions tend to lead to code that is slow, unportable or
plain incorrect.

I'd expect more of a reason than it's "more correct to do it that way".

You've already been told that it also allows better run-time checking (esp.
in debug builds), e.g. when trying to increment an iterator beyond the end
of the container or using an iterator with a container that it doesn't
belong to.