Can't find last element in list

Discussion in 'C++' started by desktop, Apr 26, 2007.

  1. desktop

    desktop Guest

    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?
    desktop, Apr 26, 2007
    #1
    1. Advertising

  2. desktop wrote:
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Apr 26, 2007
    #2
    1. Advertising

  3. desktop

    desktop Guest

    Victor Bazarov wrote:
    > desktop wrote:
    >> 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;
    >
    >> }
    >>




    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.
    desktop, Apr 26, 2007
    #3
  4. desktop wrote:
    > Victor Bazarov wrote:
    >> desktop wrote:
    >>> 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;
    >>
    >>> }
    >>>

    >
    >
    >
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Apr 26, 2007
    #4
  5. desktop

    Drew Lawson Guest

    In article <f0qnq8$4vr$-c.dk>
    desktop <> writes:
    >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.


    --
    Drew Lawson | Radioactive cats have
    | 18 half-lives
    http://www.furrfu.com/ |
    Drew Lawson, Apr 26, 2007
    #5
  6. Lawson wrote:
    > [..]
    > 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Apr 26, 2007
    #6
  7. desktop

    Drew Lawson Guest

    In article <f0qs3n$ete$>
    "Victor Bazarov" <> writes:
    >Lawson wrote:
    >> [..]
    >> 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.)

    --
    Drew Lawson For it's not the fall, but landing,
    That will alter your social standing
    Drew Lawson, Apr 26, 2007
    #7
  8. Drew Lawson wrote:
    > In article <f0qs3n$ete$>
    > "Victor Bazarov" <> writes:
    >> Lawson wrote:
    >>> [..]
    >>> 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
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Apr 26, 2007
    #8
  9. desktop

    James Kanze Guest

    On Apr 26, 7:43 pm, "Victor Bazarov" <> wrote:
    > desktop wrote:
    > > 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


    reference, I suppose you meant.

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

    > > 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;
    > > }


    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.)

    > > 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.


    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 (GABI Software) email:
    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
    James Kanze, Apr 27, 2007
    #9
  10. desktop

    James Kanze Guest

    On Apr 26, 9:05 pm, (Drew Lawson) wrote:
    > In article <f0qs3n$>
    > "Victor Bazarov" <> writes:


    > >Lawson wrote:
    > >> [..]
    > >> 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.

    --
    James Kanze (GABI Software) email:
    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
    James Kanze, Apr 27, 2007
    #10
  11. desktop

    Drew Lawson Guest

    In article <>
    James Kanze <> writes:
    >On Apr 26, 9:05 pm, (Drew Lawson) wrote:
    >> In article <f0qs3n$>
    >> "Victor Bazarov" <> writes:

    >
    >> >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.


    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.

    >> 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.


    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.)

    --
    Drew Lawson http://www.furrfu.com/
    "Please understand that we are considerably less interested
    in you than you are."
    -- Madeleine Page, on the deep truths of alt.folklore.urban
    Drew Lawson, Apr 27, 2007
    #11
  12. desktop

    James Kanze Guest

    On Apr 27, 3:43 pm, (Drew Lawson) wrote:
    > In article <>
    > James Kanze <> writes:


    > >On Apr 26, 9:05 pm, (Drew Lawson) wrote:
    > >> In article <f0qs3n$>
    > >> "Victor Bazarov" <> writes:


    > >> >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.


    > 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.

    > >> 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.


    > 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.

    --
    James Kanze (GABI Software) email:
    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
    James Kanze, Apr 27, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. xerix

    last element of list

    xerix, Apr 10, 2004, in forum: C++
    Replies:
    10
    Views:
    663
    Nick Hounsome
    Apr 11, 2004
  2. sangram
    Replies:
    16
    Views:
    1,955
  3. suresh
    Replies:
    2
    Views:
    231
    suresh
    Oct 8, 2010
  4. gniagnia
    Replies:
    8
    Views:
    167
    -berlin.de
    Feb 20, 2007
  5. STD
    Replies:
    8
    Views:
    611
    Randal L. Schwartz
    Feb 26, 2012
Loading...

Share This Page