Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Iterators

By codemonkey_uk in Technology
Fri Mar 28, 2003 at 04:01:02 PM EST
Tags: Software (all tags)
Software

Iteration is a very simple concept, and yet it is a powerful one. It is a concept that I have become so accustomed to that I have on occasion taken it for granted. I had started to assume that it was something that everyone knew and understood. Recent events, however, have proved me wrong. The design and use of iterators are something that are not as simple as I had assumed they were.

The article that follows is a programming article. I will be mostly using the C++ language to put the theory into a practical context, but I also hope that the article will be accessible to those of you that are not familiar with programming.


Before I move on to iterators I need to go back a little bit. There is another, even more basic concept used by programmers, and that is the concept of the Object. Now, the idea of the object may seem obvious now, but for a long time programmers did all of their thinking in the solution domain. That is, they thought about programming mostly in terms of what computers did, and what computers do is mostly the manipulation of numbers. Numbers are moved around in the computers memory, and sometimes maths is done with them.

Thinking about programming like that is quite hard. It takes a long time to write software that way, especially when that program is supposed to be modelling real world concepts, like customer accounts, or employees, or windows and buttons on a screen.

So along comes abstraction, and the idea of an object. This isn't even limited to object-oriented programming. It's just the idea that the programmer gets to think in terms of concepts other than the ones that the computer works with directly. It's simple stuff once you know it. With an abstraction you don't need to know how to do something every time you want to do it, you just need to know its name, and its inputs.

For instance, to draw a line you just need to know what colour, and where the end points are. You don't need to know how the video memory is laid out anymore, or how the Bresenham algorithm works, because someone, maybe you, has already done that work. Better yet, this program that you are writing doesn't have to be written all over again when you move on to the new wiz-bang super fast hardware - the only bit that has to be rewritten is that line draw, because the interface to the abstraction doesn't have to change.

And that is where iterators come in. Once you have 'objects' (even if those objects are just numbers) you can have containers of objects. Everybody is familiar with the idea of a list. Well the main thing you do with a list is you look at the things in the list. A list is a collection of objects, and there are lots and lots of different ways of storing lists, or collections in a computers memory. You can store objects in arrays - that is all one after each other in a single block of memory. Or you can store them in an linked list - where each object is stored along with the location in memory of the next object (this location in memory thing is also an object, it is usually called a pointer). You can store objects in all sorts of different ways, and each way has it's own pros and cons.

Now, as I said the main thing you want to do with a list is look at the things in the list. In fact to do pretty much anything useful with a list you have to look at the things in it. The problem is unless you realise that you can create an abstraction that separates the idea of moving around a list from how the list is stored in memory you have to write a different version of that code for every type of list you want to do it to.

That is what an iterator is. An iterator is like a bookmark. It represents a location in a collection of objects. There are basically two things you can do with a bookmark, you read (or write on!) the page it marks the location of, and you can move it to a different page.

The very simplest type of iterator in C++ is a Forward Iterator. A forward iterator lets you get the object at that location in the list, and you can move to the next location in the list. Actually the simplest iterator is the Trivial Iterator, but the simplest useful iterator is the forward iterator. Then there is Bidirectional Iterator which does everything a forward iterator does, plus (wait for it!) it also let's you go backwards in the list. Last, but certainly not least there is the Random Access Iterator that does all the things the forward and bidirectional iterators do, but also lets you move forward and backwards in jumps of multiple locations - often much more efficiently then just saying "go next" or "go back" a whole bunch of times.

It's also worth pointing out that there is also the concept of an Input Iterator, which is like a forward iterator, but read only, and an Output Iterator, which is like a forward iterator, but write only.

The uniform interface the iterators in C++ use is modelled on the syntax that pointers use. Moving forward is done using the increment operator: "++", moving backward is done using the decrement operator: "--", and reading and/or writing to the object at that location, is done with the dereference operators "*" and "->". C++ uses "begin" and "end" markers, so that forward iteration starts with "begin", and increments (++) until the iterator is equal to the "end" marker.

Typically iteration looks something like this c-style pseudocode:

for( iterator = begin; iterator!=end; ++iterator ){
DoSomething( *iterator );
}
So if you had an array, in C or C++ this might written:
char alphabet[26+1] = "abcdefghijklmnopqrstuvwxyz";
char * begin = &alphabet[0];
char * end = begin+26;
for( char* i = begin; i!=end; ++i ){
DoSomething( *i );
}
If you wanted to iterate over the contents of an STL style container, you would use it's "begin" and "end" member functions.

The interface that is used for iterators in Java is different - Java doesn't have pointers, so there is nothing after which to model iterators.

And that is really all there is to it. As I said at the start, a basically simple concept, but now one that I hope that you can see the importance of. Oh yes, at the start I also said "Recent events, however, have proved me wrong.", so I'll close by telling you what prompted me to dedicate so many words to trying to communicate these ideas.

The first incident that got me thinking about iterators again was when I discovered that a certain case tool that will remain nameless comes with a code generator that lets you create iterators - except that the iterators it generates use a different interface than the "standard" interface I described. First of all, they don't use the "begin" and "end" model, and second of all, for reasons that escape me, they have to be incremented once to get to the first object in the container. I'd like to go on the record as saying: This is not how C++ iterators should be written. As I have said in this article, iterators in C++ should work like pointers.

The second incident was today. I was working on an animation system, and needed to generate some data from the transitions that were set up for blending between sequences. The animation data comes from a well known game engine, and I discovered the iterator that they had provided for a collection of objects I had to gather the data from would only return the object that is is pointing to if you move the iterator to it's next position. That is, the two most fundamental things that an iterator is supposed to do had been combined into a single operation, and could not be done separately.

How could this happen? How could these two mistakes be made? Should I assume the programmers were stupid? No! Of course not. The problem was that I was assuming that just because I knew about the concept, that didn't mean I could assume that everybody did. After all, if no one tells you these things, how can you know?

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o Iteration
o Bresenham algorithm
o containers
o linked list
o Forward Iterator
o Trivial Iterator
o Bidirectio nal Iterator
o Random Access Iterator
o Input Iterator
o Output Iterator
o pseudocode
o iterators in Java
o Also by codemonkey_uk


