Dynamic Memory

The programs we’ve written so far have used objects that have well-defined lifetimes. Global objects are allocated at program start-up and destroyed when the program ends. Local, automatic objects are created and destroyed when the block in which they are defined is entered and exited. Local static objects are allocated before their first use and are destroyed when the program ends.

In addition to supporting automatic and static objects, C++ lets us allocate objects dynamically. Dynamically allocated objects have a lifetime that is independent of where they are created; they exist until they are explicitly freed.

Our programs have used only static or stack memory. Static memory is used for local static objects, for class static data members, and for variables defined outside any function. Stack memory is used for no-static objects defined inside functions. Objects allocated in static or stack memory are automatically created and destroyed by the compiler. Stack objects exist only while the block in which they are defined is executing; static objects are allocated before they are used, and they are destroyed when the program ends.

In addition to static or stack memory, every program also has a pool of memory that it can use. This memory is referred to as the free store or heap. Programs use the heap for objects that they dynamically allocate—that is, for objects that the program allocates at run time. The program controls the lifetime of dynamic objects; our code must explicitly destroy such objects when they are no longer needed.

Dynamic Memory and Smart Pointers

In C++, dynamic memory is managed through a pair of operators: new, which allocates, and optionally initializes, an object in dynamic memory and returns a pointer to that object; and delete, which takes a pointer to a dynamic object, destroys that object, and frees the associated memory.

Dynamic memory is problematic because it is surprisingly hard to ensure that we free memory at the right time. Either we forget to free the memory—in which case we have a memory leak—or we free the memory when there are still pointers referring to that memory—in which case we have a pointer that refers to memory that is no longer valid.

To make using dynamic memory easier (and safer), the new library provides two smart pointer types that manage dynamic objects. A smart pointer acts like a regular pointer with the important exception that it automatically deletes the object to which it points. The new library defines two kinds of smart pointers that differ in how they manage their underlying pointers: shared_ptr, which allows multiple pointers to refer to the same object, and unique_ptr, which “owns” the object to which it points. The library also defines a companion class named weak_ptr that is a weak reference to an object managed by a shared_ptr. All three are defined in the memory header.

The shared_ptr Class

Like vectors, smart pointers are templates. Therefore, when we create a smart pointer, we must supply additional information—in this case, the type to which the pointer can point. As with vector, we supply that type inside angle brackets that follow the name of the kind of smart pointer we are defining:

// shared_ptr that can point at a string
shared_ptr<string> s_ptr1;
// shared_ptr that can point at a vector of int
shared_ptr<vector<int>> s_ptr2;

A default initialized smart pointer holds a null pointer.

We use a smart pointer in ways that are similar to using a pointer. Dereferencing a smart pointer returns the object to which the pointer points. When we use a smart pointer in a condition, the effect is to test whether the pointer is null:

// if p1 is not null, check whether it's the empty string
if (s_ptr1 && s_ptr1->empty()) {
    // if so, dereference p1 to assign a new value to that string
    *s_ptr1 = "hello";
}

Next table lists operations common to shared_ptr and unique_ptr.

member	definition
shared_ptr ptr	Null smart pointer
unique_ptr ptr	Null smart pointer
ptr	as a condition check if ptr point to an object
*ptr	dereference ptr get object
ptr->member	equal to (*ptr).member
ptr.get()	Returns the stored pointer.
swap(ptr1,ptr2)	swap pointer ptr1 and ptr2
ptr1.swap(ptr2)	swap pointer ptr1 and ptr2

This table show the particular operation for shared_ptr:

member	definition
make_shared(args)	Allocates and constructs an object of type T passing args to its constructor.
shared_ptr ptr(q)	p is a copy of shared_ptr q
p=q	assign to p
p.unique()	Check if unique
p.use_count()	Returns the number of shared_ptr objects that share

The safest way to allocate and use dynamic memory is to call a library function named make_shared. This function allocates and initializes an object in dynamic memory and returns a shared_ptr that points to that object. Like the smart pointers, make_shared is defined in the memory header. When we call make_shared, we must specify the type of object we want to create. We do so in the same way as we use a template class, by following the function name with a type enclosed in angle brackets:

// shared_ptr that points to an int with value 42
auto ptr1 = make_shared<int>(10);
// shared_ptr that points to a string with value HHHHH
auto ptr2 = make_shared<string>(5, 'H');
// shared_ptr that points to a string with value HELLO
shared_ptr<string> ptr3 = make_shared<string>("HELLO");
// output: 10 HHHHH HELLO
cout << *ptr1 << " " << *ptr2 << " " << *ptr3 << endl;

Like the sequential-container emplace members, make_shared uses its arguments to construct an object of the given type. Of course, ordinarily we use auto to make it easier to define an object to hold the result of make_shared:

When we copy or assign a shared_ptr, each shared_ptr keeps track of how many other shared_ptrs point to the same object:

// copy shared_ptr
// ptr3 and ptr4 point to the same object
// object to which ptr3 and ptr4 point has two users
auto ptr4 = ptr3;

We can think of a shared_ptr as if it has an associated counter, usually referred to as a reference count. Whenever we copy a shared_ptr, the count is incremented. The counter is decremented when we assign a new value to the shared_ptr and when the shared_ptr itself is destroyed, such as when a local shared_ptr goes out of scope. Once a shared_ptr’s counter goes to zero, the shared_ptr automatically frees the object that it manages:

auto r = make_shared<int>(42); // int to which r points has one user
r = q; 
// assign to r, making it point to a different address
// increase the use count for the object to which q points
// reduce the use count of the object to which r had pointed
// the object r had pointed to has no users; that object is automatically freed

When the last shared_ptr pointing to an object is destroyed, the shared_ptr class automatically destroys the object to which that shared_ptr points. It does so through another special member function known as a destructor. Analogous to its constructors, each class has a destructor. Just as a constructor controls initialization, the destructor controls what happens when objects of that class type are destroyed.

The destructor for shared_ptr decrements the reference count of the object to which that shared_ptr points. If the count goes to zero, the shared_ptr destructor destroys the object to which the shared_ptr points and frees the memory used by that object.

The fact that the shared_ptr class automatically frees dynamic objects when they are no longer needed makes it fairly easy to use dynamic memory. For example, we might have a function that returns a shared_ptr to a dynamically allocated object of a type named Foo that can be initialized by an argument of type T:(note this is just a abstract example, this code can not run in computer now)

// factory returns a shared_ptr pointing to a dynamically allocated object
shared_ptr<Foo> factory(T arg){
    // process arg as appropriate
    // shared_ptr will take care of deleting this memory
    return make_shared<Foo>(arg);
}

Because factory returns a shared_ptr, we can be sure that the object allocated by factory will be freed when appropriate. For example, the following function stores the shared_ptr returned by factory in a local variable:

void use_factory(T arg){
    shared_ptr<Foo> p = factory(arg);
    // use p
} // p goes out of scope; the memory to which p points is automatically freed

This is simple case that show the shared_ptr and a refeence:

shared_ptr<string> getS() {
    auto s = make_shared<string>("hello");
    return s;
}

string& getS(char a) {
    string s(10, a);
    return s;
}

int main(){
    // ok output hello
    auto s1 = getS();
    cout << *s1 << endl;
    // Segmentation fault
    auto s2 = getS('A');
    return 0;
}

Programs tend to use dynamic memory for one of three purposes:

1. They don’t know how many objects they’ll need
2. They don’t know the precise type of the objects they need
3. They want to share data between several objects

The container classes are an example of classes that use dynamic memory for the first purpose. In this section, we’ll define a class that uses dynamic memory in order to let several objects share the same underlying data.

So far, the classes we’ve used allocate resources that exist only as long as the corresponding objects. For example, each vector “owns” its own elements. When we copy a vector, the elements in the original vector and in the copy are separate from one another:

vector<string> v1; // empty vector
{     // new scope
     vector<string> v2 = {"a", "an", "the"};
    v1 = v2; // copies the elements from v2 into v1
}     // v2 is destroyed, which destroys the elements in v2
    // v1 has three elements, which are copies of the ones originally in v2

