When the object associated with darr is created, it allocates a dynamic array, storing the address of the first element in its elements member.
University of Michigan at Ann Arbor
Last Edit Date: 03/27/2023
Disclaimer and Term of Use:
We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file
This personal note is adapted from Professor Amir Kamil, Andrew DeOrio, James Juett, Sofia Saleem, and Saquib Razak. Please contact us to delete this file if you think your rights have been violated.
This work is licensed under a Creative Commons Attribution 4.0 International License.
We can leverage automatic memory management and destructors by wrapping up the management of a dynamic resource in a class.
In particular, we will arrange for the constructor of a class-type object to allocate a resource and for the destructor to release that resource.
Doing so ties the management of the resource to the lifetime of the class-type object. This strategy is called resource acquisition is initialization (RAII), and it is also known as scope-based resource management.
The following is a class that manages a dynamic array:
1 class DynamicIntArray {
2 public:
3 DynamicIntArray(int size_in)
4 : elements(new int[size_in]), num_elements(size_in) {}
5
6 ~DynamicIntArray() {
7 delete[] elements;
8 }
9
10 int size() const {
11 return num_elements;
12 }
13
14 int & operator[](int i) {
15 return elements[i];
16 }
17
18 const int & operator[](int i) const {
19 return elements[i];
20 }
21
22 private:
23 int *elements;
24 int num_elements;
25 };
When a DynamicIntArray object is created, it allocates a dynamic array of the specified size. The subscript operator is overloaded to index into the array.
There are two overloads, one that returns a modifiable element by reference if applied to a non-const DynamicIntArray, and another that returns a non-modifiable element by reference to const when applied to a const DynamicIntArray.
The class also provides a size() member function to query the size of the array.
When the DynamicIntArray object dies, it deletes the dynamic array that it had allocated, so that memory does not leak.
The following is an example that uses DynamicIntArray:
1 int main() {
2 int size;
3 cout << "Enter a size:" << endl;
4 cin >> size;
5
6 DynamicIntArray darr(size); // internally allocates an array
7
8 for (int i = 0; i < darr.size(); ++i) { // size() member function
9 darr[i] = i; // overloaded subscript
10 }
11
12 ...
13 } // darr dies here, causing its destructor to run and free the array it allocated
When the object associated with darr is created, it allocates a dynamic array, storing the address of the first element in its elements member.
When darr goes out of scope, its associated object dies, and the DynamicIntArray destructor is running. The destructor deletes the array, cleaning up the resource that is was using.
Thus, with the RAII pattern, we have leveraged automatic memory management and a class-type object to successfully manage a dynamic array.
Let’s use a similar strategy to write a new version of UnsortedSet without a fixed-capacity limitation. We allow the set to have an arbitrary number of elements by decoupling the storage of the elements from that of the set object, using dynamic memory for the former.
We modify the data representation so that the member variable elements is now a pointer to the first element of a dynamic array. We also add a capacity member variable to keep track of the size of that dynamic array. The resulting class definition for UnsortedSet is as follows:
1 template <typename T>
2 class UnsortedSet {
3 public:
4 // EFFECTS: Initializes this set to be empty.
5 UnsortedSet();
6
7 // MODIFIES: *this
8 // EFFECTS: Adds value to the set, if it isn't already in the set.
9 void insert(const T &value);
10
11 // MODIFIES: *this
12 // EFFECTS: Removes value from the set, if it is in the set.
13 void remove(const T &value);
14
15 // EFFECTS: Returns whether value is in the set.
16 bool contains(const T &value) const;
17
18 // EFFECTS: Returns the number of elements.
19 int size() const;
20
21 // EFFECTS: Prints out the set in an arbitrary order.
22 void print(std::ostream &os) const;
23
24 private:
25 // MODIFIES: *this
26 // EFFECTS: Doubles the capacity of this set.
27 void grow();
28
29 // Initial size of a set.
30 static const int INITIAL_SIZE = 5;
31
32 T *elements;
33 int capacity;
34 int num_elements;
35 // INVARIANTS:
36 // elements points to the sole dynamic array associated with this set
37 // capacity is the size of the array that elements points to
38 // 0 <= num_elements && num_elements <= capacity
39 // the first num_elements items in elements are the items in the set
40 // the first num_elements items in elements contain no duplicates
41 };
Note:
elements points to the start of the sole dynamic array associated with the set, and each set has its own dynamic array.
capacity is the size of dynamic array that elements points to.
grow() doubles the capacity of the set.
INITIAL_SIZE is a constant whose value is the initial size of a set.
The following is the new constructor for UnsortedSet:
1 template <typename T>
2 UnsortedSet<T>::UnsortedSet()
3 : elements(new T[INITIAL_SIZE]),
4 capacity(INITIAL_SIZE),
5 num_elements(0) {}
The constructor allocates a dynamic array of size INITIAL_SIZE and stores the address of its first element in elements.
We satisfy the remaining representation invariants by setting capacity to INITIAL_SIZE and num_elements to 0.
We modify insert() so that if the set is out of space, it calls the grow() member function to increase the available capacity.
1 template <typename T>
2 void UnsortedSet<T>::insert(const T &value) {
3 if (contains(value)) {
4 return;
5 }
6 if (num_elements == capacity) {
7 grow(); // double the capacity;
8 }
9 elements[num_elements] = value;
10 ++num_elements;
11 }
The grow() member function doubles the capacity of the set. In C++, an array has fixed size, even if it is dynamic, so we cannot change the size of the exsiring elements array. Instead, we allocate a new dynamic array, copy over the elements, and discard the old array.
The implementation of grow() is as following:
1 template <typename T>
2 void UnsortedSet<T>::grow() {
3 T *new_arr = new T[2 * capacity]; // allocate a new array that is twice as big
4 for (int i = 0; i < num_elements; ++i) { // copy the elements to the new array
5 new_arr[i] = elements[i];
6 }
7 capacity *= 2; // update capacity
8 delete[] elements; // free the old array
9 elements = new_arr; // set elements to point to first element of the new array
10 }
The grow() function allocates a new array and deletes the old one, satisfying the invariant that there is exactly one dynamic array associated with the set. It set elements to point to that array and updates capacity to the the array's size.
Copying the elements to the new array satisfies the representation invariant that the first num_elements items in elements are the ones in the set.
The grow operation demonstrates the power of indirecton. We decoupled the storage for the elements from that of the UnsortedSet object and their lifetimes. If the old storage no longer meets our needs, we can replace it with different storage that does, killin the old array and creating a new one.
We need a destructor that frees the resource when the UnsortedSet object dies.
Note: The destructor does not cause the object to dies. The object dies when its lifetime ends:
if it is associated with a local variable, when the variable goes out of scope
if it is associated with a static variable, when the program ends
if it is a member of a class-type object, when the latter object dies
if it is an element of an array, when the array dies
if it is a dynamic object, when delete is applied to its address
The desctructo merely runs when the object dies - it gives the object a chance to put its affairs in order while it is on its deathbed. If the object is managing dynamic memory, it needs to release that memory.
1 template <typename T>
2 UnsortedSet<T>::~UnsortedSet() {
3 delete[] elements;
4 }
The representation invariant that there is exactly one dynamic array associated with each UnsortedSet ensures that after the destructor runs, there is no longer a live array associated with the dying set.
The following is the code that produces an undefined behavior because of the lifetime issue.
1 int main() {
2 UnsortedSet<int> s1;
3 for (int i = 0; i < 5; ++i) {
4 s1.insert(i);
5 }
6
7 UnsortedSet<int> s2 = s1;
8 cout << s1 << endl; // prints { 0, 1, 2, 3, 4 }
9 cout << s2 << endl; // prints { 0, 1, 2, 3, 4 }
10
11 s2.insert(5); // causes a grow
12
13 cout << s2 << endl; // prints { 0, 1, 2, 3, 4, 5 }
14 cout << s1 << endl; // UNDEFINED BEHAVIOR
15 }
The code creates a set s1 and adds five items to the set, filling it to capacity. It then creates s2 as a copy of s1; by default, this does a member-by-member copy, so that both s1.elements and s2.elements point to the same dynamic array. We then add an item into s2, causing it to grow and delete its old array. This is the same array that s1.elements is pointing to, so that when we proceed to print out s1, it accesses a dead object. The result is undefined behavior.