StrVec Class Design

Recall that the vector class stores its elements in contiguous storage. To obtain acceptable performance, vector preallocates enough storage to hold more elements than are needed (§ 9.4, p. 355). Each vector member that adds elements checks whether there is space available for another element. If so, the member constructs an object in the next available spot. If there isn’t space left, then the vector is reallocated: The vector obtains new space, moves the existing elements into that space, frees the old space, and adds the new element.

We’ll use a similar strategy in our StrVec class. We’ll use an allocator to obtain raw memory (§ 12.2.2, p. 481). Because the memory an allocator allocates is unconstructed, we’ll use the allocator’s construct member to create objects in that space when we need to add an element. Similarly, when we remove an element, we’ll use the destroy member to destroy the element.

Each StrVec will have three pointers into the space it uses for its elements:

• elements, which points to the first element in the allocated memory

• first_free, which points just after the last actual element

• cap, which points just past the end of the allocated memory

Figure 13.2 illustrates the meaning of these pointers.

Figure 13.2. StrVec Memory Allocation Strategy

In addition to these pointers, StrVec will have a static data member named alloc that is an allocator<string>. The alloc member will allocate the memory used by a StrVec. Our class will also have four utility functions:

• alloc_n_copy will allocate space and copy a given range of elements.

• free will destroy the constructed elements and deallocate the space.

• chk_n_alloc will ensure that there is room to add at least one more element to the StrVec. If there isn’t room for another element, chk_n_alloc will call reallocate to get more space.

• reallocate will reallocate the StrVec when it runs out of space.

Although our focus is on the implementation, we’ll also define a few members from vector’s interface.