Backward traversal of sequence container: stop condition

S

SpOiLeR

Hi!

Let's assume I have this

typedef std::list<std::string> string_list;
string_list sl;

If I want to traverse through this, I usually do this:

string_list::iterator i = sl.begin();
while (i != sl.end())
{
// do some work
}

This checks all strings in sl because end() gives iterator pointing to
position after the last element.

Now I want to do something a bit different:

string_list::iterator j = sl.end();
bool is_good = true;
while (j != sl.begin() && is_good)
{
is_good = IsGood (*j);
if (is_good) j--;
}

But, this leaves first string in sl unchecked (because begin() gives
iterator pointing to first element), so after looping I must do this:

if (is_good) is_good = IsGood (*j);

Is there a way to traverse backwards through string_list but to avoid this
additional check (do everything in loop)?
 
M

Matthias Kaeppler

SpOiLeR said:
Hi!

Let's assume I have this

typedef std::list<std::string> string_list;
string_list sl;

If I want to traverse through this, I usually do this:

string_list::iterator i = sl.begin();
while (i != sl.end())
{
// do some work
}

This checks all strings in sl because end() gives iterator pointing to
position after the last element.

Now I want to do something a bit different:

string_list::iterator j = sl.end();
bool is_good = true;
while (j != sl.begin() && is_good)
{
is_good = IsGood (*j);
if (is_good) j--;
}

But, this leaves first string in sl unchecked (because begin() gives
iterator pointing to first element), so after looping I must do this:

if (is_good) is_good = IsGood (*j);

Is there a way to traverse backwards through string_list but to avoid this
additional check (do everything in loop)?

Yes. Use a reverse_iterator:

string_list::reverse_iterator j = sl.rbegin();
bool is_good = true;
while( j != sl.rend() && is_good )
{
// ...
}
 
D

Dietmar Kuehl

SpOiLeR said:
Is there a way to traverse backwards through string_list but to avoid this
additional check (do everything in loop)?

The idiomatic approach is to do something like this:

string_list::reverse_iterator i = sl.rbegin();
while (i != sl.rend())
{
// do some work
}

You may recognize this code as being a small variation of code
of yours. Of course, you should probably not call 'end()' or
'rend()' in each loop but rather do something like this:

for (string_list::reverse_iterator it = sl.rbegin(), end = sl.rend();
it != end; ++it)
{
// do some work
}

Hm, thinking of it: in many cases you can use one of the existing
algorithms parameterized to do what you need.
 
M

Martijn Mulder

SpOiLeR said:
Hi!

Let's assume I have this

typedef std::list<std::string> string_list;
string_list sl;

If I want to traverse through this, I usually do this:

string_list::iterator i = sl.begin();
while (i != sl.end())
{
// do some work
}

This checks all strings in sl because end() gives
iterator pointing to position after the last element.

Now I want to do something a bit different:

string_list::iterator j = sl.end();
bool is_good = true;
while (j != sl.begin() && is_good)
{
is_good = IsGood (*j);
if (is_good) j--;
}

But, this leaves first string in sl unchecked (because
begin() gives iterator pointing to first element), so
after looping I must do this:

if (is_good) is_good = IsGood (*j);

Is there a way to traverse backwards through string_list
but to avoid this additional check (do everything in
loop)?


The iterator pair rbegin and rend do just that:

string_list::iterator j = sl.rbegin();
bool is_good = true;
while (j != sl.rend() && is_good)
{
is_good = IsGood (*j);
if (is_good) j++;
}
 
D

Dietmar Kuehl

Martijn said:
The iterator pair rbegin and rend do just that:

string_list::iterator j = sl.rbegin();

However, the type returned by 'sl.rbegin()' is not
'string_list::iterator' but 'string_list::reverse_iterator'.
 
R

Robert W Hand

Hi!

Let's assume I have this

typedef std::list<std::string> string_list;
string_list sl;

If I want to traverse through this, I usually do this:

string_list::iterator i = sl.begin();
while (i != sl.end())
Is there a way to traverse backwards through string_list but to avoid this
additional check (do everything in loop)?

Yes, std::list supports reverse iterators. Here is an example (sans
headers):

#define PRINT(X) (std::cout<<#X": "<<(X)<<'\n')

int main()
{
std::list<std::string> sl;
sl.push_back("One");
sl.push_back("Two");
sl.push_back("Three");
std::cout<<"Print list forwards:\n";
for(std::list<std::string>::const_iterator i = sl.begin();
i != sl.end(); ++i)
PRINT(*i);
std::cout<<std::endl;
std::cout<<"Now backwards!\n";
for(std::list<std::string>::reverse_iterator i = sl.rbegin();
i != sl.rend(); ++i)
PRINT(*i);
}

