How do you suggest iterating from some size_t M down to 0?

The obvious way is:

for(size_t i = M+1; i > 0; --i){...}

Another way is to depend on wraparound...

Any suggestions?


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

u.int.32.t@gmail.com wrote:
[color=blue]
> How do you suggest iterating from some size_t M down to 0?
>
> The obvious way is:
>
> for(size_t i = M+1; i > 0; --i){...}
>
> Another way is to depend on wraparound...[/color]

There is no problem with depending on that. In C++, unsigned integer types
must wrap around.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

u.int.32.t@gmail.com wrote:[color=blue]
> How do you suggest iterating from some size_t M down to 0?[/color]

I suggest not doing it.
[color=blue]
> The obvious way is:[/color]
[color=blue]
> for(size_t i = M+1; i > 0; --i){...}[/color]

Which doesn't work. You enter the loop with i == M + 1 the
first time, which certainly isn't what is wanted.
[color=blue]
> Another way is to depend on wraparound...[/color]
[color=blue]
> Any suggestions?[/color]

The obvious solution is to use int, or long, so there are no
problems.

Another obvious point is that it is preferable -- in general,
but especially in C or C++ -- to use half open intervals. So
either M or 0 would be excluded. If it is 0, no problem. If it
is M, my usual solution (even when using signed types) is:

int i = M ;
while ( i > 0 ) {
-- i ;
// ...
}

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

u.int.32.t@gmail.com, le 21/03/2006 a écrit :[color=blue]
> How do you suggest iterating from some size_t M down to 0?
>
> The obvious way is:
>
> for(size_t i = M+1; i > 0; --i){...}
>
> Another way is to depend on wraparound...
>
> Any suggestions?[/color]
size_t i = M+1;
while(--i < M+1)
{
// ..........
}

--
Pierre Maurette



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

* u.int.32.t@gmail.com:[color=blue]
> How do you suggest iterating from some size_t M down to 0?
>
> The obvious way is:
>
> for(size_t i = M+1; i > 0; --i){...}
>
> Another way is to depend on wraparound...
>
> Any suggestions?[/color]

Generally you should simply refrain from coding loops that count down.
Let them count up. Then compute whatever value you require.

However, if you absolutely must, then do it in the most straightforward
way possible.

Not offset by 1 or other ingenious workarounds for non-existent
problems, just directly

for( size_t i = m; i != size_t(-1); --i ) { ... }

assuming you want i to have the values m, m-1, m-2, ... 2, 1, and 0.

Btw., all-uppercase names such as M should not be used except for
macros.


--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

u.int.32.t@gmail.com wrote:[color=blue]
> How do you suggest iterating from some size_t M down to 0?
>
> The obvious way is:
>
> for(size_t i = M+1; i > 0; --i){...}
>
> Another way is to depend on wraparound...
>
> Any suggestions?[/color]

size_t i=M;
do {
....
} while (i--);


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

In article <1142903000.848706.169650@z34g2000cwc.googlegroups .com>,
<u.int.32.t@gmail.com> wrote:
[color=blue]
> How do you suggest iterating from some size_t M down to 0?
>
> The obvious way is:
>
> for(size_t i = M+1; i > 0; --i){...}
>
> Another way is to depend on wraparound...
>
> Any suggestions?
>
>[/color]

case 1

i in [0,M]
for(size_t i=M;/**/;--i)
{
// ...
if(i==0) break;
}

case 2
i in (0,M]

for(size_t i=M;i!=0;--i)
{
// ...
}
case 3
i in [0,M)
use case 1 with M replaced by M-1

case 4
i in (0,M)
use case 2 with M replaced by M-1

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Alf P. Steinbach wrote:[color=blue]
>
> Generally you should simply refrain from coding loops that count down.
> Let them count up. Then compute whatever value you require.[/color]

Can you elaborate on the reason?