Some classes allocate resources with a lifetime that is independent of the original object. As an example, assume we want to define a class named Blob that will hold a collection of elements. Unlike the containers, we want Blob objects that are copies of one another to share the same elements. That is, when we copy a Blob, the original and the copy should refer to the same underlying elements. like this:

Blob<string> b1; // empty Blob
{     // new scope
    Blob<string> b2 = {"a", "an", "the"};
    b1 = b2; // b1 and b2 share the same elements
}     // b2 is destroyed, but the elements in b2 must not be destroyed
    // b1 points to the elements originally created in b2

Ultimately, we’ll implement our Blob class as a template, but we won’t learn how to do. For now, we’ll define a version of our class that can manage strings. As a result, we’ll name this version of our class StrBlob.

The easiest way to implement a new collection type is to use one of the library containers to manage the elements. That way, we can let the library type manage the storage for the elements themselves. In this case, we’ll use a vector to hold our elements.

To implement the sharing we want, we’ll give each StrBlob a shared_ptr to a dynamically allocated vector. That shared_ptr member will keep track of how many StrBlobs share the same vector and will delete the vector when the last StrBlob using that vector is destroyed.

We still need to decide what operations our class will provide. For now, we’ll implement a small subset of the vector operations. We’ll also change the operations that access elements (e.g., front and back): In our class, these operations will throw an exception if a user attempts to access an element that doesn’t exist.

Our class will have a default constructor and a constructor that has a parameter of type initializer_list<string>. This constructor will take a braced list of initializers. This is StrBlob class:

#ifndef StrBlob1
#define StrBlob1
#include<memory>
#include<vector>
#include<string>
#include<initializer_list>
#include<stdexcept>

class StrBlob {
public:
    typedef std::vector<std::string>::size_type size_type;

    StrBlob() : data(std::make_shared<std::vector<std::string>>()) {
    };
    StrBlob(std::initializer_list<std::string> il)
        : data(std::make_shared<std::vector<std::string>>(il)) {
    };

    size_type size() const { return data->size(); }
    bool empty() const { return data->empty(); }
    // add and remove elements
    void push_back(const std::string& t) {
        data->push_back(t);
    }
    void pop_back();
    // element access
    std::string& front();
    std::string& back();

private:
    // a shared_ptr ponint to string of vector 
    std::shared_ptr<std::vector<std::string>> data;
    void check(size_type i, const std::string& msg) const;
};

void StrBlob::pop_back() {
    data->pop_back();
}

std::string& StrBlob::front() {
    // TODO: insert return statement here
    return data->front();
}

std::string& StrBlob::back() {
    // TODO: insert return statement here
    return data->back();
}

void StrBlob::check(size_type i, const std::string& msg) const {
    if (i > data->size()) {
        throw std::out_of_range(msg);
    }
}

#endif // !StrBlob

This is test code:

StrBlob b1;
{
    StrBlob b2 = { "a", "an", "the" };
    b1 = b2;
    b2.push_back("about");
}
cout << b1.back() << endl; // output about

Managing Memory Directly

The language itself defines two operators that allocate and free dynamic memory. The new operator allocates memory, and delete frees memory allocated by new.

Objects allocated on the free store are unnamed, so new offers no way to name the objects that it allocates. Instead, new returns a pointer to the object it allocates:

int *pi = new int; 
// pi points to a dynamically allocated,
// unnamed, uninitialized int

This new expression constructs an object of type int on the free store and returns a pointer to that object. By default, dynamically allocated objects are default initialized, which means that objects of built-in or compound type have undefined value; objects of class type are initialized by their default constructor:

string *ps = new string; // initialized to empty string
int *pi = new int; // pi points to an uninitialized int

We can initialize a dynamically allocated object using direct initialization. We can use traditional construction (using parentheses), and under the new standard, we can also use list initialization (with curly braces):

int *pi = new int(1024); // object to which pi points has value 1024
string *ps = new string(10, '9'); // *ps is "9999999999"
// vector with ten elements with values from 0 to 9
vector<int> *pv = new vector<int>{0,1,2,3,4,5,6,7,8,9};

