Take a look at this example. How many salaries do I need? Here I've planned on 10, but if I need more, there is no push_back(), as there is with vector, which would allow expansion. This program is limited to a maximum of 10 salaries.

The loop itself can end in one of three ways:

• The user can enter 10 salaries and, because the array is full, the loop will end. All of the elements in the array will be used.
• The user can enter a 0 as a salary (the sentinel), and the loop will terminate. Only some of the elements will be used in the array.
• The user can enter a non-numeric value such as the word "quit" and the cin object will enter the fail state when trying to read the next salary. The if statement inside the loop checks for this and exits when this occurs.

Once you exit the loop, you don't know which of these occurred. Even worse, you can't tell how many elements are actually valid, and which are unused. Let's fix that.

When you don't know how large an array should be when you write the code, then you should plan for the "worst case", and declare an array that you know is larger than you could ever possibly need. Then, only use part of it.

Go ahead and modify the example on the previous page. We want to allow the user to input any number of values, (or at least a very large number), instead of automatically filling the array with 10 values.

1. Define a constant that indicates the maximum number of elements used, (like 100), and use that constant in the declaration of the array.
2. Create a separate variable to track the effective size of the array. The names size and capacity are typically used for these variables.
3. Write an input loop using while that checks the necessary bounds condition, while(size < capacity)... This ensures that the loop never overfills the array.
4. Use the loop-and-a-half idiom to leave the loop whenever the sentinel value (0) is entered, or, when cin enters the failed state from invalid input.
5. Store the value into the array, and update the size variable so that the next number entered will be placed in the next element of the array.

When you traverse a partially-filled array, your algorithms must use the effective size as your loop bounds. Here's an example which computes the highest salary in the array.

double highest{0.0};
if (size > 0)
{
    highest = salaries[0];
    for (size_t i = 1; i < size; ++i){ 
        if (salaries[i] > highest){ 
            highest = salaries[i];
       } 
   } 
}

Note that you can only inspect the elements with an index less than size, because the remaining elements have never been set, so their contents are undefined.

Instead of adding items to the end of the "unoccupied" section of numbers in an array, suppose you placed each number into its correct (ordered) position instead, like this:

The array shown here is partially filled, and the next number, 3.25, has been input by the user. To put the number in its correct location you need to:

1. Locate the first number that is larger than the number you're going to insert into the array. Here, that's the number 7.1.
2. Before you can store 3.25, the 7.1 needs to be moved to the right. But first, the number occupying that spot must be moved, and so on.
3. After all of the existing numbers have been moved to the right, come back and store the new number in the spot that's been opened up.

This only makes sense when used with partially filled arrays; if you try to insert an element into a completely filled array, then the last element in the array will be lost when the previous items are moved to make room for the inserted item.

Let's look at a practical example of this algorithm. The insert() function at the top of the program has not been completed, so we're going to go ahead and do that.

1. Find the position where the new element should be inserted:

size_t pos = 0;
while (pos < size && a[pos] < value) 
{ 
    ++pos; 
}

The variable (pos) is initialized to 0. After the loop, it will contain the location where the new element should be inserted.

If there are no elements larger than the number you are inserting, pos will contain the same value as size, and the number will then be added at the end of the array, which is what you want.

2. Move the existing elements. Before you can store value in the array, you must move the existing elements out of the way (to the right), to "open up a hole" for the new value.

for (size_t i = size; i > pos; --i) 
{ 
    a[i] = a[i - 1]; 
}

You must start at the end of the array, traversing to the left, until you reach the location where you intend to insert the new element, so you don't overwrite data.

3. Insert the new element. After moving, copy the new number into position, and update the size.

a[pos] = value;
++size;

Removing elements from a partially-filled array uses a similar algorithm. Instead of moving a portion of the array to the right, to "open up a hole", you need to move all of the elements which are to the right of the deleted element leftwards to "close up the gap".

Here's a small fragment of code that does that. The variable pos is the location of the element you want to delete:

--size;
for (size_t j = pos; j < size; ++j) 
{ 
    a[j] = a[j + 1]; 
}

Before the loop, you should decrement size so that when you grab a[j + 1], it is a valid element when the array is already full.

Since, when you remove an element, the following elements are moved into the position of the deleted value, you have to be especially careful when removing multiple values from the same array. Here's an example:

for (size_t i = 0; i < size; ++i)
{
    if (a[i] == 7)
   { 
        --size;
        for (size_t j = i; j < size; ++j) 
        { 
            a[j] = a[j + 1]; 
       } 
   } 
}

If you run it, you'll see that it doesn't quite work. It should remove all of the sevens from the partially-filled array, but removes only some of them.

As you can see, when you remove the first seven, you skip over the seven immediately following it. To fix this, make sure that you adjust the loop index, so that it revisits the current index whenever you remove an element. Here's the fixed version of this problem .