Connecting Tech Pros Worldwide Forums | Help | Site Map

iterate forward OR reverse

Jim Langston
Guest
 
Posts: n/a
#1: Jul 23 '05
I have a class I designed that stores text chat in a
std::vector<sd::string>. This class has a few methods to retrieve these
strings to be displayed on the screen.

void ResetRead( bool Reverse, bool wordWrap ); // Resets iterator. We can
ignore wordwrap for now.
std::string GetLine(); // Reads a line using iterator. Increments
Iterator.

Right now it only works in Reverse, since that's the method I used first,
but now I want to do it using a forward iterator. I want to avoid having to
duplicate code, as iterating forward and reverse are exactly the same with 2
diffeernces.

1. Declare forward iterator or reverse iterator.
2. use .begin() .end() or .rbegin() .rend()

I tried this in a test program:

std::vector<std::string>::iterator* MyIt;
MyIt = (std::vector<std::string>::iterator*) new
std::vector<std::string>::reverse_iterator;
for ( *MyIt = MyVector.begin(); *MyIt != MyVector.end(); ++*MyIt )
std::cout << **MyIt << std::endl;

But it iterators forward anyway. I can see one reason is because I'm using
..begin() and .end() but I would think the program wouldn't work because
++*MyIt on a reverse iterator *should* cause the iterator to go backwards,
which it doesn't. This leads me to believe that even though
reverse_iterator is derived from iterator, it's not using virtual classes,
or something. Not sure.

Can anyone come up with a way to do this without having to declare 2
separate methods for forward reading or reverse reading, or a if block
covering the whole for block?



Donovan Rebbechi
Guest
 
Posts: n/a
#2: Jul 23 '05

re: iterate forward OR reverse


On 2005-07-02, Jim Langston <tazmaster@rocketmail.com> wrote:
[color=blue]
> std::vector<std::string>::iterator* MyIt;
> MyIt = (std::vector<std::string>::iterator*) new
> std::vector<std::string>::reverse_iterator;[/color]

Nooooooo! Don't do that. Iterators are not supposed to be used
runtime-poymorphically.

[color=blue]
> for ( *MyIt = MyVector.begin(); *MyIt != MyVector.end(); ++*MyIt )
> std::cout << **MyIt << std::endl;[/color]

Unless operator++ () is virtual, this will call the version in the
base class.

[snip][color=blue]
> ++*MyIt on a reverse iterator *should* cause the iterator to go backwards,
> which it doesn't. This leads me to believe that even though
> reverse_iterator is derived from iterator, it's not using virtual classes,
> or something. Not sure.[/color]

You only get polymorphic behaviour with virtual functions (NOT "virtual
classes")
[color=blue]
> Can anyone come up with a way to do this without having to declare 2
> separate methods for forward reading or reverse reading, or a if block
> covering the whole for block?[/color]

Use templates.
template <typename iter>
void printit ( iter start, iter end )
{
for (; start!=end; ++start)
std::cout << *start << std::endl;
}

or you could simplify by using the standard library, and generalise to
allow other ostreams:

template <typename iter>
void printit (iter start, iter end,std::ostream & out = std::cout)
{
std::copy(start,end,std::ostream_iterator(out, "\n"));
}


printit (MyVector.begin(),MyVector.end());
printit (MyVector.rbegin(),MyVector.rend());

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/
benben
Guest
 
Posts: n/a
#3: Jul 23 '05

re: iterate forward OR reverse



"Jim Langston" <tazmaster@rocketmail.com> wrote in message
news:hbmxe.3487$iv3.913@fe02.lga...[color=blue]
> I have a class I designed that stores text chat in a
> std::vector<sd::string>. This class has a few methods to retrieve these
> strings to be displayed on the screen.
>
> void ResetRead( bool Reverse, bool wordWrap ); // Resets iterator. We[/color]
can[color=blue]
> ignore wordwrap for now.
> std::string GetLine(); // Reads a line using iterator. Increments
> Iterator.
>
> Right now it only works in Reverse, since that's the method I used first,
> but now I want to do it using a forward iterator. I want to avoid having[/color]
to[color=blue]
> duplicate code, as iterating forward and reverse are exactly the same with[/color]
2[color=blue]
> diffeernces.
>
> 1. Declare forward iterator or reverse iterator.
> 2. use .begin() .end() or .rbegin() .rend()
>
> I tried this in a test program:
>
> std::vector<std::string>::iterator* MyIt;
> MyIt = (std::vector<std::string>::iterator*) new
> std::vector<std::string>::reverse_iterator;
> for ( *MyIt = MyVector.begin(); *MyIt != MyVector.end(); ++*MyIt )
> std::cout << **MyIt << std::endl;[/color]

Why do you:

1) Heap allocate the iterator?
2) Type cast the iterator?

