Well, there are a few solutions I see for this: 1) Use a value outside the range; 2) use an auxiliary vector for this or; 3) use a more complex data structure.
Also worth knowing the Null Object project pattern.
Approach 1
If you are using an integer array (which allows values of -2^31 until 2^31 - 1), but the values that interest you are only a range of those values, so you can use one of the values outside the range to represent an unfilled value. Normally the values 0 or -1 are used for this purpose (or if the data is not numerical, it can be used NULL, an empty string, the address of a struct with empty data, the address of a function that does nothing, or some other type of data that means empty, unfilled or undefined). In the case of integers, when 0 or -1 are valid, some other number outside the range can be used.
This is the memory-saving approach, and is also the most common approach.
Approach 2
On the other hand, if you can’t or don’t want to use an out-of-range value, then maybe an auxiliary vector will suit you. The simplest way is to create a vector of int, short or char of the same size as its original vector and fill it with 0 where the value of its main array should be disregarded and considered as unfilled and 1 otherwise.
To save memory, using a more sophisticated implementation, it is possible to work directly with bits in order to have a vector of char where each position of the auxiliary vector represents 8 positions of the original vector.
Approach 3
Finally, the last approach is to do something more or less like this:
typedef struct {
char usado;
int valor;
} Elemento;
And then, instead of using an array like int[], you will use Elemento[]. This approach consumes one byte more for each element you want to use (meaning 7 bits of memory are wasted per element).
This memory waste can be avoided by using it in each Elemento, eight values together with only one character to track what was marked, but in this case the 2 approach turns out to be simpler and more efficient in practice.
If your vector uses a fixed size data (e.g..:
intfour-byte,doubleof 8 bytes, etc.) so it makes no difference whether the value stored in it is high or low - the space occupied will be the same, the time to compare this value with the markup is the same, etc. In my opinion it is the simplest solution, only if the range occupies the type of the whole data and there are no unused values is that I would opt for a more complex solution (a bit array, for example). P.S. Could please [Edit] the question indicating the language and type of data used?– mgibsonbr
Edited! Thank you very much for the clarification.
– Moni
Would it be {-2 16 to 2 16} or would it be {-2 16 to 2 16-1}? Or maybe {-2 15 to 2 15-1}? The reason is that to fit in 16 bits using complement notation of 2 (the binary notation used in modern computers), then the interval would be {-2 15 to 2 15-1}.
– Victor Stafusa