When we provide an initializer inside parentheses, we can use auto to deduce the type of the object we want to allocate from that initializer. However, because the compiler uses the initializer’s type to deduce the type to allocate, we can use auto only with a single initializer inside parentheses:

auto p1 = new auto(obj); // p points to an object of the type of obj
// that object is initialized from obj
auto p2 = new auto{a,b,c}; // error: must use parentheses for the initializer

The type of p1 is a pointer to the auto-deduced type of obj. If obj is an int, then p1 is int*; if obj is a string, then p1 is a string*; and so on. The newly allocated object is initialized from the value of obj.

Although modern machines tend to have huge memory capacity, it is always possible that the free store will be exhausted. Once a program has used all of its available memory, new expressions will fail. By default, if new is unable to allocate the requested storage, it throws an exception of type bad_alloc. We can prevent new from throwing an exception by using a different form of new:

// if allocation fails, new returns a null pointer
int *p1 = new int; // if allocation fails, new throws std::bad_alloc
int *p2 = new (nothrow) int; // if allocation fails, new returns a null pointer

In order to prevent memory exhaustion, we must return dynamically allocated memory to the system once we are finished using it. We return memory through a delete expression. A delete expression takes a pointer to the object we want to free:

delete p1;

We need notice the pointer we pass to delete must either point to dynamically allocated memory or be a null pointer. Deleting a pointer to memory that was not allocated by new, or deleting the same pointer value more than once, is undefined:

auto* p1 = new int(1);
int num = 10;
int* p2 = #
delete p1; //ok
delete p2; //error

When we delete a pointer, that pointer becomes invalid. Although the pointer is invalid, on many machines the pointer continues to hold the address of the (freed) dynamic memory. After the delete, the pointer becomes what is referred to as a dangling pointer. A dangling pointer is one that refers to memory that once held an object but no longer does so. Dangling pointers have all the problems of uninitialized pointers. We can avoid the problems with dangling pointers by deleting the memory associated with a pointer just before the pointer itself goes out of scope. That way there is no chance to use the pointer after the memory associated with the pointer is freed. If we need to keep the pointer around, we can assign nullptr to the pointer after we use delete. Doing so makes it clear that the pointer points to no object.

Using shared_ptrs with new

As we’ve seen, if we do not initialize a smart pointer, it is initialized as a null pointer. As described in next table, we can also initialize a smart pointer from a pointer returned by new:

member	means
shared_ptr p(q)	p manages the object to which the built-in pointer q points; q must point to memory allocated by new and must be convertible to T*.
shared_ptr p(u)	p assumes ownership from the unique_ptr u; makes u null.
shared_ptr p(q, d)	p assumes ownership for the object to which the built-in pointer q points. q must be convertible to T*. p will use the callable object d in place of delete to free q.
shared_ptr p(p2, d)	p is a copy of the shared_ptr p2 as described in previous Table , except that p uses the callable object d in place of delete.
p.reset()	If p is the only shared_ptr pointing at its object, reset frees p’s existing object.
p.reset(q)	If the optional built-in pointer q is passed makes p point to q, otherwise makes p null.
p.reset(q, d)	If d is supplied, will call d to free q otherwise uses delete to free q.

shared_ptr<double> p1; // shared_ptr that can point at a double
shared_ptr<int> p2(new int(42)); // p2 points to an int with value 42

The smart pointer constructors that take pointers are explicit. Hence, we cannot implicitly convert a built-in pointer to a smart pointer; we must use the direct form of initialization to initialize a smart pointer:

shared_ptr<int> p1 = new int(1024); // error: must use direct initialization
shared_ptr<int> p2(new int(1024)); // ok: uses direct initialization

By default, a pointer used to initialize a smart pointer must point to dynamic memory because, by default, smart pointers use delete to free the associated object. We can bind smart pointers to pointers to other kinds of resources. However, to do so, we must supply our own operation to use in place of delete.

