17. Vector and Free Store

"Use vector as the default." -- Alex Stepanov

17.1 Introduction

The most useful class in the standard C++ library is vector. We are going to undertake an adventure: we are going to try to understand how vector was gradually built to what we have today, why it was so designed, and along the way we will gain some understanding of how we might create our own container. We will also gain an understanding of how computer programs work at a deeper level than we have encountered before.

Why bother with all of these details? The reason is, if we want to become true software professionals, we must understand how our languages use the underlying hardware!

17.2 vector basics

                        
vector<double> age(4); // a vector with 4 elements of type double
age[0]=0.33;
age[1]=22.0;
age[2]=27.2;
age[3]=54.2;

Elements of age are numbered 0 to age.size()-1.
Defining a fixed-size data structure,

                        
class vector {
    int size, age0, age1, age2, age3;
    // . . .
};

Adding an element with push_back() becomes difficult as defined vector has fixed number of elements.
We need a data member that points to the set of elements so that it points to different set of elements when more space is needed.
A pointer holds an address and is distinguished by the suffix * meaning "pointer to double".

                        
// a very simplified vector of doubles (like vector<double>)
class vector {
    int sz; // the size
    double* elem; // pointer to the first element (of type double)
public:
    vector(int s); // constructor: allocate s doubles,
                  // let elem point to them
                  // store s in sz
int size() const { return sz; } // the current size
};

17.3 Memory, addresses, and pointers

An address is a "number that indicates a location in memory".

A megabyte of memory can be visualized as following,

                          
int var = 17;

Here, an "int-size" piece of memory for var is set aside and value 17 is put in memory.


int* ptr = &var; // ptr holds the address of var

The type needed to hold the address of an int is “pointer to int” or an “int pointer” and the notation is int*.

The “address of” operator, unary &, is used to get the address of an object. So, if var happens to start at address 4096, ptr will hold the value 4096:

Each type has a corresponding pointer type.

                        
int x = 17;
int* pi = &x; // pointer to int
double e = 2.71828;
double* pd = &e; // pointer to double

To see value of the object pointed to,

                        
cout << "pi==" << pi << "; contents of pi==" << *pi << "\n";
cout << "pd==" << pd << "; contents of pd==" << *pd << "\n";

The output for *pi will be the integer 17 and the output for *pd will be the double 2.71828.
The output for pi and pd will vary depending on where the compiler allocated our variables x and e in memory.

The contents of operator can also be used on the left-hand side of an assignment:

                        
*pi = 27; // OK: you can assign 27 to the int pointed to by pi
*pd = 3.14159; // OK: you can assign 3.14159 to the double pointed to by pd
*pd = *pi; // OK: you can assign an int (*pi) to a double (*pd)

int provides the operations suitable for integers.
A pointer type provides the operations suitable for addresses.

                        
int i = pi; // error: can’t assign an int* to an int
pi = 7; // error: can’t assign an int to an int*

Also, a pointer to char (a char*) is not a pointer to int (an int*):

                        
char* pc = pi; // error: can’t assign an int* to a char*
pi = pc; // error: can’t assign a char* to an int*

Why is it an error?

                        
char ch1 = 'a';
char ch2 = 'b';
char ch3 = 'c';
char ch4 = 'd';
int* pi = &ch3; // point to ch3, a char-size piece of memory
                // error: we cannot assign a char* to an int*
                // but let’s pretend we could
*pi = 12345; // write to an int-size piece of memory
*pi = 67890;

If the compiler would have allowed the code, 12345 would be written to the memory starting at &ch3. If that write happened to overwrite the pointer itself, then the next assignment *pi=67890 would place 67890 in some completely different part of memory.

Thats why our aim is always to work at highest level of abstraction.

17.3.1 The size of operator

sizeof gives the size of an object of the type.

For an expression it gives the size of the type of the result. The result of sizeof is a positive integer.
It's unit is sizeof(char) defined to be 1. sizeof(int) is typically 4.

                            
void sizes(char ch, int i, int* p)
{
    cout << "the size of char is " << sizeof(char) << ' ' << sizeof (ch) << '\n';
    cout << "the size of int is " << sizeof(int) << ' ' << sizeof (i) << '\n';
    cout << "the size of int* is " << sizeof(int*) << ' ' << sizeof (p) << '\n';
}

