13.5. Classes That Manage Dynamic Memory

Some classes need to allocate a varying amount of storage at run time. Such classes often can (and if they can, generally should) use a library container to hold their data. For example, our StrBlob class uses a vector to manage the underlying storage for its elements.

However, this strategy does not work for every class; some classes need to do their own allocation. Such classes generally must define their own copy-control members to manage the memory they allocate.

As an example, we’ll implement a simplification of the library vector class. Among the simplifications we’ll make is that our class will not be a template. Instead, our class will hold strings. Thus, we’ll call our class StrVec.

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.

StrVec Class Definition

The push_back function calls chk_n_alloc to ensure that there is room for an element. If necessary, chk_n_alloc will call reallocate. When chk_n_alloc returns, push_back knows that there is room for the new element. It asks its allocator member to construct a new last element:

When we use an allocator to allocate memory, we must remember that the memory is unconstructed (§ 12.2.2, p. 482). To use this raw memory we must call construct, which will construct an object in that memory. The first argument to construct must be a pointer to unconstructed space allocated by a call to allocate. The remaining arguments determine which constructor to use to construct the object that will go in that space. In this case, there is only one additional argument. That argument has type string, so this call uses the string copy constructor.

It is worth noting that the call to construct also increments first_free to indicate that a new element has been constructed. It uses the postfix increment (§ 4.5, p. 147), so this call constructs an object in the current value of first_free and increments first_free to point to the next, unconstructed element.

The alloc_n_copy Member

The alloc_n_copy member is called when we copy or assign a StrVec. Our StrVec class, like vector, will have valuelike behavior (§ 13.2.1, p. 511); when we copy or assign a StrVec, we have to allocate independent memory and copy the elements from the original to the new StrVec.

The alloc_n_copy member will allocate enough storage to hold its given range of elements, and will copy those elements into the newly allocated space. This function returns a pair (§ 11.2.3, p. 426) of pointers, pointing to the beginning of the new space and just past the last element it copied:

pair<string*, string*>
StrVec::alloc_n_copy(const string *b, const string *e)
{
    // allocate space to hold as many elements as are in the range
    auto data = alloc.allocate(e - b);
    // initialize and return a pair constructed from data and
    // the value returned by uninitialized_copy
    return {data, uninitialized_copy(b, e, data)};
}

alloc_n_copy calculates how much space to allocate by subtracting the pointer to the first element from the pointer one past the last. Having allocated memory, the function next has to construct copies of the given elements in that space.

It does the copy in the return statement, which list initializes the return value (§ 6.3.2, p. 226). The first member of the returned pair points to the start of the allocated memory; the second is the value returned from uninitialized_copy (§ 12.2.2, p. 483). That value will be pointer positioned one element past the last constructed element.

The free Member

The free member has two responsibilities: It must destroy the elements and then deallocate the space that this StrVec itself allocated. The for loop calls the allocator member destroy in reverse order, starting with the last constructed element and finishing with the first:

void StrVec::free()
{
    // may not pass deallocate a 0 pointer; if elements is 0, there's no work to do
    if (elements) {
        // destroy the old elements in reverse order
        for (auto p = first_free; p != elements; /* empty */)
            alloc.destroy(--p);
        alloc.deallocate(elements, cap - elements);
    }
}

The destroy function runs the string destructor. The string destructor frees whatever storage was allocated by the strings themselves.

Once the elements have been destroyed, we free the space that this StrVec allocated by calling deallocate. The pointer we pass to deallocate must be one that was previously generated by a call to allocate. Therefore, we first check that elements is not null before calling deallocate.

Copy-Control Members

Given our alloc_n_copy and free members, the copy-control members of our class are straightforward. The copy constructor calls alloc_n_copy:

StrVec::StrVec(const StrVec &s)
{
    // call alloc_n_copy to allocate exactly as many elements as in s
    auto newdata = alloc_n_copy(s.begin(), s.end());
    elements = newdata.first;
    first_free = cap = newdata.second;
}

and assigns the results from that call to the data members. The return value from alloc_n_copy is a pair of pointers. The first pointer points to the first constructed element and the second points just past the last constructed element. Because alloc_n_copy allocates space for exactly as many elements as it is given, cap also points just past the last constructed element.

The destructor calls free:

StrVec::~StrVec() { free(); }

The copy-assignment operator calls alloc_n_copy before freeing its existing elements. By doing so it protects against self-assignment:

StrVec &StrVec::operator=(const StrVec &rhs)
{
    // call alloc_n_copy to allocate exactly as many elements as in rhs
    auto data = alloc_n_copy(rhs.begin(), rhs.end());
    free();
    elements = data.first;
    first_free = cap = data.second;
    return *this;
}

 

Like the copy constructor, the copy-assignment operator uses the values returned from alloc_n_copy to initialize its pointers.

 

Moving, Not Copying, Elements during Reallocation

 

Before we write the reallocate member, we should think a bit about what it must do. This function will

 

• Allocate memory for a new, larger array of strings

 

• Construct the first part of that space to hold the existing elements

 

• Destroy the elements in the existing memory and deallocate that memory

 

Looking at this list of steps, we can see that reallocating a StrVec entails copying each string from the old StrVec memory to the new. Although we don’t know the details of how string is implemented, we do know that strings have valuelike behavior. When we copy a string, the new string and the original string are independent from each other. Changes made to the original don’t affect the copy, and vice versa.

 

Because strings act like values, we can conclude that each string must have its own copy of the characters that make up that string. Copying a string must allocate memory for those characters, and destroying a string must free the memory used by that string.

 

Copying a string copies the data because ordinarily after we copy a string, there are two users of that string. However, when reallocate copies the strings in a StrVec, there will be only one user of these strings after the copy. As soon as we copy the elements from the old space to the new, we will immediately destroy the original strings.

 

Copying the data in these strings is unnecessary. Our StrVec’s performance will be much better if we can avoid the overhead of allocating and deallocating the strings themselves each time we reallocate.

 

Move Constructors and std::move

 

We can avoid copying the strings by using two facilities introduced by the new library. First, several of the library classes, including string, define so-called “move constructors.” The details of how the string move constructor works—like any other detail about the implementation—are not disclosed. However, we do know that move constructors typically operate by “moving” resources from the given object to the object being constructed. We also know that the library guarantees that the “moved-from” string remains in a valid, destructible state. For string, we can imagine that each string has a pointer to an array of char. Presumably the string move constructor copies the pointer rather than allocating space for and copying the characters themselves.

The second facility we’ll use is a library function named move, which is defined in the utility header. For now, there are two important points to know about move. First, for reasons we’ll explain in § 13.6.1 (p. 532), when reallocate constructs the strings in the new memory it must call move to signal that it wants to use the string move constructor. If it omits the call to move the string the copy constructor will be used. Second, for reasons we’ll cover in § 18.2.3 (p. 798), we usually do not provide a using declaration (§ 3.1, p. 82) for move. When we use move, we call std::move, not move.

The reallocate Member

Using this information, we can now write our reallocate member. We’ll start by calling allocate to allocate new space. We’ll double the capacity of the StrVec each time we reallocate. If the StrVec is empty, we allocate room for one element:

void StrVec::reallocate()
{
     // we'll allocate space for twice as many elements as the current size
     auto newcapacity = size() ? 2 * size() : 1;
     // allocate new memory
     auto newdata = alloc.allocate(newcapacity);
     // move the data from the old memory to the new
     auto dest = newdata;  // points to the next free position in the new array
     auto elem = elements; // points to the next element in the old array
     for (size_t i = 0; i != size(); ++i)
         alloc.construct(dest++, std::move(*elem++));
     free();  // free the old space once we've moved the elements
     // update our data structure to point to the new elements
     elements = newdata;
     first_free = dest;
     cap = elements + newcapacity;
}

The for loop iterates through the existing elements and constructs a corresponding element in the new space. We use dest to point to the memory in which to construct the new string, and use elem to point to an element in the original array. We use postfix increment to move the dest (and elem) pointers one element at a time through these two arrays.

The second argument in the call to construct (i.e., the one that determines which constructor to use (§ 12.2.2, p. 482)) is the value returned by move. Calling move returns a result that causes construct to use the string move constructor. Because we’re using the move constructor, the memory managed by those strings will not be copied. Instead, each string we construct will take over ownership of the memory from the string to which elem points.

After moving the elements, we call free to destroy the old elements and free the memory that this StrVec was using before the call to reallocate. The strings themselves no longer manage the memory to which they had pointed; responsibility for their data has been moved to the elements in the new StrVec memory. We don’t know what value the strings in the old StrVec memory have, but we are guaranteed that it is safe to run the string destructor on these objects.