Searching an array with an unknown length

[Hopp3r]

So I was asked to write some simple functions that would search through an array of length (s) and tell how many times an (integer, double etc. ) appeared within the array. It's pretty simple because they give you the length of the array. However one of the functions doesn't have a length passed with the other parameters!

char arrayX(char a[], char v)

Where you are asked to find amount of times value (v) is in the array.

What is the simplest way to do this?
What would be the most efficient if the array turned out to be VERY large?

[deceptikon]

What is the simplest way to do this?

It's not a matter of simple or not, it's a matter of possible or not. If you're not given a size, can't assume a size, and there's no sentinel value marking the end of the array then you're shit out of luck. In the general case, it's simply not possible to determine the size of an array when all you have is a pointer to the first element.

You seem to be missing key information to solve this problem, such as how is the array set up? Are the items in random order or are they sorted somehow? Is there a sentinel value marking the end? You should probably go back to the person who gave you the assignment and ask for details.

[Suzie999]

Well since a bog standard char is 1 byte, you simply loop every byte testing for char v..

If v is an int or double then you increment your search search by sizeof(v).

[Hopp3r]

this might be a silly question, as i'm not familiar with sizeof(), what would a loop through each byte look like?

[mrnutty]

If you don't know the size of the parameter 'a' in your example, then it is not possible to correctly write the needed logic with the given information. Sure we can assume things such as the char array is null terminated which is a natural assumtion in this case, but its still an assumption.

[Suzie999]

You said this

It's pretty simple because they give you the length of the array

That's when you can just loop through it.

sizeof(int) for example in visual studio is 4 bytes, a char is 1 byte. hers a quick example

int arrayX(char * a, char lookfor, int size){

    int found = 0;

    for (int i = 0; i < size; i++){

        if (a[i] == lookfor){

            found++;
        }
    }

    return found;

}

int main()
{
    char a[10] = {'a','b','z','c','z','e','f','g','z','z'};

    cout << arrayX(a,'z',10) << endl;

    return 0;
}

Note that this works fine for char, because char is 1 byte (the size of each element of the array if you will).

If the type were int for example, you need to do a bit of testing forinstance
check that the size of the array is divisible by the type of the array, so as not to exceed its bounds.

If you do not know the size of the array, then iy will become much more complicated, but I would not say impossible.

[NathanOliver]

@ Suzie999 the OP also said this

However one of the functions doesn't have a length passed with the other parameters!
char arrayX(char a[], char v)
Where you are asked to find amount of times value (v) is in the array.

He is trying to write a function to deal with an array where he is not getting a size of the array. If there is not a sentinal value in the array to mark the end there is no posible way to find out the size of the array that is standard conforming and portable. All you get in the function is a pointer to the first value of the array.

[deceptikon]

Note that this works fine for char, because char is 1 byte (the size of each element of the array if you will).
If the type were int for example, you need to do a bit of testing forinstance
check that the size of the array is divisible by the type of the array, so as not to exceed its bounds.

I don't understand the point you're trying to make. If you change char to int in your code example, it will still work perfectly:

int arrayX(int * a, int lookfor, int size){
    int found = 0;

    for (int i = 0; i < size; i++){

        if (a[i] == lookfor){

            found++;
        }
    }

    return found;
}

int main()
{
    int a[10] = {'a','b','z','c','z','e','f','g','z','z'};

    cout << arrayX(a,'z',10) << endl;

    return 0;
}

Did you mean only changing lookfor to int and leaving a as a pointer to char?

If you do not know the size of the array, then iy will become much more complicated, but I would not say impossible.

Please describe this "more complicated" solution of finding the size of an array when given nothing but a pointer.

[Moschops]

However one of the functions doesn't have a length passed with the other parameters!

char arrayX(char a[], char v)

Where you are asked to find amount of times value (v) is in the array.

What (almost) everyone said above is very true; if there is no length given and you don't know about any special value marking the end of the array (or some other such known information about the array that would help you find the end of it), you've got no chance. There is no way to know how long the array is if all you have is a pointer to it.

However, it is interesting that the array for which you do not have a length is a char array. In old-school C-style strings, whilst there is no special value marking the end of the char array, there is a special value marking the end of the char objects that you actually care about. The value zero (not the char '0', the actual value zero).