Moreover, even when you're counting up, you may encounter the problem of
counting up to numeric_limits<T>::max().
[color=blue]
> However, if you absolutely must, then do it in the most straightforward
> way possible.
>
> Not offset by 1 or other ingenious workarounds for non-existent
> problems, just directly
>
> for( size_t i = m; i != size_t(-1); --i ) { ... }
>
> assuming you want i to have the values m, m-1, m-2, ... 2, 1, and 0.[/color]

What if m == size_t(-1)?
[color=blue]
> Btw., all-uppercase names such as M should not be used except for
> macros.[/color]

It depends, especially for single-letter names such as M, doesn't it?
Algorithms written in math notations frequently has n going from 1 to N
(or from 0 to N-1) and such, and I have found no problems implementing
them with the same names they originally had.

--
Seungbeom Kim

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Allan W wrote:[color=blue]
> u.int.32.t@gmail.com wrote:[color=green]
> > How do you suggest iterating from some size_t M down to 0?[/color][/color]
[color=blue][color=green]
> > The obvious way is:[/color][/color]
[color=blue][color=green]
> > for(size_t i = M+1; i > 0; --i){...}[/color][/color]
[color=blue][color=green]
> > Another way is to depend on wraparound...[/color][/color]
[color=blue][color=green]
> > Any suggestions?[/color][/color]
[color=blue]
> size_t i=M;
> do {
> ....
> } while (i--);[/color]

What happens if M == 0 to start with?

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Seungbeom Kim wrote:
[color=blue]
> Alf P. Steinbach wrote:[color=green]
>>
>> Generally you should simply refrain from coding loops that count down.
>> Let them count up. Then compute whatever value you require.[/color]
>
> Can you elaborate on the reason?
>
> Moreover, even when you're counting up, you may encounter the problem of
> counting up to numeric_limits<T>::max().
>[color=green]
>> However, if you absolutely must, then do it in the most straightforward
>> way possible.
>>
>> Not offset by 1 or other ingenious workarounds for non-existent
>> problems, just directly
>>
>> for( size_t i = m; i != size_t(-1); --i ) { ... }
>>
>> assuming you want i to have the values m, m-1, m-2, ... 2, 1, and 0.[/color]
>
> What if m == size_t(-1)?[/color]

Well, you need _some_ way to end the loop, and since C++ doesn't give direct
access to the carry flag, I don't really see another way.
[color=blue][color=green]
>> Btw., all-uppercase names such as M should not be used except for
>> macros.[/color]
>
> It depends, especially for single-letter names such as M, doesn't it?
> Algorithms written in math notations frequently has n going from 1 to N
> (or from 0 to N-1) and such, and I have found no problems implementing
> them with the same names they originally had.[/color]

I also often use single-letter uppercase names for template parameters, like

template<typename T, size_t N>
class MyArray
{
};


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Alf P. Steinbach wrote:[color=blue]
> * u.int.32.t@gmail.com:[color=green]
> > How do you suggest iterating from some size_t M down to 0?[/color][/color]
[color=blue][color=green]
> > The obvious way is:[/color][/color]
[color=blue][color=green]
> > for(size_t i = M+1; i > 0; --i){...}[/color][/color]
[color=blue][color=green]
> > Another way is to depend on wraparound...[/color][/color]
[color=blue][color=green]
> > Any suggestions?[/color][/color]
[color=blue]
> Generally you should simply refrain from coding loops that
> count down. Let them count up. Then compute whatever value
> you require.[/color]

It depends. Generally, you should use the most natural form.
If the loop is "do n times", where the index is not used, the
most natural form is to use the number of times remaining to be
done as the loop invariant, which results in something like:

for ( int count = N ; count > 0 ; -- count ) ...
[color=blue]
> However, if you absolutely must, then do it in the most
> straightforward way possible.[/color]
[color=blue]
> Not offset by 1 or other ingenious workarounds for
> non-existent problems, just directly[/color]
[color=blue]
> for( size_t i = m; i != size_t(-1); --i ) { ... }[/color]
[color=blue]
> assuming you want i to have the values m, m-1, m-2, ... 2, 1,
> and 0.[/color]

