Another String reversal question

[Siemel Naran]

int StringReverse(char* psz)
{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;

}

Others have good answers. Just one other unrelated thing. For functions
returning an integer, return of zero means no error, and return of any other
number (positive or negative) means error. Are you sure you want to return
1?

 

[John Potter]

Is this variant better?
(works with any traits/allocators or other
implementation of string that do not use them)

template<class String>
String StringReverse2( const String & input )
{
String retVal;
for( String::const_iterator idx = input.end()-1;
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
retVal.push_back( *input.begin() );
return retVal;
}

It crashes on an empty string. Correctness is required before we
can talk about other things.

John

 

[John Potter]

Does it? If strlen(psz)==0 then q==psz+0-1 and so q==psz-1. q is not a
pointer to a valid object, but it's never going to get dereferenced since
!p<q. That makes it a singular pointer, no? I think that's the term.

No. A singular pointer is not initialized. It is also invalid to look
at the singular value. A past-the-end or null pointer is not
dereferenceable but it is valid to look at the value.

int* p;
if (p) // undefined behavior.

int x;
int* p(&x);
p + 1; // one past the end of the int x is valid
p + 2; // undefined behavior for just trying to compute it
p - 1; // same thing
p = new int;
delete p;
if (p) // undefined behavior

I suppose the question I'm asking is, does pointer arithmetic which gives
rise to a singular pointer constitute undefined behaviour?

Yes.

John

 

[kanze]

Artie Gold wrote:

[snip]

The function has a bug (the subtraction of 1 is faulty), but as
long as he dosn't feed an empty char array to it, it should not
crash.
Hmmm. The subtraction of 1 seems right to me.

strlen returns the length without the terminating '\0'. If he
subtracts 1, then he will swap the first character with the
one-before-last character. If the goal is to revert the string then
I call this behaviour a bug.

Perhaps I'm dense today, but...

If strlen(some_string) is x, the last character is some_string[x - 1]
or some_string + x - 1, no?

And if strlen( someString ) is 0, there is no last character, and the
expression someString + strlen( someString ) - 1 is someString - 1,
which is undefined behavior.

 

[Francis Glassborow]

In message

Others have good answers. Just one other unrelated thing. For functions
returning an integer, return of zero means no error, and return of any other
number (positive or negative) means error. Are you sure you want to return
1?

I am unconvinced of this. Where a function's return will simply denote
whether it succeeded or not a C++ programmer would use bool and a pre
C99 C programmer would use 1 for true and 0 for false (which neatly maps
to the conversions of true and false values of bool).

However the catch is that when a return value does not denote simple
success/failure but is returning an error code, 0 is used for no errors
and other values are used to distinguish the different modes of failure.

A user needs to know which convention is in operation if they are using
such functions. This is a case where understanding of the issues and the
chosen solutions is essential.

 

[kanze]

Yes, attempts to write to a string literal have been undefined
behaviour for a couple of decades. And as from 1996 the type of a
string literal in C++ has been 'array of const char'.

Just a nit, but a couple of decades would be 2 or more -- more than 20
years. In fact, writing to a string literal was legal and had well
defined semantics in K&R 1, and only became illegal with the C standard,
in 1989. Almost a decade and a half, but not quite a couple of decades.

But as a I said, it's a nit -- even 15 years is long enough for people
not to have leared what was always a bad programming technique.

 

[Artie Gold]

Artie Gold wrote:

[snip]

The function has a bug (the subtraction of 1 is faulty), but as
long as he dosn't feed an empty char array to it, it should not
crash.

Hmmm. The subtraction of 1 seems right to me.

strlen returns the length without the terminating '\0'. If he
subtracts 1, then he will swap the first character with the
one-before-last character. If the goal is to revert the string then
I call this behaviour a bug.

Perhaps I'm dense today, but...

If strlen(some_string) is x, the last character is some_string[x - 1]
or some_string + x - 1, no?

And if strlen( someString ) is 0, there is no last character, and the
expression someString + strlen( someString ) - 1 is someString - 1,
which is undefined behavior.

Of course. But that issue has been hammered out elsethread. ;-)

Cheers,
--ag

 

[Karl Heinz Buchegger]

Artie Gold wrote:
[snip]

The function has a bug (the subtraction of 1 is faulty), but
as long as he dosn't feed an empty char array to it, it should not crash.


Hmmm. The subtraction of 1 seems right to me.

strlen returns the length without the terminating '\0'.
If he subtracts 1, then he will swap the first character
with the one-before-last character. If the goal
is to revert the string then I call this behaviour a bug.

Perhaps I'm dense today, but...

No. It's me.
Damned counting.
I knew that climbing down from the trees was a failure

 

[Thomas Hansen]

Which shows that the problem is just too difficult for the average
programmer. The first thing you do is dereference end(). Try
this test to either get a fault or unexpected results.

If you look at one of the function examples just above you would have
seen that I did it like this in at least one of the functions...