To avoid duplicate try use standard algorithm facilities like for_each() and
accumulate():


void MyOp(std::string& o)
{
// play around with o
}

for_each(MyVector.begin(), MyVector.end(), MyOp); // foreward
for_each(MyVector.rbegin(), MyVector.rend(), MyOp); // backward
[color=blue]
>
> But it iterators forward anyway. I can see one reason is because I'm[/color]
using[color=blue]
> .begin() and .end() but I would think the program wouldn't work because
> ++*MyIt on a reverse iterator *should* cause the iterator to go backwards,
> which it doesn't. This leads me to believe that even though
> reverse_iterator is derived from iterator, it's not using virtual classes,
> or something. Not sure.
>
> Can anyone come up with a way to do this without having to declare 2
> separate methods for forward reading or reverse reading, or a if block
> covering the whole for block?
>
>[/color]


Jim Langston
Guest
 
Posts: n/a
#4: Jul 23 '05

re: iterate forward OR reverse



"benben" <benhongh@hotmail.com> wrote in message
news:42c67e54$0$9732$afc38c87@news.optusnet.com.au ...[color=blue]
>
> "Jim Langston" <tazmaster@rocketmail.com> wrote in message
> news:hbmxe.3487$iv3.913@fe02.lga...[color=green]
>> I have a class I designed that stores text chat in a
>> std::vector<sd::string>. This class has a few methods to retrieve these
>> strings to be displayed on the screen.
>>
>> void ResetRead( bool Reverse, bool wordWrap ); // Resets iterator. We[/color]
> can[color=green]
>> ignore wordwrap for now.
>> std::string GetLine(); // Reads a line using iterator. Increments
>> Iterator.
>>
>> Right now it only works in Reverse, since that's the method I used first,
>> but now I want to do it using a forward iterator. I want to avoid having[/color]
> to[color=green]
>> duplicate code, as iterating forward and reverse are exactly the same
>> with[/color]
> 2[color=green]
>> diffeernces.
>>
>> 1. Declare forward iterator or reverse iterator.
>> 2. use .begin() .end() or .rbegin() .rend()
>>
>> I tried this in a test program:
>>
>> std::vector<std::string>::iterator* MyIt;
>> MyIt = (std::vector<std::string>::iterator*) new
>> std::vector<std::string>::reverse_iterator;
>> for ( *MyIt = MyVector.begin(); *MyIt != MyVector.end(); ++*MyIt )
>> std::cout << **MyIt << std::endl;[/color]
>
> Why do you:
>
> 1) Heap allocate the iterator?
> 2) Type cast the iterator?
>
> To avoid duplicate try use standard algorithm facilities like for_each()
> and
> accumulate():
>
>
> void MyOp(std::string& o)
> {
> // play around with o
> }
>
> for_each(MyVector.begin(), MyVector.end(), MyOp); // foreward
> for_each(MyVector.rbegin(), MyVector.rend(), MyOp); // backward
>[/color]

Please see my reply to Donovan. The actual code I am using uses 2 functions
within a class. The code I had shown that you responded to was a test I had
tried to see if I could use iterators as polymorphic.


benben
Guest
 
Posts: n/a
#5: Jul 23 '05

re: iterate forward OR reverse


> Please see my reply to Donovan.

Hmm, I don't see any of your reply to Donovan...or is it in another
discussion?
[color=blue]
>The actual code I am using uses 2 functions
> within a class.[/color]

I don't think I understand this. Your actual code was

std::vector<std::string>::iterator* MyIt;
MyIt = (std::vector<std::string>::iterator*) new
std::vector<std::string>::reverse_iterator;
for ( *MyIt = MyVector.begin(); *MyIt != MyVector.end(); ++*MyIt )
std::cout << **MyIt << std::endl;

