StrVec
Class DesignRecall 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.
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.