开发者

How many elements are full in a C array

If you have an array in C, how can you find out how much of it is f开发者_如何学运维illed?


In a C array, any element is an object. It's not like in Java where you have references that first have to be assigned to point to objects. Anything in C behaves like a primitive type in Java.

If you have an array of pointers in C, you may view this similar to how things in Java work. You can use null pointers to designate "is not filled to point to an object":

// creates an array of 10 pointers, and initializes all of
// them to null pointers. If you leave off "{ 0 }", you 
// have to manually initialize them!
struct foo *array[10] = { 0 };

Then you can simply test with

if(array[i] == 0) {
  printf("Position %d does not point to an object!\n", i);
}


You need to keep track of this yourself. There is no concept of "full" (or anything in between for that matter): you have to define this.

Of course if the elements are contiguous in the array, you could use a NULL element to signify the "end" of the array thus defining a "full" state at the same time.


It's all filled, so the answer is whatever the size of your array is. An array is a contiguous memory segment, so it is filled by default with whatever was at that memory location before.

But you probably want to know how much of it is filled with data that you care about, and not with random data. In that case, there is no way of knowing that unless you keep track of it yourself.


I agree with other answers, but I can suggest you a way to make your work easier. You can manage the array like an object and control the adding and the removing of data. If you implement two functions, one to add elements and one to remove them, with the proper logic to manage fragmentation and multi-threading, you can track the number of elements into the array reading a counter, which is written only by add and remove function. So you don't have to execute a loop every time you need to count the elements.


From the C language perspective, there is no concept of "filled". Once an array is defined, memory is allocated to it. For arrays like array1 (see example below), elements get initialized to 0. However, for arrays like array2, the elements can have random value.

So, the notion of "filled" has to be supplied by the program. One possible to "in-band" way is to: (a) Choose one specific value of the element type (e.g. 0xFFFFFFFF) and use it to detect fill/empty property of each array element (However, realize that this approach takes away one otherwise valid value from the element set.), and (b) "initialize" all the elements of the array to that disallowed value at suitable position in the program scope. (c) To find array fill level, count the number of valid elements.

$ cat t2.c
#include <stdio.h>
#define N 10

typedef unsigned long int T;

static const T EmptyElementValue = 0xFFFFFFFF;
// Choose any suitable value above. However, the chosen value
// would not be counted as an "empty" element in the array.

static T array1[ N ];

void
printArray( T a[], size_t length )
{
    size_t i;
    for( i = 0; i < length; ++i )
    {
        printf( "%lu, ", a[ i ] );
    }
    printf( "\n" );
}

size_t
numFilledElements( T a[], size_t length )
{
    size_t fillCount = 0;
    size_t i;

    for( i = 0; i < length; ++i )
    {
        if( a[ i ] != EmptyElementValue )
        {
            fillCount += 1;
        }
    }

    return fillCount;
}

int main()
{
    T array2[ N ];
    size_t i;

    printArray( array1, N );
    printArray( array2, N );

    //------------------------------------------//

    // Make array2 empty
    for( i = 0; i < N; ++i )
    {
        array2[ i ] = EmptyElementValue;
    }

    // Use some elements in array2
    array2[ 2 ] = 20;
    array2[ 3 ] = 30;
    array2[ 7 ] = 70;
    array2[ 8 ] = 80;

    printf( "Number of elements \"filled\" in array2 = %u\n",
        numFilledElements( array2, N  ));

    // Stop using some elements in array2
    array2[ 3 ] = EmptyElementValue;

    printf( "Number of elements \"filled\" in array2 = %u\n",
        numFilledElements( array2, N ) );


    return 0;
}


$ gcc -Wall t2.c -o t2


$ ./t2
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 60225, 2280452, 1627469039, 1628881817, 2281060, 2280680, 1628304199, 1628881818, 47, 
Number of elements "filled" in array2 = 4
Number of elements "filled" in array2 = 3

$


Subtract the number of empty elements from the size of the array. ;-)

Sorry, there is no way (except you keeping track), to tell whether an array element has been modified.


in C, there is no built-in way of knowing how many elements are filled with data that you care about. You will need to build it yourself. As was previously said, if you can have a value that will not represent anything(0 for example), you could :

  1. Count the elements that do not have this undefined value.
  2. If your filled elements will be in the same block of memory, you can look for the undefined value(Sentinel)

On the other hand, if you need the extent of your data to be represented, You will need a flag array that will keep track of the elements that are set and those that aren't :

For example, if you have an array of 32 elements or less, you only need an unsigned integer to keep track of your array: 1100010 ...

Values:

1 -> Set

2 -> Set

3 -> no set

4 -> not set

5 -> not set

6 -> set

etc.

So Whenever you are filling an element you call the function that sets the correct bit and when you are "unfilling" the data you unset the bit that corresponds to it.

Once this is done, All you would need to do is simply call a popcount over the flag array.


You could do a while(yourArray != NULL)loop and through the loop just increment an integer value and that should tell you.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