How to elegantly get the enum code from its string type

[Alf P. Steinbach]

* Paul Bibbings:

In the (near) future (C++0x), would the following achieve the same?

#include <vector>

int main()
{
std::vector<int> v(100, 22222);
decltype(v.size()) i;
for (i = 0; i < v.size(); ++i)
{
// Do something
}
}

No, that would not achieve the same.

It would achieve the opposite.

It would (generally) mix signed and unsigned, which is what you'd like to avoid.


Cheers & hth.,

- Alf

 

[Keith H Duggar]

Maybe. Just calculate :

6 * 3  + 1  = 19 % 32 = 19
6 * 8  + 3  = 51 % 32 = 19
6 * 13 + 5 =  85 % 32 = 19
6 * 18 + 7 = 115 % 32 = 19

Therefore the solution (3,1) is not unique. The results are (3,1),
(8,3), (13,5), (18,7)

Those are /congruent/ not /equal/. The this definition of
division (as opposed to modular inverse) is in terms of
/equality/ not /congruence/ relations ie you need to
remove the (% 32).

 

[Kai-Uwe Bux]

Keith H Duggar wrote: [...]
/un/signed is a finite modular group having no sign. Kai-UweBux's
nit not withstanding ie that their canonical C++ /representation/
is "positive" in a trivial sense. Once one stops wrongly thinking
of them as "positive" one also loses the temptation to use them
for "positive only" values.

This is too strong a claim. The interpretation of unsigned
types as modeling a finite modular group works well for the
three operators +, -, and *. It does not work for the operators
/, %, <, and >.

I don't see how you come to that conclusion regarding / % < >?
Given that for unsigned p and q division and modulus, p / d and
p % d, are both defined by p = d * q + r ie in terms of * and +,
and that you claim my view is appropriate for both * and +, it
seems odd to claim it "doesn't work" for / and %.

As for < and > are you saying that a finite modular group
cannot be ordered? Or that /sign/ is necessary for ordering?
I don't think so. Please demonstrate these claims.

Anyhow, it seems to me that, in the words of Leigh, / % < > all
work "just fine" for an /un/signed interpretation that is "having
no sign". Not only that, but the defining equation for / and % is
even simpler for unsigned than it is for integer viz:

unsigned
--------
Let p and d be unsigned
Let p = d * q + r for unsigned * and + and unsigned q and r
such that r < d
Then p = d * q + r has a unique solution with q called the
"quotient" and r the "remainder" and
Define p / d = q
Define p % d = r

integer
-------
Let p and d be integers
Let p = d * q + r for integer * and + and integers q and r
such that |r| < |d| and sgn(r) = sgn(p)
Then p = d * q + r has a unique solution with q called the
"quotient" and r the "remainder" and
Define p / d = q
Define p % d = r

note that constraint on r is simpler for unsigned than it is for
integer, otherwise the defining equations are the same and they
are "just fine" for unsigned as "having no sign" ie there is not
a single reference to sign (nor subtraction) in them (as there
must be for integer).

So can you please demonstrate your claim that /un/signed "does
not work for the operators /, %, <, and >"? Thanks!

Ok, I'll try.

First of all, the claim "unsigned means no-sign" is different from the
claim I was commenting on:

/un/signed is a finite modular group having no sign.

And I have trouble more with the first part of the claim than the second.
The second can be interpreted as saying that operations on unsigned types
can be explained without reference to signs. This is true (as far as I
see) but not very strong a claim since with those explanations we tend to
implicitly assume "positive" values. Nonetheless, please allow me to
focus

Except I'm saying that implicit assumption is a /problem/ when
dealing with unsigned. But, I agree let's stick to the math for
now. It's more fun and more easily "proved" LOL.

in my discussion on the "finite modular group" aspect of the unsigned
types. What I shall argue is that this point of view does not do justice
to the operators /, %, and <.

