3 ms·

>It's not clear to me how you're supposed to "tack the item on to the end of the array", though. That's not an operation arrays naturally support. It's a small

by mrob 7y ago

>It's not clear to me how you're supposed to "tack the item on to the end of the array", though. That's not an operation arrays naturally support. It's a small change to avoid the append. First check the final array item separately, and return success if it matches. If it doesn't match, overwrite the final array item with the desired item, and continue as before except this time checking if you're within array bound - 1.

MRD85 7y ago
Do most array structures have a pointer to last element? Or similarly useful do they track length?
- mrob 7y ago
  Not in C and similar languages, but you already need to know the length for the bounds check.
  - e12e 7y ago
    I think you could argue Pascal is similar to c? And Pascal typically encodes length/size in the first slot.
Someone 7y ago
It probably is easier to reserve an array item for that sentinel marker. In either case, it requires your array to be writable, and you’re giving up having multiple searches through the same array operating at the same time. Also, on modern hardware, the ‘ran out of items’ check is essentially free. Nowadays, the only realistic use for this would be a case where you have a fixed-size array that you search frequently, where the same end marker can be used all the time, so that you can add that sentinel marker once. I’ve a hard time thinking of examples, but do not rule out cases inside OS kernels or search trees for computer chess or similar games. A variant would be to use this in C, and, when the program allocates N+1 chars to hold a string of length <N, allocate N+2 chars, and set the last one to zero, to ‘guarantee’ that later strlen or strcpy calls don’t run on forever, even if a strncpy copies N+1 bytes. I don’t see how that ‘guarantee’ would add much, though.
- Arnavion 7y ago
  >Nowadays, the only realistic use for this would be a case where you have a fixed-size array that you search frequently, where the same end marker can be used all the time, so that you can add that sentinel marker once. The sentinel needs to be identical to the value you're searching for, otherwise you're trading "compare a pointer" for "compare a value with an arbitrary equality implementation" which is no better (and probably worse).

by mrob 7y ago

MRD85 7y ago

Do most array structures have a pointer to last element? Or similarly useful do they track length?

mrob 7y ago
Not in C and similar languages, but you already need to know the length for the bounds check.
- e12e 7y ago
  I think you could argue Pascal is similar to c? And Pascal typically encodes length/size in the first slot.

Someone 7y ago

It probably is easier to reserve an array item for that sentinel marker. In either case, it requires your array to be writable, and you’re giving up having multiple searches through the same array operating at the same time. Also, on modern hardware, the ‘ran out of items’ check is essentially free. Nowadays, the only realistic use for this would be a case where you have a fixed-size array that you search frequently, where the same end marker can be used all the time, so that you can add that sentinel marker once. I’ve a hard time thinking of examples, but do not rule out cases inside OS kernels or search trees for computer chess or similar games. A variant would be to use this in C, and, when the program allocates N+1 chars to hold a string of length <N, allocate N+2 chars, and set the last one to zero, to ‘guarantee’ that later strlen or strcpy calls don’t run on forever, even if a strncpy copies N+1 bytes. I don’t see how that ‘guarantee’ would add much, though.

Arnavion 7y ago
>Nowadays, the only realistic use for this would be a case where you have a fixed-size array that you search frequently, where the same end marker can be used all the time, so that you can add that sentinel marker once. The sentinel needs to be identical to the value you're searching for, otherwise you're trading "compare a pointer" for "compare a value with an arbitrary equality implementation" which is no better (and probably worse).