Reverse Iteration

[Tomás]

Looking at the following function:

#include <cstddef>
#include <iostream>

template<typename T, std::size_t len>
void PrintOutStrings( const char* const (&Array)[len] )
{
for (std::size_t i = 0; i < len; ++i) std::cout << Array;
}

Let's say we want to print the strings out backwards... how do you
usually do it? I've a way of doing it and I'm wondering what you think of
it?

#include <cstddef>
#include <iostream>

template<typename T, std::size_t len>
void PrintOutStringsBackwards( const char* const (&Array)[len] )
{
for (std::size_t i = len - 1; ~i; --i) std::cout << Array;
}

My rationale here is that the counter variable "i" will get smaller and
smaller. It will become 0, and then when it's decremented again, it will
become 0xFFFF (or 0xFFFFFFFF, or 0xFFFFFFFFFFFFFFF...). If we then invert
the bits using the "~" operator, then we'll get 0; so the loop should
stop then.

Any potential pitfalls?

A quiet nod of approval would do me.

-Tomás

 

[Ivan Vecerina]

: Let's say we want to print the strings out backwards... how do you
: usually do it? I've a way of doing it and I'm wondering what you think
of
: it?
:
: #include <cstddef>
: #include <iostream>
:
: template<typename T, std::size_t len>
: void PrintOutStringsBackwards( const char* const (&Array)[len] )
: {
: for (std::size_t i = len - 1; ~i; --i) std::cout << Array;
: }
:
: My rationale here is that the counter variable "i" will get smaller and
: smaller. It will become 0, and then when it's decremented again, it will
: become 0xFFFF (or 0xFFFFFFFF, or 0xFFFFFFFFFFFFFFF...). If we then
invert
: the bits using the "~" operator, then we'll get 0; so the loop should
: stop then.
:
: Any potential pitfalls?

It is ok and portable, but excessively "smart" in my opinion,
with too many "moving parts" (/opportunities for error):
if a signed integer type is used, code will be broken

I find the following loop to be simpler and more "natural":
for ( std::size_t i = len; i-- ; ) std::cout << Array;

: A quiet nod of approval would do me.

Personally, I would not accept your version in a code review.



Cheers,
Ivan

 

[Dietmar Kuehl]

template<typename T, std::size_t len>
void PrintOutStrings( const char* const (&Array)[len] )
{
for (std::size_t i = 0; i < len; ++i) std::cout << Array;
}

Actually, I consider the above function already to be "wrong". The
"correct" version looks like this:

template<typename T, std::size_t len>
void PrintOutStrings( const char* const (&Array)[len] )
{
std::copy(array + 0, array + len,

Let's say we want to print the strings out backwards...

.... which kind of prescribes how the reversed version will look like:

template<typename T, std::size_t len>
void PrintOutStrings( const char* const (&Array)[len] )
{
std::copy(std::reverse_iterator<char const*>(array + len),
std::reverse_iterator<char const*>(array + 0),

for (std::size_t i = len - 1; ~i; --i) std::cout << Array;

I think this should work. However, the more conventional version
is actually much less error prone and requires less thinking about:

for (std::size_t i = len; i--; ) std::cout << Array;

 

[Andrew Koenig]

I think this should work. However, the more conventional version
is actually much less error prone and requires less thinking about:

for (std::size_t i = len; i--; ) std::cout << Array;

I don't think there's anything specifically wrong with this approach.
However, it doesn't translate to the iterator domain, because it generates
an off-the-beginning value. Doing so is OK for integers, but not for
iterators.

For that reason, I would be inclined to write the loop as follows:

{ std::size_t i = len; while (i) { --i; std::cout << Array; }}

Yes it's a little longer, but (for example) you can translate it to

{ const Element* p = Array + len; while (p != Array) { --p; std::cout <<
*p; }}

without affecting its validity.

 

[Tomás]

Personally, I would not accept your version in a code review.

That input is very helpful. I consider myself to be a very proficient
programmer, but I've never been employed as a programmer or had to submit a
project, so it's good to see where "The Boss" will reject my code.

Maybe I'm being naive here, but what if I replace my code with the
following:

#include <cstddef>
#include <iostream>

template<typename T, std::size_t len>
void PrintOutStringsBackwards( const char* const (&Array)[len] )
{
/***************************************************
The array has "len" amount of items; therefore the
final item's index is "len - 1". This shall be
our starting value for "i".
***************************************************/

/***************************************************
Before each iteration, the following expression is
tested to be true: "~i".
The expression will be false when "i" had the
value 0... but was then decremented. On all platforms
(for unsigned types), 0 decremented becomes 0xFF.
The invertor operator then inverts all bits, turning
0xFF into 0, which is false.
***************************************************/

for (std::size_t i = len - 1; ~i; --i) std::cout << Array;
}


Are the comments enough to make my boss accept the code?

How about if I do this:

inline
bool NotGoneBelowZero(std::size_t const i)
{
return ~i;
}

And then change the loop to:

for (std::size_t i = len - 1; NotGoneBelowZero(i); --i)


Why am I so anxious to use this code? I suppose I'm an efficiency freak. For
instance, you'll almost never see me use the postincrement/postdecrement
operators. Instead of:

k = j++;

I'll write:

k = j;
++j;

Because I think to myself, "Why invite the creation of an unnecessary
temporary"?

Another thing I wanted to try for efficiency reasons was to replace the
boolean OR operator with the bitwise OR operator in "if" statements:

char* a;
char* b;
....
....
if (a || b)
{

}


I created a thread here recently asking if it would be:
a) more efficient
b) advisable

to replace that with:

if ( a | b )


but sadly I never got a response.


-Tomás

 

[Ivan Vecerina]

: :
: > I think this should work. However, the more conventional version
: > is actually much less error prone and requires less thinking about:
: >
: > for (std::size_t i = len; i--; ) std::cout << Array;
:
: I don't think there's anything specifically wrong with this approach.
: However, it doesn't translate to the iterator domain, because it
generates
: an off-the-beginning value. Doing so is OK for integers, but not for
: iterators.

First of all, in the iterator case, maybe we should be using
reverse_iterator instead of iterating backwards ?


: For that reason, I would be inclined to write the loop as follows:
:
: { std::size_t i = len; while (i) { --i; std::cout << Array; }}

Is it worth using an extra scope only to replace the <for> with a <while>
?

: Yes it's a little longer, but (for example) you can translate it to
:
: { const Element* p = Array + len; while (p != Array) { --p; std::cout
: << *p; }}
:
: without affecting its validity.

[ could use a for(; as well ]


I get that the point is to avoid decrementing the iterator past "begin".
But the translation seems non-trivial to me in any case,
and I am unsure of the overall readability.


In the iterator case, in practice, I tend to check for the
empty case upfront, then write:
const Element* p = Array+len;
do {
std::cout << *p;
} while( --p != Array );
When some kind of loop setup is required, this comes naturally
with index-based iterations as well.


Would anyone want to write:

for( const Element* p = Array+len ; p!=Array && (--p,true) ; )

?
Quite a particular idiom, but I would still prefer it to your example,
as it keeps all the iteration logic within the for statement...



Let's all hope for better for_each / functor support in C++0x,
as it seems pathetic to have so many ways to iterate backwards,
none appearing to be clearly superior.

Regards,
Ivan

 

[Ben Pope]

Personally, I would not accept your version in a code review.

That input is very helpful. I consider myself to be a very proficient
programmer, but I've never been employed as a programmer or had to submit a
project, so it's good to see where "The Boss" will reject my code.

Maybe I'm being naive here, but what if I replace my code with the
following:

#include <cstddef>
#include <iostream>

template<typename T, std::size_t len>
void PrintOutStringsBackwards( const char* const (&Array)[len] )
{
/***************************************************
The array has "len" amount of items; therefore the
final item's index is "len - 1". This shall be
our starting value for "i".
***************************************************/

/***************************************************
Before each iteration, the following expression is
tested to be true: "~i".
The expression will be false when "i" had the
value 0... but was then decremented. On all platforms
(for unsigned types), 0 decremented becomes 0xFF.
The invertor operator then inverts all bits, turning
0xFF into 0, which is false.
***************************************************/

for (std::size_t i = len - 1; ~i; --i) std::cout << Array;
}


Are the comments enough to make my boss accept the code?

I doubt it. Code should be self documenting for the most part. A
simple for loop should not require bit operations like that, or a
comment spanning over 10 lines of comment just for the loop variable.

How about if I do this:

inline
bool NotGoneBelowZero(std::size_t const i)
{
return ~i;
}

And then change the loop to:

for (std::size_t i = len - 1; NotGoneBelowZero(i); --i)

Although the function name is sort of descriptive, the mere presence of
the function is strange.

It's also misleading. -2 is below zero, and size_t i = -2 would not be
caught. If you were doing:
for (std::size_t i = len - 1; i -= 2

Why am I so anxious to use this code? I suppose I'm an efficiency freak. For
instance, you'll almost never see me use the postincrement/postdecrement
operators. Instead of:

k = j++;

I'll write:

k = j;
++j;

Because I think to myself, "Why invite the creation of an unnecessary
temporary"?

I'm sure the compiler will optimise these minutiae.

Another thing I wanted to try for efficiency reasons was to replace the
boolean OR operator with the bitwise OR operator in "if" statements:

char* a;
char* b;
...
...
if (a || b)
{

}


I created a thread here recently asking if it would be:
a) more efficient
b) advisable

to replace that with:

if ( a | b )


but sadly I never got a response.

My guess would be that it depends on the value of a.

I think your concerns about efficiency are vastly over estimated.

You'd do much better to concern yourself with architectural and
algorithmic problems then these which may or may not shave off a clock
cycle or two.

Personally, I think the following is really neat to solve your problem,
it's partly stolen from Dietmar, but I use reverse_copy instead of
reverse iterators, which are just odd:

#include <string>
#include <iostream>
#include <algorithm>

int main() {
int arr[4] = {0,1,2,3};

std::cout << "forwards" << "\n";
std::copy(arr, arr+4,
std:stream_iterator<int>(std::cout, "\n"));

std::cout << "backwards" << "\n";
std::reverse_copy(arr, arr+4,
std:stream_iterator<int>(std::cout, "\n"));
}


Ben Pope

 

[Dietmar Kuehl]

for (std::size_t i = len; i--; ) std::cout << Array;

I don't think there's anything specifically wrong with this approach.
However, it doesn't translate to the iterator domain, because it generates
an off-the-beginning value.

However, typically the algorithms cannot be translated between integer
and iterator based versions easily anyway: when not using an iterator,
the integer is generally necessary for some reason, e.g. because the
relative offset between elements is important. As stated in my
article, I would use an algorithm or, although this was not stated,
an iterator based loop unless I specifically need the iterator. And
the obvious approach to traverse in the reverse direction is actually
to use the same algorithm like when traversing in the normal direction
but with reverse iterators.

 

[Ivan Vecerina]

:
: > Personally, I would not accept your version in a code review.
:
: That input is very helpful. I consider myself to be a very proficient
: programmer, but I've never been employed as a programmer or had to
submit a
: project, so it's good to see where "The Boss" will reject my code.
:
: Maybe I'm being naive here, but what if I replace my code with the
: following:
....
: Are the comments enough to make my boss accept the code?


Still a reject.
Why use all the extra commenting when a concise alternative exists?

: How about if I do this:
:
: inline
: bool NotGoneBelowZero(std::size_t const i)
: {
: return ~i;
: }
:
: And then change the loop to:
:
: for (std::size_t i = len - 1; NotGoneBelowZero(i); --i)

Still a reject.
Using a custom function only adds to the confusion, for no benefit.

: Why am I so anxious to use this code? I suppose I'm an efficiency freak.

You may well find out that i--
is actually evaluated faster than ~--i !!



: For instance,
: you'll almost never see me use the postincrement/postdecrement
: operators. Instead of:
:
: k = j++;
:
: I'll write:
:
: k = j;
: ++j;

That makes sense for user-defiend types. Not for built-ins.


To get a most efficient bakwards loop, you would probably want
to use a decremented pointer rather than an index ( the p
offset calculation is often relatively expensive).
But the best result is likely to depend on the specific compiler
that you are using.

: Another thing I wanted to try for efficiency reasons was to replace the
: boolean OR operator with the bitwise OR operator in "if" statements:
:
: char* a;
: char* b;
: ...
: ...
: if (a || b)
: {
:
: }
:
:
: I created a thread here recently asking if it would be:
: a) more efficient
: b) advisable
:
: to replace that with:
:
: if ( a | b )
:
: but sadly I never got a response.