for( myString::const_iterator idx = input.end()-1;

....but I should have tested more thourough before posting...
[snip]

 

[Siemel Naran]

I should have said zero usually means no error.

I am unconvinced of this. Where a function's return will simply denote
whether it succeeded or not a C++ programmer would use bool and a pre
C99 C programmer would use 1 for true and 0 for false (which neatly maps
to the conversions of true and false values of bool).

Yes, for functions returning bool the convention is true means success (and
true maps to a non-zero integer). And third, functions could throw to
signify an error. For functions returning int the convention is zero means
success.

 

[Siemel Naran]

On 18 Dec 2003 21:47:37 -0500, "George van den Driessche"

int x;
int* p(&x);
p + 1; // one past the end of the int x is valid
Fine.

p + 2; // undefined behavior for just trying to compute it
p - 1; // same thing

Fine, but what could possibly go wrong. My compilers don't complain or
crash (ie. they do the right thing). But I guess other platforms could mess
up?

 

[John Potter]

On 19 Dec 2003 02:40:03 -0500, there came a drop of sanity from John
Potter <[email protected]> containing:

If you look at one of the function examples just above

There is no code above that which was written by you. If you look at
the rest of my post, you will find that everything you wrote is
defective.

you would have
seen that I did it like this in at least one of the functions...

for( myString::const_iterator idx = input.end()-1;

Which decrements begin when the string is empty. Which undefined
behavior do you prefer?

Running loops backwards with subscripts is fairly easy, with
pointers/iterators is fairly hard. The library has reverse_iterators
because getting it right is non-trivial. It also has algorithms because
over 80% of non-counting loops written are defective. That includes
those published in textbooks. I always assume that my first attempt is
likely wrong. It is a rare pleasure when that assumption is wrong.

John

 

[Francis Glassborow]

In message

Fine, but what could possibly go wrong. My compilers don't complain or
crash (ie. they do the right thing). But I guess other platforms could mess
up?

UB is generally an issue for the executable not for the compiler. That
is the point, the compiler is required to accept the code unless it can
demonstrate that it will always fail and that the code will always be
executed (rather hard unless it is working as an interpreter)

When we come to execution time either p-1 or p+2 maybe pointer into
memory that does not belong to the process, and the consequences can be
anything (on protected memory systems it usually results in the process
being aborted). If you look as if you are about to touch memory you do
not own then the OS is entitled to do whatever it wants -- but that
action is outside the domain of the C++ Standard and so is undefined (by
C++)

 

[Francis Glassborow]

In message

Yes, for functions returning bool the convention is true means success (and
true maps to a non-zero integer). And third, functions could throw to
signify an error. For functions returning int the convention is zero means
success.

I think that I probably have an unusually extensive reading of relevant
literature but cannot recall any such statement being made by good, bad
or indifferent authors. Perhaps you could jog my memory with a few
references.

While I would give 'use bool to report success/failure' as a very strong
guideline, it is not an option when writing code that needs to be
compatible to all versions of C and to C++ so I continue to have strong
doubts that any convention such as the one you claim exists in the wider
C & C++ programming community.

Note that zero denotes success for return from main, and it also does so
for comparison functions passed to qsort and bsearch but it does not do
so for comparison functions passed to the various C++ sort and search
functions.

 

[Jeff Schwab]

John,

What do you mean "one past the end of the int x?" Are you sure that's
valid? I know the address marking the end of an array is always valid...

Fine, but what could possibly go wrong. My compilers don't complain or
crash (ie. they do the right thing).

Siemel,

That's not necessarily the right thing, even if it is what you expect.

But I guess other platforms could mess up?

No, the platform isn't messing up, you are. There may not be any
address with value p + 2. The very act of computing it could cause a
bus error.

The address you're computing probably is valid most of the time.
However, this is not a good habit to develop. The fact that it has not
been a problem for you yet does not mean it won't be.

-Jeff

 

[Dhruv]

int x;
int* p(&x);
p + 1; // one past the end of the int x is valid
p + 2; // undefined behavior for just trying to compute it

In particular, what's wrong with computing p+2? What's the rationale
behind not allowing it?

p - 1; // same thing
p = new int;
delete p;
if (p) // undefined behavior

Same thing? AFAIK, delete is not allowed to mofdify the pointer passed to
it, so just accessing the value stored in the pointer should not be a
problem? Or is my thinking orthogonal to the standard?


Regards,
-Dhruv.

 

[John Potter]

In message

UB is generally an issue for the executable not for the compiler. That
is the point, the compiler is required to accept the code unless it can
demonstrate that it will always fail and that the code will always be
executed (rather hard unless it is working as an interpreter)

When we come to execution time either p-1 or p+2 maybe pointer into
memory that does not belong to the process, and the consequences can be
anything (on protected memory systems it usually results in the process
being aborted). If you look as if you are about to touch memory you do
not own then the OS is entitled to do whatever it wants -- but that
action is outside the domain of the C++ Standard and so is undefined (by
C++)

Which also allows the compiler to insert code which runs nethack if
executed. Fat pointers can hold base and bound values to allow
checking of all pointer arithmetic.

John

 

[Francis Glassborow]

Same thing? AFAIK, delete is not allowed to mofdify the pointer passed to
it, so just accessing the value stored in the pointer should not be a
problem? Or is my thinking orthogonal to the standard?

I do not think you are thinking clearly about what happens on hardware
that has address registers, and particularly with oSs that do proper
memory management.

 

[John Potter]

What do you mean "one past the end of the int x?" Are you sure that's
valid?

Yes.

| 5.7/4 For the purposes of these operators, a pointer to a
| non-array object behaves the same as a pointer to the first element of
| an array of length one with the type of the object as its element type.

It is always valid to add one to a dereferencable pointer value.

John

 

[John Potter]

In particular, what's wrong with computing p+2? What's the rationale
behind not allowing it?

I don't think C++ is rational. There is no rationale.

Same thing? AFAIK, delete is not allowed to mofdify the pointer passed to
it, so just accessing the value stored in the pointer should not be a
problem? Or is my thinking orthogonal to the standard?

I think you are confusing operator delete with the delete expression.
The delete expression does anything the compiler generates including
assigning an invalid value to the pointer or adding the value of the
pointer expression to a list of addresses which cause email to your
boss in a program that produces that rvalue.

See 5.3.5/4. The delete expresion invalidates the pointer. The only
thing that may be done with a pointer holding an invalid value is to
assign a new value. You are not allowed to look at the old value.

John