Display: Sort:
Iterators | 208 comments (122 topical, 86 editorial, 0 hidden)
suggestions... (4.00 / 1) (#3)
by pb on Thu Mar 27, 2003 at 07:09:37 PM EST

Perhaps you could add in a section of examples, like how to use the different types of iterators, how using an iterator differs from other traditional approaches for iterating through a data structure, or how to implement a simple iterator?

Also, see if you can condense every two or three paragraphs or so into one paragraph, and cut out the chatter. Or if you like the chatter, well, at least try to organize everything a bit more coherently.

Iterators are a very simple concept, and it shouldn't take very long to explain them; they iterate; they provide a means to traverse a data structure, to visit each of its members. More concrete analogies would be, say, if you had a list of people, or a stack of paper, or a map of 100 cities, and you wanted to go through each person in the list, each sheet in the stack, each city on the map... one at a time. That's it. Really. Oh, and maybe you can step backwards through the list too.

That is to say, I think the concept of the iterator far more intuitive than the arbitrary C++ sytax and methods involved in creating and using them. I love the STL in principle, but I hate using it; maybe if I had a really good reference, or if the syntax was shorter, less ugly, more consistent, or easier to remember, I'd use it more than I do.
---
"See what the drooling, ravening, flesh-eating hordes^W^W^W^WKuro5hin.org readers have to say."
-- pwhysall

Just a small note (4.83 / 6) (#5)
by jacob on Thu Mar 27, 2003 at 07:28:09 PM EST

because I'm happy to see a tech article in the queue:

Iterators are very much an artifact of the procedural world. In the world of functional programming, it's much more common to have functions that represent various kinds of iterations over a collection than it is to have a datum that represents a current place in the collection. map, for instance, takes a function and a list and produces a list containing the function applied to all the elements in the original list. For instance, in Haskell,

map (\x->x-1) [1,2,3,4,5]

produces

[0,1,2,3,4]
. Once I learned about map and its cousins, I was surprised how often the C++ iterator + for-loop combinations I used to write were really just map or something in disguise.

--
"it's not rocket science" right right insofar as rocket science is boring

--Iced_Up

look in <algorithm> (5.00 / 4) (#11)
by twistedfirestarter on Thu Mar 27, 2003 at 07:42:06 PM EST

particularly the for_each function. It will do exactly what you are talking about with a function object.

[ Parent ]
bind (5.00 / 1) (#160)
by ucblockhead on Sat Mar 29, 2003 at 10:11:42 AM EST

Unfortunately, the STL argument binding templates are crap, so <algorithm> is hard to use without resorting to third-party libraries like boost.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
.. parts of boost will become std this year [n/t] (5.00 / 1) (#178)
by jongleur on Sat Mar 29, 2003 at 05:03:16 PM EST


--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]
yes... (5.00 / 1) (#180)
by ucblockhead on Sat Mar 29, 2003 at 05:35:47 PM EST

I've been hearing that...which parts? I'd guess the smart pointers stuff and bind, right?
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
Yes (list inside) (5.00 / 1) (#208)
by jongleur on Thu Jul 10, 2003 at 02:15:17 AM EST

here
--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]
Lazy streams (5.00 / 4) (#24)
by Pseudonym on Thu Mar 27, 2003 at 09:57:24 PM EST

In the lazy functional world, you don't even need functions as iterators. Simply return a lazy stream and you're there.

To be fair, though, there is no free lunch. In return for easy iterators, declarative programmers need a number of design patterns and techniques, some of them quite ugly, to simulate global state for when you find you need that.



sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
[ Parent ]
Using iterators (4.00 / 2) (#16)
by smallstepforman on Thu Mar 27, 2003 at 08:19:30 PM EST

Until recently, I never had a need to use iterators, since all projects in the past were doable with linked lists and pointers. I never really understood why people to go through the overhead of setting up iterators to transverse lists.  The very last project I worked on needed to create a list of display objects, where each object could be of a seperate type (hence size difference).  Ofcourse, I could have solved the problem using good old fashioned pointers, but a better solution using polymorphism and iterators presented itself.  Needless to say, the display architecture ended up being quite elegent indeed, all thanks to the power of iterators and transversing a list of unique object types. I had one of those moments where the theory finally *clicked* in my head, you know, one of those "Aha" moments.

These days I'm probably overusing iterators.

Yes but (none / 0) (#141)
by x3nophil3 on Fri Mar 28, 2003 at 06:24:21 PM EST

You were using iterators all along!

Otherwise you would have had a very novel double-linked list implementation. Something had to store the position while you were traversing the list...

[ Parent ]

Not really (none / 0) (#170)
by greenrd on Sat Mar 29, 2003 at 02:53:48 PM EST

One wouldn't usually use iterator objects - i.e. encapsulated pieces of data with actual methods - without realising it.

You could say that the i in for(i=10;i-->0;) is an iterator... but then I'd have to disagree with your choice of words.


"Capitalism is the absurd belief that the worst of men, for the worst of reasons, will somehow work for the benefit of us all." -- John Maynard Keynes
[ Parent ]

Well you can disagree (none / 0) (#174)
by x3nophil3 on Sat Mar 29, 2003 at 03:50:12 PM EST

   The i in a for loop is imho certainly an iterator. STL iterators are often just pointers which I don't think of as being significantly different from an index (pointers can be derived from indexes, and vice versa).

   But it's a question of opinion, I suppose.

[ Parent ]

Recursion (none / 0) (#171)
by ucblockhead on Sat Mar 29, 2003 at 03:07:04 PM EST

NodeType* Search(Foo target) {
  if( Node->Data == target)
     return Node;
  else if( Node->Next != NULL )
    return Search(Node->Next);
  else
    return NULL;
}
Technically speaking, nothing stores the "current" location, at least not in a single place.

Not a good way to do things in imperitave languages, but common elsewhere.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Depends how you think about it (none / 0) (#175)
by x3nophil3 on Sat Mar 29, 2003 at 03:55:34 PM EST

Nothing is storing the current location within the scope of the high-level language. 'Something' is certainly storing the current location at the machine level, though ... the frame/base pointer.

I see your point tho'

[ Parent ]

Iterators are a step backwards (4.12 / 8) (#20)
by jjayson on Thu Mar 27, 2003 at 08:55:29 PM EST

APL (and Lisp to a lesser extent) solved this problem 50 years ago. Iterators are maddeningly low-level. More often than not, you wish to iterate over an entire collection. APL's solution is two fold. First, operators implicitly iterate over collections. "3+1 2 3", will produce "3+1 3+2 3+3." This is intuitive behavior and similar to Lisp's explicit use of map. Second, there are adverbs to change the way a function is applied to its operands. "func each 1 2 3" will produce "(func 1) (func 2) (func 3)." There are ways that generalize these techniques for more specific iteration constucts and across multiple operands. There are also adverbs in APL-like languages that do the same as accumulate/reduce in Lisp, collecting the returned results with a function. These constructs allow more power than iterators with less code and less oportunity for error.

Why have no mass-use languages picked up on these techniques? I think that part of the blame can fall on wanting to have very strong typing. This makes treating an array the same as scalar data different, even though the underlying nature of the problem doesn't change.
_______
Smile =)
* bt krav magas kitten THE FUCK UP
<bt> Eat Kung Jew, bitch.

I don't see what (none / 0) (#22)
by jacob on Thu Mar 27, 2003 at 09:47:42 PM EST

strong typing has to do with it. It doesn't seem to me that there's anything going on in what you're describing other than operator overloading, which isn't a trick at all to type-check. Unless there's some subtlety I'm missing?

--
"it's not rocket science" right right insofar as rocket science is boring

--Iced_Up

[ Parent ]
maybe (none / 0) (#25)
by jjayson on Thu Mar 27, 2003 at 10:01:44 PM EST

The trend to strong typing says that a collection should not be allowed to be used where an atomic datum is expected. This prevents things link implicit looping. It might be able to be solved with operator overloading, but that would require overloading each operator for each possible collection. It seems to be far cleaner to just put it in the language.

However, this implicit behavior is not nearly as useful when you cannot say when you want it to apply and generalize it to user-defined operators.
_______
Smile =)
* bt krav magas kitten THE FUCK UP
<bt> Eat Kung Jew, bitch.

[ Parent ]

I think (none / 0) (#28)
by jacob on Thu Mar 27, 2003 at 10:15:57 PM EST

you're confusing implementation with type-checking. I think if the type system had a rule that said:
  • (app EXPR1 EXPR2) is well-typed with type B if EXPR1 has type A -> B and EXPR2 has type A.
  • (app EXPR1 EXPR2) is well-typed with type (arrayof B) if EXPR1 has type A -> B and EXPR2 has type (arrayof A).
My comment about overloading just meant that I don't think this type-checking rule would be harder to implement than a type-checking rule that verified operators in the presence of overloading, not that this feature ought to be implemented by some mechanism that introduced implicit overloaded operators.


--
"it's not rocket science" right right insofar as rocket science is boring

--Iced_Up

[ Parent ]
I'm not just talking about arrays... (none / 0) (#32)
by jjayson on Thu Mar 27, 2003 at 11:48:07 PM EST

I'm talking about other collection types, too.
_______
Smile =)
* bt krav magas kitten THE FUCK UP
<bt> Eat Kung Jew, bitch.

[ Parent ]
still works. (none / 0) (#33)
by jacob on Fri Mar 28, 2003 at 12:12:14 AM EST

(app EXPR1 EXPR2) has type C(B) if EXPR1 has type A -> B and EXPR2 has type C(A) seems like it would do it, where C ranges over collection types (these could be built-in or user-definable, or both). It'd be reasonably fancy type-theory stuff to write a type-checker that inferred all this stuff automatically, but completely doable. (I'd bet that it'd be much easier if you were willing to have mandatory type annotations a la C++.)

This is all just talking about how you judge a program type-safe, of course. Actually implementing the desired semantics is a different problem (but I don't see any major problem there either). Seems to me the major problem with implementing this is just that most people would on the surface be hesitant to give certain datatypes magical semantics, but maybe in this case magical semantics are worthwhile.

--
"it's not rocket science" right right insofar as rocket science is boring

--Iced_Up

[ Parent ]

magic (none / 0) (#37)
by jjayson on Fri Mar 28, 2003 at 12:30:15 AM EST

Seems to me the major problem with implementing this is just that most people would on the surface be hesitant to give certain datatypes magical semantics, but maybe in this case magical semantics are worthwhile.
This is some of what I am talking about. Of course this is implementable, but the current attitudes are against treating collections as basic units to operator over. People want to be told when they pass an array to a function that only expects an atom. I see this as related to the push for strong typing in this way. It isn't so much the typing mechanism, but the attitudes and expectation on how types should work. Or does this not make any sense?

Of course, implicit looping is only a minor part. I would accept explicit combinators and think they would be worth it.
_______
Smile =)
* bt krav magas kitten THE FUCK UP
<bt> Eat Kung Jew, bitch.

[ Parent ]

ah, I see what you're saying (nt) (none / 0) (#93)
by jacob on Fri Mar 28, 2003 at 10:59:22 AM EST



--
"it's not rocket science" right right insofar as rocket science is boring

--Iced_Up

[ Parent ]
I see what you are saying... (none / 0) (#35)
by jjayson on Fri Mar 28, 2003 at 12:17:13 AM EST

However, it doesn't really work.

First, EXPR1 and EXPR2 can be more than just an array. It can be a multi-dimentional matrix (array or array of array of ...).  As long as EXPR1 and EXPR2 are of a comfortable rank, it should be legal, so it is more than just a parsing issue.

Second, you would still want this behavior to be possible on user defined functions and combinators seem to be the only way to do this. The procedural paradigm doesn't cover these very well.
_______
Smile =)
* bt krav magas kitten THE FUCK UP
<bt> Eat Kung Jew, bitch.

[ Parent ]

Different paradigms, really. [nt] (none / 0) (#36)
by tang gnat on Fri Mar 28, 2003 at 12:18:14 AM EST



[ Parent ]
Fun w/ containers (5.00 / 1) (#148)
by tmoertel on Fri Mar 28, 2003 at 08:30:05 PM EST

It might be able to be solved with operator overloading, but that would require overloading each operator for each possible collection. It seems to be far cleaner to just put it in the language.
The problem is that just putting it in the language means that the programmer may not have the opportunity what define what it means to operate on collections. For example, Haskell doesn't by default let you perform numeric operations on list-like containers, but if you tell it what you mean, it will be happy to let you do so. Here, I define that binary operators are applied respectively itemwise and unary operators are applied itemwise:
module ContainerNum where

instance Num a => Num [a] where

    (+)         = zipWith (+)
    (-)         = zipWith (-)
    (*)         = zipWith (*)
    abs         = map abs
    negate      = map negate
    signum      = map signum
    fromInteger = const []
And now we can perform numeric operations on lists (vectors), lists of lists (matricies), and so on:
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 5.04.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Loading package haskell98 ... linking ... done.
Prelude> :load /home/thor/work/k5/ContainerNum.hs
Compiling ContainerNum ( /home/thor/work/k5/ContainerNum.hs, interpreted )
Ok, modules loaded: ContainerNum.

*ContainerNum> [1,2,3] + [3,4]
[4,6]
*ContainerNum> [1,2] + [3,4]
[4,6]
*ContainerNum> [[1,2],[3,4]] + [[1,2],[3,4]]
[[2,4],[6,8]]
*ContainerNum> negate [1,2,3]
[-1,-2,-3]
*ContainerNum> [0,1,2] * [1,2,3]
[0,2,6]
Note that these definitions say that if you can perform numeric operations on values of type a, you can use my definitions to perform them on values of type [a] (list of a values). So this definition will work for matricies (type [[a]]) or lists of matricies ([[[a]]]) and so on because Haskell will apply the definitions inductively. In short, it's not a hassle.

Also note how I handled the corner case where the lists you are "adding" are not of the same size. I decided to add as many items as possible, but for another problem I might want to throw an error if the lists aren't equal in size.

The point I'm trying to make is that there isn't necessarily one right way. I would rather use a language that let me tell it the right way than one that assumed the right way and made me do real work to get the job done.

--
My blog | LectroTest

[ Disagree? Reply. ]


[ Parent ]
<algorithm> (none / 0) (#162)
by ucblockhead on Sat Mar 29, 2003 at 10:29:25 AM EST

You can do that sort of thing with C++ iterators, though it is clunky. You could do the first with for_each and there's a template that will copy one container to another, passing all of the contained objects through a functor. (I forget, offhand, what it is...it's in <algorithm>.)
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
Functional programming style seeping into C++ (none / 0) (#177)
by jongleur on Sat Mar 29, 2003 at 04:55:31 PM EST

I can't find the link but there's a list somewhere of all the libraries up for consideration for inclusion into this year's standard, and one of them is the lambda lib. This allows off-the-cuff closures (making foreach actually useful), but also partial function application in the way described by the parent article. In general, functional programming concepts are seeping into C++ and some will become standard (or at least get more publicity) this year. Template metaprogramming itself has to be done in functional programming style as there are no rebindable variables at compile time. One final link, FC++ is a lib (not up for inclusion in the standard alas, but from what I understand the libs which are have much of the same functionality) that implements many of the Haskell prelude functions for C++.
--
"If you can't imagine a better way let silence bury you" - Midnight Oil
[ Parent ]
Jebus Chribt (1.77 / 18) (#26)
by A Proud American on Thu Mar 27, 2003 at 10:12:42 PM EST

If this is the best and most interesting K5 technology piece anyone here can come up with, it's a sad state of affairs.

What's next, an entire article on while loops?

____________________________
The weak are killed and eaten...


Yeah, right (2.50 / 2) (#144)
by hondo77 on Fri Mar 28, 2003 at 06:44:25 PM EST

Annoy a Republican: work hard, be well-off, enjoy life, and still dislike Dubya.

[ Parent ]
Yes. (4.00 / 1) (#164)
by tkatchev on Sat Mar 29, 2003 at 11:05:11 AM EST

With a sequel explaining what "variables" are and why you would want one.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Brief comment on design philosophy (4.75 / 4) (#27)
by Pseudonym on Thu Mar 27, 2003 at 10:15:45 PM EST

Before I move on to iterators I need to go back a little bit. There is another, even more basic concept used by programmers, and that is the concept of the Object. Now, the idea of the object may seem obvious now, but for a long time programmers did all of their thinking in the solution domain.

...then along came OO design, and programmers did all of their thinking in the subset of the solution domain that was object oriented programming. :-)

Thankfully, we're back in the real world now. We understand that software design is the process of mapping the problem domain onto the solution domain. It follows that you have to think about the solution domain in order to find the most appropriate solution, and sometimes OO programming isn't it.

C++, for example, has many language features (e.g. templates, ad-hoc overloading), design patterns (e.g. iterators) and "add-on" techniques (e.g. domain-specific scripting, relational databases) which all may be more appropriate solutions to some problem than objects alone.



sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Hmm (none / 0) (#152)
by Simon Kinahan on Sat Mar 29, 2003 at 07:28:48 AM EST

You seem to have a very limited definition of object orientation. All but the last two of the techniques you name build on object-oriented ideas to solve specific problems. Templates and overloading are necessary in strongly typed OO languages, but are basically artifacts of the type system (not that that makes them bad). Design patterns are specifically *good*, general OO designs (not all OO designs are good, obviously).

This perspective seems to come from C++, in that the earlier versions of the language were somewhat broken, but still "object oriented", and this seems to have given people the impression that object-orientation is not good for much. The point being missed is that other, much older, OO languages, such as Eiffel, always had these features, and still others, such as Smalltalk, were designed in such a way as to not need them.

Simon

If you disagree, post, don't moderate
[ Parent ]

OO *design*, not *programming* (none / 0) (#185)
by Pseudonym on Sat Mar 29, 2003 at 08:36:33 PM EST

In my comment, I only dealt with object oriented design. The task of OO design was to map problem-space entities onto objects.

Nowadays, the philosophy we map problem-space entities onto objects, templates, ad-hoc overloading, design patterns and whatever else we feel we can get away with.

What codemonkey appeared to say was that until OO design came along, design took place in the solution domain, and objects all of a sudden designers freedom to work more with problem domain abstractions. This is partly true, but IMO misleading, and that's what I took issue with.



sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
[ Parent ]
How to iterate... (3.50 / 2) (#34)
by tang gnat on Fri Mar 28, 2003 at 12:14:09 AM EST

You use pointers or indexes - whichever is faster for the situation.

int i;
for(i=MAX; i--; )
{
  /* Do stuff with i */
}

Alternately,

for(p=start; p!=0; p=p->next)
{
  /* Do stuff with *p */
}

In some cases, iterators are not technically the best way to do things. For example, if the same operation is performed on each element of a set independently of nearby elements, then it should be designed with parallel computing in mind.

My OOPY rant (4.33 / 3) (#38)
by Blarney on Fri Mar 28, 2003 at 12:30:16 AM EST

I like this article. I've used STL, and it sure can be helpful. Iterators truly are cool. Pointers and arrays certainly do suck. However, the central problem of OOP still remains - it depends upon code reuse to an extensive degree, yet libraries of general-purpose classes are not generally available, defeating the whole purpose. If you can't just go and get a pre-written class/template for what you want to do, there's no real point. Beneath the pretty surface of iterators and access functions will lurk the dirty underbelly of for loops, pointers, and bilge - and you'll have to do it yourself, because nobody else wants to.

too right. (4.00 / 4) (#39)
by twistedfirestarter on Fri Mar 28, 2003 at 12:36:08 AM EST

C++ needs something like CPAN.

[ Parent ]
Only sort of true (none / 0) (#114)
by x3nophil3 on Fri Mar 28, 2003 at 02:46:21 PM EST

STL is a general purpose library that provides in template form abstractions that represent all sorts of data structures.

It doesn't rely so much on code reuse, or other C++ mechanics (externally). Templates are a very novel way of moddeling abstractions. I frequently use STL templates in what would otherwise be C code, simply because instantiating a vector<FooStruct> is easier than implementing linked lists over and over again.

And I defy you to find a OO language which completely removes the need for loops and pointers.

[ Parent ]

All sorts of data structures (none / 0) (#116)
by Blarney on Fri Mar 28, 2003 at 03:04:58 PM EST

So what's the STL template for "audio file"?

Just an example of the sort of thing that everybody writes every time they want it, and that never ever makes it to complete bugfree status.

[ Parent ]

Er, ok (none / 0) (#121)
by x3nophil3 on Fri Mar 28, 2003 at 03:57:29 PM EST

I meant data structure in the computer science sense, obviously.

Yes, I suppose file formats do constitute data-structures, though. There a host of libraries that can be used for this, but yes there is no convergence towards a 'standard' library like you might get in newer languages.

Like almost every argument of this nature it leads to the 'pick the right tool for the job' conclusion. Have fun writing really efficient protocol or OLTP database handling code in Perl, or Java. The answer is one language is only as much better than any other as it's proponents are one-sided...

[ Parent ]

Eh? (none / 0) (#145)
by DJBongHit on Fri Mar 28, 2003 at 07:29:32 PM EST

instantiating a vector<FooStruct> is easier than implementing linked lists over and over again

I'm sure you know this, but if you need a linked list, a vector isn't what you want. :P

~DJBongHit

--
GNU GPL: Free as in herpes.

[ Parent ]
OO depends on reuse ? (none / 0) (#125)
by Simon Kinahan on Fri Mar 28, 2003 at 04:26:24 PM EST

How ? Admittedly there were some very overblown claims made for reuse in OO in the early days, but really object orientation is just a way to organise code to make it more extensible and maintainable. By and large, reuse still only happens within projects, and general libraries are only available for features that are needed in similar form by lots of systems.

Simon

If you disagree, post, don't moderate
[ Parent ]
Don't forget the Leaky Abstractions paper (n/t) (none / 0) (#129)
by ph317 on Fri Mar 28, 2003 at 04:45:59 PM EST



[ Parent ]
Other languages ? (4.71 / 7) (#50)
by Simon Kinahan on Fri Mar 28, 2003 at 05:01:14 AM EST

C++ does something unusual with iterators (as with many things) and takes them beyond mere iteration; turning them into a general abstraction for positions in a collection. Java's iterators are more standard for an imperative language.

In languages that have first class function closures, like Smalltalk and Lisp, they tend to use active iteration functions, rather than passive iterator objects, so in smalltalk, you just write "Collection do: [ :element | ... stuff ... ]" to iterate over a collection. I like the compactness of this.  

Simon

If you disagree, post, don't moderate

Similar in Ruby (5.00 / 1) (#54)
by treefrog on Fri Mar 28, 2003 at 06:35:43 AM EST

Ruby's iterators fall out of the language's structure.

You see, Ruby has the concept of a block, which is, as it sounds, a piece of code. But the nice thing is, I can associate a block of code with a particular method or subroutine, so the block is called from that subroutine, passing local variables if required.

So, for example, I could create an array, and use the each method to iterate through all values.

names=["Tom","Dick","Harry"]
names.each { |x| print "Hello ",x }

Here the block is enclosed in the curly braces. The |x| is a list of local variables passed into the block, enclosed by vertical bars, i.e. |variable_list|. The thing is, we can also use this concept from the other end, and pass local variables out to a block, without knowing a priori what that block is going to do. This is done with a yield statement. The following example (from the Pickaxe book ("Programming Ruby : A Pragmatic Programmers Guide" by Andy Hunt and Dave Thomas) whows how it could be used. In this case, it is implementing a find_all method in the Array class.

class Array
   def find_all
      found=[]
      self.each { |i| found<<i if yield(i) }<br>       return found
   end
end

So this has implemented a method that iterates through an array, passing out each value in turn to a block (whose contents are as yet unknown) putting the returned values into a second array (which is then returned) if the block evaluates to true. For example:

[1,3,5,7,9].find_all{ |x| x*x > 30 } returns [7,9]

There are many other things you can do with Ruby blocks and iterators, including using them for transactional processing. I would recommend anyone interested to take a look at the Pickage book. It is available on-line. In particular, the chapter on containers. This chapter also contains an interesting discussion on the relationship between the concept of iteration in different languages, including C++, Java and Smalltalk.

The combination of the block and the yield statement make it possible to write good general purpose methods which pass iterated values out to associated blocks.

Best regards, treefrog


Twin fin swallowtail fish. You don't see many of those these days - rare as gold dust Customs officer to Treefrog
[ Parent ]

You can make something... (4.00 / 1) (#113)
by the on Fri Mar 28, 2003 at 02:44:17 PM EST

...remarkably like closures in C++ and use much the same idiom. See fc++ or lambda.

--
The Definite Article
[ Parent ]
That's twisted ... (5.00 / 1) (#118)
by Simon Kinahan on Fri Mar 28, 2003 at 03:07:37 PM EST

I like it very much. However, there's presumably no way to write an expression within a function that evaluates to a closure over the function's local variables, since there's no way around the fact blocks of code are not first-class citizens in C++. Java gets closer on that front, because of the anonymous class syntax. The lack to truly, syntactically first-class functions makes it hard to use for the things higher-order functions are used for in Smalltalk, where there is no control construct not based on blocks (closures).

Simon

If you disagree, post, don't moderate
[ Parent ]
Use named classes (5.00 / 1) (#127)
by the on Fri Mar 28, 2003 at 04:36:05 PM EST

You can used a named one instead - even if you start having to put things in the wrong scope. I use constructions akin to currying in my C++ code - and these capture the values of local variables. It's not as elegant as a real functional language because you actually have to do work yourself rather than let the compiler take care of things automatically.

I don't just do it for the hell of it either. I do a lot of mathematical coding where it's very convenient to be able to manipulate (polynorphic) function objects and glue them together in various ways. It can actually result in compact and readable code though the compilers often get lost trying to optimize.

--
The Definite Article
[ Parent ]

I see that it's useful ... (4.00 / 1) (#130)
by Simon Kinahan on Fri Mar 28, 2003 at 04:59:33 PM EST

... it's just less useful than in other languages, because I can't write:

int i;
vector<int> vec;
foreach(vec) (element)
{
  i += element;
}

Or similar. I see what you mean about putting things a scope further out than you would, but it reduces the readability of the code, relative to what it would be in a language with lexical closures, or more "natural" C++ idiom, and should therefore be avoided unless there's a good reason for it.

I see what you mean about mathematical code, though. I have been doing some such things recently, and will bear the FC++ stuff in mind.

Simon

If you disagree, post, don't moderate
[ Parent ]

Bear it in mind (5.00 / 1) (#133)
by the on Fri Mar 28, 2003 at 05:11:42 PM EST

    and will bear the FC++ stuff in mind

That's the correct approach. Bear it in mind and see what ideas might be useful. But don't, whatever you do, actually use it! fc++ borders on insane. One idiom that I did find very useful is this:

class X {
  ...
public:
  ...
  ...
  template<class Y> ... operator()(Y ... ) const { ... }
};

In other words, it's a polymorphic function object. That thing so saved my ass a number of months ago!

--
The Definite Article
[ Parent ]

Indeed (none / 0) (#140)
by x3nophil3 on Fri Mar 28, 2003 at 06:19:09 PM EST

And functors (function-objects) are a common convention for solving the problems you appear to be discussing (I know no smalltalk).

Note that functors can also be type-generic, which allows for all sorts of interestign madness, that can be useful in mathematical contexts.

[ Parent ]

I don't use the word 'functor' (none / 0) (#142)
by the on Fri Mar 28, 2003 at 06:26:09 PM EST

That already has a meaning in category theory. The fc++ papers call them functoids which is ugly. I think my favorite this week is 'function object'.

--
The Definite Article
[ Parent ]
Yeah (none / 0) (#143)
by Simon Kinahan on Fri Mar 28, 2003 at 06:31:15 PM EST

"Functor" is also the name for a parameterised module (actually very like a C++ template) in Standard ML. Possibly that meaning is connected to the category theory one, but the word is much too heavily overloaded. The C++ STL things should just be called function objects, since that's what they are.

Simon

If you disagree, post, don't moderate
[ Parent ]
"funcables" (none / 0) (#190)
by NFW on Sat Mar 29, 2003 at 11:25:19 PM EST

Just kidding.


--
Got birds?


[ Parent ]

Callable, ... (5.00 / 1) (#192)
by Simon Kinahan on Sun Mar 30, 2003 at 07:07:28 AM EST

... now I come to think of it is a name used for such things in other languages.

Simon

If you disagree, post, don't moderate
[ Parent ]
accumulate (none / 0) (#161)
by ucblockhead on Sat Mar 29, 2003 at 10:16:39 AM EST

I know it is tangential to your point, but you could actually do:

i=std::accumulate(vec.begin(),vec.end(),0);
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

What's the big deal? (4.00 / 6) (#68)
by Delirium on Fri Mar 28, 2003 at 07:57:46 AM EST

Maybe I'm missing something, but it seems like the concept of iterators could be summed up with "they let you iterate through the elements of some collection," and should be familiar to anyone who's used any of the various languages that have a "foreach" keyword. Whether the concept is implemented with C++ iterators as "for(vector<int>::iterator i = vec.begin(); i != vec.end(); ++i)" or as "foreach i in vec" and so on are just implementation details that don't strike me as particularly interesting or unusual.

If it pisses you off so much... (4.33 / 3) (#73)
by BruTeQ on Fri Mar 28, 2003 at 08:19:44 AM EST

Has anyone noticed the way he hates Iterators implemented is how they're implemented in Java? Has anyone even LOOKED at the rederence to the Java Docs?

I'd use an iterator like this [bear with me, I'm not a good programmer]:

LinkedList ll=new LinkedList();
Iterator i=ll.getIterator();
while(i.hasNext) {
System.out.println("LinkedList ll has: "+ i.next() );
}

Is that so wrong?

language consistant idioms (5.00 / 4) (#78)
by codemonkey_uk on Fri Mar 28, 2003 at 08:43:36 AM EST

The problem with the iterators I was talking about is not the design, but the context of the design. Writting iterators in C++ in that same way as you would in Java is only helpful if are porting Java code to C++.

Design does not exist in a vacume; the context of the design is this case is the language.

Think of cars, which is better, left hand or right hand drive? The answer is it depends on were the car will be driven. The same principal is at play here.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Nope (4.00 / 2) (#80)
by Simon Kinahan on Fri Mar 28, 2003 at 08:51:07 AM EST

But Java iterators (like those in most languages) are just iterators. C++ iterators are fancy pointer-like things. There's nothing wrong with either model, they're just different, but IMHO, you should write code that is culturally consistent with the language you're writing it in. Now C++ (thanks to the STL) has started to develop some conventions about how things should be done, we should stick to them. Although I generally prefer Java to C++, given a choice, it would irritate me if someone implemented an iterator in C++ like a Java one.

Conventional (java-style) iterators actually have 3 operations, if you break it down as much as possible: "give me the current element", "move to the next element", and "are there any more elements ?". Java combines the second and third ones, to save typing, and not must else.

Simon

If you disagree, post, don't moderate
[ Parent ]

Iteration in Java (none / 0) (#124)
by swr on Fri Mar 28, 2003 at 04:26:10 PM EST

I prefer to use a for loop instead of a while loop. This has the advantage that the iterator's scope is limited to the loop it is actually used in.

for (Iterator i = someCollection.iterator() ; i.hasNext() ; ) {
Foo foo = (Foo)i.next();
doSomethingWithFoo(foo);
}

I've written enough code like that to wish Java could do something more like map(this.doSomethingWithFoo, someCollection) instead of the above verbage.



[ Parent ]
Java Syntax will be changing in 1.5 (5.00 / 1) (#128)
by lordpixel on Fri Mar 28, 2003 at 04:43:52 PM EST

Take a look at this page:
http://jcp.org/aboutJava/communityprocess/jsr/tiger/enhanced-for.html

Quoting the relevant part:

The current for loop construct is powerful, but somewhat ill-suited to iteration over collections. The standard idiom to iterate over a collection is somewhat verbose:

    for (Iterator i = c.iterator(); i.hasNext(); ) {  // No ForUpdate
        String s = (String) i.next();
        ...
    }

The situation is made little better with the addition of generics:

    for (Iterator<String> i = c.iterator(); i.hasNext(); ) {
        String s = i.next();
        ...
    }

We propose a second form of the for loop specifically designed for iteration over collections and arrays. Traditionally this is done using a foreach keyword, but it seems unnecessary and counterproductive to add a keyword at this late date. Under the the syntax of this proposal, the above code could be replaced by this:

    for (String s : c) {
        ...
    }

Similarly, the following code could be used to calculate the sum of an int array.

    int sum = 0;
    for (int e : a)  // e is short for element; i would be confusing
        sum += e;

End Quotation.

Commentry:

The combination on generics and the iterator aware for loop syntax (which will also iterate over the new typesafe Enum support that's coming, BTW) is going to lead to some very clean, readable code.

I'm really hoping this stuff is available in 1.5. The feature designs presented so far are very nice because they all integrate with each other. Its synergy :) (why do I feel like a dirty marketer whenever I use that word?)

I am the cat who walks through walls, all places and all times are alike to me.
[ Parent ]

Iterators in perl - example using a closure (3.66 / 3) (#87)
by czth on Fri Mar 28, 2003 at 09:49:13 AM EST

package String::Iterator;

sub New {
  my ($class,$str,$i) = (@_[0,1],0);
  bless sub {
    substr($str,$i++,1)
  }, $class
}

sub Next {
  shift->()
}

package main;

my $iter = String::Iterator->New("foo");
while(my $ch = $iter->Next()) {
  print "iterator got '$ch'\n";
}

Of course Next is just syntactic sugar and it would work just as well not to bless the sub and to just use while(my $ch = $iter->()).

You'll note that this iterator also, like the second one the author denigrates, returns the item and advances the pointer all at once. To suggest that this is not a valid iterator (and in many cases better than separating the dereference and increment operations) is ignorant.

Furthermore, if no-one tells you "these things" you can always (a) read books or (b) ask.

czth

ignorant? (4.66 / 3) (#88)
by codemonkey_uk on Fri Mar 28, 2003 at 10:27:42 AM EST

Combining the fetch and the advance may be okay for input & output iterators, but it really is a very limited form of iteration, and of no use what so ever for more "complex" algorithms such as sorting, or non-linier (ie binary) searches.

The reason I don't think that this combining of the two operations is useful is because it saves typing at the expense of flexibility.

If you need to separate the functions for forward iteration it makes sense, for the sake of consistency, to keep that separation the same for input & output iterators.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Don't abuse my iterators (3.00 / 5) (#89)
by czth on Fri Mar 28, 2003 at 10:33:05 AM EST

Combining the fetch and the advance may be okay for input & output iterators, but it really is a very limited form of iteration, and of no use what so ever for more "complex" algorithms such as sorting, or non-linier (ie binary) searches.

Well, there's your problem - trying to do sorting and binary searches on my iterators. Don't do that. It's not what they were designed for. All an iterator does by definition is iterates. Anything else is extra, although not wrong; I like C++ iterators just fine.

Suppose my iterator had Inc and Get methods. How would you binary search it? How would you sort it? Inquiring minds want to know.

czth

[ Parent ]

classes of iterator (4.50 / 2) (#90)
by codemonkey_uk on Fri Mar 28, 2003 at 10:52:06 AM EST

To do a binary search you need a random access iterator. To do a linier search you need a forward iterator. I think you need a random access iterator to do a sort, though given an input iterator and an output iterator you can output a sorted copy.

Because these different classes of iterator form a heirarchy (though, in the STL it is conceptual, rather than based on inheritance) a random access iterator "is a" forward iterator, and a forward iterator "is a" input iterator.

Becuase your iterator combines "fetch" and "advance", something a forward iterator must not do, code written to work with it will not work with a forward iterator.

However, if you think that having a combined "fetch and advance" operation is a powerful tool, then I would advise you provide it in addition to seperate operations.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Logical fallacies with forward iterators (3.25 / 4) (#97)
by czth on Fri Mar 28, 2003 at 12:00:57 PM EST

To do a binary search you need a random access iterator. To do a linier search you need a forward iterator. I think you need a random access iterator to do a sort, though given an input iterator and an output iterator you can output a sorted copy.

Thus your original comment about combining fetch/advance inhibiting binary search and sorting was basically a red herring, since it wasn't relevant to my iterator.

Becuase your iterator combines "fetch" and "advance", something a forward iterator must not do, code written to work with it will not work with a forward iterator.

Why must it not do that? Because of how you or someone else equally unimportant has defined "forward iterator"? So, what you're saying is "your X-type object is bad because it doesn't fit my definition of X, so won't work with code using my definition of X." Looks like a circular argument to me.

However, if you think that having a combined "fetch and advance" operation is a powerful tool, then I would advise you provide it in addition to seperate operations.

And throw in a kitchen sink method too, in case anyone needs it? Taking a page from "Extreme Programming" here, it's bad to build stuff just because you think (not "know") someone will need it later. Usually it's not good for APIs to expose more than one way to do something.

My definition of forward iterator is an iterator that goes forward. Simple and accurate. You can define it how you like, but don't try to impose those definitions on the rest of the world.

czth

[ Parent ]

A common vocabulary is important (4.66 / 3) (#101)
by codemonkey_uk on Fri Mar 28, 2003 at 12:17:13 PM EST

I think an important point for me to make at this time is that these are not my definitions, they are part of the vocabulary that describes the STL, part of C++. I realise that you gave me a perl example, and that it is not right of me or anyone else to try "force" the c++ idioms and vocabulary onto the perl development community, though I do think that there are advantages for everybody if to a certain extent we can agree to use the same language to describe the same concepts.

May I ask, is the iterator design you presented common in Perl? Is it used within the core language or libraries? If so then we should just agree to disagree, otherwise I have to ask why, in the face of what I think are coherent arguments for the interface separations I am advocating, do you insist that "move" and "fetch" be a single operation?

I have said in a reply to some one else's comment that I have no inherent problem with, for instance, the Java way of doing things, it's just that implementing a Java-style iterator for your C++ container class is counter productive, because you fail to leverage either the STL algorithms or the existing knowledge of the target audience.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

To each his own iterator (1.60 / 5) (#105)
by czth on Fri Mar 28, 2003 at 12:58:54 PM EST

I think an important point for me to make at this time is that these are not my definitions, they are part of the vocabulary that describes the STL, part of C++.

Yes, I realize that, I'm quite fluent in C++ and STL.

I realise that you gave me a perl example, and that it is not right of me or anyone else to try "force" the c++ idioms and vocabulary onto the perl development community, though I do think that there are advantages for everybody if to a certain extent we can agree to use the same language to describe the same concepts.

That's nice, the answer is "no." You can't redefine a general term like "forward iterator." If you'd like to say "STL forward iterator" (or in the existing context of the C++ STL refer to a forward iterator) to leverage existing definitions, that's fine, but you can't export the definitions of one particular realm to the general; that doesn't remove confusion, it creates it.

May I ask, is the iterator design you presented common in Perl? Is it used within the core language or libraries?

No.

If so then we should just agree to disagree, otherwise I have to ask why, in the face of what I think are coherent arguments for the interface separations I am advocating, do you insist that "move" and "fetch" be a single operation?

What coherent arguments? "C++ does it" is the only one I've seen and it hardly holds any water among users of other languages. The reason I like move and fetch as a single operation is usage patterns - that's the way we use iterators. Several modules here have iterators like that, because it just makes sense; it's quite compact and leads to less function call overhead because the general pattern is something like while(my $item = $iter->Next()) { ... } and using $item in the loop, rather than repeatedly calling a Current method (or operator* in C++). Most likely in C++ the pattern is the same: assign the element to a local variable, and advance the iterator, e.g. for(MyList::iterator i = theList.begin(); i != theList.end(); i++) { MyElement& item = *i; ... }.

I have said in a reply to some one else's comment that I have no inherent problem with, for instance, the Java way of doing things, it's just that implementing a Java-style iterator for your C++ container class is counter productive, because you fail to leverage either the STL algorithms or the existing knowledge of the target audience.

Agreed, if something works in a given instance don't wrest it to look like something else - for example, don't try to make my convenient get-and-advance iterator look like a C++ iterator.

czth

[ Parent ]

closing argument (none / 0) (#131)
by codemonkey_uk on Fri Mar 28, 2003 at 05:03:35 PM EST

Okay, mostly I'm just arguing the toss, but looking back at what I wrote I realised I didn't explicitly state what the main argument, in my opinion, is for separating the "Fetch" and "Advance" operations, and it boils down to flexibility. As the implementer of a container of objects, you empower the user by providing a more flexible interface, and IMHO there is not much more annoying for a programmer than not being able to do what you want to do with some data because someone thought they would "make your life easier" by limiting the flexibility of the interface they provide to access that data in favour of "connivence".

And that is about it.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Very obvious reason with pointers (3.50 / 2) (#136)
by x3nophil3 on Fri Mar 28, 2003 at 06:04:31 PM EST

If you think of iterators as pointers then there is a very obvious reason why you want to seperate fetch and advance.

If you want to do multiple operations on whatever an iterator references, then coupling fetch and advance means either the referenced object or the iterator has to be copied, or the iterator has to be decremented each time it's referent is operated on.
If the iterator is in fact a vanilla pointer then this is cheap, if the iterator is not a pointer but an object then this can become very expensive.

Each language has it's own paradigm. In situations in which perl is appropriate making local copies of data may be fine, in situations where C++ is appropriate this is not always true.


[ Parent ]

Braino (none / 0) (#138)
by x3nophil3 on Fri Mar 28, 2003 at 06:06:37 PM EST

Odd. Somehow that got flipped around in my head. I meant 'an obvious reason when not using pointers'.


[ Parent ]
No need (none / 0) (#168)
by greenrd on Sat Mar 29, 2003 at 02:45:07 PM EST

If you want to do multiple operations on whatever an iterator references, then coupling fetch and advance means either the referenced object or the iterator has to be copied, or the iterator has to be decremented each time it's referent is operated on.

No. Let's take Java as an example. If you want to use an object returned from Iterator.next() multiple times, you just... uh... use it multiple times. The next() method returns an object, or to be precise, a reference to an object, so no object copying is needed.


"Capitalism is the absurd belief that the worst of men, for the worst of reasons, will somehow work for the benefit of us all." -- John Maynard Keynes
[ Parent ]

Right (none / 0) (#176)
by x3nophil3 on Sat Mar 29, 2003 at 04:07:26 PM EST

My (unclear) point was that you should have the choice about whether or not you want to make a local copy of the pointer/reference/object/whatever.

I'm sure there are cases where you might want to dereference a large number of iterators each a small number of times within a loop.


[ Parent ]

Why increment first? (5.00 / 4) (#92)
by Viliam Bur on Fri Mar 28, 2003 at 10:58:15 AM EST

for reasons that escape me, they have to be incremented once to get to the first object in the container.

The list may also contain zero items. So before you start walking through the list, you should check whether it is not empty. Calling "increment" once to get the first item (or to get an "end of list") does this.

while (I->next()) {
  do_something_with(I->data);
}

Of course, the other possible way is to have two functions, one to say whether list is empty and second to get the next element.


if (!I->is_empty()) {
  do {
    do_something_with(I->data);
  } while (I->next());
}


side effects (4.50 / 2) (#95)
by codemonkey_uk on Fri Mar 28, 2003 at 11:08:08 AM EST

I can see how this can be useful, but I prefer my methods to be free from side effects. I like to be able to decide: Do I want to fetch the value, or do I want to move to the next element? Do I want to check that the iterator is valid, or do I want to validate it.

I'm sure that there is a name for the principal. "Separation of Concerns" keeps coming to mind, but looking that up on the internet indicates that it means something else entirely. Anyway, whatever this principal is called, by combining the "advance" and the "test valid" operations into a single member function you violate it.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Small nitpick (4.66 / 6) (#107)
by carlossch on Fri Mar 28, 2003 at 01:44:55 PM EST

I agree with your points concerning "Separation of Concerns", but side effects are not related to that. Side effects are any alteration of state caused by invocation of a function. That is, anything that violates the mathematical idea of a function (same input => same output) has side effects associated with it. IO, random number generation functions, etc.

Many methods can be implemented in a side effect free manner, but dereferencing an iterator is inherently dependent on the state of that iterator, and thus most iterator operations are side-effectful.

Carlos
-- He took a duck in the face at two hundred and fifty knots.
[ Parent ]

Good article and even better discussions. (3.75 / 4) (#96)
by jbm on Fri Mar 28, 2003 at 11:18:26 AM EST

Stride iterators are a little talked about item in STL land because they aren't in yet. But they are interesting to think about and are necessary for tree structures.

Stride iterators & tree structures (5.00 / 2) (#98)
by codemonkey_uk on Fri Mar 28, 2003 at 12:02:07 PM EST

You wrote:
"[Stride iterators] are necessary for tree structures."
Can you elaborate on this point? I've done my fair share of work with tree structures, and I've never needed stride iterators as they are descibed in the Stepanov interview:
"Stride iterator is an iterator adaptor that takes a random access iterator range and provides a (random access iterator) such that ++ on it goes through a stride (a sequence of iterator n steps apart)."
In fact, when the interviewer persists with the conection between strides and trees Stepanov quite explicitly states:
"I did not mean to say that stride iterators ... have anything to do with tree traversal"

---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
Basically I'm wrong (4.33 / 3) (#106)
by jbm on Fri Mar 28, 2003 at 01:20:00 PM EST

there goes my rating of 4.0! :)

Stride iterators can be used for tree structures when the tree structure is built using an array (of any dimension). As an example, heaps could be written with stride iterators.

But you are correct, stride iterators are not necessary for tree structures.

[ Parent ]

Necessary? (5.00 / 1) (#122)
by x3nophil3 on Fri Mar 28, 2003 at 04:12:16 PM EST

There are some places where stride iterators could be handy:

Vertex arrays
Frame buffers (graphics data)

And they could be really useful for implementing some algorithms (crude downsampling).

But I don't think they're ever necessary. You can always increment an iterator more than once. If you implement a collection you can define any sort of iterator you like.

And don't forget that STL runs the serious risk of becoming so incredibly flexible that 90% of people can no longer figure out how to use it.


[ Parent ]

Alright already (5.00 / 1) (#132)
by jbm on Fri Mar 28, 2003 at 05:06:15 PM EST

I'm wrong. :)

You're correct forward iterators could be called multiple times to act like stride iterators. But there are cases where that is terrible. For example if using a heap, the block of code using the iterator would have to understand how to calculate (or call functions which calculate) moving through a heap. That's is just nasty.

[ Parent ]

That's interesting (5.00 / 1) (#134)
by x3nophil3 on Fri Mar 28, 2003 at 05:27:20 PM EST

I was under the impression that stride iterators would move through a data structure in a uniform way. Is that not the case?

But of course you could very easily create an iterator that knew how to move through a heap, or a pre, post, and in-order traversal iterator for a tree. I'm just not sure that stride iterators are meant to do this, I think of them as having a parameterized stride.

Hmm, I dunno.

[ Parent ]

My thinking (5.00 / 1) (#139)
by jbm on Fri Mar 28, 2003 at 06:12:47 PM EST

I've seen the word stride used in describing C++ iterators as a parameter that is set when moving an iterator. But I've also seen the stride of an iterator set during the constructor.

I assumed (rightly or wrongly can be argued) that a constant expression, not just a constant value, would be in fashion with stride iterators.

[ Parent ]

Internal vs. external iterators (4.75 / 4) (#104)
by aziegler on Fri Mar 28, 2003 at 12:52:35 PM EST

All iterators in C/C++/Java are "external" iterators, which lead to potential problems.

Ruby, on the other hand, has "internal" iterators:

[1, 1, 2, 3, 5, 8, 13, 21].each { |i| puts i }

This will iterate over the array and put each item on a line. For most uses of iterators, this is far preferable (and is relatively thread safe1). External iterators (C++-like) are possible, certainly, and work better in some cases (especially when you need to iterate over multiple collections in parallel), but iterators themselves aren't hard.

If there's interest, I may put together an "Introducing Ruby" article.

-austin
1 It's thread safe in that multiple threads can iterate on a given collection indepdendently; it's not thread safe in that the iterators don't lock the collections.

Ruby iterators (none / 0) (#183)
by Merc on Sat Mar 29, 2003 at 07:21:03 PM EST

This is one of the things a good modern language should do. I really get tired of writing the same "for" loop over and over again in other languages. In Ruby, iterators almost always work the way you expect, and they save lots of typing.

Java's java.util.Iterator works somewhat like Ruby's iterator in that it doesn't imply that you're working with an array. You never need to know the length of the list you're iterating over, just whether there's a "next" element.

The other advantage to using either the Java Iterator interface or the Ruby internal iterators is that they're hard to misuse.

When I look at the C++ style for-loop-dependant "iterators" it doesn't surprise me to find out that the convention for their use is sometimes broken. A good language or interface should enforce a way of doing things instead of just relying on a convention.

I strongly recommend that every programmer at least take a look at Ruby. I have yet to meet someone who tried it and didn't like it. It has a pretty familliar syntax, yet provides a level of object-orientation that few other languages match or exceed. Now it isn't the fastest language, and doesn't have CPAN's extensive library, but just give it a couple of years of optimization.



[ Parent ]
Flow control (4.50 / 4) (#109)
by jd on Fri Mar 28, 2003 at 01:48:25 PM EST

There is iteration (a code block repeats N times, where N is either a fixed number or a fixed condition).

There is recursion (a code block is re-entered N times, where N is determined by means of a fixed condition).

Iteration and recursion are functionally identical but are programatically very different. Iteration is generally computationally cheaper, but recursion (because you've local variables per cycle) can be much easier to program, especially when the result of one cycle is the input of the next.

Iteration and recursion may have the test at the start (zero or more cycles) or at the end (one or more cycles). The "default" in C is to have the test at the start. In PASCAL, while-loops have the test at the start, and repeat-loops have the test at the end.

The key with iteration of any kind is to understand what it is you're looping through. That will often tell you the type and structure of loop that you'll want to use.

Tail recursion, baby! (4.50 / 2) (#126)
by ENOENT on Fri Mar 28, 2003 at 04:29:36 PM EST

Don't forget that tail recursion IS iteration. In Scheme, recursion is all you get, but tail recursion is guaranteed not to consume any extra stack space.

So nyah.


[ Parent ]
Nitpick (5.00 / 2) (#202)
by zakalwe on Mon Mar 31, 2003 at 07:50:55 AM EST

Scheme does provide iteration, using do, though it doesn't tend to be used much - tail recursion is more elegant.

[ Parent ]
The Default? (5.00 / 4) (#135)
by x3nophil3 on Fri Mar 28, 2003 at 05:48:38 PM EST


while( 1 ) {
Something();
}

do {
Something();
} while( 1 );

How is one a default and the other not? For loops evaluate the test first, but that only makes 2 out of 3, not really a default behaviour.

[ Parent ]

FWIW, Also known as cursors (5.00 / 4) (#117)
by KWillets on Fri Mar 28, 2003 at 03:07:09 PM EST

In the database world, iterators are known as cursors, which have been used for about twenty years to provide a procedural interface to data accessed via SQL, a non-procedural language.

As some have noted, it's usually preferable to use a set-oriented operation instead of an iterator.  SQL is one example of a language which doesn't use cursors or loops, except in extensions to the core language.  Most problems are solved by using SQL joins or search predicates to replace looping in the client process.

Use of a cursor follows roughly the same lifecycle as an iterator.  The cursor is created, its associated SQL statement is executed, and each row of the result set is fetched in a loop until an end-of-data condition is reached.

Databases and Iterators (4.50 / 2) (#123)
by Simon Kinahan on Fri Mar 28, 2003 at 04:18:59 PM EST

SQL may not expose database iterators to the outside world, but they're generally used as the common concurrency within the database's physical algebra.

Simon

If you disagree, post, don't moderate
[ Parent ]
Good article (5.00 / 4) (#146)
by DJBongHit on Fri Mar 28, 2003 at 07:49:26 PM EST

Or at least half of one. I wish I had seen this in the queue so I could post an editorial comment.

Good start on the idea of iterators, but I would have liked to see more information on why they are useful (i.e. STL's algorithms, and the fact that if you implement iterators for a custom data type or container, STL's algorithms will all suddenly work beautifully on your data). They are the common language of the STL, and it would have been nice if you had talked about this a bit more.

I've been programming in C for 12 years or so, and while I've known C++ for 8 years, I had never written a big project in it, or really played around much with templates or the STL. I was one of those "I know C++, but I prefer C" people. Well, no more. When I started my latest project (a commercial game engine) I decided to give C++ a real chance, and I'm very glad I did - templates and STL make my life MUCH easier and simpler, not to mention the fact that when you can accomplish with one already-debugged call into STL what would have previously taken 20 or 30 lines of code, bugs are far less frequent and easier to track down when they do rear their ugly heads. Also, as long as you're careful about potential code bloat, templates help immensely with writing generic and high-performance code. Without templates, you're usually limited to one or the other.

It's too bad STL's map isn't written as efficiently as it could be, though (I don't think it's mentioned in the spec, but at least STLPort's implementation allocates and deallocates its node structures on every insertion/deletion)... I had to go and reimplement it myself (yes, I realize I could have fixed that with a custom allocator, but at that point I decided that I might as well write my own red-black tree instead so I could have full control over the performance). On the plus side, since I gave my implementation iterators, it was a simple drop-in replacement in our very large codebase :)

~DJBongHit

--
GNU GPL: Free as in herpes.

It's probably good you didn't (1.60 / 10) (#157)
by twistedfirestarter on Sat Mar 29, 2003 at 08:48:17 AM EST

try to edit. codemonkey ignores you then he mods you down...

STL's map

There is no STL map. STL is a standard. I take it you are either talking about the GNU map or the MSVC map. If you are worried about map inefficiency, try the hash_map, it's non standard but both GNU and MSVC provide one (GNU is better, surprisingly).

[ Parent ]

liar (4.25 / 4) (#158)
by codemonkey_uk on Sat Mar 29, 2003 at 09:08:41 AM EST

You are a liar. I moderated two of your comments, one a 3 (average) and one a 4 (above average). I vast majority of editorial comments posted to this article received a 4s and 5s. A quick scan of the comments I've posted show 8 replies to editorial comments along the lines of "thanks, that's fixed now". Just because I didn't use *your* suggestions, perhaps because, as I said already on several occasions, I didn't have time to do any major rewrites, doesn't mean I ingore editorial suggestions. I see you've written a grant total of zero articles, which gives a real weight of authority to your accusations. Oh, and way to misquote me in your new sig. Wanker.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
You just lied. (2.14 / 7) (#159)
by twistedfirestarter on Sat Mar 29, 2003 at 09:16:41 AM EST

"dont mod in your own stories" don't you understand?

And we all know ratings can be changed afer the fact.

Moderating editorial, or topical, comments down in your own story is just fucking rude. I went to the trouble of reading your story, and suggesting changes. Give me a fucking 5 or nothing. I don't care if you ignore me, but modding me down is just plain annoying. It's ambushing people who post in your goddamn story.

And it's more than 2 - it's nearly all of my comments, both editorial and topical. I counted, liar.

[ Parent ]

Bite me (5.00 / 4) (#165)
by codemonkey_uk on Sat Mar 29, 2003 at 12:53:53 PM EST

Changed after the fact? That's a laugh. Why would I bother? Actually, now I'm tempted too. If your going to go round telling people I've been "moding you down" I might as well have the satisfaction of actually doing so.

Who exactly are you quoting? Because as long as I've been active on K5 moderation is been basically without rules. You got a problem with how I moderate? Tell it it the admins, see how much they care.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

The best part is (none / 0) (#194)
by jubal3 on Sun Mar 30, 2003 at 08:48:26 AM EST

that this same guy gave me a 0 because he didn't like my content on a comment.


***Never attribute to malice that which can be easily attributed to incompetence. -HB Owen***
[ Parent ]
STL (5.00 / 1) (#186)
by DJBongHit on Sat Mar 29, 2003 at 09:45:43 PM EST

codemonkey ignores you then he mods you down...

I'm gonna stay out of this one. I've never seen codemonkey exhibit that kind of behavior when the comment in question didn't deserve it.

There is no STL map. STL is a standard.

Yes, thank you. I realize that. However, the STL spec stays out of the details of memory management for portability reasons, and most implementations of set and map do things the way I said (allocate and free nodes on every insertion and deletion) which is unacceptable for our purposes.

I take it you are either talking about the GNU map or the MSVC map. If you are worried about map inefficiency, try the hash_map, it's non standard but both GNU and MSVC provide one (GNU is better, surprisingly).

I'm using STLPort, which is a fork of SGI's STL implementation. It focuses on performance, which is what I'm looking for, and it works with both gcc and MSVC. The main reason I chose this route, aside from the excellent performance it gives me, is that I don't want to use a compiler-dependent STL. Even though we're currently using gcc on all platforms, I didn't want to limit us in the future, because we plan to port the engine to PS2 and XBox, as well as any other console which may come along. By using the exact same STL everywhere, we can rely on certain performance characteristics.

And yes, STLPort has hash_map, seeing as how it was originally an SGI extension to the STL.

~DJBongHit

--
GNU GPL: Free as in herpes.

[ Parent ]
STL on PS2 (none / 0) (#191)
by codemonkey_uk on Sun Mar 30, 2003 at 04:33:46 AM EST

Hi,

If your planning on using the STL on the PS2 you might want to take care to plan ahead for memory fragmentations issues. Feel free to email me (via my website) if you want any help with planning ahead for this particular problem. :)


---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Allocators (5.00 / 1) (#182)
by sholden on Sat Mar 29, 2003 at 06:52:05 PM EST

It's too bad STL's map isn't written as efficiently as it could be, though (I don't think it's mentioned in the spec, but at least STLPort's implementation allocates and deallocates its node structures on every insertion/deletion)... I had to go and reimplement it myself (yes, I realize I could have fixed that with a custom allocator, but at that point I decided that I might as well write my own red-black tree instead so I could have full control over the performance). On the plus side, since I gave my implementation iterators, it was a simple drop-in replacement in our very large codebase :)

An allocator would have worked for other data structures as opposed to being embedded in your specific data structure.

And of course there is always boost pool. It's not exactly what you wanted, but in many cases will provide a good enough alternative.

--
The world's dullest web page


[ Parent ]
Yeah (4.00 / 1) (#187)
by DJBongHit on Sat Mar 29, 2003 at 09:57:53 PM EST

An allocator would have worked for other data structures as opposed to being embedded in your specific data structure.

Yeah, I know. However, and I didn't mention this in my original comment, a standard binary tree doesn't do everything I need it do. I need to be able to iterate through the structure in very wierd ways. I can't give many details without risking my job and future financial success :), but our occlusion/visibility algorithm depends on a quite strange data structure - it's basically two intertwined binary trees with some status flags in each node that determine what the "next node" means. It's not a standard binary tree, and it can't generally be iterated normally. But the end result of this wierdness is that, with no preprocessing (a'la Quake's BSP tree building step), our engine can determine nearly perfect visibility (no false negatives, few false positives) from an arbitrary viewpoint and arbitrary geometry in logarithmic time. John Carmack will be my bitch someday, mark my words :D.

And of course there is always boost pool. It's not exactly what you wanted, but in many cases will provide a good enough alternative.

Yeah, I've heard good things about Boost, and I'm going to take a look into it when I get a chance. No time now, our next milestone is creeping up rapidly :)

~DJBongHit

--
GNU GPL: Free as in herpes.

[ Parent ]
Well then (5.00 / 1) (#193)
by sholden on Sun Mar 30, 2003 at 08:43:03 AM EST

Of course the STL isn't going to provide you with data structures like that. In fact, I guess you are glad they don't since that would greatly reduce the chances of Carmack ever being your bitch. :)

--
The world's dullest web page


[ Parent ]
XML iterators? (4.00 / 2) (#149)
by martingale on Fri Mar 28, 2003 at 11:26:31 PM EST

I can't remember where I read this now, but recently somebody mentioned that what XML needs is a good iterator design. I find this quite intriguing. The iterators I've come across tend to be useful on (linear) lists. Besides that, I'm familiar with pre/post/in-order traversal for trees of course.

Now XML code is both tree-like and list-like in general, but surely a good iterator concept there would be more than a blend of forward/backward/pre/in/post? I could imagine things like skipping to the next similar tag, or some fancy DTD based navigation. Anyone have any comments on this?

Iterators in XML (4.33 / 6) (#153)
by localroger on Sat Mar 29, 2003 at 07:51:48 AM EST

While it is possible in concept to design beautiful mechanisms for working with XML data, when the XML database grows larger than a few K the actual mechanics of implementing those methods become awful.

Since records in XML are length-inspecific there is no way to randomly target them. There isn't even any way to efficiently code a reverse iterator! You can kludge these things by indexing the XML file but then you've just reinvented the relational database, only less efficiently.

This goes to the heart of my complaint with the way programming is taught since 1990 or so. The mechanics of how the computer works are hidden behind abstractions like objects, and people aren't taught the "irrelevant" details of how object code must shovel data around in order to implement those things. This leads to people trying totally unworkable schemes like using XML as a database file structure.

XML is a great way of transporting data but a lousy way of working with data in real time.

I can haz blog!
[ Parent ]

Gentle Sir: (5.00 / 2) (#163)
by tkatchev on Sat Mar 29, 2003 at 11:00:24 AM EST

XML is a format for tagged text, not a database management system.

Text as in, stuff you read, you know?

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Could've fooled me (5.00 / 4) (#166)
by localroger on Sat Mar 29, 2003 at 01:20:35 PM EST

Like HTML, XML is being adopted for all kind of hare-brained things that have nothing to do with its original purpose. Since any form of data can be converted into text (str$() or MIME anyone?) XML can be used to store any kind of data, and I've seen people using it in just this way.

I have seen several projects (and I suspect many more exist) attempting to use XML as a database storage format because of its inviting open-endedness. As long as these datasets are modest and the machines fast such schemes even seem to work. But they scale extremely poorly.

I can haz blog!
[ Parent ]

Sure. (none / 0) (#173)
by tkatchev on Sat Mar 29, 2003 at 03:11:50 PM EST

A database in XML is really no different from a database in HTML. Except that XML is a more sane and more modern format.

There are, unfortunately, a whole boatload of hare-brained solutions in IT... :((

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Yes! (none / 0) (#169)
by ucblockhead on Sat Mar 29, 2003 at 02:51:40 PM EST

Though unfortunately a lot of XML advocates have yet to figure this out.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
They're idiots. (none / 0) (#172)
by tkatchev on Sat Mar 29, 2003 at 03:10:13 PM EST

Don't listen to them. XML is a brilliant idea when used right; the database idiots will soon find some other form of distraction and stop abusing what is potentially a very useful format.

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

not quite what I had in mind, but here goes... (5.00 / 3) (#184)
by martingale on Sat Mar 29, 2003 at 08:02:33 PM EST

I did leave myself open to your criticism, so I accept your point. However, it's skirting the issue. Using XML as a database (except in the abstract sense of information store) was furthest from my mind, and is certainly not efficient beyond literally a couple of handfuls of records.

I tend to strongly associate XML with older languages such as HTML, so what I had in mind were XML documents of the same size and complexity as contemporary HTML documents, say. OpenOffice.org uses XML to represent word processing documents, for example. In those cases, there really isn't an issue with parsing the whole structure into a big chunk of memory, web browsers do it all the time for HTML documents.

The point of my question is what do you do once you have this relatively complex parse tree in memory, perhaps having calculated a few generic statistics (how many tags of one type or another, tree depth, whatever). Navigating such a tree is still a challenge.

Say you've recuperated an XML document from a news site, and you want to write an agent whose job it is to do something "intelligent" with the document. If it's an HTML document, you can hard-code some heuristics about the meanings and uses of various tags, and even some standard document layouts (navigation section, content section, whatever, I'm not suggesting this is an easy problem here).

So I think the question I posed is still a good one. To restate it in a more precise form: Given the full DTD information and a fully accessible parse tree in memory, are xml code libraries naturally limited to the standard list and tree navigation heuristics, or can the DTD be used to infer higher level navigation heuristics (which would then make sense for that particular DTD)?

[ Parent ]

Tree-in-memory (5.00 / 2) (#188)
by localroger on Sat Mar 29, 2003 at 10:18:08 PM EST

I think this is the key; you can't just do operations on XML. You must cache the bits you need to do non-simplistic operations (and here, reverse iteration is non-simplistic).

The problem with having a library do this transparently for you is that it doesn't know in advance what operations you want. To do this without arbitrarily wasting gigabytes of storage you would have to specify a whole list of potential indexing requirements. And when you get to the point that you've done that well enough for the result to be useful, you've put in just as much work as if you coded the whole thing from scratch in BASIC using Get and Put.

OK, maybe not that bad but almost. Really.

I can haz blog!
[ Parent ]

bresenham (2.33 / 6) (#179)
by turmeric on Sat Mar 29, 2003 at 05:11:27 PM EST

is the future... it is taking an recursive function and turning it iterative,, or other wya around? its related to fractal compression and the future. discrete math. end of standard calculus. but first we need to stop war.

WTH... (none / 1) (#195)
by tkatchev on Sun Mar 30, 2003 at 11:57:23 AM EST

...is a "bresenham"? The only one I know of is a line drawing algorithm...

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

circle drawing algorithm? (none / 1) (#196)
by turmeric on Sun Mar 30, 2003 at 12:37:52 PM EST

polygon drawing algorithm? etc etc etc etc etc?

[ Parent ]
So? (none / 0) (#197)
by tkatchev on Sun Mar 30, 2003 at 12:54:05 PM EST

Why would we need one?

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

Filtered Iterators..... (4.25 / 4) (#181)
by TonyPaulDay on Sat Mar 29, 2003 at 05:58:33 PM EST

Must admit my STL knowledge is patchy (pretty much nonexistent)... but on development of some Delphi Container structures, one of the more interesting techniques I used was a form of Iterators with applyable filter functions.

I'm sure this is nothing unique, but building some form of this into an iterative framework seemed a very powerfull concept, and allowed very simple (for instance) seperation of a aggregate function, from what it has to work over (even more so than with vanilla iterators), and things like popping only relevant info from a stack etc.

I was wondering if this is standard in other container frameworks, or even if people have built this sort of layer over the top, and where to look at for ideas on extending/improving on what I did.

Filtered iterators (and stuff) in Java (5.00 / 3) (#200)
by swr on Mon Mar 31, 2003 at 05:49:41 AM EST

I was wondering if this is standard in other container frameworks, or even if people have built this sort of layer over the top, and where to look at for ideas on extending/improving on what I did.

The Apache Jakarta Commons Collections sub-sub-project has some Java code that does that, among other things. I think the closest to your example is a static utility method IteratorUtils.filteredIterator that takes an iterator and a predicate function[*] as arguments, and returns a new iterator that only returns those elements from the original iterator for which the predicate function returns true.

[*] Java doesn't really support function references, so you have to define a class with a single method and instantiate it. This is relatively easy with anonymous inner classes, although it requires an annoying amount of typing.



[ Parent ]
Thanks, I'll take a look (nt) (3.00 / 2) (#201)
by TonyPaulDay on Mon Mar 31, 2003 at 07:47:38 AM EST



[ Parent ]
Way easy in Perl ;o). (none / 1) (#207)
by Alhazred on Thu Apr 03, 2003 at 09:06:54 PM EST

Perl being way more polymorphic than either C++ or Java. Closures can provide the filtering mechanism, so an iterator can simply accept an optional extra argument which is a code block providing the filter logic, and because its a closure it can capture context required later on (when the filtering is performed vs when the iterator is instantiated) quite easily.
That is not dead which may eternal lie And with strange aeons death itself may die.
[ Parent ]
I like iterators... (4.00 / 2) (#203)
by awgsilyari on Mon Mar 31, 2003 at 10:45:17 AM EST

I wish I could take them over to C land which is where I code... In my most recent work project I've had to do: a block-chained memory allocator (simple linked list); a hash table with each bucket kept in sorted order (and a deletion function for it); a linked list of blocks pulled out of the block-chained memory allocator (heh); link lists of gstate objects, each of which contains several linked lists of some other objects in them.

OO aside, the concept of an iterator as a standard, uniform way to traverse and manipulate doubly-linked lists is something that C could really use. Have you ever written an in-order linked list insertion for a doubly linked list? All the prev/next pointers could give you a headache, not to mention the special end cases (at least for a single list the special case is only at one end, in the double list both ends are special).

--------
Please direct SPAM to john@neuralnw.com

Is that really hard? (5.00 / 2) (#206)
by lukme on Thu Apr 03, 2003 at 01:14:39 PM EST

You do realize that all of the objects you mentioned can be coded in C in an object oriented manner as in:

typedef struct my_object
{
void *(forward_iter)(void *);
void *(delete_func)(void *);
} MO;

typedef struct hash_table {MO p;...} HT

ht_init(HT* ht) {...} /* constructor */
ht_delete(HT* ht) {ht->p->delete_func(ht);} /* a virtual destructor */
ht_insert(HT* ht,void *val) {...}
void *forward_iter(MO *mo)
{
if(mo->forward_iter)
return mo->forward_iter(mo);
return NULL;
}

Am I missing somthing?
Just as a side note, I have written singly likned lists, doubly linked lists, curcular lists, an AVL tree, hash tables and a skip list. Personally, the skip list is particularly difficult to do.


-----------------------------------
It's awfully hard to fly with eagles when you're a turkey.
[ Parent ]
You people and your petty iterators... (2.00 / 3) (#205)
by ThreadSafe on Mon Mar 31, 2003 at 07:37:36 PM EST

when will you learn to code 'beyond iteration'?

Make a clone of me. And fucking listen to it! - Faik

Iterators | 208 comments (122 topical, 86 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!