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.
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
Originally Posted by phantomotap