My bet would be that the latter will rather slow things down.
But again, you'd have to measure this on a specific platform.


I would strongly recommend postponing creative and heroic
optimization efforts until you have a piece of code that
really needs a runtime speed boost.
Then investigate it seriously, and get advice (here or
elsewhere).

Or at least first study the current state of the art.
http://www.google.com/search?q=premature+optimization+unnecessary+optimization+C++


Cheers,
Ivan

 

[Dietmar Kuehl]

Maybe I'm being naive here, but what if I replace my code with the
following:

#include <cstddef>
#include <iostream>

template<typename T, std::size_t len>
void PrintOutStringsBackwards( const char* const (&Array)[len] )
{
/***************************************************
The array has "len" amount of items; therefore the
final item's index is "len - 1". This shall be
our starting value for "i".
***************************************************/

/***************************************************
Before each iteration, the following expression is
tested to be true: "~i".
The expression will be false when "i" had the
value 0... but was then decremented. On all platforms
(for unsigned types), 0 decremented becomes 0xFF.
The invertor operator then inverts all bits, turning
0xFF into 0, which is false.
***************************************************/

for (std::size_t i = len - 1; ~i; --i) std::cout << Array;
}


Are the comments enough to make my boss accept the code?

Personally, I would reject the code for the simple reason that a
trivial operation needs far too much explanation! I need *no*
comment at all for the simple loop