Memory used by a vector:

                            
vector<int> v(1000);  // vector with 1000 elements of type int
cout << "the size of vector<int>(1000) is " << sizeof (v) << '\n';

Output:

                            
the size of vector<int>(1000) is 20

Drill

Create pointer_test.cpp. Include the usual header file. Create pointers to char, int, and double variables. Then assign them to the address (&) of variables of the right type. Print out both the pointer and de-reference it and print the value. Then use sizeof(x) to print the size of the pointers and the variables.

17.4 Free store and pointers

The compiler sets aside memory for

code (code storage or text storage)
global variables (static storage)
function calls for arguments and local variables (stack storage or automatic storage)
free (unallocated) storage

The C++ language makes this “free store” (also called the heap) available through an operator called new.

                        
double* p = new double[4]; // allocate 4 doubles on the free store

                        
char* q = new double[4]; // error: double* assigned to char*

The new returns a pointer to a double but a double isn't a char.
It should not be assigned to the pointer to char variable q.

17.4.1 Free-store allocation

We request memory to be allocated on the free store by the new operator:

The new operator returns a pointer to the allocated memory.
A pointer value is the address of the first byte of the memory.
A pointer points to an object of a specified type.
A pointer does not know how many elements it points to.

Example:

                            
int* pi = new int; // allocate one int
int* qi = new int[4]; // allocate 4 ints (an array of 4 ints)
double* pd = new double; // allocate one double
double* qd = new double[n]; // allocate n doubles (an array of n doubles)

Pointers to objects of different types are different types.

                            
pi = pd; // error: can’t assign a double* to an int*
pd = pi; // error: can’t assign an int* to a double*

Allowing assignment of pointers to different types would allow type errors.

17.4.2 Access through pointers

The subscript operator [ ] can also be used.

                            
double* p = new double[4]; // allocate 4 doubles on the free store
double x = *p; // read the (first) object pointed to by p
double y = p[2]; // read the 3rd object pointed to by p

The [ ] and * operators can also be used for writing

                            
*p = 7.7; // write to the (first) object pointed to by p
p[2] = 9.9; // write to the 3rd object pointed to by p

The “contents of” operator allows to read and write the object pointed to by a pointer p:

                            
double x = *p; // read the object pointed to by p
*p = 8.8; // write to the object pointed to by p

The [ ] operator treats memory as a sequence of objects with the first one pointed to by a pointer p:

                            
double x = p[3]; // read the 4th object pointed to by p
p[3] = 4.4; // write to the 4th object pointed to by p
double y = p[0]; // p[0] is the same as *p

17.4.3 Ranges

The pointer doesn't know how many elements it points to.

                            
double* pd = new double[3];
pd[2] = 2.2;
pd[4] = 4.4;
pd[–3] = –3.3;

The advantage of using vector rather than using memory allocated by new is that a vector knows its size so that out-of-range access can be prevented.
Also, we can assign one double* to another double* independently of how many objects each points to.

                              
double* p = new double; // allocate a double
double* q = new double[1000]; // allocate 1000 doubles
q[700] = 7.7; // fine
q = p; // let q point to the same as p
double d = q[700]; // out-of-range access!

Here, q[700] refers to two different memory locations and the last use is an out-of-range access.

17.4.4 Initialization

                            
double* p0; // uninitialized: likely trouble
double* p1 = new double; // get (allocate) an uninitialized double
double* p2 = new double{5.5}; // get a double initialized to 5.5
double* p3 = new double[5]; // get (allocate) 5 uninitialized doubles

It is good to ensure that pointers are initialized and the object they point to are also intialized.

Declaring p0 without initializing is trouble.

                            
*p0 = 7.0;

Here 7.0 is assigned to some location in memory. We have no idea where. Uninitialized pointers are a major source of C++ bugs!

Memory allocated by new is not initialized for built-in types.
An initializer list can be specified for an array of objects allocated by new.

                            
double* p4 = new double[5] {0,1,2,3,4};
double* p5 = new double[] {0,1,2,3,4};

Also, a program with uninitialized variables can run differently. If a type X has a default constructor,

                            
X* px1 = new X; // one default-initialized X
X* px2 = new X[17]; // 17 default-initialized Xs