A shared_ptr can coordinate destruction only with other shared_ptrs that are copies of itself. Indeed, this fact is one of the reasons we recommend using make_shared rather than new. That way, we bind a shared_ptr to the object at the same time that we allocate it. There is no way to inadvertently bind the same memory to more than one independently created shared_ptr.

Consider the following function that operates on a shared_ptr:

// ptr is created and initialized when process is called
void process(shared_ptr<int> ptr)
{
    // use ptr
}    // ptr goes out of scope and is destroyed

The parameter to process is passed by value, so the argument to process is copied into ptr. Copying a shared_ptr increments its reference count. Thus, inside process the count is at least 2. When process completes, the reference count of ptr is decremented but cannot go to zero. Therefore, when the local variable ptr is destroyed, the memory to which ptr points will not be deleted.

The smart pointer types define a function named get that returns a built-in pointer to the object that the smart pointer is managing. This function is intended for cases when we need to pass a built-in pointer to code that can’t use a smart pointer. The code that uses the return from get must not delete that pointer.

shared_ptr<int> p2(new int(10));
auto* p3 = p2.get();
{
    // undefined: two independent shared_ptrs point to the same memory
    shared_ptr<int> p4(p3);
}    // block ends, p4 is destroyed, and the memory to which q points is freed
cout << *p2 << endl;    // undefined; the memory to which p2 points was freed

In this case, both p2 and p4 point to the same memory. Because they were created independently from each other, each has a reference count of 1. When the block in which q was defined ends, q is destroyed. Destroying q frees the memory to which q points. That makes p into a dangling pointer, meaning that what happens when we attempt to use p is undefined. Moreover, when p is destroyed, the pointer to that memory will be deleted a second time.

The shared_ptr class gives us a few other operations, which are listed in previous table. We can use reset to assign a new pointer to a shared_ptr:

p = new int(1024); // error: cannot assign a pointer to a shared_ptr
p.reset(new int(1024)); // ok: p points to a new object

Like assignment, reset updates the reference counts and, if appropriate, deletes the object to which p points. The reset member is often used together with unique to control changes to the object shared among several shared_ptrs. Before changing the underlying object, we check whether we’re the only user. If not, we make a new copy before making the change:

if (!p.unique())
    p.reset(new string(*p)); // we aren't alone; allocate a new copy
*p += newVal; // now that we know we're the only pointer, okay to change this object

Smart Pointers and Exceptions

In previous chapter we noted that programs that use exception handling to continue processing after an exception occurs need to ensure that resources are properly freed if an exception occurs. One easy way to make sure resources are freed is to use smart pointers. When we use a smart pointer, the smart pointer class ensures that memory is freed when it is no longer needed even if the block is exited prematurely:

void f(){
    shared_ptr<int> sp(new int(42)); // allocate a new object
    // code that throws an exception that is not caught inside f
}    // shared_ptr freed automatically when the function ends

When a function is exited, whether through normal processing or due to an exception, all the local objects are destroyed. In this case, sp is a shared_ptr, so destroying sp checks its reference count. Here, sp is the only pointer to the memory it manages; that memory will be freed as part of destroying sp.

In contrast, memory that we manage directly is not automatically freed when an exception occurs. If we use built-in pointers to manage memory and an exception occurs after a new but before the corresponding delete, then that memory won’t be freed:

Many C++ classes, including all the library classes, define destructors that take care of cleaning up the resources used by that object. However, not all classes are so well behaved. In particular, classes that are designed to be used by both C and C++ generally require the user to specifically free any resources that are used.

unique_ptr

A unique_ptr “owns” the object to which it points. Unlike shared_ptr, only one unique_ptr at a time can point to a given object. The object to which a unique_ptr points is destroyed when the unique_ptr is destroyed. Next table lists the operations specific to unique_ptrs.

unique_ptr u1	Null unique_ptrs that can point to objects of type T.
unique_ptr<T, D> u2	u1 will use delete to free its pointer; u2 will use a callable object of type D to free its pointer.
unique_ptr<T, D> u(d)	Null unique_ptr that point to objects of type T that uses d, which must be an object of type D in place of delete.
u=nullptr	Deletes the object to which u points; makes u null.
u.release()	Relinquishes control of the pointer u had held, returns the pointer u had held and makes u null.
u.reset()	Deletes the object to which u points
u.reset(p)	If the built-in pointer q is supplied,makes u point to that object.
u.reset(nullptr)	Otherwise makes u null.

