Partially Filled Arrays and Tracking Used Elements

A C style array always takes up a fixed amount of memory. It stores a predetermined number of elements, determined by how it's declared.

Often, the number of values stored in the array is much less than the total capacity. This number is also often changing (up or down).

In this situation, the array is said to be partially filled, and your program needs to keep track of the actual number of elements.

The standard practice to keep track of used elements is to create an integer variable dedicated for this purpose. This integer might be called the size, count, or number of used elements (or variations thereof).

All parts of your program that read or write the array must acknowledge and obey this count, and not the array's capacity.

For instance, you might have an array that's capable of holding 8 integers, but it currently only holds 3 values. The count should be 3. When the count is zero, no value has been stored.

A new value is stored in an index that equals the count.

Then the count is incremented, and now the array has one element, located at index 0. A loop printing all the values should iterate from 0 up to (but not including) the count.

The other storage locations are still there but should be ignored as they don't form part of the logical list of data, but a loop continuing up to the capacity would try to print garbage.

#include <iostream>

int main()
{
    const int capacity = 8;
    int values[capacity] = {};
    int used = 0;

    values[used] = 10;
    // Increment the value before the expression uses it
    ++used;

    values[used] = 20;
    ++used;

    values[used] = 30;
    ++used;

    for (int i = 0; i < used; ++i)
    {
        std::cout << values[i] << '\n';
    }

    return 0;
}

The capacity is the fixed amount of storage available. The count or number of used elements is the number of positions in the array that currently hold meaningful data.

These are often different, for instance, a program can have a 5 integer array but currently holds only 2 actual values. If a loop tries to print everything when it iterates up to the capacity (5 in this case) it will print the 2 "good" values, followed by 3 meaningless values (old data or initialized to 0s).

#include <iostream>

int main()
{
    const int capacity = 5;
    int data[capacity] = {};
    int used = 0;

    data[used] = 7;
    ++used;

    data[used] = 14;
    ++used;

    // Incorrect: looping to capacity instead of used.
    // for (int i = 0; i < capacity; ++i)
    // {
    //     std::cout << data[i] << '\n';
    // }

    for (int i = 0; i < used; ++i)
    {
        std::cout << data[i] << '\n';
    }

    return 0;
}

There's no room in a partially filled array for a new element when the number of used elements equals the capacity. To add a new value to such an array, you should check first if the number of used elements is strictly less than the capacity.

Then, store the new value at index equal to the current count, and finally increment the count.

If the condition isn't met, an addition should not be performed.

Failing to check this would write an element at index equal to the capacity, a position outside the valid range for the array; producing undefined behavior.

#include <iostream>

int main()
{
    const int capacity = 4;
    int list[capacity] = {};
    int used = 0;

    // Include the upper boundary in this loop
    for (int n = 1; n <= 6; ++n)
    {
        if (used < capacity)
        {
            list[used] = n * 10;
            ++used;
        }
        else
        {
            std::cout << "Array is full, cannot add " << n * 10 << '\n';
        }
    }

    for (int i = 0; i < used; ++i)
    {
        std::cout << list[i] << '\n';
    }

    return 0;
}

Removing an element does not alter the capacity of the array itself, but reduces the number of used elements by one. After removing an element at a particular position, all elements after it must be shifted down by one index, filling in the vacated space.

For example, if we removed an element at index 2, we'd copy the element at index 3 to index 2, the element at index 4 to index 3, and so on until the last used element. Finally, we'd decrement the count; the old position in memory now contains a duplicate of the previous element but is no longer recognized as meaningful data.

#include <iostream>

int main()
{
    const int capacity = 6;
    int seq[capacity] = {5, 10, 15, 20, 25, 0};
    int used = 5;

    // Remove the element at index 2.
    for (int i = 2; i < used - 1; ++i)
    {
        seq[i] = seq[i + 1];
    }

    --used;

    for (int i = 0; i < used; ++i)
    {
        std::cout << seq[i] << '\n';
    }

    return 0;
}

When working with partially filled arrays, it's crucial to use the count integer, not the array's capacity, in all operations on the data it represents: printing, searching, modification, addition, removal they should all be controlled by the count. The capacity of a partially filled array is a fixed parameter related to the physical memory.

The count, on the other hand, is a dynamic property determined by the operations in your program.

If you keep track of count accurately, your partially filled array would mimic a dynamically sized list, while still utilizing a fixed size C style array.

Ignoring the count would typically lead to either printing/processing meaningless data or an illegal memory access.