Explicitly initialize if Y has a constructor but not a default constructor

                            
Y* py1 = new Y; // error: no default constructor
Y* py2 = new Y{13}; // OK: initialized to Y{13}
Y* py3 = new Y[17]; // error: no default constructor
Y* py4 = new Y[17] {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};

17.4.5 The null pointer

The value zero is called the null pointer when assigned to a pointer.

                            
if (p0 != nullptr) // consider p0 valid

An if-statement really checks whether its condition is nullptr.

                            
if (p0) // consider p0 valid; equivalent to p0!=nullptr

17.4.6 Free-store deallocation

It is always a good idea to return memory to the free store once it's use is finished.

                            
double* calc(int res_size, int max) // leaks memory
{
    double* p = new double[max];
    double* res = new double[res_size];
    // use p to calculate results to be put in res
    return res;
}

double* r = calc(100,1000);

The call calc(100,1000) will render the space needed for 1000 doubles unusable for the rest of the program.

The operator delete returns memory to the free store.

                            
double* calc(int res_size, int max)
// the caller is responsible for the memory allocated for res
{
    double* p = new double[max];
    double* res = new double[res_size];
    // use p to calculate results to be put in res
    delete[] p; // we don’t need that memory anymore: free it
    return res;
}

double* r = calc(100,1000);
// use r
delete[] r; // we don’t need that memory anymore: free it

The 2 forms of delete are:

delete p frees the memory for an individual object allocated by new.
delete[ ] p frees the memory for an array of objects allocated by new.

Deleting an object twice is a bad mistake.

                            
int* p = new int{5};
delete p; // fine: p points to an object created by new
// . . . no use of p here . . .
delete p; // error: p points to memory owned by the free-store manager

The problem here is that the programmer doesn't own the object anymore to delete it and it might be possible that the free-store manager already assigned the pointer to some another object which can be mistakenly deleted.

Deleting null pointer is harmless.

                            
int* p = nullptr;
delete p; // fine: no action needed
delete p; // also fine (still no action needed)

Drill

Write two programs:

A C++ program that loops allocating new double[10000] and prints how many times it has gone through the loop. How long did it run? How much memory were you able to allocate? Is this different on PythonAnywhere than on your laptop? (If you only run on PA, that is OK.)
A Python program that recursively increments and prints a variable. How many times could you make a recursive call?

17.5 Destructors

Just as the way a constructor is called when an object class is created, a destructor is called when an object goes out of scope.
It makes sure that an object is properly cleaned up before it is destroyed.

                        
// a very simplified vector of doubles
class vector {
    int sz; // the size
    double* elem; // a pointer to the elements
public:
     vector(int s) // constructor
          :sz{s},
          elem{new double[s]} // allocate memory
          {
              for (int i=0; i<s; ++i)
                  elem[i]=0; // initialize elements
          }

     ~vector() // destructor
          { delete[] elem; } // free memory
          // . . .
};

void f3(int n)
{
    double* p = new double[n]; // allocate n doubles
    vector v(n); // the vector allocates n doubles
    // . . . use p and v . . .
    delete[ ] p; // deallocate p’s doubles
} // vector automatically cleans up after v

Every class the "owns" resources needs a destructor! (Resources: files, buffers, threads, locks, etc.)

17.5.1 Generated destructors

Destructors are called when the object is destroyed.

                            
struct Customer {
    string name;
    vector<string> addresses;
    // . . .
};

void some_fct()
{
    Customer fred;
    // initialize fred
    // use fred
}

When some_fct exits, fred will go out of scope and be destroyed.

17.5.2 Destructors and free store

Whatever resources a class object needs to function, it acquires in a constructor.
During the object’s lifetime it may release resources and acquire new ones.
At the end of the object’s lifetime, the destructor releases all resources still owned by the object.

                            
Shape* fct()
{
    Text tt {Point{200,200},"Annemarie"};
    // . . .
    Shape* p = new Text{Point{100,100},"Nicholas"};
    return p;
}

void f()
{
    Shape* q = fct();
    // . . .
    delete q;
}

If there is a class with a virtual function, it needs a virtual destructor.

If a class has a virtual function it is likely to be used as a base class, and
If it is a base class its derived class is likely to be allocated using new, and
If a derived class object is allocated using new and manipulated through a pointer to its base, then
It is likely to be deleted through a pointer to its base.

17.6 Access to elements

