Iterator additions:

Oh, and what does everyone think about using the observer pattern in a container to notify every iterator that it connects to that they are invalidated when the container removes items or inserts items? good idea?

===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

re: AP''s comment. Ummm.....okay? What are you saying, man?

re: topic
Definitely allow the use of erase by iterator. This is how all of STL''s containers work, and it''s extremely useful. It''s also nice if the erase function returns an iterator to the next element.

I think the observer is overkill. I''d leave it up to the client to be aware of which operations can invalidate his iterators. Having an observer in there is a step toward over-complicating what could be a nice, compact class.

Removing from anywhere but the tip/end of a stack/queue is inefficient, but possible. I think it''s up to you whether or not you want to allow this practice. As a purist, I''d lean toward disallowing it, but as a client, I might be perturbed if there is absolutely no way to do it.

quote:

---

Original post by Stoffel
re: topic
Definitely allow the use of erase by iterator. This is how all of STL''s containers work, and it''s extremely useful. It''s also nice if the erase function returns an iterator to the next element.

I think the observer is overkill. I''d leave it up to the client to be aware of which operations can invalidate his iterators. Having an observer in there is a step toward over-complicating what could be a nice, compact class.

Removing from anywhere but the tip/end of a stack/queue is inefficient, but possible. I think it''s up to you whether or not you want to allow this practice. As a purist, I''d lean toward disallowing it, but as a client, I might be perturbed if there is absolutely no way to do it.

---

Yeah, you gave me a bunch to think about.

anyhow, my container ADT as it stands supports insertion and iteration.

Insertion is kind of a mixed bag, some structures have well defined insertion routines (stack, queue, BST, heap, hash table, etc), while others are not well defined but workable (list, array, graph, network), while others yet are just totally unintuitive for insertion (any tree without a special property).


And the same goes for removal, except that the heap becomes unintuitive for random item removals as well.

So i''ve created an intermediary class, which takes the insertion, iteration and removal routines and puts them into a "Robust Container", leaving the container class only able to change its capacity, determine if its full or empty, count how many items exist in it, determine if an item is in the container, and traverse the container using an internal traversal routine, processing each item (non destructive) with a visitor.

The difference between the traverse routine and getting an iterator is that you can save the position of an item with an iterator, tell the list to remove the item at the iterator, insert after the iterator, etc, whereas the traverser simply performs some non-destructive operation on the data in the list.

The question i have is this:

should robust tree''s like the BST and Heap (if you desperately need to remove a random item, i suppose it could re-heap the tree... pain in the ass though) inherit from the non-robust binary tree, or compose the non-robust binary tree?

===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

Search & destroy? Yeah performance isn''t that great, but you can effect a random delete without a random iterator then.

Magmai Kai Holmlor
- The disgruntled & disillusioned

Mithrandir,

It''s good to have container specific iterators, which expose functionality that''s natural for the container. For instance, it''s not natural for array to insert/remove items to/from the middle, but for list it is, thus they should have different iterator interfaces.

Anyway, there is sense in what Anonymous Poster is saying. You''ll get many times better container library, if you build it for your own needs than try to implement it just as end in itself. If you build it for your own needs, you''ll have only things, which are practical, implemented and dump too generic tries, which would just produce practically unusable code.

Taking that random insertion/erasing iterator of array container as example: Yes, you could implement that, but that would produce bunch of new problems which needs to get solved. In addition to this, that would be inefficient and you wouldn''t probably never even use that operation, but explicitly perform it if really needed.

Lazy code generation really rocks and gives you better perspective on things. Maybe I should write papers about that

Cheers, Altair


"Only two things are infinite, the universe and human stupidity, and I''m not sure about the former." - Albert Einstein

indeed.

my iterator hierarchy was planned to look something like this:


iterator
linear iterator, hierarchy iterator, graph iterator, etc.


i''ve since removed graph iterators, and i think i''ll allow the users to manually play around with nodes themselves if they need to.


As for random removal/inserion into an array, i''ve already developed it. its not that difficult, and I even managed to add a time halving solution. since the array is circular, it allows instant insertion to the front and back, and if the item to remove/insert falls in the front half of the list, instead of moving everything after it upwards, it moves everything before it downwards.

its pretty cool.

===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

Mithrandir,

So, how are you planning to have container specific implementations for those iterators in your hierarchy? You could have like abstract iterator template base classes and container specific implementations for those, but for such simple operations you must perform with iterators, virtual calls would cause bad overhead, particularly when compiler can''t inline those calls.

What you should do is to dump that hierarchy and design some layout for iterators that you utilize in methods, which take iterators as arguments. Those methods must be template methods so that compiler can employ compile time polymorphism on those iterators thus making them alot more efficient.

It''s not question of which operations are easy to add to a container, but which operations are really useful. If you just keep adding all little pieces that comes into your mind, soon you''ll have huge piles of useless code that will collapse on you and cause nothing but maintainance problems.

I know it''s kind of fun to write some little helper classes such as matrices, vectors, containers, etc., but if you really want to build some good libs, you don''t go that way around. I don''t want to depress you, of course it''s good OOP practice to write those little classes, but it''s not very practical. I have written some container classes myself too, but I didn''t do it until I found out that STL didn''t provide efficient enough implementations for some utilizations where I needed those. When I had to implement those containers, I had very good perspective on what kind those container should be, because I had to implement them for real world case after all and didn''t need to speculate "what if..."

Cheers, Altair


"Only two things are infinite, the universe and human stupidity, and I''m not sure about the former." - Albert Einstein

I''ve implemented half of the library within the past 3 days, so i have a much more firm grasp on the way its organised now.

Container: Allows capacity setting, basic traversing using a visitor pattern, emptying (but not inserting), counting how many items exist in it, and cloning.

Robust container : container: allows insertion, uses factory method to generate one way iterator, allows removal based on iterator, allows searching and returns one way iterator (list, BST, hash table, etc)

Dispenser : container: allows insertion of one item at a time, removal of the "top" item, and viewing of the "top" item (stack, queue, heap, etc)

Hierarchy : container: assumes that data is arranged recursively, and that all data is related to its parent. Allows iteration based on recursive 2-way iterator, allows removal of sub-trees, and pre/post order traversals using a visitor pattern.

Graph: Assumes a collection of data which is connected to 0 or more other data items. allows insertion of nodes and edges, removal based on linear iterator of nodes, removal based on linear iterator of edges attached to node, allows depth/breadth first traversal.


gotta go to class, post more later.

===============================================
Have I no control, is my soul not mine?
Am I not just man, destiny defined?
Never to be ruled, nor held to heel!