Output:

Print list forwards:
*i: One
*i: Two
*i: Three

Now backwards!
*i: Three
*i: Two
*i: One

There is a const_reverse_iterator available as well.
 
W

Wolfie

SpOiLeR scribbled:
If I want to traverse through this, I usually do this:

string_list::iterator i = sl.begin();
while (i != sl.end())
{
// do some work
}

This checks all strings in sl because end() gives iterator pointing to
position after the last element.
Is there a way to traverse backwards through string_list but to avoid
this additional check (do everything in loop)?

Something like this?

if (sl.size() > 0)
{
string_list::iterator i = sl.end;
do {
i--;
// do some work...
} while (i != sl.begin());
}

The size() check is there to make sure you can decrement
the iterator and use the result.
 
C

Clark S. Cox III

Let's assume I have this

typedef std::list<std::string> string_list;
string_list sl; [snip]

Now I want to do something a bit different:

string_list::iterator j = sl.end();

Note, that the first time through the loop, j == sl.end(), and you
dereference j, thus invoking undefined behavior.
bool is_good = true;
while (j != sl.begin() && is_good)
{
is_good = IsGood (*j);
if (is_good) j--;
}

But, this leaves first string in sl unchecked (because begin() gives
iterator pointing to first element), so after looping I must do this:

if (is_good) is_good = IsGood (*j);

Is there a way to traverse backwards through string_list but to avoid this
additional check (do everything in loop)?

Use reverse iterators:

string_list::reverse_iterator i = sl.rbegin();
string_list::reverse_iterator end = sl.rend();
bool is_good = true;
for(; i != end && is_good; ++i)
{
is_good = IsGood (*i);
}

You can even hide the loop altogether:

string_list::reverse_iterator begin(sl.rbegin());
string_list::reverse_iterator end(sl.rend());

//I'm assuming that IsGood is a function
bool is_good = end == std::find_if(begin, end,
std::not1(std::ptr_fun(IsGood)));

//If IsGood is an instance of an adaptable predicate, use this instead:
//bool is_good = end == std::find_if(begin, end, std::not1(IsGood));
 
C

Clark S. Cox III

SpOiLeR scribbled:



Something like this?

if (sl.size() > 0)
{
string_list::iterator i = sl.end;
do {
i--;
// do some work...
} while (i != sl.begin());
}

The size() check is there to make sure you can decrement
the iterator and use the result.

A minor nit: While that will work, use empty() instead of size():
if (!sl.empty())
{
....
}

list::empty() completes in constant time, while list::size() can be
linear (i.e. it is OK for an implementation of std::list to walk the
entire list in order to determine its size).
 
A

Andrew Koenig

Let's assume I have this

typedef std::list<std::string> string_list;
string_list sl;

If I want to traverse through this, I usually do this:

string_list::iterator i = sl.begin();
while (i != sl.end())
{
// do some work
}

This checks all strings in sl because end() gives iterator pointing to
position after the last element.

Now I want to do something a bit different:

string_list::iterator j = sl.end();
bool is_good = true;
while (j != sl.begin() && is_good)
{
is_good = IsGood (*j);
if (is_good) j--;
}

The right way to traverse a list backward is to decrement *before* accessing
elements:

string_list::iterator j = sl.end();
bool is_good = true;
while (j != sl.begin() && is_good)
{
--j;
is_good = IsGood(*j);
}
 
M

Martijn Mulder

The iterator pair rbegin and rend do just that:
However, the type returned by 'sl.rbegin()' is not
'string_list::iterator' but
'string_list::reverse_iterator'.

It's perfectly acceptable to use 'iterator' in a generic sense when it is not
clear what kind of iterator is used. For all we know, rbegin() might return a
reverse_iterator /or/ a const_reverse_iterator. What we do know is that we can
use the iterator to iterate over a range of objects.

A reverse iterator is a perfectly ordinary iterator.

What is interesting in the case of the reverse_iterators, is that applying
operator ++ to it, the result is equivalent to operator -- in an ::iterator (or
::const_iterator).
 
C

Clark S. Cox III

It's perfectly acceptable to use 'iterator' in a generic sense when it is not
clear what kind of iterator is used. For all we know, rbegin() might return a
reverse_iterator /or/ a const_reverse_iterator.

No, we know, from the original post that sl.rbegin() returns a
(std::list<std::string>::reverse_iterator), because string_list is a
typedef for (std::list said:
What we do know is that we can
use the iterator to iterate over a range of objects.

You cannot implicitly convert a
(std::list<std::string>::reverse_iterator) to a
(std::list<std::string>::iterator). No way, no how.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top