Vector Implementation and Element Access

The Vector implementer must detect out-of-range access and inform the user, who then decides what action to take.

Programming

A Request Outside the Stored Elements

Every container has a rule about which positions are legal. A Vector holds a fixed number of elements, and its subscript operator lets a program pick one of them by index. Asking for an index that does not correspond to a stored element is an error in the program that made the request. This article looks at how the Vector implementation responds to such a request, and at the one mechanism the source uses to respond: throwing an exception.

What do you think happens?

A Vector holds four elements, and the program asks for index -1. Does the Vector hand back some element, or does something else happen?

It returns the element at the last position
It returns a reference to some default element
It throws an exception instead of returning an element

Reveal answer

Answer:

It throws an exception instead of returning an element.

The guard at the top of the subscript operator tests whether i is less than 0. Index -1 is not a position inside the Vector, so the test is true and the throw runs. A failing guard causes an out_of_range exception to be thrown, and a passing guard is the only case that returns a reference to an element.

Keep one question in mind as you read: when a request falls outside the valid range, what should happen to the code that made the request? The guarded code shown later gives one concrete answer, and the rest of the article traces how that answer plays out.

Who Detects and Who Decides

The source states the design goal directly. The person who writes the Vector implementation is responsible for detecting an attempted out-of-range access. Detection alone is not enough. The implementer must then tell the user about the problem, and once the user knows, the user can take appropriate action.

Two things are ruled out by this design. The request is not quietly repaired, for example by clamping the index to a nearby valid position. It is also not quietly ignored, for example by returning nothing and letting the program continue as if nothing happened. The error is surfaced so that the code that caused it, or the code that calls it, can respond.

The job splits into two parts. The Vector knows the valid range, because it knows its own size. The user knows what the program should do next, such as stopping, logging the problem, or trying a different index. Throwing an exception is the channel through which the Vector hands the problem to the user without deciding on the user's behalf.

The Valid Index Range

The valid indices of a Vector are the positions that hold stored elements. The guard in the subscript operator describes this range from both sides: an index below zero is rejected, and so is an index equal to or greater than size(). Taken together, an index is valid when it is 0 or greater and strictly less than size(). The diagram below places the boundaries on a Vector of size 4.

Which indices map to real stored elements, and where do the first valid index, the last valid index, and the first invalid index fall relative to size?

Notice that the first invalid index for this Vector is exactly size(). The position one past the last element is not a stored element, so the guard treats it the same way it treats -1. Both invalid cases share one throw path, which is why a single guard covers the whole range.

Reading the Guard Condition

The guard appears at the top of the function, before any element is touched. The source describes its test as i less than 0, or size() less than or equal to i. Those are two comparisons joined by an or, so the throw runs when either one is true. The guard is written as an illustrative sketch below; it follows the condition the source describes, but it is not a copy of the source's literal code.

python

reference operator[](int i) {
    if (i < 0 || size() <= i)
        throw out_of_range("index out of range");
    return elem[i];
}

reference operator[](int i) {
    if (i < 0 || size() <= i)
        throw out_of_range("index out of range");
    return elem[i];
}

Notes on the code

The guard runs first, before any element is read.
The first test covers indices below the valid range.
The second test covers indices at or past size().
The return statement is reached only when neither test is true.

What does each part of the guard condition contribute, and which exact input values make it true?

The two tests do different jobs. The first handles the lower side of the range, so an index of -1 makes it true. The second handles the upper side, so an index equal to size() makes it true. Because the two are joined by or, the throw path is taken as soon as one of them succeeds, and the second comparison is never needed for an input the first test has already rejected.

Tracing a Valid Access and a Rejected One

Worked example

Two calls to the same subscript operator

A Vector of size 4 receives two calls: one with index 2, and one with index -1. Trace what the guard decides for each call.

1
Call with index 2, first test
Is 2 less than 0? No. The first test is false, so the guard moves on to the second test.
2
Call with index 2, second test
Is size() less than or equal to 2? That is 4 less than or equal to 2, which is false. Both tests are false, so neither throw condition holds.
3
Call with index 2, return
The guard passes and the function returns a reference to the element stored at index 2.
4
Call with index -1, first test
Is -1 less than 0? Yes. The first test is true, which is enough for the or to make the whole guard true.
5
Call with index -1, throw
The second test is never evaluated for this input. The throw runs and an out_of_range exception is raised, so no element is returned.

Result

Index 2 takes the valid path and returns a reference to an element. Index -1 takes the throw path at the first test, and the exception carries the problem out of the function.

Where the Two Paths Split

After the guard check, which step does the valid path take and which step does the out-of-range path take, and at exactly which decision point do they split?

Every call enters at the same point and must pass the guard. The split happens at the decision node, and only one of the two outgoing paths is taken for a given index. The valid path ends by returning a reference to a stored element. The throw path ends in an exception rather than a returned element, and it is the only path that hands control to whoever called the function. The guard decision is therefore the moment where the behavior of a valid request and a rejected request diverges.

Mistakes When Reading the Guard

Common mistake
Assuming the Vector repairs a bad index on its own
What it looks like
Expecting index -1 to quietly become index 0.
Why it fails
The source says the request is not quietly repaired. The implementer detects the problem and reports it.
Do this instead
Treat a rejected index as an error signal that the caller must handle through the exception.
Common mistake
Thinking the second test must run for every bad index
What it looks like
Reasoning through size() <= i for index -1 before checking i < 0.
Why it fails
The first test is true for -1, so the or is already true and the second test is not needed for that input.
Do this instead
Evaluate the tests in order and stop once one of them decides the outcome.
Common mistake
Believing index equal to size() is a valid position
What it looks like
Treating index 4 as the last element of a Vector of size 4.
Why it fails
The second test uses less than or equal to, so an index equal to size() triggers the throw.
Do this instead
The last valid index is size() minus 1; size() itself is the first invalid index.
Common mistake
Expecting the guard to run after the element is read
What it looks like
Imagining the element is fetched and then checked.
Why it fails
The guard sits at the top of the function, before any element is touched.
Do this instead
Picture the guard as the gate every call must pass through first.

Checking Your Trace

EASY

The same Vector of size 4 receives a request for index 4. Which test in the guard is true, and which path does the call take?

Hints

Compare 4 against size(), which is 4 here.
Ask whether the second test, size() less than or equal to i, is satisfied.
Decide whether a returned reference or a thrown exception comes out of the call.

Your attempt (not saved)

MEDIUM

A Vector of size 10 receives requests for indices 0, 9, 10, and -3. For each one, state whether the guard is true, which test made it true (if any), and whether the call returns a reference or throws. Then identify the single index where the first test is the one that decides the outcome.