We use get() and set() to make vector read and write elements.

                        
// a very simplified vector of doubles
class vector {
    int sz; // the size
    double* elem; // a pointer to the elements
public:
    vector(int s) :sz{s}, elem{new double[s]} { /* . . . */ } // constructor
    ~vector() { delete[] elem; } // destructor

    int size() const { return sz; } // the current size

    double get(int n) const { return elem[n]; } // access: read
    void set(int n, double v) { elem[n]=v; } // access: write
};

Both get() and set() access the elements using the [ ] operator on the elem pointer: elem[n].

17.7 Pointers to class objects

The notion of “pointer” is general. The use of pointers to vectors is the same as that of pointers to chars.

                        
vector* f(int s)
{
    vector* p = new vector(s); // allocate a vector on free store
    // fill *p
    return p;
}

void ff()
{
    vector* q = f(4);
    // use *q
    delete q; // free vector on free store
}

When we delete a vector, its destructor is called.

                        
vector* p = new vector(s); // allocate a vector on free store
delete p; // deallocate

When the vector on free store is created the new operator first allocated memory then invokes the vector's constructor.
When the vector is deleted the delete operator first invokes the vector's destructor then deallocates the memory used for the vector.

                        
vector<vector<double>>* p = new vector<vector<double>>(10);
delete p;

This works for 2D vectors as well. delete p invokes the destructor for vector<vector<double>>. This destructor in turn invokes the destructor for its vector<double> cleaning everything.

All classes support the operator . (dot) for accessing members given the name of an object:

                        
vector v(4);
int x = v.size();
double d = v.get(3);

All classes support the operator –> (arrow) for accessing members, given a pointer to an object:

                        
vector* p = new vector(4);
int x = p–>size();
double d = p–>get(3);

17.8 Messing with types: void* and casts

The type void* means “pointer to some memory that the compiler doesn’t know the type of.”
There are no objects of type void and we use it to mean "no value returned".

                        
void v; // error: there are no objects of type void
void f(); // f() returns nothing — f() does not return an object of type void

A pointer to any object type can be assigned to a void*,

                        
void* pv1 = new int; // OK: int* converts to void*
void* pv2 = new double[10]; // OK: double* converts to void*

Since the compiler doesn’t know what a void* points to, we must tell it:

                        
void f(void* pv)
{
    void* pv2 = pv; // copying is OK (copying is what void*s are for)
    double* pd = pv; // error: cannot convert void* to double*
    *pv = 7; // error: cannot dereference a void*
    // (we don’t know what type of object it points to)
    pv[2] = 9; // error: cannot subscript a void*
    int* pi = static_cast<int*>(pv); // OK: explicit conversion
    // . . .
}

A static_cast can be used to explicitly convert between related pointer types, such as void* and double*.
An operation such as static_cast is called an explicit type conversion or colloquially a cast.
Two casts that are potentially even nastier than static_cast:

reinterpret_cast can cast between unrelated types, such as int and double*.
const_cast can “cast away const.”

                        
Register* in = reinterpret_cast<Register*>(0xff);
void f(const Buffer* p)
{
    Buffer* b = const_cast<Buffer*>(p);
    // . . .
}

17.9 Pointers and references

A reference is an automatically dereferenced immutable pointer. Pointers and references differ in these ways:

Assignment to a pointer changes the pointer’s value (not the pointed-to value).
To get a pointer you generally need to use new or &.
To access an object pointed to by a pointer you use * or [ ].
Assignment to a reference changes the value of the object referred to (not the reference itself).
You cannot make a reference refer to a different object after initialization.
Assignment of references does deep copy (assigns to the referred-to object); assignment of pointers does not (assigns to the pointer object itself).
Beware of null pointers.

Example:

                        
int x = 10;
int* p = &x; // you need & to get a pointer
*p = 7; // use * to assign to x through p
int x2 = *p; // read x through p
int* p2 = &x2; // get a pointer to another int
p2 = p; // p2 and p both point to x
p = &x2; // make p point to another object

The corresponding example for references is

                        
int y = 10;
int& r = y; // the & is in the type, not in the initializer
r = 7; // assign to y through r (no * needed)
int y2 = r; // read y through r (no * needed)
int& r2 = y2; // get a reference to another int
r2 = r; // the value of y is assigned to y2
r = &y2; // error: you can’t change the value of a reference
        // (no assignment of an int* to an int&)