for (std::size_t i = len; i--; ) std::cout << Array;

and I would expect most professional programmers to gather the
intend and operation immediately (well, I know that many
professional programmers are not up to the task of understanding
this loop immediately but I consider this not a fault of the code
but the fault of the person who made them professional programmers
in the first place). As stated before, to make it plain what the
intend is, I would use

std::copy(Array.rbegin(), Array.rend(),
std:stream_iteartor<char const*>(std::cout));

(this is a different version assuming that the sequence is
maintained by a container).

How about if I do this:

inline
bool NotGoneBelowZero(std::size_t const i)
{
return ~i;
}

And then change the loop to:

for (std::size_t i = len - 1; NotGoneBelowZero(i); --i)

This is, IMO, going from bad to worse: now I need to look-up even
another function to figure out what this trivial operation does!

Why am I so anxious to use this code? I suppose I'm an efficiency freak.

Then use the algorithms! The can do interesting optimizations you
might not even dream up.

Another thing I wanted to try for efficiency reasons was to replace the
boolean OR operator with the bitwise OR operator in "if" statements:

char* a;
char* b;
...
...
if (a || b)
{

}


I created a thread here recently asking if it would be:
a) more efficient
b) advisable

to replace that with:

if ( a | b )

but sadly I never got a response.

The semantics of 'a || b' and 'a | b' are different. For example,
'if (a == 0 || a->next == val)' can work while the result of changing
the expression to use the bitwise operator is rather likely to fail.
In general, it is almost always better to write the easy to read
code because this version tends to be correct and also tends to
survive maintenance correct. Tricky code is much easier to break.
Optimization is in order when profiling shows the need. Only where
equivalent approaches are obvious (e.g. using 'i++' or '++i' without
using the result of the expression) the typically more efficient
(i.e. '++i') should be used.

In addition, it always pays off to measure: if you are performance
freak, you would *not* use your "clever" approach as it is, at least
on my machine, consistently slower than the other approach:

kuehl@codegard:/tmp/c++> time tst 2
test2: 1000000000

real 0m11.128s
user 0m10.981s
sys 0m0.072s
kuehl@codegard:/tmp/c++> time tst 1
test1: 1000000000

real 0m11.489s
user 0m11.353s
sys 0m0.084s

.... and here is the source:

#include <vector>
#include <iostream>

enum { size = 10000000 };
enum { repeat = 100 };

void test1()
{
int array[size];
std::size_t count = 0;
for (std::size_t c = 0; c < repeat; ++c)
{
for (std::size_t i = size - 1; ~i; --i)
array = 1;
for (std::size_t i = size - 1; ~i; --i)
count += array;
}
std::cout << "test1: " << count << "\n";
}

void test2()
{
int array[size];
std::size_t count = 0;
for (std::size_t c = 0; c < repeat; ++c)
{
for (std::size_t i = size; i--; )
array = 1;
for (std::size_t i = size; i--; )
count += array;
}
std::cout << "test2: " << count << "\n";
}

int main(int ac, char* av[])
{
ac == 1 || av[1][0] == '1'? test1(): test2();
}

 

[JustBoo]

On Wed, 08 Feb 2006 19:27:21 +0100, Dietmar Kuehl

Wow. "Now that's what I'm talkin' about!"

When I have understanding of computers I shall be the Supreme Being!
- Evil, Time Bandits