Unlike shared_ptr, there is no library function comparable to make_shared that returns a unique_ptr. Instead, when we define a unique_ptr, we bind it to a pointer returned by new. As with shared_ptrs, we must use the direct form of initialization:

unique_ptr<double> p1; // unique_ptr that can point at a double
unique_ptr<int> p2(new int(42)); // p2 points to int with value 42

Because a unique_ptr owns the object to which it points, unique_ptr does not support ordinary copy or assignment. Although we can’t copy or assign a unique_ptr, we can transfer ownership from one (nonconst) unique_ptr to another by calling release or reset:

// transfers ownership from p1 (which points to the string Stegosaurus) to p2
unique_ptr<string> p2(p1.release()); // release makes p1 null
unique_ptr<string> p3(new string("Trex"));
// transfers ownership from p3 to p2
p2.reset(p3.release()); // reset deletes the memory to which p2 had pointed

There is one exception to the rule that we cannot copy a unique_ptr: We can copy or assign a unique_ptr that is about to be destroyed. The most common example is when we return a unique_ptr from a function:

unique_ptr<int> clone(int p) {
    // ok: explicitly create a unique_ptr<int> from int*
    return unique_ptr<int>(new int(p));
}

weak_ptr

A weak_ptr is a smart pointer that does not control the lifetime of the object to which it points. Instead, a weak_ptr points to an object that is managed by a shared_ptr. Binding a weak_ptr to a shared_ptr does not change the reference count of that shared_ptr. Once the last shared_ptr pointing to the object goes away, the object itself will be deleted. That object will be deleted even if there are weak_ptrs pointing to it—hence the name weak_ptr, which captures the idea that a weak_ptr shares its object “weakly.”

Dynamic Arrays

The new and delete operators allocate objects one at a time. Some applications, need the ability to allocate storage for many objects at once. For example, vectors and strings store their elements in contiguous memory and must allocate several elements at once whenever the container has to be reallocated.

To support such usage, the language and library provide two ways to allocate an array of objects at once. The language defines a second kind of new expression that allocates and initializes an array of objects. The library includes a template class named allocator that lets us separate allocation from initialization. Using an allocator generally provides better performance and more flexible memory management.

new and Arrays

We ask new to allocate an array of objects by specifying the number of objects to allocate in a pair of square brackets after a type name. In this case, new allocates the requested number of objects and (assuming the allocation succeeds) returns a pointer to the first one:

// call get_size to determine how many ints to allocate
int *pia = new int[get_size()]; // pia points to the first of these ints

The size inside the brackets must have integral type but need not be a constant. We can also allocate an array by using a type alias to represent an array type. In this case, we omit the brackets:

using ten_arr = int[10];
int* p2 = new ten_arr;

Although it is common to refer to memory allocated by new ten_arr[] as a “dynamic array,” this usage is somewhat misleading. When we use new to allocate an array, we do not get an object with an array type. Instead, we get a pointer to the element type of the array. Even if we use a type alias to define an array type, new does not allocate an object of array type. Because the allocated memory does not have an array type, we cannot call begin or end on a dynamic array.

By default, objects allocated by new—whether allocated as a single object or in an array—are default initialized. We can value initialize the elements in an array by following the size with an empty pair of parentheses.

int* pia = new int[10]; // block of ten uninitialized ints
int* pia2 = new int[10](); // block of ten ints value initialized to 0
string* psa = new string[10]; // block of ten empty strings
string* psa2 = new string[10](); // block of ten empty strings

Under the new standard, we can also provide a braced list of element initializers:

int* pia = new int[10]{ 1,2,3,4,5,6,7,8,9,0 };
string* psa = new string[10]{ "nvifd",string(10,'A') };

To free a dynamic array, we use a special form of delete that includes an empty pair of square brackets:

