The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

STL Iterator's

I need to execute a body of code using either a forward iterator or a reverse iterator depending on a condition. Is there a way to do this without moving the 'body of code' to a separate function or duplicating the code.

Best I can come up with is two separate for loops, one for each type of iterator and then have the common code block in a called function.

This all seems messy. ie. creating a new function just to work with the two iterators.
Neville Franks Send private email
Tuesday, April 03, 2007
 
 
Can you make it a template method, like ...

class<T>
void foo(T begin, T end)
{
 for (T it = begin; it != end; ++it)
 { ... }
}

... which you'd invoke using iterator or using reverse_iterator as T? Perhaps you can use for_each with either type of iterator.
Christopher Wells Send private email
Tuesday, April 03, 2007
 
 
I guess the reason why you're concerned is that from within your loop you want to access other local variables that are defined outside the loop.

Another way would be to encapsulate the directionality of the iterator, like:

class MyIterator
{
private:
 //use one or other of these
 iterator it;
 reverse_iterator revit;
 //remember which of the above we're using
 bool b;
public:
 ... a couple of constructors ...
 ... iterator-like methods which delegate either to it or to revit ...
}

Not pretty but it seems like what you're asking for.
Christopher Wells Send private email
Tuesday, April 03, 2007
 
 
Yes there are a number of variables that would need to be passed to the function. I just don't like the idea of creating a function for no good reason other than to use iterators.

I finished up doing it the old C/C++ way:

    for( int npos = bSelectionsDown ? 0 : vSourceNodes.size()-1 ;
        npos != ( bSelectionsDown ? vSourceNodes.size() : -1 ) ;
        bSelectionsDown ? ++npos : --npos
      )
    {
        somevar = vSourceNodes.at( npos );
...
    }
Neville Franks Send private email
Tuesday, April 03, 2007
 
 
> Yes there are a number of variables that would need to be passed to the function.

FWIW I like to do this by putting the variables in a struct or class, which I then pass-in by reference.
Christopher Wells Send private email
Tuesday, April 03, 2007
 
 
Are you implementing an iterator or using one?

If you are USING one then you can do:

Iterator iter = doItFoward ? getForwardIterator() ? getReverseIterator();

while (iter.hasNext()) {

  // do stuff

}

(forgive the Java-like pseudocode)
DJ Clayworth
Tuesday, April 03, 2007
 
 
Your scenario is best implemented using a function class. A function class is more flexible than a normal function because it can store states during iterations.

For example, assume that you need to process a collection. However, the process needs to know if the iterator is going forward or reverse forward, because the code is slightly different. You could write:

class Functor
{
public:
    Functor(bool bForward) : _bDirection(bForward) { }
    void operator(int value)
    {
            //actual code,
            //use _bDirection to differentiate handling code
            //store partial result in _result
    }
    int GetResult() { return _result; }
protected:
    bool _bDirection;
    int _result;
};

Now put the function class in use:
Fuctor func(true);  //calculate using forward direction
func = for_each(v.begin(), v.end(), func);
int result = func.GetResult();

Functor func(false); //claculate using reverse forward direction
func = for_each(v.rbegin(), v.rend(), func);
int result = func.GetResult();
Glitch
Tuesday, April 03, 2007
 
 
>Are you implementing an iterator or using one?

If you are USING one then you can do:

Iterator iter = doItFoward ? getForwardIterator() ? getReverseIterator();

--
I'm using one, but this won't work, at least not with STL as it has different types for the forward and reverse iterators. ie.

iterator iter = vec.begin();    // fwd iterator
reverse_iterator iter = vec.rbegin();  // reverse iterator
Neville Franks Send private email
Tuesday, April 03, 2007
 
 
>Your scenario is best implemented using a function class. A function class is more flexible than a normal function because it can store states during iterations.

Agreed, this would be the most elegant. I still have the problem of having to move the inner block of code to a function (class) which will never be re-used elsewhere just to use the iterators.