So what are the 2 functions within what class you are mentioning? My
previous post suggested a better alternative.
[color=blue]
>The code I had shown that you responded to was a test I had
> tried to see if I could use iterators as polymorphic.[/color]

Iterators are not guarenteed to be polymorphic. Actually, you don't see many
virtual functions in the STL anyways.

ben


Jim Langston
Guest
 
Posts: n/a
#6: Jul 23 '05

re: iterate forward OR reverse



"benben" <benhongh@hotmail.com> wrote in message
news:42c7839b$0$20029$afc38c87@news.optusnet.com.a u...[color=blue][color=green]
>> Please see my reply to Donovan.[/color]
>
> Hmm, I don't see any of your reply to Donovan...or is it in another
> discussion?[/color]

Here is the reply I was talking about:


"Donovan Rebbechi" <abuse@aol.com> wrote in message
news:slrndcbvq2.3r8.abuse@panix2.panix.com...[color=blue]
> [SNIP]
> Use templates.
> template <typename iter>
> void printit ( iter start, iter end )
> {
> for (; start!=end; ++start)
> std::cout << *start << std::endl;
> }
>
> or you could simplify by using the standard library, and generalise to
> allow other ostreams:
>
> template <typename iter>
> void printit (iter start, iter end,std::ostream & out = std::cout)
> {
> std::copy(start,end,std::ostream_iterator(out, "\n"));
> }
>
>
> printit (MyVector.begin(),MyVector.end());
> printit (MyVector.rbegin(),MyVector.rend());[/color]

I can see how either of these methods would work in the example I had given,
simply outputting the entire vector, but the iterator needs to suvive
between calls.

class CChatBuffer
{
private:
std::vector<std::string>::reverse_iterator r_MIter; // Message Iterator
std::vector<std::string> MessageBuffer; // Buffer to hold messages from
server
public:
void ResetRead( bool Reverse );
std::string GetLine();
// Other class variables/methods not shown
};

void CChatBuffer::ResetRead( bool Reverse )
{
if ( ! Reverse )
r_MIter = MessageBuffer.rend(); // Not allowing forward yet, so set to
end
r_MIter = MessageBuffer.rbegin();
}

std::string CChatBuffer::GetLine()
{
if ( r_MIter != MessageBuffer.rend() )
return (*r_MIter++);
else
return "";
}

I can see also storing iter_start and iter_end in my class (didn't think of
that) and setting them to .rbegin() or .rend() in my ResetRead. I can't
see, however, how I could save the iterator in my class between calls of
GetLine so that GetLine knows if it's a forward or reverse iterator. I
played around with some test code just now but still couldn't figure out how
to do it.



benben
Guest
 
Posts: n/a
#7: Jul 23 '05

re: iterate forward OR reverse



"Jim Langston" <tazmaster@rocketmail.com> wrote in message
news:DZXxe.1010$x82.851@fe03.lga...[color=blue]
>
> "benben" <benhongh@hotmail.com> wrote in message
> news:42c7839b$0$20029$afc38c87@news.optusnet.com.a u...[color=green][color=darkred]
> >> Please see my reply to Donovan.[/color]
> >
> > Hmm, I don't see any of your reply to Donovan...or is it in another
> > discussion?[/color]
>
> Here is the reply I was talking about:
>
>
> "Donovan Rebbechi" <abuse@aol.com> wrote in message
> news:slrndcbvq2.3r8.abuse@panix2.panix.com...[color=green]
> > [SNIP]
> > Use templates.
> > template <typename iter>
> > void printit ( iter start, iter end )
> > {
> > for (; start!=end; ++start)
> > std::cout << *start << std::endl;
> > }
> >
> > or you could simplify by using the standard library, and generalise to
> > allow other ostreams:
> >
> > template <typename iter>
> > void printit (iter start, iter end,std::ostream & out = std::cout)
> > {
> > std::copy(start,end,std::ostream_iterator(out, "\n"));
> > }
> >
> >
> > printit (MyVector.begin(),MyVector.end());
> > printit (MyVector.rbegin(),MyVector.rend());[/color]
>
> I can see how either of these methods would work in the example I had[/color]
given,[color=blue]
> simply outputting the entire vector, but the iterator needs to suvive
> between calls.
>
> class CChatBuffer
> {
> private:
> std::vector<std::string>::reverse_iterator r_MIter; // Message Iterator
> std::vector<std::string> MessageBuffer; // Buffer to hold messages from
> server
> public:
> void ResetRead( bool Reverse );
> std::string GetLine();
> // Other class variables/methods not shown
> };
>
> void CChatBuffer::ResetRead( bool Reverse )
> {
> if ( ! Reverse )
> r_MIter = MessageBuffer.rend(); // Not allowing forward yet, so set[/color]
to[color=blue]
> end
> r_MIter = MessageBuffer.rbegin();
> }
>
> std::string CChatBuffer::GetLine()
> {
> if ( r_MIter != MessageBuffer.rend() )
> return (*r_MIter++);
> else
> return "";
> }
>
> I can see also storing iter_start and iter_end in my class (didn't think[/color]
of[color=blue]
> that) and setting them to .rbegin() or .rend() in my ResetRead. I can't
> see, however, how I could save the iterator in my class between calls of
> GetLine so that GetLine knows if it's a forward or reverse iterator. I
> played around with some test code just now but still couldn't figure out[/color]
how[color=blue]
> to do it.
>
>
>[/color]