delete p; // p must point to a dynamically allocated object or be null
delete [] pa; // pa must point to a dynamically allocated array or be null

The second statement destroys the elements in the array to which pa points and frees the corresponding memory. Elements in an array are destroyed in reverse order. That is, the last element is destroyed first, then the second to last, and so on.

The library provides a version of unique_ptr that can manage arrays allocated by new. To use a unique_ptr to manage a dynamic array, we must include a pair of empty brackets after the object type:

// up points to an array of ten uninitialized ints
unique_ptr<int[]> up(new int[10]);
up.release(); // automatically uses delete[] to destroy its pointer

unqiue_ptrs that point to arrays provide slightly different operations than those we used in previous, we can use the subscript operator to access the elements in the array:

for (size_t i = 0; i < 10; i++) {
    up[i] = i;
}

Unlike unique_ptr, shared_ptrs provide no direct support for managing a dynamic array. If we want to use a shared_ptr to manage a dynamic array, we must provide our own deleter:

// to use a shared_ptr we must supply a deleter
shared_ptr<int> sp(new int[10], [](int *p) { delete[] p; });
sp.reset(); // uses the lambda we supplied that uses delete[] to free the array

The fact that shared_ptr does not directly support managing arrays affects how we access the elements in the array:

for (size_t i = 0; i < 10; i++) {
    *(sp.get() + i) = i;
}

The allocator Class

An aspect of new that limits its flexibility is that new combines allocating memory with constructing object(s) in that memory. Similarly, delete combines destruction with deallocation. Combining initialization with allocation is usually what we want when we allocate a single object. In that case, we almost certainly know the value the object should have.

When we allocate a block of memory, we often plan to construct objects in that memory as needed. In this case, we’d like to decouple memory allocation from object construction. Decoupling construction from allocation means that we can allocate memory in large chunks and pay the overhead of constructing the objects only when we actually need to create them.

The library allocator class, which is defined in the memory header, lets us separate allocation from construction. It provides type-aware allocation of raw, unconstructed, memory. Next table outlines the operations that allocator supports. In this section, we’ll describe the allocator operations.

methods	means
allocator a	Defines an allocator object named a that can allocate memory for objects of type T.
a.allocate(n)	Allocates raw, unconstructed memory to hold n objects of type T.
a.deallocate(p, n)	Deallocates memory that held n objects of type T starting at the address in the T* pointer p.
a.construct(p, args)	which is used to construct an object in the memory pointed to by p
a.destory(p)	Runs the destructor on the object pointed to by the T*pointer p.

Like vector, allocator is a template. To define an allocator we must specify the type of objects that a particular allocator can allocate. When an allocator object allocates memory, it allocates memory that is appropriately sized and aligned to hold objects of the given type:

allocator<string> alloc; // object that can allocate strings
auto const p = alloc.allocate(n); // allocate n unconstructed strings

The memory an allocator allocates is unconstructed. We use this memory by constructing objects in that memory. In the new library the construct member takes a pointer and zero or more additional arguments:

auto q = p; // q will point to one past the last constructed element
alloc.construct(q++); // *q is the empty string
alloc.construct(q++, 10, 'c'); // *q is cccccccccc
alloc.construct(q++, "hi"); // *q is hi!

It is an error to use raw memory in which an object has not been constructed:

cout << *q << endl; // disaster: q points to unconstructed memory!

When we’re finished using the objects, we must destroy the elements we constructed, which we do by calling destroy on each constructed element. The destroy function takes a pointer and runs the destructor on the pointed-to object:

while (q != p)
    alloc.destroy(--q); // free the strings we actually allocated

Once the elements have been destroyed, we can either reuse the memory to hold other strings or return the memory to the system. We free the memory by calling deallocate:

alloc.deallocate(p, n);

The pointer we pass to deallocate cannot be null; it must point to memory allocated by allocate. Moreover, the size argument passed to deallocate must be the same size as used in the call to allocate that obtained the memory to which the pointer points.

As a companion to the allocator class, the library also defines two algorithms that can construct objects in uninitialized memory.