A reference and a pointer are both implemented by using a memory address.

17.9.1 Pointer and reference parameters

To change the value of a variable to a value computed by a function we have following choices,

                            
int incr_v(int x) { return x+1; } // compute a new value and return it
void incr_p(int* p) { ++*p; } // pass a pointer
// (dereference it and increment the result)
void incr_r(int& r) { ++r; } // pass a reference

Returning the value often leads to the most obvious code,

                            
int x = 2;
x = incr_v(x); // copy x to incr_v(); then copy the result out and assign it

Using a pointer argument alerts the programmer that something might be changed,

                            
int x = 7;
incr_p(&x) // the & is needed
incr_r(x);

The need to use & in incr_p(&x) alerts the user that x might be changed. incr_r(x) “looks innocent.”
The function has to beware of null pointer,

                            
incr_p(nullptr); // crash: incr_p() will try to dereference the null pointer
int* p = nullptr;
incr_p(p); // crash: incr_p() will try to dereference the null pointer

incr_p() protects against,

                            
void incr_p(int* p)
{
    if (p==nullptr)
        error("null pointer argument to incr_p()");
    ++*p; // dereference the pointer and increment the object pointed to
}

At the end we can say that the choice depends on the nature of function,

For tiny objects prefer pass-by-value.
For functions where “no object” (represented by nullptr) is a valid argument use a pointer parameter (and remember to test for nullptr).
Otherwise, use a reference parameter.

17.9.2 Pointers, references, and inheritance

Example in terms of pointers or references:

                            
void rotate(Shape* s, int n); // rotate *s n degrees
Shape* p = new Circle{Point{100,100},40};
Circle c {Point{200,200},50};
rotate(p,35);
rotate(&c,45);

For references,

                            
void rotate(Shape& s, int n); // rotate s n degrees
Shape& r = c;
rotate(r,55);
rotate(*p,65);
rotate(c,75);

17.9.3 An example: lists

A short list of Norse gods

A list like this is called a doubly-linked list where we can find both the predecessor and the successor.
A list where we find only the successor is called a singly-linked list.

Define links,

                            
struct Link {
    string value;
    Link* prev;
    Link* succ;
    Link(const string& v, Link* p = nullptr, Link* s = nullptr)
          : value{v}, prev{p}, succ{s} { }
};

Build list of Norse gods,

                            
Link* norse_gods = new Link{"Thor",nullptr,nullptr};
norse_gods = new Link{"Odin",nullptr,norse_gods};
norse_gods–>succ–>prev = norse_gods;
norse_gods = new Link{"Freia",nullptr,norse_gods};
norse_gods–>succ–>prev = norse_gods;

Insert operation,

                            
Link* insert(Link* p, Link* n) // insert n before p (incomplete)
{
    n–>succ = p; // p comes after n
    p–>prev–>succ = n; // n comes after what used to be p’s predecessor
    n–>prev = p–>prev; // p’s predecessor becomes n’s predecessor
    p–>prev = n; // n becomes p’s predecessor
    return n;
}

Improving insert operation,

                            
Link* insert(Link* p, Link* n) // insert n before p; return n
{
    if (n==nullptr)
        return p;
    if (p==nullptr)
        return n;
    n–>succ = p; // p comes after n
    if (p–>prev)
        p–>prev–>succ = n;
    n–>prev = p–>prev; // p’s predecessor becomes n’s predecessor
    p–>prev = n; // n becomes p’s predecessor
    return n;
}

Now we can write,

                            
Link* norse_gods = new Link{"Thor"};
norse_gods = insert(norse_gods,new Link{"Odin"});
norse_gods = insert(norse_gods,new Link{"Freia"});

17.9.4 List operations

Operations:

The constructor
insert: insert before an element
add: insert after an element
erase: remove an element
find: find a Link with a given value
advance: get the nth successor

                            
Link* add(Link* p, Link* n) // insert n after p; return n
{
    // much like insert (see exercise 11)
}

Link* erase(Link* p) // remove *p from list; return p’s successor
{
    if (p==nullptr)
        return nullptr;
    if (p–>succ)
        p–>succ–>prev = p–>prev;
    if (p–>prev)
        p–>prev–>succ = p–>succ;
    return p–>succ;
}

