How do I provide virtual 'iterators' ?

I have a 'Graph' class, which has derived classes for Adjacency Matrix and Adjacency List representations.

How do I provide iterators for traversing vertices and edges, when the iterator classes would have different implementations for the different derived classes ?
The following way is the only one I can think of, but seems quite cumbersome.

Code:

class Base { public: class BaseIterator { }; virtual const BaseIterator& begin(); virtual const BaseIterator& end(); }; class Foo:public Base { public: class FooIterator:public Base::BaseIterator { }; //Implementation of the functions }; class Bar:public Base { public: class BarIterator:public Base::BaseIterator { }; //... };

Or is there a pattern for doing this that I'm not aware of ?
Would composition be a better idea here compared to polymorphism ?
I mean, I can think like..a Graph can 'have' several representation 'objects' within it.

Edit: All the involved classes are templates,not sure if that makes the situation different.

Quote:

How do I provide iterators for traversing vertices and edges, when the iterator classes would have different implementations for the different derived classes ?

O_o

You are aware that the inheriting the iterators doesn't buy you any implementation, correct?

That is, you will be inheriting solely to allow polymorphisms over for the interface; you will not inherit to simplify the implementation.

You can't return a constant reference from all the functions that return iterators; you have to return a value.

Code:

virtual const BaseIterator& begin() { // This does not work. return(BaseIterator(/**/)); }

You have to have a value that can be owned, mutated, and destroyed separate from the class so containing an iterator and returning a reference to it will also not work. You can use inheritance, but you can't use the iterators themselves as references to an object so returning pointers to newly crafted iterators will also not work.

Code:

it * i(begin(c)); // ... (*i++); // What would this do?

Both sets of the three nested types, `view::iterator' and `view::const_iterator', require reference semantics in the form of referencing the container, but as with pointers, the nested types themselves must be value types. (I'm assuming the base also has a particular way of navigating from an iterator.) Yes, the `iterator' and `const_iterator' will be different types when you are completely done.

Quote:

Or is there a pattern for doing this that I'm not aware of ?

You are apparently not aware of the "non-virtual interface" pattern.

You are apparently not aware that the definitions of iterator is set.

I think you also may not know about "type erasure".

In other words, do your job as if the view represented by the iterators were normal iterators of entirely unrelated classes. You do not need inheritance for the iterators. You should not use inheritance for the iterators.

Quote:

Would composition be a better idea here compared to polymorphism ?

Are you suggesting that the classes representing a different view should contain a generic `Graph' object?

That is certainly one way to go about it, but you lose inheritance based polymorphisms.

Code:

void Go ( const Base & fGraph ); // ... Go(list); // This will not work.

Are you suggesting that the derived iterators should contain an iterator of type `Graph::iterator'?

You would still lose inheritance based polymorphisms.

Code:

void Go ( Base::iterator fCursor , Base::iterator fTerminus ); // ... Go(list.begin(), list.end()); // This will not work.

However, containment is indeed part of the solution.

*shrug*

Do you need a hint? You may look after my signature for a hint, but you should not look until you have carefully considered what I've said.

Soma

Code:

// ... template < FValue > class Iterator { // ... template < FValue , FIterator > class Virtual { }; // ... template < FIterator > Iterator ( FIterator f ); // ... Iterator operator ++ () { Iterator s(*this); // ... m->advance(); // ... return(s); } // ... Virtual * m; // ... }; // ... template < FValue > class ConstIterator { // ... }; // ... template < FValue > class Graph { // ... class GraphIterator { // ... }; // ... GraphIterator begin() { return(/**/); } // ... virtual Iterator<FValue> vbegin() { // ... return(Iterator<FValue>(this->begin()); } // ... virtual const Iterator<FValue> vbegin() const; // ... }; // ... template < FValue > class Matrix: public Graph<FValue> { // ... class MatrixIterator { // ... }; // ... MatrixIterator begin() { return(/**/); } // ... virtual Iterator<FValue> vbegin() { // ... return(Iterator<FValue>(this->begin()); } // ... }; // ... template < FValue > class List: public Graph<FValue> { // ... };

Quote:

Originally Posted by phantomotap

O_o

You are aware that the inheriting the iterators doesn't buy you any implementation, correct?

That is, you will be inheriting solely to allow polymorphisms over for the interface; you will not inherit to simplify the implementation.

Yes, that is/was the goal.
I already have (part of the) iterator for the Matrix class, made up as needed.
That already works with ranged for loops, so I think it is behaving nicely.

Quote:

In other words, do your job as if the view represented by the iterators were normal iterators of entirely unrelated classes. You do not need inheritance for the iterators. You should not use inheritance for the iterators.

I get that now.

How about for_each like virtual functions, that would take two functions as arguments (the first being a condition check and the second being the action that executes if the condition returns true) ?
If that is sufficient for implementing the algorithms, what do I gain by designing iterators (other than compatibility with the standard library) ?

(will concentrate on your example in detail when I manage some time)

Quote:

How about for_each like virtual functions, that would take two functions as arguments (the first being a condition check and the second being the action that executes if the condition returns true) ?

O_o

That does not and can not satisfy the abstraction of algorithms without the virtual `each' function using polymorphic types or only value types in the interface.

You can do it that way, but that path is a mistake. You would need multiple `each' functions for different "compare" and "action" complexities. You would need to accept an object which can represent any function of the relevant signature.

Ultimately, this approach is more work. If you do the `Iterator' and `ConstIterator' template classes correctly, you only need to do it once ever. With that in mind, the creation of specific iterator classes for specific containers is no different than what you'd usual expect as making the virtual interface is a trivial function consisting of a single line.

Quote:

If that is sufficient for implementing the algorithms, what do I gain by designing iterators (other than compatibility with the standard library) ?

You seem to be under the impression that the other approach removes the need for iteration logic to exist. You are wrong.

Code:

class SExample { virtual void each ( std::function<bool(value_type &)> fCondition , std::function<void(value_type &)> fAction ) { // ... for(/**/) { // This logic is iterative in nature. // If we move this logic into a // class that is applied iteratively // as a response to `operator ++ ()' // the work for external iterators // is complete. if(fCondition(*it)) { fAction(*it); } } // ... } }; class SDerived: public SExample { virtual void each ( std::function<bool(value_type &)> fCondition , std::function<void(value_type &)> fAction ) { // ... for(/**/) { // This can only use the inherited implementation. // if the iteration is already abstract. // If the iteration is abstract, the // iterators already must exist in some form. // If the iteration is not abstract, we // must do the work here which instead // could be easily moved into a class. } // ... } };

What do you gain by directly implementing iterator logic within each implementation of the `each' method?

The code to iterate over every element must exist. You must code the iteration logic in any event.

You will have other methods that navigate nodes within the different graph classes; knowing you will use the same process of navigation within a class for every important method where navigation is required suggests that you will use a function to isolate the particulars of navigation.

Code:

class SExample { virtual void each ( std::function<bool(value_type &)> fCondition , std::function<void(value_type &)> fAction ) { // ... // uses `next' // ... } private: node * next ( node * f ) { node * s; // ... // Which way do we move? // ... return(s); } }; class SDerived: public SExample { virtual void each ( std::function<bool(value_type &)> fCondition , std::function<void(value_type &)> fAction ) { // ... // uses `next' // ... } private: node * next ( node * f ) { node * s; // ... // Which way do we move? // ... return(s); } };

Now the implementation of `each' could be identical except for the fact that `next' isn't virtual and is bound by type to the particulars of the graph variant.

What do you gain by directly implementing iterator logic within each implementation of the `next' method?

The code to iterate over every element must still exist. We haven't eliminated the need for the code; we have only placed the into a specific method of the container class.

The `node' class, by whatever designs, must also exist even if it has no methods. What have we gained by placing the `next' method within the container? We haven't reduced code or complexity.

Code:

class SExample { struct node{/**/}; node * next ( node * f ) { node * s; // ... // Which way do we move? // ... return(s); } }; // versus class SExample { class node { // ... node * next() { node * s; // ... // Which way do we move? // ... return(s); } // ... }; };

What do we gain by using `node' directly?

Code:

node * sC(mO); node * sT(mT); while(sC != sT) { // ... sC = sC->next(); }

Is using `node' directly more complicated? Is using `node' directly less complicated?

What is an iterator? An iterator is just an abstraction and the related refinements thereof of the common pointer concept.

Specifically, an iterator is an object presenting a reference to another object as having a particular interface which holds to value semantics.

The `node' class, by whatever designs, must also exist. The navigation logic must exist.

How far are we from an iterator?

Code:

class SExample { class node { // ... node * next() { node * s; // ... // Which way do we move? // ... return(s); } // ... }; class Iterator { // ... Iterator operator ++ (int) { Iterator s(*this); m = m->next(); return(s); } // ... node * m; }; };

What have we gained?

Well, before we consider what we have gained, let us consider what price we paid.

What have we spent? What have we lost?

It took me about ten seconds to write the increment operator for the iterator class.

Is the time spent implementing iterators a cost or a loss? That depends on what we have gained!

What have we gained?

Everything that may need to navigate the container can do so with the same interface.

Navigating an abstract container without even needing to be aware of the containers existence is absurdly powerful.

Want to provide that `each' method? Use iterators correctly and you provide `each' for every complete container.

Want to conditionally examine every aspect of a sequence so that you may build a refinement of that sequence? Use iterators correctly and you provide the functionality for every complete container.

Want to find a particular element within a given range? Use iterators correctly with `std::find_if' and you've found your element without even needing to know about the container.

Want to copy a range of elements? Use iterators correctly with `std::copy' and you've found your element without even needing to know about the container.

No my friend, you don't provide iterators so that you have access to the implementations of the standard algorithms. The few algorithms that you would be likely to provide are irrelevant. You aren't shooting for compatibility so that you get access to a few standard algorithms. You make you container complete, compatible with the standard library, so that everything can use your container without needing to know anything about it. Correctly implementing iterators and other container aspects grants you access to uncountably many algorithms and implementations. What do you gain? You give your clients access to millions of lines of code, tens of thousands of algorithms, and an interface they are already likely to understand and be comfortable using.

What about the cost of virtual iterators?

Remember when I said that if you made the `Iterator' and `ConstIterator' template classes I suggest correctly you would only ever need to write it once? That power comes from the standard of the iterator interface.

Code:

template < typename FContainer > typename MGetVirtualIterator<FContainer>::type vbegin ( FContainer & f ) { return(typename MGetVirtualIterator<FContainer>::type(f.begin())); } template < typename FContainer > typename MGetVirtualIterator<FContainer>::type vend ( FContainer & f ) { return(typename MGetVirtualIterator<FContainer>::type(f.end())); }

These functions and all the relevant overloads exist in my library.

Code:

void Go ( VirtualIterator<int> fOrigin , VirtualIterator<int> fTerminus ); // ... std::vector<int> s1(/**/); std::list<int> s2(/**/); std::map<int> s3(/**/); std::deque<int> s4(/**/); // ... Go(vbegin(s1), vend(s1)); Go(vbegin(s2), vend(s2)); Go(vbegin(s3), vend(s3)); Go(vbegin(s4), vend(s4));

This example code works just fine for me, and if you write the facilities correctly, it will work for you as well.

Soma

Worked wonderfully, making a 'node' for traversing all edges of the graph was challenging.
One thing I noticed was the massive repetition in the iterator code between classes and also different types of iterator of the same class.

Also when making (non const) iterators, I have a scenario that an 'user made' change in the (node)object pointed by the iterator can't be efficiently reflected in the (main) object's inner data.
I have ignored it for now, but I think this will come up again.

Thanks for the help, this thread will be a 'reference' when I need some brainstorming about iterators.

Quote:

One thing I noticed was the massive repetition in the iterator code between classes and also different types of iterator of the same class.

O_o

Well, now that you have that done, would you like me to help you explore the solution to this repetition with hints?

Would you like to hear some hints about the alternatives to the implementation of the derived types?

*shrug*

It is up to you; I'm sure you'll find a solution without my help.

Quote:

I have a scenario that an 'user made' change in the (node)object pointed by the iterator can't be efficiently reflected in the (main) object's inner data.

Well, without knowing the details, I'll simply assume that neither `node' nor `graph' has a complete interface if you can't do what needs to be done.

Soma

Quote:

Originally Posted by phantomotap

O_o

Well, now that you have that done, would you like me to help you explore the solution to this repetition with hints?

Would you like to hear some hints about the alternatives to the implementation of the derived types?

Not now.
I'll be back in a few weeks after a vacation, and then I can compare your hints to what I shall have designed by then.

Quote:

Well, without knowing the details, I'll simply assume that neither `node' nor `graph' has a complete interface if you can't do what needs to be done.

Well, the important('matrix' or 'lists') data remains safe.
What I tried/(and probably failed) to design was something similar in functionality to Boost.Bimap, which appears somewhat over complicated to me.

I have two data structures storing the same data.
A hash table for mapping data of an arbitrary template type to integers.
And an array to map integer indices to that type.
The (vertex)node contains an index and pointer to the second one.
But to detect changes made by the reference returned, I am compelled to keep track of previous states, then perform at least a search and then possibly update the hash table.

Most of the member functions implemented do the simultaneous updation manually, but this problem proves that the design was faulty.

Quote:

I have two data structures storing the same data.

O_o

So, just checking my understanding, you have a `node' that references elements in both the array and table yet directly references neither container?

It sounds to me like an elaboration on the approach used by `std::map' (description only) or insert iterators (example code).

You would not then have to keep track of previous states, but you will still have the issue of updating both views, but the iterator will have more information available so that you can make those changes. (The `node' would not have this information; it would just be the iterators that have this extra information and simply mutates the `node' by providing this information to the `node' on demand.)

I have a container that, given your description, is similar in nature, and obviously I have implemented iterators for my container. The iterator, on dereference, returns a complex value object which references back to the iterator so that the value object may update the iterator as changes in value are applied. The true value of the iterator is queried (`it->value') much like for `std::map' (`it->second') only always being returned as a constant due to the complexity of the update. The true value of the iterator is mutated only by virtue of assignment of similar complex objects (`*it=it_t::value_t(/*value*/)') which has no real similarity in the standard library.

One way or the other, you may not be able to directly reference a simple value within the iterator and get the job done directly; it is better to yield a complex value or fake value from which a true value may be queried and mutated than to try and detect changes though lists of previous states.

*shrug*

Some containers are just complicated, and you are using multiple containers to do, semantically, a single job.

Quote:

Most of the member functions implemented do the simultaneous updation manually, but this problem proves that the design was faulty.

Updation? I like that non-word. ^_^

From my understanding, that may be true, but it maybe not so bad as you think.

*shrug*

Anyway, you should wrap the update within a "RAII" construct. You don't want an exception trashing everything just because the hash table update fails after the array update completes.

Soma

Code:

struct Graph { // ... typedef pair</*Index*/, /*Data*/> value_type; // ... struct node { // ... void update ( const value_type & fData , /**/ fTable , /**/ fArray ) { // ... // We don't want this assignment to happen unless // everything is successful so we just do it here. *this = Graph::Update(fData, fTable, fArray, this); // ... } // ... }; // ... struct Iterator { // ... Iterator & operator * () // We know everything we need { // so we pretend to be return(*this); // something we are not } // for the sake of interface. // ... Iterator & operator = ( const value_type & fData ) { m->update(fData, mTable, mArray); } // ... node * m; /**/ mTable; /**/ mArray; // ... }; // ... static node Update ( const value_type & fData , /**/ fTable , /**/ fArray , node * fNode ) { // ... // Do the update in such a way that an exception will unwind // any changes to a useable and consistent state. // ... TABLE_ROLLBACK s1(fTable); s1->update(fData.first, fData.second); TABLE_ROLLBACK s2(fArray); s2->update(fData.first, fData.second); // We have had no errors so the update is complete. // Now we need to construct a new `node' having all the new // and old information like position within a linked list or whatever. return(node(fData.first, fData.second, fNode->mOther, fNode->mNecessary, fNode->mStuff)); } // ... Iterator begin() { // ... // The `Iterator' doesn't use the table or array directly. // The `Iterator' just carries a reference so that `Update' may // use the actual table and array. // We could alternatively store a reference back to // `this' which is probably easier. return(Iterator(this->mOrigin, this->mTable, this->mArray)); } // ... };