K&R chapter 6.3 Question 'how to calculate the number of array elements'

Discussion in 'C Programming' started by Herrcho, Feb 10, 2004.

  1. Herrcho

    Herrcho Guest

    in K&R Chapter 6.3

    it mentions two methods to calculate NKEYS.

    and points out the first one which is to terminate the list of
    initializers with a null pointer, then loop along keytab until the end
    is found is less efficient than using sizeof operator , since size of
    the array is completely determined at compile time.

    i don't quite understand this. Could anyone explain to me in detail ?

    Thanks in advance..
     
    Herrcho, Feb 10, 2004
    #1
    1. Advertising

  2. Herrcho

    Mark Shelor Guest

    Re: K&R chapter 6.3 Question 'how to calculate the number of arrayelements'

    Herrcho wrote:

    > in K&R Chapter 6.3
    >
    > it mentions two methods to calculate NKEYS.
    >
    > and points out the first one which is to terminate the list of
    > initializers with a null pointer, then loop along keytab until the end
    > is found is less efficient



    Yes, the first method would need to be performed at runtime, with
    initialization code such as:

    #include <stdlib.h>

    unsigned int nkeys;

    for (nkeys = 0; keytab[nkeys].word != NULL; nkeys++)
    ;


    > than using sizeof operator , since size of
    > the array is completely determined at compile time.



    The second method requires no runtime code, and leaves all the work up
    to the compiler:

    #define NKEYS (sizeof keytab / sizeof keytab[0])

    The latter is much simpler, n'est-ce pas?

    Mark
     
    Mark Shelor, Feb 10, 2004
    #2
    1. Advertising

  3. Herrcho

    Mike Wahler Guest

    "Herrcho" <> wrote in message
    news:...
    > in K&R Chapter 6.3
    >
    > it mentions two methods to calculate NKEYS.
    >
    > and points out the first one which is to terminate the list of
    > initializers with a null pointer,


    Or more generally, a value which has been specified to
    mean 'terminator'. E.g. an array of integer values which
    are defined as 'valid' data if nonnegative. A 'terminator'
    value for this could be e.g. -1.

    > then loop along keytab until the end
    > is found


    This would be 'manual' counting. It happens at run time,
    so it consumes processor time. It also is 'fragile' since
    it depends upon the array's elements being properly initialized.

    It's also not very flexible, since it disallows storing (in
    any array element, intentionally or inadvertently) any possible
    value the array's element type could represent (a 'terminator'
    value would belong to this set.)

    > is less efficient


    Because 'sizeof' provides the value at compile-time. Thus
    the value is already known at program startup. No need for the
    program to consume processor time to calculate it.

    >than using sizeof operator , since size of
    > the array is completely determined at compile time.
    >
    > i don't quite understand this. Could anyone explain to me in detail ?


    I hope I did.

    A caveat:

    'sizeof' will only correctly report the size of an array if
    that array is in the same scope where the 'sizeof' operator
    is used. Passed as an argument to a function, an array's
    type is 'demoted' to a pointer type (the value is the address
    of the array's first element).

    #include <stdio.h>

    int g_array[] = {1,2,3,-1}; /* using -1 as 'terminator' for */
    /* array of non-negative value */

    size_t size(int arg[10]) /* the [10] is ignored, 'arg's type is really */
    /* 'int*' ('pointer to int') */
    {
    return sizeof arg;
    }

    void other_stuff(int *arg) /* note that we can pass either a 'real' */
    /* pointer, or an array of ints as the */
    /* parameter */
    {
    --arg[2]; /* decrement element 2 (imagine this is part of a */
    /* larger algorithm, e.g. where the 2 is replaced */
    /* by the value of some other variable. IOW we */
    /* don't know by looking at this statment what */
    /* that value is) */
    }

    void more_stuff(void)
    {
    ++g_array[3]; /* increment element 3 (imagine this is part of a */
    /* larger algorithm, e.g. where the 3 is replaced */
    /* by the value of some other variable. IOW we */
    /* don't know by looking at this statment what */
    /* that value is) */
    }

    /* 'Manually' counts array elements, */
    /* uses -1 as terminator value */
    size_t count_em(int arg[]) /* yet another possible syntax for */
    /* a pointer or array argument */
    {
    size_t count = 0;
    size_t i = 0;

    while(arg[i++] >= 0)
    count += sizeof *arg; /* '*arg' means same thing as 'arg[0]' */

    return count;
    }

    int main()
    {
    int m_array[] = { 2, 6, 0, 7, 5, -1}; /* using -1 as 'terminator' for
    */
    /* array of non-negative value */

    printf("size of g_array as reported by sizeof operator :"
    " %2lu bytes\n",
    (unsigned long)sizeof g_array); /* prints sizeof(int) * 4, */
    /* e.g. 16 on a Win32 platform */

    printf("size of g_array as reported by size() function :"
    " %2lu bytes\n",
    (unsigned long)size(g_array)); /* prints the size of type 'int*' */
    /* e.g. 4 on a Win32 platform */

    putchar('\n');

    printf("size of m_array as reported by sizeof operator :"
    " %2lu bytes\n",
    (unsigned long)sizeof m_array); /* prints sizeof(int) * 5, */
    /* e.g. 24 on a Win32 platform */

    printf("size of m_array as reported by size() function :"
    " %2lu bytes\n",
    (unsigned long)size(m_array)); /* prints the size of type 'int*' */
    /* e.g. 4 on a Win32 platform */

    putchar('\n');

    /* Hereafter, size values stated in comments
    are those obtained on Win32 platform */

    printf("size of g_array as reported by count_em() function :"
    " %2lu bytes\n",
    (unsigned long)count_em(g_array)); /* prints size of the portion */
    /* of array preceding element */
    /* with value -1 (here, 12) */

    printf("size of m_array as reported by count_em() function :"
    " %2lu bytes\n",
    (unsigned long)count_em(m_array)); /* prints size of the portion */
    /* of array preceding element */
    /* with value -1 (here, 20) */

    putchar('\n');

    other_stuff(m_array); /* do some stuff with 'm_array' */
    printf("%s\n\n", "other_stuff(m_array) called");

    printf("size of m_array as reported by count_em() function :"
    " %2lu bytes\n",
    (unsigned long)count_em(m_array)); /* prints the number of array */
    /* of array preceding element */
    /* with value -1 (here, 8) */
    /* -- because m_array[2] was */
    /* 'accidentally' set to -1. */
    /* OOPS! :) */

    putchar('\n');

    more_stuff();
    printf("%s\n\n", "more_stuff() called (touches g_array)");

    puts("Better not call count_em(g_array) !!!");

    #if 0
    printf("size of g_array as reported by count_em() function :"
    " %2lu bytes\n",
    (unsigned long)count_em(g_array)); /* prints the number of array */
    /* of array preceding element */
    /* with value -1. But WAIT!! */
    /* there's no element with a */
    /* value of -1!! (due to what */
    /* 'more_stuff()' did) */
    /* execution of this statment */
    /* would produce 'undefined' */
    /* behavior (wich is why I */
    /* "#if-d" it out */

    /* this last issue is why we should always provide an array's size */
    /* (typically expressed as number of elements) as an extra paramter */
    /* to functions to which arrays are passed. It provides a 'hard limit */
    /* on how many elements can be accessed, regardless of their values. */
    /* And again, remember that sizeof will only report correct size for */
    /* arrays in same scope (of course some other mechanism for determining */
    /* size might be used instead, e.g. a #define for the size of the array) */

    /* recommended syntax for calcuating count of array elements using sizeof:
    */
    /*
    /* sizeof array_name / sizeof *array_name
    */

    #endif

    return 0;
    }


    Output:
    -------------------------------------------------------------
    size of g_array as reported by sizeof operator : 16 bytes
    size of g_array as reported by size() function : 4 bytes

    size of m_array as reported by sizeof operator : 24 bytes
    size of m_array as reported by size() function : 4 bytes

    size of g_array as reported by count_em() function : 12 bytes
    size of m_array as reported by count_em() function : 20 bytes

    other_stuff(m_array) called

    size of m_array as reported by count_em() function : 8 bytes

    more_stuff() called (touches g_array)

    Better not call count_em(g_array) !!!
    -------------------------------------------------------------

    Hope I didn't foul all that up. If I did, we'll hear about
    it soon enough! :)


    > Thanks in advance..


    You're welcome after the fact. :)

    -Mike
     
    Mike Wahler, Feb 10, 2004
    #3
  4. On Mon, 09 Feb 2004 22:38:19 -0800, Herrcho wrote:

    > in K&R Chapter 6.3
    >
    > it mentions two methods to calculate NKEYS.
    >
    > and points out the first one which is to terminate the list of
    > initializers with a null pointer, then loop along keytab until the end
    > is found is less efficient than using sizeof operator , since size of
    > the array is completely determined at compile time.
    >
    > i don't quite understand this. Could anyone explain to me in detail ?
    >
    > Thanks in advance..


    Don't have the book handy, but it seems simpl enough. Here's the first
    case:

    char *array[100] = { val1, val2, ... NULL };

    Now you can loop through the array until you reach the NULL; if you've
    filled in all the values array[0] ... array[98] with values and array[99]
    with NULL, you'll get your count. Like so:

    int i;

    for ( i = 1; i <= 100; i++ )
    if ( array[i-1] == NULL )
    break;

    Thing is, that requires 100 loops and comparisons. Now try this:

    char *array[100];

    size_t n = sizeof(array)/sizeof(array[0]);

    Assuming a char * takes, say, 4 bytes, then the size of the array will be
    400 bytes, the size of array[0] will be 4 bytes, and 400/4 == 100, which
    is the number of elements. Better yet, since sizeof is a compile-time
    thing, this works out to a simple assignment: size_t n = 100;
     
    Kelsey Bjarnason, Feb 10, 2004
    #4
  5. Herrcho

    pete Guest

    Kelsey Bjarnason wrote:
    >
    > On Mon, 09 Feb 2004 22:38:19 -0800, Herrcho wrote:
    >
    > > in K&R Chapter 6.3
    > >
    > > it mentions two methods to calculate NKEYS.
    > >
    > > and points out the first one which is to terminate the list of
    > > initializers with a null pointer, then loop along keytab
    > > until the end is found is less efficient than using sizeof
    > > operator , since size of the array is completely
    > > determined at compile time.
    > >
    > > i don't quite understand this.
    > > Could anyone explain to me in detail ?
    > >
    > > Thanks in advance..

    >
    > Don't have the book handy, but it seems simpl enough.
    > Here's the first case:
    >
    > char *array[100] = { val1, val2, ... NULL };
    >
    > Now you can loop through the array until you reach the NULL; if you've
    > filled in all the values array[0] ... array[98]
    > with values and array[99] with NULL, you'll get your count.
    > Like so:
    >
    > int i;
    >
    > for ( i = 1; i <= 100; i++ )
    > if ( array[i-1] == NULL )
    > break;
    >
    > Thing is, that requires 100 loops and comparisons.


    char *ptr;

    for (ptr = array; ptr != NULL; ++ptr);

    --
    pete
     
    pete, Feb 10, 2004
    #5
  6. Herrcho

    pete Guest

    pete wrote:
    >
    > Kelsey Bjarnason wrote:


    > > char *array[100] = { val1, val2, ... NULL };


    > char *ptr;


    char **ptr;

    > for (ptr = array; ptr != NULL; ++ptr);


    --
    pete
     
    pete, Feb 10, 2004
    #6
  7. "pete" <> wrote in message
    news:...
    > Kelsey Bjarnason wrote:
    > >
    > > char *array[100] = { val1, val2, ... NULL };

    ....
    > > int i;
    > >
    > > for ( i = 1; i <= 100; i++ )
    > > if ( array[i-1] == NULL )
    > > break;
    > >
    > > Thing is, that requires 100 loops and comparisons.

    >
    > char *ptr;
    >
    > for (ptr = array; ptr != NULL; ++ptr);


    Two questions:
    1. How many loops would this execute in your opinion, given the
    initialization above? (I admit, I assume the NULL is the *last* element in
    the array.)
    2. How does it calculate the number of elements? ;-)
     
    Peter Pichler, Feb 20, 2004
    #7
    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. Peter Hansen
    Replies:
    2
    Views:
    905
    yaipa h.
    Jun 27, 2003
  2. Jim Barlow
    Replies:
    5
    Views:
    390
    Jim Barlow
    Mar 13, 2008
  3. Hicham Mouline
    Replies:
    1
    Views:
    397
    Kai-Uwe Bux
    Apr 11, 2010
  4. Cool Wong
    Replies:
    8
    Views:
    134
    Robert Klemme
    Jun 28, 2007
  5. Markus Fischer
    Replies:
    0
    Views:
    104
    Markus Fischer
    May 13, 2005
Loading...

Share This Page