Ok, I think I start to understand your problem now.

Basically, you are trying to dynamically reverse the access direction of an
iterator. What is in my mind, is about three different ways of achieving it.
But switching forward and reverse iterator is not a good idea because it is
typically resolved at compile time, not at runtime.

First, std::vector<T>::iterator defines a bidirectional iterator, so you can
use ++ for pointing to the next element, or -- for pointing to the previous
element.

Second, std::vector supports subscription. So using an integer to store the
index can make your class much easier to read and write.

And finally, if applicable, you can merge ResetRead and GetLine, so GetLine
now takes an additional parameter bool reverse.

And worth to note, the iterator returned by calling begin() points to the
first element, end() the ONE PAST the last element; rbegin() the last
element, and rend() the ONE BEFORE the first element.

ben


Jim Langston
Guest
 
Posts: n/a
#8: Jul 23 '05

re: iterate forward OR reverse


"benben" <benhongh@hotmail.com> wrote in message
news:42c89194$0$20855$afc38c87@news.optusnet.com.a u...[color=blue]
>
> "Jim Langston" <tazmaster@rocketmail.com> wrote in message
> news:DZXxe.1010$x82.851@fe03.lga...[color=green]
>>
>> "benben" <benhongh@hotmail.com> wrote in message
>> news:42c7839b$0$20029$afc38c87@news.optusnet.com.a u...[color=darkred]
>> >> Please see my reply to Donovan.
>> >
>> > Hmm, I don't see any of your reply to Donovan...or is it in another
>> > discussion?[/color]
>>
>> Here is the reply I was talking about:
>>
>>
>> "Donovan Rebbechi" <abuse@aol.com> wrote in message
>> news:slrndcbvq2.3r8.abuse@panix2.panix.com...[color=darkred]
>> > [SNIP]
>> > Use templates.
>> > template <typename iter>
>> > void printit ( iter start, iter end )
>> > {
>> > for (; start!=end; ++start)
>> > std::cout << *start << std::endl;
>> > }
>> >
>> > or you could simplify by using the standard library, and generalise to
>> > allow other ostreams:
>> >
>> > template <typename iter>
>> > void printit (iter start, iter end,std::ostream & out = std::cout)
>> > {
>> > std::copy(start,end,std::ostream_iterator(out, "\n"));
>> > }
>> >
>> >
>> > printit (MyVector.begin(),MyVector.end());
>> > printit (MyVector.rbegin(),MyVector.rend());[/color]
>>
>> I can see how either of these methods would work in the example I had[/color]
> given,[color=green]
>> simply outputting the entire vector, but the iterator needs to suvive
>> between calls.
>>
>> class CChatBuffer
>> {
>> private:
>> std::vector<std::string>::reverse_iterator r_MIter; // Message
>> Iterator
>> std::vector<std::string> MessageBuffer; // Buffer to hold messages
>> from
>> server
>> public:
>> void ResetRead( bool Reverse );
>> std::string GetLine();
>> // Other class variables/methods not shown
>> };
>>
>> void CChatBuffer::ResetRead( bool Reverse )
>> {
>> if ( ! Reverse )
>> r_MIter = MessageBuffer.rend(); // Not allowing forward yet, so set[/color]
> to[color=green]
>> end
>> r_MIter = MessageBuffer.rbegin();
>> }
>>
>> std::string CChatBuffer::GetLine()
>> {
>> if ( r_MIter != MessageBuffer.rend() )
>> return (*r_MIter++);
>> else
>> return "";
>> }
>>
>> I can see also storing iter_start and iter_end in my class (didn't think[/color]
> of[color=green]
>> that) and setting them to .rbegin() or .rend() in my ResetRead. I can't
>> see, however, how I could save the iterator in my class between calls of
>> GetLine so that GetLine knows if it's a forward or reverse iterator. I
>> played around with some test code just now but still couldn't figure out[/color]
> how[color=green]
>> to do it.
>>
>>
>>[/color]
>
> Ok, I think I start to understand your problem now.
>
> Basically, you are trying to dynamically reverse the access direction of
> an
> iterator. What is in my mind, is about three different ways of achieving
> it.
> But switching forward and reverse iterator is not a good idea because it
> is
> typically resolved at compile time, not at runtime.
>
> First, std::vector<T>::iterator defines a bidirectional iterator, so you
> can
> use ++ for pointing to the next element, or -- for pointing to the
> previous
> element.[/color]