I guess we don't live in a perfect world. ;-)
Neville Franks Send private email
Tuesday, April 03, 2007
 
 
And another issue with the separate function (class) is the extra overhead in doing a call for every iteration. In this particular case this isn't a problem, but it could well be.
Neville Franks Send private email
Tuesday, April 03, 2007
 
 
You could make a single template class that wraps two iterators, and uses whichever one is appropriate. If the compiler decides that the member functions can be inlined, the only penalty you will pay is the if statement that decides which iterator to use. Here's the start of an implementation, many more details would need to be filled in before this would be useful.

template<class BaseIterator,class BaseReverseIterator>
class TwoWayIterator
{
public:
    TwoWayIterator & operator=(const BaseIterator & iter)
    {
        forwardIterator = iter;
        directionForward = true;
        return *this;
    }
    TwoWayIterator & operator=(const BaseReverseIterator & iter)
    {
        reverseIterator = iter;
        directionForward = false;
        return *this;
    }
    TwoWayIterator & operator++()
    {
        if (directionForward)
            ++forwardIterator;
        else
            ++reverseIterator;
        return *this;
    }
    bool operator!=(const BaseIterator & iter)
    {
        return forwardIterator != iter;
    }
    bool operator!=(const BaseReverseIterator & iter)
    {
        return reverseIterator != iter;
    }
private:
    BaseIterator    forwardIterator;
    BaseReverseIterator    reverseIterator;
    bool    directionForward;
};
Mark Ransom Send private email
Tuesday, April 03, 2007
 
 
Actually it is quite easy to tell the iterator type:

if ( typeid(it)==typeid(vSourceNodes.begin() )
{
  //forward iterator case:
}

If you do not use typeid(), you can overload a function with different types of params:

bool IsForwardIterator(std::vector<int>::iterator)
{ return true; }

bool IsForwardIterator(std::vector<int>::reverse_iterator)
{ return false; }
Glitch
Tuesday, April 03, 2007
 
 
> I just don't like the idea of creating a function for no good reason other than to use iterators.

I think I hear the mating cry of a C++ programmer desperately clinging to the old C style of coding.  ;)

If you use the C style, then it will be ugly. If you abandon C style coding and learn to embrace std::for_each then you will have a little function object. Until you get used to it, it will feel weird, and possibly seem "wrong".

Tuesday, April 03, 2007
 
 
I've had another idea, much simpler than my first. This assumes that the container provides a bidirectional iterator.

container c;
bool isforward;
container::iterator i, iEnd;
    ...
i = isforward ? c.begin() : c.end();
iEnd = isforward ? c.end() : c.begin();
while (i != iEnd)
{
    if (!isforward)
        --i;
    ...
    if (isforward)
        ++i;
}
Mark Ransom Send private email
Wednesday, April 04, 2007
 
 
Mark, STL uses different iterators for forward and reverse as I mentioned above.

iterator iter = vec.begin();    // fwd iterator
reverse_iterator iter = vec.rbegin();  // reverse iterator

So I can't see how your example will work.

To the poster re. hanging onto old world C/C++ coding. That isn't the case. If it was I wouldn't have posted in the first place. I provided several reasons why I don't like the idea moving the code to its own function and calling it for every iteration.
Neville Franks Send private email
Wednesday, April 04, 2007
 
 
Reverse iterators are only necessary if you want to use operator++ to go backwards. In this case, I'm using operator-- to go backwards, which any old bidirectional iterator can do. Vector, list, deque, map, and set all provide bidirectional iterators.
Mark Ransom Send private email
Wednesday, April 04, 2007
 
 
>Reverse iterators are only necessary if you want to use operator++ to go backwards.

Your example doesn't work because the STL end() iterator is behind the last element in the container. You could probably do:

i = c.end()-1;

but it all gets messy quickly because of the difference between the begin() and end() iterators and management of the for loop exit condition.

I don't think you could safely assume:

i = c.begin()-1;

is valid.