methods	means
uninitialized_copy	Copy block of memory
uninitialized_copy_n	Copy block of memory
uninitialized_fill	Fill block of memory
uninitialized_fill_n	Fill block of memory

As an example, assume we have a vector of ints that we want to copy into dynamic memory. We’ll allocate memory for twice as many ints as are in the vector. We’ll construct the first half of the newly allocated memory by copying elements from the original vector. We’ll construct elements in the second half by filling them with a given value:

int main() {
    vector<int> v(2, 2);
    allocator<int> alloc;
    auto p = alloc.allocate(v.size() * 2);
    auto q = uninitialized_copy(v.begin(), v.end(), p);
    uninitialized_fill_n(q, v.size(), 20);
    for (size_t i = 0; i < v.size() * 2; i++) {
        cout << p[i] << endl;
    }
    return 0;
}
//output
//2
//2
//20
//20

Using the Library: A Text-Query Program

To conclude our discussion of the library, we’ll implement a simple text-query program. Our program will let a user search a given file for words that might occur in it. The result of a query will be the number of times the word occurs and a list of lines on which that word appears.

Design of the Query Program

#pragma once
#include<fstream>
#include<vector>
#include<string>
#include<set>
#include<memory>
#include<map>
#include<sstream>
#include<iostream>

// when we write more than one class in a FILE:
// we need protected that first declaration class
// then implement method by declaration sequential

class QueryResult;

class TextQuery {
public:
    using line_no = std::vector<std::string>::size_type;

    TextQuery() = default;
    TextQuery(std::ifstream& input);
    QueryResult query(const std::string& s);
private:
    // input file
    std::shared_ptr<std::vector<std::string>> file;
    // map of each word to the set of the lines in which that word appears
    std::map <std::string, std::shared_ptr<std::set<line_no>>> wm;
};

class QueryResult {
    friend std::ostream& print(std::ostream&, const QueryResult&);
public:
    QueryResult() = default;
    QueryResult(std::string s,
        std::shared_ptr<std::set<TextQuery::line_no>> p,
        std::shared_ptr<std::vector<std::string>> f) :
        s_word(s), lines(p), file(f) {
    }

private:
    std::string s_word;
    std::shared_ptr<std::vector<std::string>> file;
    std::shared_ptr<std::set<TextQuery::line_no>> lines;
};

// TextQuery member
TextQuery::TextQuery(std::ifstream& input)
    :file(new std::vector<std::string>) {
    std::string line, text;
    while (getline(input, line)) {
        //read a line and save to vector string
        file->push_back(line);

        //get current line_no
        size_t n = file->size() - 1;

        //save one word where appeared
        std::istringstream ss(line);
        while (ss >> text) {
            // if word isn't already in wm, subscripting adds a new entry
            auto& lines = wm[text];
            if (!lines) {
                lines.reset(new std::set<line_no>);
            }
            // insert this line number
            lines->insert(n);
        }
    }
}

QueryResult TextQuery::query(const std::string& s) {
    // we'll return a pointer to this set if we don't find s
    static std::shared_ptr<std::set<line_no>> nodata(new std::set<line_no>);

    auto location = wm.find(s);
    if (location != wm.end()) {
        return QueryResult(s, location->second, file);
    }
    else {
        return QueryResult(s, nodata, file);
    }
}

// QueryResult member
std::ostream& print(std::ostream& out, const QueryResult& qr) {
    // TODO: insert return statement here
    out << qr.s_word << " appear " << (qr.lines)->size() << " times:" << std::endl;
    for (auto& line : *(qr.lines)) {
        out << line + 1 << ": " << (qr.file)->at(line) << std::endl;
    }
    return out;
}

Main program

#include<fstream>
#include<iostream>
#include "ch12_3.h"
using namespace std;

int main() {
    ifstream input("text.txt");
    TextQuery tq(input);

    string s;
    while (true) {
        cout << "input a word you want query:" << endl;
        if (!(cin >> s) || s == "q") {
            break;
        }
        auto qr = tq.query(s);
        print(std::cout, qr);
    }
    return 0;
}