First, let me discuss the issue of order. I agree that < _can_ be defined
for unsigned values (after all it is. However, the notion of < does
not interact nicely with the additive structure of the modular
arithmetic. One very basic and important property of < for integers (or
real numbers for that matter) is _translation invariance_:

(*) for integers a, b, and c: a < b if and only if a+c < b+c

This does not hold _mod N_. In fact, a finite group cannot be totally
ordered as to satisfy (*). Taking N = 32 as a small example, we have

8 < 15

but

8 + 20 = 28
15 + 20 = 35 = 3 mod 32

thus

15+20 < 8+20

I agree. However, it is common for different groups to exhibit
different properties for operators. And translation invariance
of < is not a requirement, as you point out, of finite groups.

So, even though comparing unsigned values in C++ is meaningful, the
meaning is not really well-aligned with the interpretation of unsigned
values as representing values in a modular group.

I'm not getting this one. It seems C++ < > are well-aligned with
/finite/ modular groups.

Actually, they are not aligned at all. The only connection of the order and
the group structure is that the identity element of the group, i.e., 0 is
also the minimum with respect to the order. Other than that, the order and
the algebra are not related by any formula (like translation invariance).
That's why I'd say they are not well-aligned.

Of course, since there is no relation at all, the algebraic structure and
the order also do not _conflict_ one another.

Now hold on. The definition of division above is an /equality/
not a /congruence/ (2) and that applies for both the modular and
"regular" versions of the definition. So there is no (mod 32)
in /this/ definition of division (1). So the unique solution is
(3,1). Or am I missing something fundamental?

Well, the point under discussion is, which interpretation for the unsigned
types is appropriate. Let me try to make this question precise by
formalizing the two interpretations.

Let N denote the set of non-negative integers: {0, 1, 2, ... }. Let N_k
denote the subset {0, 1, 2, ..., 2^k-1 } of the first 2^k counting numbers.
Let M_k denote the set { [0], [1], [2], ... } of congruence classes mod 2^k.
Now let T be the set of admissible values of an unsigned type of bitlength
k. There are two obvious maps

f : T --> N_k
g : T --> M_k

The first map f corresponds to the _interpretation_ of the unsigned type T
as modeling the first 2^k counting numbers, and the map g corresponds to the
interpretation of the unsigned type T as modeling the finite modular group
with 2^k elements. To say that a certain operator of C++ is better
interpreted one way or the other can be made precise by saying that it
corresponds via f or g to a mathematical notion in N_k or M_k. E.g., the
operator + is best interpreted in the second way:

g(a+b) = g(a) + g(b) for all a,b in T
+ on the left is C++
+ on the right is addition in M_k

however, there are a,b in T such that f(a+b) != f(a)+f(b).

Conversely, there is no mathematical notion of less-than in M_k, but there
is a mathematical notion of less-than in N_k and:

a < b if and only if f(a) less than f(b)
< is C++
less than is in N_k

In this sense, the interpretation via f is more natural for operator<


Now, for the question whether (-) defined / and %. Here are the relevant
statements:

1) For any two numbers p, d in N_k with d != 0, there are unique numbers q
and r in N_k satisfying
(a) p = d * q + r
(b) r < d

2) There are elements [p], [d] in M_k with [d] != [0] such that more than
one pair ([q], [r]) exists, for which
(a) [p] = [d] * [q] + [r]
(b) r < d

So, (-) defines division with remainder in N_k but not in M_k. Now, the C++
operators / and % model division with remainder in N_k. Hence, they are best
interpreted via the map f but not via the map g:

f(a/b) and f(a%b) are the unique elements of N_k satisfying
f(a) = f(b) * f(a/b) + f(a%b) and f(a%b) < f(b)

Replacing f with g renders the statements false because uniqueness fails.

(1) There is a another common definition of "division" which /is/
based on congruence instead of equality and defines division by d
as multiplication by d^-1 the multiplicative inverse of d where

d * d^-1 =m= 1

with =m= representing congruence modulo m.

However, this definition is limited to d which are coprime to the
modulus and is more difficult to calculate so it would be rather
inconvenient for a programming language. Also the result merges
the quotient and remainder in an interesting way into a single
result even if the remainder is not 0. Finally, and importantly
for this context, the multiplicative inverse definition does
not apply at all to "regular" arithmetic on integers.

True. This definition of division makes (partial) sense in M_k, but it does
not correspond to any operator in C++.

(2) Meh while I was going back to respond to


I realized an unfortunate and careless s/integer/unsigned/g led
to this phrase "for unsigned * and +" in "Let p = d * q + r for
unsigned * and + and unsigned q and r". That is not intended to
imply the = is a congruence (it is not) nor that the itermediate
expressions in the definition are modulo something. "unsigned
p, d, q, r" just means they are members of the group.

Anyhow, the point is, in response to both the the snip above and
the bad substitution, definitions frequently involve "meta" sets,
functions, etc. So the pedantic full blown definition of modular
division would involve /integers/ proper along with /integer/
addition, multiplication, etc. So < does not trigger suspicion
for me because in the back of my mind I know there is the larger
precise definition that uses integer < if necessary.

Pulling the integer interpretation in when necessary is precisely, what I
advicate It just so happens that I think, the integer interpretation is
the _right one_ for /, %, and <.

[...]

I think we have to resolve the central issue of (-) above first.

Right. I hope, what I wrote is comprehensible.


Best

Kai-Uwe Bux

 

[Michael Doubez]

Yes that is correct not sure if I would use that trick though as I prefer
typedefs and the current alternative:

for (std::vector<int>::size_type i = 0 ...

And unless the index is significant, I prefer:
for( auto& x: v)
{
// ...
}

Alf is trolling by saying you cannot do this due to
some imaginary "bad mixing" of signed and unsigned.

Well, you can do it provided you know the rules of unsigned promotion
and every coders around you and those that will maintain the code
afterward. And if you are aware that it can produce bug that are data
dependent:

Such as:
void foo( unsigned int a, int b )
{
std::cout<<a<<'+'<<b<<((a+b>6)?" > 6":" <= 6");
}

Which will of course produce
foo( 1, 2)
1+2 <= 6
foo( 10, -6)
10+-6 <= 6
foo( 4, -6)
4+-6 > 6

I have not read the relevant thread (I stopped when the squabble
became petty) but I guess, it has already been highlighted.

 

[Öö Tiib]

* Vladimir Jovic:

    [...]

At a guess you'd need at least some thousand enum values in
order for a std::map to perform better. In that case you'd use
some system instead of mapping strings to individual values
(and you'd not use an enum). And even with the horror of
thousands of non-systematic enum values a std::map would be a
premature optimization.

Anything over a hundred, and std::map will begin to make a
significant difference.  But... how many enum's contain more
than a 100 constants?  And in how many programs will this
difference be significant?

I've written a program which generates such mappings
automatically.  I've used it in many applications.  Globally,
linear search outperforms std::map here, because most enum's
have relatively few members (and linear search has less fixed
overhead).  And done correctly, linear search allows static
initialization, which in turn means that the mapping can safely
be used in the constructors of static objects.

If you wrote a program (i assume code generator) then why you did not
sort the mapping? With sorted mapping it is a binary search.

 

[Keith H Duggar]

Yes and Alf's suggestion of using a signed type for the index actually
increases signed/unsigned mixing rather than reducing it (hence my claim he
is trolling).

You fail again. Yet another example of your lack of comprehension
and/or dishonest snipping. Here is Alf's suggestion restored:

I recommend writing that as

#include <vector>
#include <blahblah.h> // Index, size()

int main()
{
std::vector< int > v( 100, 22222 );
for( Index i = 0; i < size( v ); ++i )
{
// Do something.
}
}

Does your brain even allow you to /see/ the 'size(v)' call? (I'm
guessing it hyperactively short-circuits as soon as it tokenizes
"Index" and evaluates the remainder of the line as whitespace. You
should have a doctor examine that bug.) What type do you think it
returns? Hint, it doesn't return size_t.

KHD

 

[Ian Collins]

Using such a free function to avoid using size_type is an absurd
pointless idea but a dumb troll such as yourself will no doubt disagree.
Clue troll: size_type is a public typedef of a container, it is public
because it is *designed* to be used, it is part of a container's
interface. You are advocating against the fundamental design principles
of the language.

Can you please keep the personal apart from the technical?

 

[Kai-Uwe Bux]

Can you please keep the personal apart from the technical?

Do you really think, it would be an improvement if the above was written in
two paragraphs, one criticizing the idea of wrapping std::vector with free
functions to replace unsigned by signed types and a second paragraph purely
devoted to belligerent insults? <g>


Best

Kai-Uwe Bux

 

[Ian Collins]

Do you really think, it would be an improvement if the above was written in
two paragraphs, one criticizing the idea of wrapping std::vector with free
functions to replace unsigned by signed types and a second paragraph purely
devoted to belligerent insults?<g>

 

[Ian Collins]

You could at least learn to trim signatures!

I try to but it is an almost impossible task when dealing with some of
the people in this forum. I have blocked Keith Duggar as I am fed up
with the pointless arguments and insults.

No, it isn't. If you ever work in a team loaded with headstrong
individuals, you will quickly learn how, or you will end up on a trolley
in A&E.

 

[Michael Doubez]

And unless the index is significant, I prefer:
for( auto& x: v)
{
// ...
} [snip]
I have not read the relevant thread (I stopped when the squabble
became petty) but I guess, it has already been highlighted.

Yes and Alf's suggestion of using a signed type for the index actually
increases signed/unsigned mixing rather than reducing it [snip].

Actually, I also prefer using signed type for index in order to
preserve consistency:

for( int i = 0 ; i < size ; ++i )
{
// ...
}

Can easily be changed to

for( int i = size-i ; i >= 0 ; --i )
{
// ...
}

Which is not possible with signed type.

 

[Paul Bibbings]

No, that would not achieve the same.

It would achieve the opposite.

It would (generally) mix signed and unsigned, which is what you'd like
to avoid.

You see, what I have done here is to reply to a thread without first
noticing that more than half of it had been lost to Dr. Killfile and
then, of course, missed the point entirely.

Apologies for the noise

Regards

Paul Bibbings

 

[Michael Doubez]

Actually, I also prefer using signed type for index in order to
preserve consistency:

for( int i = 0 ; i < size ; ++i )
{
  // ...
}

Can easily be changed to

for( int i = size-i ; i >= 0 ; --i )
{
  // ...
}

Which is not possible with [un]signed type.

[corrected]

Right. But for an unsigned type the transformation is still fairly
straightforward:

for ([unsigned] i = size; i > 0; )
        {
        --i;
        // ...
        }

Technically, it is true but the loop control now depends on the loop
body.

Let's try:

for (unsigned i = size; i-- > 0; )
{

}

But it is IMO strange to initialize an index outside its bound.

Let face it, it doesn't really roll off the tongue, does it ?

 

[Keith H Duggar]

Right. I hope, what I wrote is comprehensible.

Yes, it was excellent. Thank you.

Actually, they are not aligned at all. The only connection of the order and
the group structure is that the identity element of the group, i.e., 0 is
also the minimum with respect to the order. Other than that, the order and
the algebra are not related by any formula (like translation invariance).
That's why I'd say they are not well-aligned.

Of course, since there is no relation at all, the algebraic structure and
the order also do not _conflict_ one another.

Ah ok, now I understand your point and I agree with you now on
this point. Operators < and > are neither well-aligned nor in
conflict with unsigned as implementing modular arithmetic. So
emphasizing the modular arithmetic does not do justice to the
other operations defined on unsigned. I agree.

What I took issue with earlier was the phrasing "does not work

Now hold on. The definition of division above is an /equality/
not a /congruence/ (2) and that applies for both the modular and
"regular" versions of the definition. So there is no (mod 32)
in /this/ definition of division (1). So the unique solution is
(3,1). Or am I missing something fundamental?

Well, the point under discussion is, which interpretation for the unsigned
types is appropriate. Let me try to make this question precise by
formalizing the two interpretations.

Let N denote the set of non-negative integers: {0, 1, 2, ... }. Let N_k
denote the subset {0, 1, 2, ..., 2^k-1 } of the first 2^k counting numbers.
Let M_k denote the set { [0], [1], [2], ... } of congruence classes mod 2^k.
Now let T be the set of admissible values of an unsigned type of bitlength
k. There are two obvious maps

f : T --> N_k
g : T --> M_k

The first map f corresponds to the _interpretation_ of the unsigned type T
as modeling the first 2^k counting numbers, and the map g corresponds to the
interpretation of the unsigned type T as modeling the finite modular group
with 2^k elements. To say that a certain operator of C++ is better
interpreted one way or the other can be made precise by saying that it
corresponds via f or g to a mathematical notion in N_k or M_k. E.g., the
operator + is best interpreted in the second way:

g(a+b) = g(a) + g(b) for all a,b in T
+ on the left is C++
+ on the right is addition in M_k

however, there are a,b in T such that f(a+b) != f(a)+f(b).

Conversely, there is no mathematical notion of less-than in M_k, but there
is a mathematical notion of less-than in N_k and:

a < b if and only if f(a) less than f(b)
< is C++
less than is in N_k

In this sense, the interpretation via f is more natural for operator<

Now, for the question whether (-) defined / and %. Here are the relevant
statements:

1) For any two numbers p, d in N_k with d != 0, there are unique numbers q
and r in N_k satisfying
(a) p = d * q + r
(b) r < d

2) There are elements [p], [d] in M_k with [d] != [0] such that more than
one pair ([q], [r]) exists, for which
(a) [p] = [d] * [q] + [r]
(b) r < d

So, (-) defines division with remainder in N_k but not in M_k. Now, the C++
operators / and % model division with remainder in N_k. Hence, they are best
interpreted via the map f but not via the map g:

f(a/b) and f(a%b) are the unique elements of N_k satisfying
f(a) = f(b) * f(a/b) + f(a%b) and f(a%b) < f(b)

Replacing f with g renders the statements false because uniqueness fails.

Hmm, yes this is a very clever formalization of the qualifer
"better interpreted". I'm forced to agree. unsigned is "better
interpreted" as a set of counting numbers for / and %. Thanks!

True. This definition of division makes (partial) sense in M_k, but it does
not correspond to any operator in C++.
Agreed.




Pulling the integer interpretation in when necessary is precisely, what I
advicate It just so happens that I think, the integer interpretation is
the _right one_ for /, %, and <.
Agreed.

Now agreed.

Now agreed.

Thank you, Kai-Uwe, for this excellent demonstration. This has
been very instructive. I appreciate your patience and effort ;-)

KHD