That's why there are different forward and reverse iterators.
Neville Franks Send private email
Wednesday, April 04, 2007
 
 
Yes, I considered all that. That's why the iterator is decremented at the beginning of the loop, but incremented at the end. Note carefully where the ... is inside the loop; that's where the meat of your code goes.

Let's step through it. The forward case is pretty simple, with the twist of using a while loop instead of a for; we'll gloss over it for now. In the backward case, the iterator starts at end(), which is really last+1. At the beginning it's decremented, so now it points to the last element of the container. Then your code operates on that last element. Nothing happens at the end of the loop, so we start again at the beginning. Now the decrement takes us to last-1. Etc, etc... Finally the loop starts with the iterator at begin()+1. The decrement takes it down to the first element, and your code operates on that. The next time through the loop, i==begin() and the loop terminates. That's BEFORE the decrement can try to go to begin()-1.
Mark Ransom Send private email
Wednesday, April 04, 2007
 
 
Mark,
My apologies. I didn't look at the while loop and its inards. That is simple and clever and should work just fine.
Neville Franks Send private email
Thursday, April 05, 2007
 
 
Thanks. For the record, I don't think there's anything wrong with the solution you came up with either, as long as your container is a vector.

When I'm iterating through a vector, I always waffle on whether to use an iterator or an integer index. Generally the index has the cleaner and more familiar syntax. Like you, I'm reluctant to move a few lines of code into a function (or worse yet a functor) just so I can use for_each.
Mark Ransom Send private email
Thursday, April 05, 2007
 
 
Do ::iterator and ::reverse iterator really not have a common ancestor that you can cast them to while still allowing you to use ++?
DJ Clayworth
Tuesday, April 10, 2007
 
 
I'm not aware of any guarantees made for derivation of iterator and reverse_iterator. If they do have a common ancestor, it's probably just an implementation detail and not portable. And I certainly can't see operator++ being declared virtual, so even if there's a common ancestor it won't be of any use to you.
Mark Ransom Send private email
Tuesday, April 10, 2007
 
 
Why not write the original loop like so?

{
  int nBegin = bSelectionsDown ? 0 : vSourceNodes.size() - 1;
  int nEnd  = bSelectionsDown ? vSourceNodes.size() : -1;
  int nStep  = bSelectionsDown ? +1 : -1;

  for (int nPos = nBeginPos; nPos != nEndPos; nPos += nStep) 
    {
        somevar = vSourceNodes.at( npos );
...
    }
}

Of course this will work only for vectors/deques.
ananthd Send private email
Saturday, April 14, 2007
 
 
I have to say I've never seen the advantage of using STL iterators. I always considered it was a lot more code than what its worth. You make your loops look nice, when browsing over it, but when it comes to an external developer understanding or maintaining the code it becomes very implicit. Its only obvious to the original coder.

But I'm up any enlightenment you may give why you would want to do it.
Entity Send private email
Friday, April 27, 2007
 
 
Iterators work with ALL containers, indexes only work with vectors and deques. And an iterator is likely to be more efficient on a deque.

All of the standard algorithms work with iterators. A pointer works as an iterator, so they're all backwards compatible. Getting the pointers to a vector is even more awkward than using the iterators, so you're better off saving that technique for old-fashioned arrays.

The problem of other developers being unfamiliar with iterators would go away if eveyone would just start using them. That's one reason why I use them even for vectors, just to stay in the habit.
Mark Ransom Send private email
Friday, April 27, 2007
 
 
1. convert the code block into a functor. (Class with operator() defined).
2. Use the std::for_each() with forward and reverse iterators

Look at the pseudo code below.

FunctorClass funcOp;
if( forward == true)
    std::for_each(container.begin(), container.end(), funcOp)
else
    std::for_each(container.rbegin(), container.end(), funcOp)

I think above is the simplest option to meet your criteria. Since the forward and reverse iterators donot have a common base class, using a single variable for both types of iterators are not possible.
Nitin Bhide Send private email
Monday, April 30, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz