13.5. Classes That Manage Dynamic Memory
AdvancedSome 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.
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 memoryfirst_free, which points just after the last actual elementcap, 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 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_copywill allocate space and copy a given range of elements.freewill destroy the constructed elements and deallocate the space.chk_n_allocwill ensure that there is room to add at least one more element to theStrVec. If there isn’t room for another element,chk_n_allocwill callreallocateto get more space.reallocatewill reallocate theStrVecwhen it runs out of space.
Although our focus is on the implementation, we’ll also define a few members from vector’s interface.
StrVec Class Definition
Having sketched the implementation, we can now define our StrVec class:
// simplified implementation of the memory allocation strategy for a vector-like class
class StrVec {
public:
StrVec(): // the allocator member is default initialized
elements(nullptr), first_free(nullptr), cap(nullptr) { }
StrVec(const StrVec&); // copy constructor
StrVec &operator=(const StrVec&); // copy assignment
~StrVec(); // destructor
void push_back(const std::string&); // copy the element
size_t size() const { return first_free - elements; }
size_t capacity() const { return cap - elements; }
std::string *begin() const { return elements; }
std::string *end() const { return first_free; }
// ...
private:
std::allocator<std::string> alloc; // allocates the elements
// used by the functions that add elements to the StrVec
void chk_n_alloc()
{ if (size() == capacity()) reallocate(); }
// utilities used by the copy constructor, assignment operator, and destructor
std::pair<std::string*, std::string*> alloc_n_copy
(const std::string*, const std::string*);
void free(); // destroy the elements and free the space
void reallocate(); // get more space and copy the existing elements
std::string *elements; // pointer to the first element in the array
std::string *first_free; // pointer to the first free element in the array
std::string *cap; // pointer to one past the end of the array
};The class body defines several of its members:
- The default constructor (implicitly) default initializes
allocand (explicitly) initializes the pointers tonullptr, indicating that there are no elements. - The
sizemember returns the number of elements actually in use, which is equal tofirst_free - elements. - The
capacitymember returns the number of elements that theStrVeccan hold, which is equal tocap - elements. - The
chk_n_alloccauses theStrVecto be reallocated when there is no room to add another element, which happens whencap == first_free. - The
beginandendmembers return pointers to the first (i.e.,elements) and one past the last constructed element (i.e.,first_free), respectively.
Using construct
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_allocreturns, push_back knows that there is room for the new element. It asks its allocator member to construct a new last element:
void StrVec::push_back(const string& s)
{
chk_n_alloc(); // ensure that there is room for another element
// construct a copy of s in the element to which first_free points
alloc.construct(first_free++, s);
}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
TrickyBefore 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
C++11We 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.
What remains is to update the pointers to address the newly allocated and initialized array. The first_free and cap pointers are set to denote one past the last constructed element and one past the end of the allocated space, respectively.
INFO
Exercises Section 13.5
Exercise 13.39: Write your own version of StrVec, including versions of reserve, capacity (§ 9.4, p. 356), and resize (§ 9.3.5, p. 352).
Exercise 13.40: Add a constructor that takes an initializer_list<string> to your StrVec class.
Exercise 13.41: Why did we use postfix increment in the call to construct inside push_back? What would happen if it used the prefix increment?
Exercise 13.42: Test your StrVec class by using it in place of the vector<string> in your TextQuery and QueryResult classes (§ 12.3, p. 484).
Exercise 13.43: Rewrite the free member to use for_each and a lambda (§ 10.3.2, p. 388) in place of the for loop to destroy the elements. Which implementation do you prefer, and why?
Exercise 13.44: Write a class named String that is a simplified version of the library string class. Your class should have at least a default constructor and a constructor that takes a pointer to a C-style string. Use an allocator to allocate memory that your String class uses.