Can't find last element in list

[desktop]

How do I find the last element in the list numsx defined below?

int* myfind(int* arr_start, int* arr_end, int& s) {
int not_found = 666;
int* result = &not_found;

while (arr_start != arr_end){
if (*(arr_start) == s)
{
result = arr_start;
}

arr_start++;
}

return result;
}



int main() {

int numsx[] = { 1, 2, 3, 4, 5, 7, 8, 9};
int* resultx;
int endx = (sizeof(numsx)/4)-1;
int sx = 9;

resultx = ::myfind( numsx, numsx + endx,sx);

std::cout << *resultx << std::endl;

return 0;

}

I have thought about:

while (arr_start != arr_end+1){
....
....


instead, but since "arr_end+1" is unknow territory I guess its bad style.

Is there someway to make sure that the last element in a list is read
and only terminate afterwards?

 

[Victor Bazarov]

How do I find the last element in the list numsx defined below?

int* myfind(int* arr_start, int* arr_end, int& s) {

Why is 's' passed by

int not_found = 666;
int* result = &not_found;

while (arr_start != arr_end){
if (*(arr_start) == s)
{
result = arr_start;
}

arr_start++;
}

return result;

Clutter, clutter... Given the interface (forget the 666) you
should implement this as

while (arr_start != arr_end) {
if (*arr_start == s)
break;
++arr_start;
}
return arr_start;

}



int main() {

int numsx[] = { 1, 2, 3, 4, 5, 7, 8, 9};
int* resultx;
int endx = (sizeof(numsx)/4)-1;

Two mistakes. First, don't use 4, use 'sizeof(int)'. Second,
you're much better off if you don't subtract 1. Use the range
where the upper value is not includede (this is called "an open
range"). IOW

int endx = sizeof(numsx) / sizeof(numsx[0]);

int sx = 9;

resultx = ::myfind( numsx, numsx + endx,sx);

Since 'resultx' is a pointer, it could be equal to 'numsx + endx',
which will mean "not found".

std::cout << *resultx << std::endl;

return 0;

}

I have thought about:

while (arr_start != arr_end+1){
...
...


instead, but since "arr_end+1" is unknow territory I guess its bad
style.

No, it's actually better.

Is there someway to make sure that the last element in a list is read
and only terminate afterwards?

See above.

V

 

[desktop]

Why is 's' passed by


Clutter, clutter... Given the interface (forget the 666) you
should implement this as

while (arr_start != arr_end) {
if (*arr_start == s)
break;
++arr_start;
}
return arr_start;

Problem is that I am not allowed to use 'break'. I am going to use a
custom made optimizer that will not allow the use of the 'break' keyword.

 

[Victor Bazarov]

Problem is that I am not allowed to use 'break'. I am going to use a
custom made optimizer that will not allow the use of the 'break'
keyword.

Oh, come on! Use 'return', then.

V

 

[Drew Lawson]

How do I find the last element in the list numsx defined below?

int* myfind(int* arr_start, int* arr_end, int& s) {
int not_found = 666;
int* result = &not_found;

while (arr_start != arr_end){
if (*(arr_start) == s)
{
result = arr_start;
}

arr_start++;
}

return result;
}

Since no one seems to have picked this nit -- if your target value
isn't in the list, you return a pointer to a local variable, which
goes poof when you return.

Common and hazardous pattern for that, assuming that you *have* to
return a pointer, is to return a null pointer for "not found." Just
make sure that any caller is testing for null.

 

[Victor Bazarov]

[..]
Common and hazardous pattern for that, assuming that you *have* to
return a pointer, is to return a null pointer for "not found." Just
make sure that any caller is testing for null.

And here is the kicker -- there is no way to "make sure that any
caller is testing". It's the caller's responsibility. All you can
do is document the proper way of using your function. This is
especially important for library designers. It's easy when you
design/implement both the function and the code that calls it.
What if you don't?

V

 

[Drew Lawson]

[..]
Common and hazardous pattern for that, assuming that you *have* to
return a pointer, is to return a null pointer for "not found." Just
make sure that any caller is testing for null.

And here is the kicker -- there is no way to "make sure that any
caller is testing". It's the caller's responsibility. All you can
do is document the proper way of using your function. This is
especially important for library designers. It's easy when you
design/implement both the function and the code that calls it.
What if you don't?

The C answer is culture -- learning that anything that returns a
pointer can return NULL. Here be dragons.

The C++ answer seems to be, "why do you need a pointer?"

For the OP's task, I'd lean more toward returning an index, but
that has the same out-of-bounds issues for the failure value. But
a subscripting exception is easier to debug than rogue-pointer
memory corruption. So this case has me sold on containers and
subscripts. (Still making the C --> C++ cultural shift.)

 

[Victor Bazarov]

[..]
Common and hazardous pattern for that, assuming that you *have* to
return a pointer, is to return a null pointer for "not found." Just
make sure that any caller is testing for null.

And here is the kicker -- there is no way to "make sure that any
caller is testing". It's the caller's responsibility. All you can
do is document the proper way of using your function. This is
especially important for library designers. It's easy when you
design/implement both the function and the code that calls it.
What if you don't?

The C answer is culture -- learning that anything that returns a
pointer can return NULL. Here be dragons.

The C++ answer seems to be, "why do you need a pointer?"

It really has nothing to do with pointers/indices/anything else.
It's the inability in either language to force the caller to use the
returned value in the way it is intended to be used.

Nothing prevents me from calling 'printf' without ever assigning or
checking the return value, although it is known that the return value
type is 'int' and what the number means.

For the OP's task, I'd lean more toward returning an index, but
that has the same out-of-bounds issues for the failure value. But
a subscripting exception is easier to debug than rogue-pointer
memory corruption. So this case has me sold on containers and
subscripts. (Still making the C --> C++ cultural shift.)

That's not as generic as returning the "end" value (just like 'find'
and related algorithms from the Standard Library do).

V

 

[James Kanze]

Why is 's' passed by

reference, I suppose you meant.

Even more important, why is it passed by non-const reference?
Presumably, he wants to change it.

Clutter, clutter... Given the interface (forget the 666) you
should implement this as

while (arr_start != arr_end) {
if (*arr_start == s)
break;
++arr_start;
}
return arr_start;

Except that that won't pass code review in most serious shops.
It's very confusing to have a loop exit in two different
locations.

What he's implementing is nothing more than a linear search.
And the algorithm for a linear search is well known:

WHILE NOT finished AND NOT found
DO
avance to next
DONE

In C++, in this case:

int*
myFind( int* start, int* end, int searchValue )
{
int* current = start ;
while ( current != end && *current != searchValue ) {
++ current ;
}
return current ;
// Or:
// return current == end ? NULL : current ;
// if that is the convention. Just returning
// the end is more idiomatic in C++.
}

int main() {
int numsx[] = { 1, 2, 3, 4, 5, 7, 8, 9};
int* resultx;
int endx = (sizeof(numsx)/4)-1;

Two mistakes. First, don't use 4, use 'sizeof(int)'. Second,
you're much better off if you don't subtract 1. Use the range
where the upper value is not includede (this is called "an open
range"). IOW

It's called a half open interval. An open interval would be
exclusive at both ends.

Historically, different languages have different traditions; the
half-open interval is very, very idiomatic for C and its
derivatives (C++, Java and I suppose C#). In my experience, it
also works best in general, and I would probably use it in other
languages as well.

int endx = sizeof(numsx) / sizeof(numsx[0]);

int sx = 9;
resultx = ::myfind( numsx, numsx + endx,sx);

Since 'resultx' is a pointer, it could be equal to 'numsx + endx',
which will mean "not found".

That's the modern, idiomatic C++ solution. Much code still
conforms to the traditional solution, still idiomatic in C, of
returning NULL for not found. The mapping is trivial, see my
comments on the return, above.

If you are just learning C++, of course, you're better off
learning to use the idiomatic solutions. Except that if this is
homework (probably, since if not, the obvious solution is
std::find), the prof may have other ideas. (And of course, in a
professional context, you conform to the desires of your
employer.)

No, it's actually better.

But only because C/C++ have special rules which make it legal.
You're allowed to form the address of an element one passed the
end of an array, but not to dereference the resulting pointer.

As I said, it's the idiomatic way of doing things in C++.

 

[James Kanze]

[..]
Common and hazardous pattern for that, assuming that you *have* to
return a pointer, is to return a null pointer for "not found." Just
make sure that any caller is testing for null.

And here is the kicker -- there is no way to "make sure that any
caller is testing". It's the caller's responsibility. All you can
do is document the proper way of using your function. This is
especially important for library designers. It's easy when you
design/implement both the function and the code that calls it.
What if you don't?

The C answer is culture -- learning that anything that returns a
pointer can return NULL. Here be dragons.

The professional answer doesn't depend on the language: you read
the documentation of a function before using it.

The C++ answer seems to be, "why do you need a pointer?"

For the OP's task, I'd lean more toward returning an index, but
that has the same out-of-bounds issues for the failure value. But
a subscripting exception is easier to debug than rogue-pointer
memory corruption. So this case has me sold on containers and
subscripts. (Still making the C --> C++ cultural shift.)

Actually, returning a null pointer is probably the most robust
and the easiest to debug. On most implementations,
dereferencing a null pointer will make the program go boom
immediately. Using an out of bounds index or a one-past-the-end
pointer will usually just return garbage; your program ends up
outputting wrong values, and you have to figure out why.

 

[Drew Lawson]

The professional answer doesn't depend on the language: you read
the documentation of a function before using it.

As the user of the function, that is what I'd do.

As the writer of the function, which is what I thought Victor was
getting at, I'd go with what is "standard" for the language, and
that does depend on the language.

Of course, you can always write C++ as if it's Fortran77, but I
pity the person who gets to maintain it later.

Actually, returning a null pointer is probably the most robust
and the easiest to debug. On most implementations,
dereferencing a null pointer will make the program go boom
immediately. Using an out of bounds index or a one-past-the-end
pointer will usually just return garbage; your program ends up
outputting wrong values, and you have to figure out why.

By "containers and sucscripts" I was intending to reference
std::vector<>.at(), which I believe will throw an exception if given
a bogus index.

(But for what I actually wrote, I agree.)

 

[James Kanze]

As the user of the function, that is what I'd do.

As the writer of the function, which is what I thought Victor was
getting at, I'd go with what is "standard" for the language, and
that does depend on the language.

You mean you were discussing design issues, how to best design
the function.

Of course, you can always write C++ as if it's Fortran77, but I
pity the person who gets to maintain it later.

Don't I know it. There's an awful lot of C++ out there that was
written as if it were C.

By "containers and sucscripts" I was intending to reference
std::vector<>.at(), which I believe will throw an exception if given
a bogus index.

Except that 1) that's not what you want, and 2) no one uses
vector<>::at() anyway. The implementations of std::vector I use
will also core dump if you access the vector with an invalid
index or iterator. And in general, one past the end is the
idiomatic way of signaling that you haven't found what you were
looking for.

If, however, the function is defined to return a pointer, and is
called with C-style arrays, it's already not idiomatic C++,
it's idiomatic C, and idiomatic C would be to return a null
pointer. Which is also more robust.