That's a nice solution too, although it hadn't occurred to me.
Probably because the only times I use size_t is when I'm
dealing with a container, and if I'm not using iterators, then
it's because I need the index. And as you say, when dealing
with indexes, it's almost always more natural to start at the
beginning.
[color=blue]
> Btw., all-uppercase names such as M should not be used except
> for macros.[/color]

Or, when posting code, to represent arbitrary (constant) values?
(I don't know, but it's a convention I've seen occasionally. It
doesn't mean that such a symbol will occur in an actual
program.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

* Seungbeom Kim:[color=blue]
> Alf P. Steinbach wrote:[color=green]
>> Generally you should simply refrain from coding loops that count down.
>> Let them count up. Then compute whatever value you require.[/color]
>
> Can you elaborate on the reason?
>
> Moreover, even when you're counting up, you may encounter the problem of
> counting up to numeric_limits<T>::max().
>[color=green]
>> However, if you absolutely must, then do it in the most straightforward
>> way possible.
>>
>> Not offset by 1 or other ingenious workarounds for non-existent
>> problems, just directly
>>
>> for( size_t i = m; i != size_t(-1); --i ) { ... }
>>
>> assuming you want i to have the values m, m-1, m-2, ... 2, 1, and 0.[/color]
>
> What if m == size_t(-1)?[/color]

The code is well-behaved for this case, as for any other.

However, if you want to enumerate all bit patterns that can occur for a
size_t, or for any integral type T, in a single loop, then you need some
loop state in addition to a T, whether T is int or char or size_t or...

One technique is to essentially duplicate the loop; do one value as a
special case first, and then a general loop to do the rest.

[color=blue][color=green]
>> Btw., all-uppercase names such as M should not be used except for
>> macros.[/color]
>
> It depends, especially for single-letter names such as M, doesn't it?[/color]

No. Especially not for single-letter names.

[color=blue]
> Algorithms written in math notations frequently has n going from 1 to N
> (or from 0 to N-1) and such,[/color]

Interesting. Let's use math notation for everything in C++. Darn, my
text editor won't let me move symbols around, and where the &/()=% are
the greek letters?

[color=blue]
> and I have found no problems implementing
> them with the same names they originally had.[/color]

Heh. :-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Allan W wrote:[color=blue]
> size_t i=M;
> do {
> ....
> } while (i--);[/color]

Many thanks for this - the best of all suggestions. I hadn't thought of
it myself. However, I would prefer using a for loop, to make it a bit
shorter and also (more important) make i local to the loop:

// iterate over (M,0]
for ( unsigned i=M; i--; )
....

// iterate over [M,0]
for ( unsigned i=M+1; i--; )
....

Regards,
Ivan


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Alf P. Steinbach wrote:

[...][color=blue][color=green]
> > Algorithms written in math notations frequently has n going
> > from 1 to N (or from 0 to N-1) and such,[/color][/color]
[color=blue]
> Interesting. Let's use math notation for everything in C++.
> Darn, my text editor won't let me move symbols around, and
> where the &/()=% are the greek letters?[/color]

Well, C++ officially allows Unicode in symbol names, even if not
all compilers are up to date. There are surely editors out
there which can handle Unicode. And both Windows and Linux
allow remapping the keyboard, to get the characters you want.

So we're getting there, at least in theory. I'm just waiting
for the day I have a function with two local variables, on named
A, and the other with the Greek capital letter Alpha. Beats
using O0 and OO hands down.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Alf P. Steinbach wrote:
if you want to enumerate all bit patterns that can occur for a[color=blue]
> size_t, or for any integral type T, in a single loop, then you need some
> loop state in addition to a T, whether T is int or char or size_t or...[/color]

No, you dont:

unsigned int i = 0;
do {
foo(i);
} while (0 != ++i);

The only case in which you need additional loop state is when you use a
test-first
loop (as that must support lengths [0..N] inclusive, i.e. N+1 states)

HTH,
Michiel Salters


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

> > u.int.32.t@gmail.com wrote:[color=blue][color=green][color=darkred]
> > > How do you suggest iterating from some size_t M down to 0?[/color][/color][/color]
[color=blue]
> Allan W wrote:[color=green]
> > size_t i=M;
> > do {
> > ....
> > } while (i--);[/color][/color]

kanze wrote:[color=blue]
> What happens if M == 0 to start with?[/color]

Then the loop only iterates once.

Did you read the original request to mean anything else?


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Allan W wrote:[color=blue][color=green][color=darkred]
> > > u.int.32.t@gmail.com wrote:
> > > > How do you suggest iterating from some size_t M down to 0?[/color][/color][/color]
[color=blue][color=green]
> > Allan W wrote:[color=darkred]
> > > size_t i=M;
> > > do {
> > > ....
> > > } while (i--);[/color][/color][/color]
[color=blue]
> kanze wrote:[color=green]
> > What happens if M == 0 to start with?[/color][/color]
[color=blue]
> Then the loop only iterates once.[/color]
[color=blue]
> Did you read the original request to mean anything else?[/color]

I'm not sure what the original request really wanted. I do know
that in C++, I only use half-open intervals, e.g. [0...M), or in
this case, either [M...0) (which isn't a problem) or (M...0].

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

>>>> u.int.32.t@gmail.com wrote:[color=blue][color=green][color=darkred]
>>>>> How do you suggest iterating from some size_t M down to 0?[/color][/color][/color]
[color=blue][color=green][color=darkred]
>>> Allan W wrote:
>>>> size_t i=M;
>>>> do {
>>>> ....
>>>> } while (i--);[/color][/color][/color]
[color=blue][color=green]
>> kanze wrote:[color=darkred]
>>> What happens if M == 0 to start with?[/color][/color][/color]
[color=blue]
> Allan W wrote:[color=green]
>> Then the loop only iterates once.
>> Did you read the original request to mean anything else?[/color][/color]

kanze wrote:[color=blue]
> I'm not sure what the original request really wanted. I do know
> that in C++, I only use half-open intervals, e.g. [0...M), or in
> this case, either [M...0) (which isn't a problem) or (M...0].[/color]

For me that is the most frequent type of loop, but not the
only kind. I try not to lock myself into either technique --
sometimes we want test-at-end (because we always want to
iterate at least once) and sometimes test-at-start (because
we don't).

The original request said, "iterating from some size_t M down to 0"
which I believe means that it will always iterate at least once,
since by definition any size_t is >=0, and I take "down to 0"
to include 0. However, with test-at-start, the interval (M..0] is
simply

for (size_t i=M; i--; ) {
...
}

which is equivalent to the while loop you posted on Mar 21,
and the interval [M..0) is

for (size_t i=M; i; --i) {
...
}


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

u.int.32.t@gmail.com wrote:[color=blue]
> How do you suggest iterating from some size_t M down to 0?[/color]

Don't. Loops other than [a, b) in C++ is really ackward and iterating
over an inclusive range is worse than kicking a puppy. For [-M, 0], I
would transform that to [0, M+1) and use:

const size_t end = M+1;
for (size_t i = 0; i != end; ++i)
cout << (end-1)-i;
[color=blue]
> The obvious way is:
>
> for(size_t i = M+1; i > 0; --i){...}
>
> Another way is to depend on wraparound...
>
> Any suggestions?[/color]

Here's one I've written but never used (it's been tested though):

#define inclusive_for(init, cond, inc) \
if (bool ar3_d0n3_ = false) {} \
else for (init; !ar3_d0n3_; (ar3_d0n3_ = !(bool)(cond)) || ((inc),
false))

inclusive_for (size_t i = M, i != 0, --i)
cout << i;

If you *really* need an inclusive loop without generating any overflows
at all.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]