Safely working out how many rows in an array?

Discussion in 'C Programming' started by pkirk25, Sep 27, 2006.

  1. pkirk25

    pkirk25 Guest

    Assume an array of structs that is having rows added at random. By the
    time it reaches your function, you have no idea if it has a few hundred
    over over 10000 rows.

    When your function recieves this array as an argument, is there a safe
    way to establish how many rows that are or should I iterate over a
    field I know will always be used and use the final value of the
    iterator as the value of the array?
     
    pkirk25, Sep 27, 2006
    #1
    1. Advertising

  2. pkirk25 said:

    > Assume an array of structs that is having rows added at random. By the
    > time it reaches your function, you have no idea if it has a few hundred
    > over over 10000 rows.
    >
    > When your function recieves this array as an argument, is there a safe
    > way to establish how many rows that are or should I iterate over a
    > field I know will always be used and use the final value of the
    > iterator as the value of the array?


    The trick is to keep track of how many elements the array has, and to pass
    that information to functions that need it. Objects are relatively cheap.
    Something as small as a size_t is practically free! So don't be squeamish
    about using them.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Sep 27, 2006
    #2
    1. Advertising

  3. "pkirk25" <> writes:
    > Assume an array of structs that is having rows added at random. By the
    > time it reaches your function, you have no idea if it has a few hundred
    > over over 10000 rows.
    >
    > When your function recieves this array as an argument, is there a safe
    > way to establish how many rows that are or should I iterate over a
    > field I know will always be used and use the final value of the
    > iterator as the value of the array?


    You need to rethink your question.

    It's not possible to pass an array as an argument in C. What you can
    do is, for example, pass the address of (equivalently: a pointer to)
    an array's first element as an argument. This pointer can then be
    used to access the elements of the array, but it doesn't tell you how
    many there are.

    The language does a few things that seemingly conspire to make it
    *look* like you're passing the array itself, but you're really not.

    As Richard Heathfield wrote, the most straightforward way to do this
    is to keep track of the size yourself and pass it to your function as
    an extra argument.

    Other solutions exist.

    You should also read section 6 of the comp.lang.c FAQ, available at
    <http://www.c-faq.com>.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Sep 27, 2006
    #3
  4. pkirk25

    pkirk25 Guest

    Richard Heathfield wrote:
    [snip]
    >
    > The trick is to keep track of how many elements the array has, and to pass
    > that information to functions that need it. Objects are relatively cheap.
    > Something as small as a size_t is practically free! So don't be squeamish

    [snip]

    A file has over 300k rows of which less than 100 are likely to be of
    interest.

    int ScanFile(const FILE *srcFile,
    struct realm_structure *rlm,
    int *i)
    {
    /*
    1. do something very clever to find a match
    2. update the struct so its a useful matrix
    3. i++
    */
    return 0;
    }

    Is this what you were thinking?

    If i get the iteration of the count wrong in any 1 function, I could
    end up confused. But as a way of dealing with the problem, it does
    look very good.
     
    pkirk25, Sep 27, 2006
    #4
  5. pkirk25

    Michael Mair Guest

    Richard Heathfield wrote:
    > pkirk25 said:
    >
    >>Assume an array of structs that is having rows added at random. By the
    >>time it reaches your function, you have no idea if it has a few hundred
    >>over over 10000 rows.
    >>
    >>When your function recieves this array as an argument, is there a safe
    >>way to establish how many rows that are or should I iterate over a
    >>field I know will always be used and use the final value of the
    >>iterator as the value of the array?

    >
    > The trick is to keep track of how many elements the array has, and to pass
    > that information to functions that need it. Objects are relatively cheap.
    > Something as small as a size_t is practically free! So don't be squeamish
    > about using them.


    Indeed.

    @OP:
    An alternative not using less but more space is using a data structure
    different from an array if it is more suitable to your problem. Arrays
    do not grow rows magically, so you have to deal with reallocation,
    keeping track of the number of rows etc.
    If you, for example, use linked lists, then insertion of new rows
    is comparatively cheap and iteration costs (but for a constant factor)
    the same as for an array.

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Sep 27, 2006
    #5
  6. On Tue, 26 Sep 2006 23:06:17 +0000, Richard Heathfield wrote:

    > pkirk25 said:
    >
    >> Assume an array of structs that is having rows added at random. By the
    >> time it reaches your function, you have no idea if it has a few hundred
    >> over over 10000 rows.
    >>
    >> When your function recieves this array as an argument, is there a safe
    >> way to establish how many rows that are or should I iterate over a field
    >> I know will always be used and use the final value of the iterator as
    >> the value of the array?

    >
    > The trick is to keep track of how many elements the array has, and to pass
    > that information to functions that need it. Objects are relatively cheap.
    > Something as small as a size_t is practically free! So don't be squeamish
    > about using them.


    Put another way, don't ever discard information. Ideally, such information
    is kept from the very beginning, and not derived at some intermediate
    point.
     
    William Ahern, Sep 27, 2006
    #6
  7. On 26 Sep 2006 16:02:31 -0700, "pkirk25" <> wrote:

    >When your function recieves this array as an argument, is there a safe
    >way to establish how many rows that are [...]


    Usually, you pass the "dimension" of the array to your function.
    A prototype of that function could be the following:

    void yourFunction(int rows[], int rowCount);

    Alternatively, you may want to use a "sentinel value".

    An example of a an array terminated by a sentinel value is argv, one
    of the two parameters of the function main():

    int main(int argc, char *argv[])

    The standard prescribes that argv[argc] shall be a null pointer, so
    the following code is perfectly legal:

    #include <stdio.h>

    int main(int argc, char *argv[])
    {
    int count;
    for (count=0; argv[count]; count++)
    ;
    printf("argc=%d\n", argc, count);
    return 0;
    }
     
    Andrea Laforgia, Sep 27, 2006
    #7
  8. On Wed, 27 Sep 2006 01:27:28 +0200, Andrea Laforgia
    <> wrote:

    > printf("argc=%d\n", argc, count);


    Of course, it is:

    > printf("argc=%d\n", count);


    I would demonstrate that argc == count.
     
    Andrea Laforgia, Sep 27, 2006
    #8
  9. On Tue, 2006-26-09 at 16:02 -0700, pkirk25 wrote:
    > Assume an array of structs that is having rows added at random. By the
    > time it reaches your function, you have no idea if it has a few hundred
    > over over 10000 rows.
    >
    > When your function recieves this array as an argument, is there a safe
    > way to establish how many rows that are or should I iterate over a
    > field I know will always be used and use the final value of the
    > iterator as the value of the array?
    >


    I'm not sure if I understand your question, but the usual method for
    doing this is to pass the length of the array into the function:

    int my_function (char array[], size_t len);

    --
    Andrew Poelstra <http://www.wpsoftware.net/projects/>
     
    Andrew Poelstra, Sep 27, 2006
    #9
  10. Andrew Poelstra <> writes:
    > On Tue, 2006-26-09 at 16:02 -0700, pkirk25 wrote:
    >> Assume an array of structs that is having rows added at random. By the
    >> time it reaches your function, you have no idea if it has a few hundred
    >> over over 10000 rows.
    >>
    >> When your function recieves this array as an argument, is there a safe
    >> way to establish how many rows that are or should I iterate over a
    >> field I know will always be used and use the final value of the
    >> iterator as the value of the array?
    >>

    >
    > I'm not sure if I understand your question, but the usual method for
    > doing this is to pass the length of the array into the function:
    >
    > int my_function (char array[], size_t len);


    And keep in mind that, in a parameter declaration (and *only* in a
    parameter declaration), "char array[]" really means "char *array".

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Sep 27, 2006
    #10
  11. pkirk25

    pkirk25 Guest

    Why size_t?

    Many thanks all.

    I curious why people prefer a size_t instead of int? On my PC, a quick
    sizeof shows both are same size, though that could be down the the %d
    in prinft("%d", sizeof(tSize_t))
     
    pkirk25, Sep 27, 2006
    #11
  12. Keith Thompson <> wrote:

    >
    > As Richard Heathfield wrote, the most straightforward way to do this
    > is to keep track of the size yourself and pass it to your function as
    > an extra argument.


    i'm still a newb in C, i don't use the same way as Richard Heathfield
    wrote, rather i initiate the array with null value, then i can
    iterate...

    is that way of doing wrong ???
    --
    une bévue
     
    =?ISO-8859-1?Q?Une_b=E9vue?=, Sep 27, 2006
    #12
  13. pkirk25

    Guest

    Re: Why size_t?

    pkirk25 ha scritto:

    > I curious why people prefer a size_t instead of int?


    The ISO standard states that "size_t" is the type of sizeof, so you
    should use it to specify the "size" of your data. It is not guaranteed
    that size_t matches the int type, but only that it is an unsigned type.
    Using size_t instead of int is much more correct, since it is portable
    and since data size is obviously and unsigned value.
     
    , Sep 27, 2006
    #13
  14. pkirk25

    Michael Mair Guest

    Re: Why size_t?

    wrote:
    > pkirk25 ha scritto:
    >>I curious why people prefer a size_t instead of int?

    >
    > The ISO standard states that "size_t" is the type of sizeof, so you
    > should use it to specify the "size" of your data. It is not guaranteed
    > that size_t matches the int type, but only that it is an unsigned type.
    > Using size_t instead of int is much more correct, since it is portable
    > and since data size is obviously and unsigned value.


    Other examples:
    strlen() returns size_t
    malloc()'s parameter is of type size_t

    There are several functions where one would expect a size_t return
    value or parameter; that you find int (or another type) instead, is
    mainly for historic reasons.

    There is one main disadvantage: size_t is an unsigned integer type.
    unsigned types need more care in some places; a classic is the
    beloved
    for (index = size-1; index >= 0; --index)
    way of writing an endless loop.
    There is no corresponding signed type which is a pity (POSIX gives
    you ssize_t which is useful in many respects).

    If I start something new and have the choice, then I go for size_t.


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Sep 27, 2006
    #14
  15. Une bévue said:

    > Keith Thompson <> wrote:
    >
    >>
    >> As Richard Heathfield wrote, the most straightforward way to do this
    >> is to keep track of the size yourself and pass it to your function as
    >> an extra argument.

    >
    > i'm still a newb in C, i don't use the same way as Richard Heathfield
    > wrote, rather i initiate the array with null value, then i can
    > iterate...
    >
    > is that way of doing wrong ???


    Show us what you mean, using a small C program that compiles correctly, and
    we'll find out together.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Sep 27, 2006
    #15
  16. lid (Une bévue) writes:
    > Keith Thompson <> wrote:
    >> As Richard Heathfield wrote, the most straightforward way to do this
    >> is to keep track of the size yourself and pass it to your function as
    >> an extra argument.

    >
    > i'm still a newb in C, i don't use the same way as Richard Heathfield
    > wrote, rather i initiate the array with null value, then i can
    > iterate...
    >
    > is that way of doing wrong ???


    It depends on what you mean. I don't know what "initiate the array
    with null value" is supposed to mean.

    One way to let a function know how many elements an array has is to
    use a sentinal value, i.e., assign some unique value to the last
    element of the array. If it happens to be an array of pointers, and a
    null pointer is not otherwise a valid value, then marking the end of
    the array with a null pointer value is a reasonable approach.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Sep 27, 2006
    #16
  17. pkirk25

    bert Guest

    Keith Thompson wrote:
    > lid (Une bévue) writes:
    > > i'm still a newb in C, i don't use the same way as Richard Heathfield
    > > wrote, rather i initiate the array with null value, then i can
    > > iterate...
    > >
    > > is that way of doing wrong ???

    >
    > It depends on what you mean. I don't know what "initiate the array
    > with null value" is supposed to mean.


    I think it means initially filling the whole array with
    the end-of-array sentinel value. Then when you add
    a new element, it already has a sentinel value after it.
    --
     
    bert, Sep 27, 2006
    #17
  18. bert <> wrote:

    >
    > I think it means initially filling the whole array with
    > the end-of-array sentinel value. Then when you add
    > a new element, it already has a sentinel value after it.


    right, this method is ok ?

    nb : this is the case when the max number of elements is known in
    advance, otherwise i've a minimum count of elements to start with, when
    the elements number is over this min the array is arranged such that i
    don't have to malloc for it rather for the next i set to null.
    --
    une bévue
     
    =?ISO-8859-1?Q?Une_b=E9vue?=, Sep 27, 2006
    #18
  19. pkirk25

    bert Guest

    Une bévue wrote:
    > bert <> wrote:
    >
    > >
    > > I think it means initially filling the whole array with
    > > the end-of-array sentinel value. Then when you add
    > > a new element, it already has a sentinel value after it.

    >
    > right, this method is ok ?
    >
    > nb : this is the case when the max number of elements is known in
    > advance, otherwise i've a minimum count of elements to start with, when
    > the elements number is over this min the array is arranged such that i
    > don't have to malloc for it rather for the next i set to null.


    Well, there's nothing that anybody could call wrong with
    this method. True, some people would find sentinel
    values not mixing well with dynamic reallocation, but it
    still comes down to a matter of personal taste, and what
    style or mixture you find readable and maintainable.
    --
     
    bert, Sep 28, 2006
    #19
  20. pkirk25

    bert Guest

    Une bévue wrote:
    > bert <> wrote:
    >
    > >
    > > I think it means initially filling the whole array with
    > > the end-of-array sentinel value. Then when you add
    > > a new element, it already has a sentinel value after it.

    >
    > right, this method is ok ?
    >
    > nb : this is the case when the max number of elements is known in
    > advance, otherwise i've a minimum count of elements to start with, when
    > the elements number is over this min the array is arranged such that i
    > don't have to malloc for it rather for the next i set to null.


    Nobody could call it a wrong method. Some people find that
    sentinel values do not mix well with dynamic reallocation, but
    it's still just a matter of personal taste, and what style
    or mixture you have found to be readable and maintainable.
    --
     
    bert, Sep 28, 2006
    #20
    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. Marco Ippolito
    Replies:
    0
    Views:
    2,587
    Marco Ippolito
    Oct 11, 2004
  2. =?Utf-8?B?U3R1?=

    session vars how many is to many ?

    =?Utf-8?B?U3R1?=, Mar 5, 2005, in forum: ASP .Net
    Replies:
    5
    Views:
    338
  3. dee
    Replies:
    2
    Views:
    399
  4. Ram Laxman
    Replies:
    5
    Views:
    14,665
    Thomas Tutone
    Apr 12, 2004
  5. TBass
    Replies:
    4
    Views:
    420
    Daniel T.
    Jan 9, 2008
Loading...

Share This Page