Link* find(Link* p, const string& s) // find s in list;
// return nullptr for “not found”
{
    while (p) {
        if (p–>value == s)
            return p;
        p = p–>succ;
    }
    return nullptr;
}

Link* advance(Link* p, int n) // move n positions in list
// return nullptr for “not found”
// positive n moves forward, negative backward
{
    if (p==nullptr)
        return nullptr;
    if (0<n) {
        while (n––) {
            if (p–>succ == nullptr)
                return nullptr;
            p = p–>succ;
        }
    }
    else if (n<0) {
            while (n++) {
                if (p–>prev == nullptr)
                    return nullptr;
                p = p–>prev;
            }
          }
    return p;
}

17.9.5 List use

Example:

                            
Link* norse_gods = new Link("Thor");
norse_gods = insert(norse_gods,new Link{"Odin"});
norse_gods = insert(norse_gods,new Link{"Zeus"});
norse_gods = insert(norse_gods,new Link{"Freia"});
Link* greek_gods = new Link("Hera");
greek_gods = insert(greek_gods,new Link{"Athena"});
greek_gods = insert(greek_gods,new Link{"Mars"});
greek_gods = insert(greek_gods,new Link{"Poseidon"});

Here, Zeus is a Greek god, rather than a Norse god. Also, the Greek god of war is Ares, not Mars.

Fixing,

                            
Link* p = find(greek_gods, "Mars");
if (p)
    p–>value = "Ares";


Link* p = find(norse_gods, "Zeus");
if (p) {
    if (p==norse_gods)
        norse_gods = p–>succ;
    erase(p);
    greek_gods = insert(greek_gods,p);
}

Printing lists,

                            
void print_all(Link* p)
{
    cout << "{ ";
    while (p) {
        cout << p–>value;
        if (p=p–>succ) cout << ", ";
    }
    cout << " }";
}
print_all(norse_gods);
cout<<"\n";

print_all(greek_gods);
cout<<"\n";

The code gives,

                            
{ Freia, Odin, Thor }
{ Zeus, Poseidon, Ares, Athena, Hera }

17.10 The this pointer

Implementing Link::insert() by copying our previous global insert()

                        
Link* Link::insert(Link* n) // insert n before p; return n
{
    Link* p = this; // pointer to this object
    if (n==nullptr)
        return p; // nothing to insert
    if (p==nullptr)
        return n; // nothing to insert into
    n–>succ = p; // p comes after n
    if (p–>prev)
        p–>prev–>succ = n;
    n–>prev = p–>prev; // p’s predecessor becomes n’s predecessor
    p–>prev = n; // n becomes p’s predecessor
    return n;
}

Alternatively, we could simply use this instead of p:

                        
Link* Link::insert(Link* n) // insert n before this object; return n
{
    if (n==nullptr)
        return this;
    if (this==nullptr)
        return n;
    n–>succ = this; // this object comes after n
    if (prev)
        prev–>succ = n;
    n–>prev = prev; // this object’s predecessor becomes n’s predecessor
    prev = n; // n becomes this object’s predecessor
    return n;
}

The compiler ensures that we do not change the value of this in a member function.

                        
struct S {
  // . . .
  void mutate(S* p)
  {
      this = p; // error: this is immutable
      // . . .
  }
};

17.10.1 More link use

Continuing example of Norse gods, we correct the mistakes,

                            
Link* p = greek_gods–>find("Mars");
if (p)
    p–>value = "Ares";

Moving Zeus into correct Pantheon,

                            
Link* p2 = norse_gods–>find("Zeus");
if (p2) {
    if (p2==norse_gods)
        norse_gods = p2–>next();
    p2–>erase();
    greek_gods = greek_gods–>insert(p2);
}

Printing the lists,

                            
void print_all(Link* p)
{
    cout << "{ ";
    while (p) {
        cout << p–>value;
        if (p=p–>next())
            cout << ", ";
    }
    cout << " }";
}
print_all(norse_gods);
cout<<"\n";

print_all(greek_gods);
cout<<"\n";

The above code gives,

                              
{ Freia, Odin, Thor }
{ Zeus, Poseidon, Ares, Athena, Hera }

Test Yourself!

Answers

1. b; 2. b; 3. b; 4. c;

Drill