Standard-Library vector
A Vector is not useful until initialization gives its elem member a pointer to real storage and sets sz to the element count.
A Vector Without Storage
Declaring a struct gives you a set of named members, but it does not give those members useful values. Consider a Vector whose elem member is meant to point to a sequence of doubles and whose sz member records how many doubles there are. Until something makes elem point at real storage, the Vector has no elements to work with. By itself, the Vector is not of much use, because its elem pointer does not point to anything.
This section is about the step that fixes that problem. Initializing a struct means allocating memory for its members and assigning values to them. The function vector_init does exactly that for a Vector. It takes a Vector and a count s, and it changes the Vector it receives. Before reading the explanation, make a prediction about what the caller's Vector looks like after the call returns, compared with before.
What do you think happens?
After vector_init(v, s) returns, what is the state of the caller's Vector v compared with before the call?
Reveal answer
elem points to a new array of s doubles and sz holds s
The function takes the Vector by nonconst reference, so it works on the caller's own object. It allocates an array with new double[s], stores the returned pointer in v.elem, and sets v.sz to s. The array lives on the free store and remains available after the function returns.
What a Vector Holds Inside Itself
A Vector object holds two members that describe its elements. The elem member is a pointer that says where the elements are. The sz member is a count that says how many elements there are. Neither member is complete without the other: the pointer alone does not say how many items to expect, and the count alone does not say where they live.
Free store: an area of memory, also known as dynamic memory or the heap, from which the new operator allocates. Arrays created with new live there, not inside the object that points to them.
The Vector handle and its elements are therefore separate things. The Vector is a small object that holds the pointer and the count. The elements are a separate array on the free store, and the Vector only knows where that array begins and how long it is.
Tracing vector_init Step by Step
The function signature is void vector_init(Vector& v, int s). The body does two jobs, and each one fills a different member. The first job is allocation. The expression new double[s] asks for an array of s doubles, and new returns a pointer to that array. The second job is assignment: that pointer is stored in v.elem, which previously pointed at nothing. Then v.sz is set to s, recording how many elements the array holds.
- The ampersand makes v a nonconst reference to the caller's Vector
- new double[s] allocates the array and returns a pointer to its first element
- v.elem receives that pointer, replacing the earlier value that pointed to nothing
- v.sz receives the count s, so the two members describe the same array
Initializing a Vector for four doubles
A caller declares a Vector v that has no storage yet, then calls vector_init(v, 4). What is the state of v afterward?
- 1Before the call
v.elem does not point to real storage, so v has no elements to work with.
- 2Allocation
new double[4] creates an array of four doubles on the free store and returns a pointer to its first element.
- 3Pointer assignment
The pointer is assigned to v.elem. The Vector now points to real storage.
- 4Count assignment
v.sz = 4 records that the array holds four elements, so elem and sz now agree.
v.elem points to a free-store array of four doubles and v.sz is 4. The Vector is now usable.
Why the Ampersand Changes Everything
The ampersand in Vector& declares that v is passed by nonconst reference. The function then operates on the caller's own Vector rather than on a separate copy. This is why vector_init can modify the vector passed to it. A nonconst reference permits writes through the reference, so the assignments to elem and sz are allowed.
Without the ampersand, the function would receive a copy. Its assignments would update that copy, and the changes would disappear when the function returns. The caller's Vector would still have an elem that points to nothing. The reference is what carries the initialization back to the caller.
How Long Free-Store Objects Last
The other important property is lifetime. An object allocated on the free store is independent of the scope in which it was created. It does not disappear when the function that allocated it returns. It lives until it is destroyed using the delete operator. That is why the array allocated inside vector_init is still available to the caller after the function ends.
The lifecycle of such an array has three stages. First, new allocates it and returns a pointer. Second, the array remains valid while the pointer is stored somewhere, such as in elem, and the program is still running. Third, delete destroys it. Between the second and third stages, the array can be used through its pointer from any scope that still holds that pointer.
Mistakes Beginners Make with Initialization
Common mistake Creating a Vector and assuming it can hold elements
Why it failsDeclaring the struct does not make elem point to storage. Until initialization assigns a pointer, the Vector has no elements.
Do this insteadCall vector_init, or perform the equivalent allocation and assignments, before using the Vector.
Common mistake Setting elem without setting sz, or the reverse
Why it failsThe pointer says where the elements are and the count says how many there are. A correct initialization sets both.
Do this insteadAssign both v.elem and v.sz so they describe the same array.
Common mistake Taking the Vector by value and expecting the caller's object to change
Why it failsWithout the ampersand the function works on a copy, and its assignments vanish when it returns.
Do this insteadDeclare the parameter as Vector& so the function receives a nonconst reference to the caller's object.
Common mistake Assuming the array is freed when the function that created it returns
Why it failsFree-store objects live until they are destroyed with delete, not until the creating function returns.
Do this insteadKeep the pointer available and destroy the array with delete when the program no longer needs it.
Trace the State Yourself
A caller declares Vector v, then calls vector_init(v, 3). Without looking back, describe the value of v.elem and v.sz after the call, and say where the three doubles live. Then explain what would change if the parameter were written as Vector without the ampersand.
Hints
- Ask first what new double[s] returns, then where v.elem gets that value.
- Remember that the array lives on the free store, not inside v.
- Without the ampersand, the function assigns to a copy. Ask what the caller's v looks like when the copy disappears.
Summary of the Initialization Mechanism
- 1A Vector is not useful until initialization gives elem a pointer to real storage and sets sz to the element count.
- 2
vector_initallocates an array with new double[s], assigns the returned pointer to v.elem, and assigns s to v.sz. - 3Passing Vector& by nonconst reference lets
vector_initmodify the caller's Vector instead of a copy. - 4Free-store arrays live until they are destroyed with delete, so they survive the return of the function that created them.
At a glance
- A Vector is not useful until initialization gives elem a pointer to real storage and sets sz to the element count.
vector_initallocates an array with new double[s], assigns the returned pointer to v.elem, and assigns s to v.sz.- Passing Vector& by nonconst reference lets
vector_initmodify the caller's Vector instead of a copy. - Free-store arrays live until they are destroyed with delete, so they survive the return of the function that created them.