Yes, I know this, but then I would need an if statement to determine weather
to increment or decrement it. I suppose the trinary function would work
though.

return ((reverse)?*r_MIter++:*r_MIter--));

Hmm.. this might work using the storing of the iterator begin and end in
variables. I'll have to test this.
[color=blue]
>
> Second, std::vector supports subscription. So using an integer to store
> the
> index can make your class much easier to read and write.[/color]

Doesnt' solve problem of wanting to use as few conditional statements as
possible.
[color=blue]
> And finally, if applicable, you can merge ResetRead and GetLine, so
> GetLine
> now takes an additional parameter bool reverse.[/color]

I could do this. But dont see how it will help. GetLine is called line by
line, not for the whole vector. It's being used (currently) to display text
to the screen using directx calls, later to write buffer to text file, or
any other thing my program needs to deal with text buffers.
[color=blue]
> And worth to note, the iterator returned by calling begin() points to the
> first element, end() the ONE PAST the last element; rbegin() the last
> element, and rend() the ONE BEFORE the first element.[/color]

Noted and understood, which is only reason same logic works for both forward
and reverse iterators as long os you use proper .begin() or .rbegin() etc...

thanks, got some testing to do.


msalters
Guest
 
Posts: n/a
#9: Jul 23 '05

re: iterate forward OR reverse




Jim Langston schreef:[color=blue]
> I have a class I designed that stores text chat in a
> std::vector<sd::string>. This class has a few methods to retrieve these
> strings to be displayed on the screen.
>
> void ResetRead( bool Reverse, bool wordWrap ); // Resets iterator. We can
> ignore wordwrap for now.
> std::string GetLine(); // Reads a line using iterator. Increments
> Iterator.
>
> Right now it only works in Reverse, since that's the method I used first,
> but now I want to do it using a forward iterator. I want to avoid having to
> duplicate code, as iterating forward and reverse are exactly the same with 2
> diffeernces.[/color]

In your code, yes. The generated code is probably slightly more
complex.
E.g. the forward iterator for vector can be a raw pointer, with the
built-in operator++. The reverse_iterator's operator++ definitely can't
be, which means it has to be a class. Of course, this method is usually
inlined so the generated code is the same.

As a result, begin() may return a T* (std::string* in your case)
while rbegin() must return a class.
[color=blue]
> Can anyone come up with a way to do this without having to declare 2
> separate methods for forward reading or reverse reading, or a if block
> covering the whole for block?[/color]

Refactor the contents of the "whole for block" into a separate
function.
You now have an if-block covering two two-line for-statements (or two
calls to std::for_each( ). Try that too, and see how nice it looks ).

Regards,
Michiel Salters

Closed Thread