Containers: The iterator object

[jacob navia]

Ian Collins a écrit :

I though returning NULL indicated that the iterator is at the end of the
container?

Actually it will call the currently defined error function with the
error "CONTAINER_ERROR_OBJECT_CHANGED". If that function returns (and
doesn't abort the program) the iterator returns NULL.

 

[Ian Collins]

Ian Collins a écrit :

Actually it will call the currently defined error function with the
error "CONTAINER_ERROR_OBJECT_CHANGED". If that function returns (and
doesn't abort the program) the iterator returns NULL.

Then I think that's wrong. It is one reason why I said it would be a
nightmare defining the operations that do and don't invalidate an iterator.

 

[jacob navia]

Ian Collins a écrit :

Then I think that's wrong.

Of course! I am ALWAYS wrong

But maybe you care to explain why?

Thanks

It is one reason why I said it would be a

nightmare defining the operations that do and don't invalidate an iterator.

It is very simple. ALL operations that modify the container other
than through the iterator invalidate all iterators to that container.

When you use an iterator over a container, you are allowed to

o Read anything even from different iterators.

o Write through a single iterator. THAT iterator (the one you use
to modify the container) is NOT invalidated. ALL others are.

This is different to C++ where the rules go for pages and pages.

 

[Eric Sosman]

[...] Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!

Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been inserted
or removed in front of or behind it.

Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.

 

[jacob navia]

Eric Sosman a écrit :

[...] Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!

Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been inserted
or removed in front of or behind it.

Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.

The rule is very easy

If you change the contents of a container, all iterators to it are invalid
and will call the error routine.

The only changes are allowed through the iterator you are using. You can delete
and replace items, or add before/after if it is a sequential container. If you
do this, any OTHER iterators are invalidatee of course, but not the iterator you use
to do the change.

 

[Andrew Poelstra]

Then I think that's wrong. It is one reason why I said it would be a
nightmare defining the operations that do and don't invalidate an iterator.

I think that as far as modifying lists while iterators are active
goes, you are simply Not Supposed To Do That. Jacob is trying to
make sure that if you do, something consistent will happen, even
if that's something potentially confusing.

 

[Eric Sosman]

Eric Sosman a écrit :

On 03/22/10 03:07 AM, Eric Sosman wrote:
[...] Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!

Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been inserted
or removed in front of or behind it.

Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.

The rule is very easy

... though the implementation may not be.

If you change the contents of a container, all iterators to it are invalid
and will call the error routine.

That's the easy part.

The only changes are allowed through the iterator you are using. You can
delete
and replace items, or add before/after if it is a sequential container.
If you
do this, any OTHER iterators are invalidatee of course, but not the
iterator you use
to do the change.

That's the hard part. FWIW, Java dodges the problem for hash
tables by (1) permitting only deletions during iteration, not
insertions, and (2) re-hashing only when a table grows, not when
items are removed. Thus, an iterator can be sure that the table
will not re-hash itself during iteration. If reorganizations could
occur, keeping the iteration sane would (it seems to me) be a good
deal more difficult.

 

[Ian Collins]

I think that as far as modifying lists while iterators are active
goes, you are simply Not Supposed To Do That. Jacob is trying to
make sure that if you do, something consistent will happen, even
if that's something potentially confusing.

Fair enough.

 

[Andrew Poelstra]

Fair enough.

Having said that, I just realized that since doing this is
(maybe) a programming error, there should be a flag in the
iterator that can be checked with assert().

 

[Ian Collins]

Ian Collins a écrit :

Of course! I am ALWAYS wrong

Why do you always spit the dummy when someone disagrees with you?

But maybe you care to explain why?

In this case, efficiency (remember this is C we a talking about). In
C++, the most commonly used container is std::vector. Anywhere you
would malloc an array of something in C, you can use std::vector in C++.
A vector<T> iterator can be as simple as a T*, so accessing items in a
vector through an iterator is just as efficient as accessing element in
an array through a pointer.

It is one reason why I said it would be a

It is very simple. ALL operations that modify the container other
than through the iterator invalidate all iterators to that container.

When you use an iterator over a container, you are allowed to

o Read anything even from different iterators.

o Write through a single iterator. THAT iterator (the one you use
to modify the container) is NOT invalidated. ALL others are.

This is different to C++ where the rules go for pages and pages.

As I've said many times, the complexity of a problem is invariant. The
choice is where to put it!

 

[Flash Gordon]

Ian Collins a écrit :

Of course! I am ALWAYS wrong

But maybe you care to explain why?

I can.

It is one reason why I said it would be a

It is very simple. ALL operations that modify the container other
than through the iterator invalidate all iterators to that container.

When you use an iterator over a container, you are allowed to

o Read anything even from different iterators.

o Write through a single iterator. THAT iterator (the one you use
to modify the container) is NOT invalidated. ALL others are.

This is different to C++ where the rules go for pages and pages.

I don't know C++ rules for this kind of thing, but I'll describe a real
situation I've got. In my case it is implemented using a database, but
it could equally well be implemented with a list...

I have one job which is repeatedly starts at the beginning of the list,
goes through it sometimes changing state fields on some of the records,
sometimes deleting them, sometimes adding new items to the *end* of the
list (i.e. not the current node the iterator is on.

There is a logically separate task which could be interspersed with the
first task either by being a separate thread, or being a function which
is called between steps through the list described above. This iterates
through a second list, and under some conditions added entries to the
end of the first list.

For this particular program, restarting the iterator on the first list
when items are added to the end of the list would be completely the
*wrong* thing to do (but it's what would happen with your described
implementation), and in some situations could actually cause an
effective lockup preventing things from being done where my customer
actually gets fined if the job isn't done.

The first list I talked about was a list of jobs to be run. Sometimes
the jobs won't complete (and might continue to not complete for a long
time). Sometimes the jobs decide to submit more jobs to be run later.
The second list is a list of jobs to be scheduled at defined time
intervals (anything from once a minute to once a day).

 

[Nick]

Eric Sosman a écrit :

On 03/22/10 03:07 AM, Eric Sosman wrote:
[...] Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!

Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been inserted
or removed in front of or behind it.

Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.

The rule is very easy

If you change the contents of a container, all iterators to it are invalid
and will call the error routine.

But as Flash pointed out, that stops you using your container as a queue
- which seems a bit of a drastic limitation. There will be things that
can always blow up iteration (as someone else pointed out, running in
arbitrary order through a hash table is one) but adding items to the end
of a simple linked-list shouldn't prevent me reading the next item. Nor
from deleting from the front of the list.

If this container is to replace all the messy add-hoc structures we
cobble together, it has to be able to do the common things we do that
way.

I think you need to rethink this. Simplicity is now getting in the way
of usefulness.

 

[jacob navia]

Nick a écrit :

Eric Sosman a écrit :

On 3/21/2010 5:01 PM, Ian Collins wrote:
On 03/22/10 03:07 AM, Eric Sosman wrote:
[...] Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!
Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been inserted
or removed in front of or behind it.
Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.

The rule is very easy

If you change the contents of a container, all iterators to it are invalid
and will call the error routine.

But as Flash pointed out, that stops you using your container as a queue
- which seems a bit of a drastic limitation.

You misunderstand completely. I have implemented already queues using a
list container.

You use the list directly, i.e. using
for (list_element=List->First; list_element != NULL;
list_element = list_element->Next ) {
// Use list_element->data here
}

You see?

You can use the components of the containers directly and iterate them
WITHOUT using any iterators at all.

Iterators are useful for MOST uses, but not for ALL uses. But you are
NOT limited to using iterators. You can use the containers directly.

There will be things that
can always blow up iteration (as someone else pointed out, running in
arbitrary order through a hash table is one) but adding items to the end
of a simple linked-list shouldn't prevent me reading the next item. Nor
from deleting from the front of the list.

That can be only done safely with lists. An abstract iterator through
ANY container can't do that. If not, you end up with MESSY rules like
in C++, where each container defines what is allowed and what is not
allowed. That is impossible to remember. Description of limitations for
the standard conntainers are QUITE lengthy.

If this container is to replace all the messy add-hoc structures we
cobble together, it has to be able to do the common things we do that
way.

It does that. Iterators though, are an abstraction that is useful in
MOST cases but not in ALL cases.

I think you need to rethink this. Simplicity is now getting in the way
of usefulness.

No. This design offers simplicity AND usefulness. You can use simple
iterators OR you can access a container directly.

 

[jacob navia]

Nick a écrit :

But as Flash pointed out, that stops you using your container as a queue
- which seems a bit of a drastic limitation.

In a std::deque, erasing and inserting objects in the middle will
invalidate all iterators and references. But inserting an element at
either end (through push_back(…) or push_front(…) or insert(c.end(),…)
or insert(c.begin(),…)) will not invalidate references, though it may
invalidate iterators.

Easy to remember isn't it?

And what is invalidated depends on the implementation. GREAT.
Now, remember that FOR EACH container you have to remember a similar
set of rules, regarding what is invalidated and what is not.

I think that simple rules are less error prone than baroque
specs. Obviously in special cases you will not use iterators
but use the container elements directly, iterating them for
a specific container. That allows you to erase at the same time
that you append, change whatever, you are on your own.

Yes, in C we can *improve* things to what already has been done.

jacob

 

[jacob navia]

Iterators Must Go
Andrei Alexandrescu

This slides set critics some of the misfeatures of the C++ iterators
implementation.
There are sevearl sites wth the video of this presentation, for
instance:

http://boostcon.blip.tv/


Another interesting one is:
Iterators: Signs of Weakness in Object-Oriented Languages
Henry G. Baker

I have read his prose for some years, but this paper is heavy.
Essentially it is a critique of C and C++ where you can't define
anonymous functions and you need iterators...

Another one is:
http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf
This is theory heavy paper... I find it difficult to read, but I
will try to finish it when I have some time.

 

[jacob navia]

Richard Heathfield a écrit :

Yes, if you bear in mind that the whole point of a deque is that it's a
double-ended queue. If you need to insert items in the middle, a deque
isn't the obvious data structure to choose.

Then, it is obvious that using an iterator in a dequeue is not a good
idea.

My point was precisely what you say:

If you want an object that makes ABSTRACTION from any particular
container implementation (an iterator) then you MUST make
compromises.

If you leave OPEN the possibility of using the container object directly
then you have the best of both worlds.

That is what I am proposing.

(1) SIMPLE rules for iterators.
(2) Specific container access for going through all items for a
specific container.

[snip]

Each data structure has its own strengths and weaknesses. The trick
is to choose one whose strengths you can exploit without being hamstrung
by the weaknesses of that choice. If those weaknesses get in the way,
the chances are good that you're using the wrong structure.

Exactly. Then, if you want to make an abstract object valid for ANY
container (an iterator) you can't address any SPECIFIC characteristic
of a container. The iterator I proposed has that characteristc:

(1) Any write to the object other than through the iterator invalidates
all iterators to that object.
(2) You have limited write access to the container, being able to modify
only the current object.

 

[Ian Collins]

Richard Heathfield a écrit :

Then, it is obvious that using an iterator in a dequeue is not a good
idea.

No it isn't. Iterators are the perfect tool for walking the container
(in either direction), of for passing to standard algorithms.

My point was precisely what you say:

If you want an object that makes ABSTRACTION from any particular
container implementation (an iterator) then you MUST make
compromises.
True.

If you leave OPEN the possibility of using the container object directly
then you have the best of both worlds.

Did anyone suggest otherwise?

That is what I am proposing.

(1) SIMPLE rules for iterators.
(2) Specific container access for going through all items for a
specific container.

There's nothing wrong with that, just don't let the rules get in the way
of efficiency.

Exactly. Then, if you want to make an abstract object valid for ANY
container (an iterator) you can't address any SPECIFIC characteristic
of a container. The iterator I proposed has that characteristc:

I think I see where you are coming from now. C++ iterators are specific
to each container, but the algorithms that work with them are generic.
You are proposing a single iterator type and algorithms that work with it?

(1) Any write to the object other than through the iterator invalidates
all iterators to that object.
(2) You have limited write access to the container, being able to modify
only the current object.

How does 2 relate to iterators, assuming they only reference on object
in a container?

 

[Andrew Poelstra]

Nick a écrit :

You misunderstand completely. I have implemented already queues using a
list container.

You use the list directly, i.e. using
for (list_element=List->First; list_element != NULL;
list_element = list_element->Next ) {
// Use list_element->data here
}

You see?

You can use the components of the containers directly and iterate them
WITHOUT using any iterators at all.

Iterators are useful for MOST uses, but not for ALL uses. But you are
NOT limited to using iterators. You can use the containers directly.

I agree. It's Bad Polymorphism if you have an iterator that does
two different things (ie, what you want OR destroy itself, other
iterators and the list) depending on the specific data structure
you obtained it from.

Now, given that if you use one iterator's list-manipulation
functions, it will invalidate all other iterators, I think
you do need to have a concept of a "const" iterator, which
you pass to algorithms that guarantee they won't screw you
around.

 

[Flash Gordon]

Nick a écrit :

Eric Sosman a écrit :
On 3/21/2010 5:01 PM, Ian Collins wrote:
On 03/22/10 03:07 AM, Eric Sosman wrote:
[...] Keep a "change counter"
in the collection, incremented each time something is inserted
or removed. Copy the counter into the iterator when the iterator
is created. Each time the iterator is used, compare its count
to the collection's count; a mismatch means Danger, Will Robinson!
Potential danger, but in many case the iterator would still be valid.
Attempting to define and support those cases would be a nightmare. For
example the iterator would still be valid after items have been
inserted
or removed in front of or behind it.
Perhaps I'm over-generalizing, but I assumed the notion of
"iterator" was intended to extend to all containers, not just
ordered containers. For example, if insertion or deletion causes
a hash table to reorganize while an iteration is in progress,
things get hairy.

The rule is very easy

If you change the contents of a container, all iterators to it are
invalid
and will call the error routine.

But as Flash pointed out, that stops you using your container as a queue
- which seems a bit of a drastic limitation.

You misunderstand completely. I have implemented already queues using a
list container.

You use the list directly, i.e. using
for (list_element=List->First; list_element != NULL;
list_element = list_element->Next ) {
// Use list_element->data here
}

You see?

You can use the components of the containers directly and iterate them
WITHOUT using any iterators at all.

If you can do that for any ordered container, then what need iterators?
If not, then for your containers to be generic you need to support the
kind of operation I was talking about.

Iterators are useful for MOST uses, but not for ALL uses. But you are
NOT limited to using iterators. You can use the containers directly.

So you get the overheads of generic containers with the work of using
the specific type of data structure you've selected directly. Sounds
like the worst of both worlds to me, at least in terms of the things I do.

Remember, trees are also often used for ordered data and have a nice
ordered access. If you think you can't do what I was talking about with
trees as well as linked lists, then consider that the database I'm
actually using for this uses btrees for the index, and I'm using an
iterator to traverse that tree whilst doing inserts and deletes.

That can be only done safely with lists.

No, it can be done with trees as well. I'll agree you can't do it with a
hash (not easily anyway).

An abstract iterator through
ANY container can't do that. If not, you end up with MESSY rules like
in C++, where each container defines what is allowed and what is not
allowed. That is impossible to remember. Description of limitations for
the standard conntainers are QUITE lengthy.

No, it's a simple rule you need (the ones in C++ might be complex). The
simple rule is that if it is an ordered container you can do it, if it
isn't you can't.

It does that. Iterators though, are an abstraction that is useful in
MOST cases but not in ALL cases.

Iterators are useful on trees as well as lists, and useful with the
ability to add/delete else where in the tree whilst iterating.

No. This design offers simplicity AND usefulness. You can use simple
iterators OR you can access a container directly.

They may be useful for some situations, but they are not generic enough
to be useful to me as a generic library, and not targeted enough for
when I don't want a generic library.

They may well be perfect for other people.

 

[ng2010]

In the last discussion we discussed how to do "GetNext" etc with
containers.

I think it is important that the user code stays as abstract as
possible, without getting into the specifics of any container, as Mr
Becarisse said (if I remember correctly).

Well, this could be done as follows. Please tell me what do you think.

Thanks

--------


All containers should be able to support the "GetNext" and the
"GetPrevious" functions.

That, of course, is false. It is only true to you, for you don't know any
better (apparently). So, before you start in on details, you better
discuss the alternative choices and why the above stated design is best.

(Aside: If this is a user group, it surely doesn't need first-time
library builders acting like they have definitive library designs.
"neophytes" WILL get sucked into the other neophyte's personal R&D, and
surely C is "well-evolved" and not a research project in real usage (?)).

(Aside 2: JN, if you think C is so great and good and readily usable, why
don't you go actually USE it instead of trying to extend/modify it? Your
actions say that C is not up to the task. And you are going on and on
about FOUNDATIONAL issues with the language. I was trying to be helpful
when I said don't waste your time.)