As such, if I had to guess, either the question is wrong (i.e. length should be there) or whoever set the question intends this to be a C-style string with a zero on the end marking the end of the char objects you care about, and didn't tell you.

[NathanOliver]

I would guess that the char array he is getting is a string and it is null terminated as well but that is just a guess. Without seeing the problem statement it's impossible to tell what is going on. Just like getting the size of an array from only a pointer to the begining ;)

[Suzie999]

Please describe this "more complicated" solution of finding the size of an array when given nothing but a pointer.

I don't have a solution, but I do know it would be complicated, and I've learnt never to assume something is impossible in the land of programming.

This is something that first popped into my dumb head though.

int SizeOf(int * v){

    int i = 0;
    while (v[i] < 2147483648 && v[i] > -2147483647){

        i++;
    }

    return i;
}


int main()
{
    int i[5] = {1,2,3,4,5};

    cout << SizeOf(i) << endl;;

    return 0;
}

I know in reality, there is no assurance that another int does not follow i[4]
and I would also probably check each value for being unsigned too, but like I said, I do not have a solution.

[deceptikon]

I don't have a solution, but I do know it would be complicated

If you don't know of a solution, how do you know it would be complicated? ;)

I've learnt never to assume something is impossible in the land of programming.

That's not a bad thing, though in this case it is indeed impossible without introducing assumptions about the contents of the array or relying on non-portable solutions. Note that I'm making the same hedge about the unknown here. While I'm not aware of a platform-specific hack that would give you the size of an array through a pointer to its first element, I can't confidently say that no such solution exists.

while (v[i] < 2147483648 && v[i] > -2147483647)

I suspect you believe that this loop works because 2147483648 is overflowing a signed int and wrapping around to INT_MIN on your implementation. When I test the code on Visual Studio 2012 (Windows 7), v[5] is -858993460. The maximum value for signed int is 2147483647 as well, and by saying 2147483648 the behavior on this implementation is to wrap to -2147483648, which is certainly less than -858993460. Thus the loop terminates with the correct result, but certainly not because it's working as intended.

You can break the code by making any value in the array negative.

A more portable loop would be:

while (v[i] < INT_MAX && v[i] > INT_MIN)

But then the bug that caused it to appear to work for your test case will completely fail, overrun the array, and like crash in short order.

I know in reality, there is no assurance that another int does not follow i[4]

Actually, you do have that guarantee. There's no case where a pointer to int, when dereferenced, will evaluate to a value outside the range of signed int. You might get lucky and hit a trap representation if the source array type isn't int, but that would cause abnormal termination rather than a useful return value from SizeOf()

All in all, I won't say your idea is a bad notion, but it's certainly not going to work for the intended purpose.

[Suzie999]

Thinking about it, I'm unsure why anyone would give a student such a task, how could you ever have a c-style array you do not know the size of anyway?

I suppose one reason might be to teach them that you need to know and keep track od the size of your arrays, the hard (but rememberable) way.

[deceptikon]

Thinking about it, I'm unsure why anyone would give a student such a task, how could you ever have a c-style array you do not know the size of anyway?

I suspect one of two things:

1. The OP simply misinterpreted the problem requirements (most likely).
2. The problem requirements are wrong for some reason.

[CGSMCMLXXV]

I do know it would be complicated

[...] in this case it is indeed impossible without introducing assumptions about the contents of the array or relying on non-portable solutions.

Both right. There is a solution, but is complicated and non-portable. It's both complicated and non-portable because you rely on OS to extract that info. For example, under Linux platform you can check /proc/(PID)/ to see that info (see this).

[mrnutty]

while (v[i] < 2147483648 && v[i] > -2147483647)

I have no words...except this sentence.

[Hopp3r]

OP here, posting from my ipod so bear with me. These are the specifics for this function of array processing taken directly from the assignment. I'd figure it's safe to assume some things about the array as its not an advanced class.

int arrayX(char a[ ], char v)

Function arrayX takes two parameters.
a - an array of type char
v - char value that you are searching for
Return: the frequency of the value v in the array a.

[NathanOliver]

Do you know if the char array is null terminated? If that is all the instructions say then based on what you posted I would say it is impossible. If the char array is null terminated then when you are going through the array your stop condition will be if where you are at is equal to '\0'

//...
int i = 0;
while(charArray[i++] != '\0')
{
    // check goes here
}
//...