Dynamic Memory Allocation

Allocate an array with an unpredictable number of elements

When you use a declaration to create an array in C++, you must always specify the number of elements in the array when you write the program. Here are two ways to do that. (Use the data type size_t for a variable that holds the number of elements in an array, or the number of bytes in a block of memory.)

	int a[3];   //Create an array containing 3 elements.

	int b[] {   //Create another array containing 3 elements.
		10,
		20,
		30
	};

	//If you need a variable holding the number of elements in the array b,
	const size_t n {size(b)};

If you don’t know the number of elements when you write the program, then you can’t use a declaration to make an array. For example, you can’t get the number of elements from input after the program has started running:

	cout << "How many elements do you need in your array? ";
	size_t n {0};
	cin >> n;
	int a[n];   //Try to create an array with n elements.  Won't compile.

The simplest application of dynamic memory allocation (written with the operators new and delete[]) is to create an array when you can’t predict when you’re writing the program how many array elements you will need.

new1.C, new1.txt.
Loop through the block of memory with a size_t i subscript.
Not bothering to check cin for input failure.

new2.C, new2.txt.
Loop through the block of memory with an int *q pointer.
What happens if the user requests too much dynamically allocated memory?

How many ints do you want to store? 99999999999
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted (core dumped)

echo $?     (See the exit status number producted by the program.)
134         (134 = 128 + 6.  6 is number of the abort signal SIGABRT.)

new3.C. Catch the bad_alloc exception.

How many ints do you want to store? 99999999999        (almost 100 billion)
Sorry, Linux has no room for 99999999999 ints.         (civilized error message)

echo $?                                                (civilized exit status)
1

Use a vector object instead of new and delete[]

It’s easier to use a C++ standard library vector object instead of new and delete[], because we don’t have to tell the program up front how many items we want to store.

vectorint1.C, vectorint1.txt
The v in this program is our first example of a C++ object.
This particular object v is a vector of int’s, which is like an expandable array of int’s.
The name of the data type of this object is vector<int>.
(A data type that has <angle brackets> in its name is called a template data type.)
In C++, a function attached to an object is called a member function of the object.
(Use a period (.) to attach a function to an object.)
This program demonstrates two member functions attached to the object v, size and push_back.

vectordouble1.C, vectordouble1.txt
Since class vector is a template class, we can easily create many different flavors of it:
- vector<int>
- vector<double>
- vector<string>
- etc.
This program is the same as the previous one, except that this vector stores double’s instead of int’s.
The push_back member function of this vector takes an argument that is a double, not an int.

vectorint2.C, vectorint2.txt.
This time, the vector<int> is born empty.
We can also loop through a vector with the same range for loop that we used to loop through an array:
see range.C, range.txt.
I’m demonstrating three of the member functions of v, push_back, size, and capacity.
Exercise.
Uncomment the following statements in vectorint2.C immediately after the call to the push_back member function.
```
		cout << "v.size() = " << v.size() << "\n";
		cout << "v.capacity() = " << v.capacity() << "\n";
```
Does the vector’s capacity grow faster than its size?
Does the capacity ever suddenly double as the vector gradually increases in size?

vectordouble2.C, vectordouble2.txt
This program is the same as the previous one, except that this vector stores double’s instead of int’s, so the auto variable in this range for loop is a double.

The C++ Standard Library contains many other container classes that are template classes. For example,

Use a vector when you want to add new values only at the end of the container (via push_back).

Use a list when you want to add new values anywhere in the container (via insert).
For example,

#include <vector> //for class vector
#include <list>   //for class list
using namespace std;

	vector<int> v;            //born empty, put capable of holding ints
	v.push_back(20);          //insert at the end of the vector

	list<int> li;             //born empty, put capable of holding ints
	li.insert(begin(li), 10); //insert at the beginning of the list
	li.insert(end(li), 30);   //insert at the end of the list

Kill your variables in an unpredictable order

The order in which variables are declared determines the order in which they die:
```
#include <cstdlib>

int main()
{
	int i {10};
	int j {20};
	int k {30};

	return EXIT_SUCESS; //k, j, i die here, in that order.
}
```
But if we have a game where the variables are Klingon warships, you probably can’t know in advance what order they will be destroyed in.
It depends on what the user decided to do when the program runs.
You will have to create each variable with new instead of with a declaration.
(And you will have to remember to write delete at each point where a variable dies.)
We will do this later in the course.

HW

states.C, states.txt
vector.C by an151 has a vector of ints.

vector.C by mjj1 has a vector of ints and sums them up.

#include <algorithm>   //for the accumulate algorithm

	const int sum {accumulate(begin(v), end(v), 0)};

vector.C by kklassen2 finds the biggest int in a vector of ints.
There’s also a min_element algorithm.

#include <algorithm>   //for the max_element and distance algorithms

	const auto it {max_element(begin(v), end(v))};

	if (it == end(v)) {
		cerr << "The vector was empty.  There was no maximum element.\n";
	} else {
		cout << "The maximum element was " << *it
			<< " at location " << distance(it, begin(v)) << "\n";
	}

vectorbag.C by ljl8 has a vector of item structures.
(See also bettervectorgrocery.C.)
Initialize total_cost to 0.00 to make it look like a price in dollars and cents.
```
#include <iomanip>

	cout << fixed << setprecision(2) << total_cost << "\n";
```