Introduction to Computer Science PDF Fall 2024

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 Memory Management...

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 Memory Management 186 Section 16 Memory Management We have learned how to allocate dynamic memory and used it to implement our first dynamic data structure our_list. However, we have never freed the memory we have allocated. In particular, we have no function to remove elements from the list. We will now learn about correct memory management, especially that there needs to be a delete for every new. To simplify the example, we will take a look at the slightly simpler dynamic data structure stack. This is essentially a linked list that allows to insert and remove elements only at the front (also called top), as it is the case with a stack of books sitting on a table (see Figure 16.1). Figure 16.1: The data structure stack is a linked list that allows insertion and removal of elements only at the front, like a stack of books where we can add and remove books only from the top. Subsection 16.1 Basic Stack Functionality Our data structure stack should support the following functionality: class stack { public: // post: push an element onto the stack void push(int value); // pre: non-empty stack // post: delete top-most element from the stack void pop(); // pre: non-empty stack // post: return value of top-most element int top() const; // post: return whether stack is empty bool empty() const;... }; Memory Management 187 As for the linked list, we need a struct for the nodes of the data structure: struct lnode { int value; lnode* next; // constructor lnode(int v, lnode* n) : value(v), next(n) {} }; A stack then essentially is a pointer to the top-most node (also see Figure 16.2): class stack { public: void push(int value);... private: lnode* topn; }; element (type lnode) topn 1 5 6 value (type int) next (type lnode*) Figure 16.2: A stack is defined by a pointer (here topn) to the top-most node of a sequence of linked nodes (of type lnode). To create an (empty) stack, we can implement the following default constructor stack() : topn(nullptr) {} // default constructor that initializes the pointer topn with the null pointer. Note that the automatically generated constructor would “default-initialize” topn, which means leaving it uninitialized (and in particular would not lead to it being set to the null pointer!). Now let us add further functionality to check whether the stack is empty (empty) and to look at the top element (top) if not. // POST: returns true if stack is empty, false otherwise bool stack::empty() const { return topn == nullptr; } Memory Management 188 // PRE: stack must be non-empty // POST: returns the stack's top value int stack::top() const { assert(!empty()); return topn->value; } Recall here that topn->value is an abbreviation for (*topn).value, so the pointer to the struct is dereferenced and then the member value is accessed. Since dereferencing null pointers leads to undefined behavior, it is really important that the stack is not empty when calling top. We can add an element to the stack exactly as for linked lists: void stack::push(int value) { topn = new lnode(value, topn); } For instance, the call push(4) leads to a new node with value 4 and next pointer to the current top node being generated and to the top pointer being redirected to this new node. See Figure 16.3. topn 4 1 5 6 Figure 16.3: The effect of calling push(4) on the stack from Figure 16.2. The red node is added with the next pointer to the (previously) top element and the pointer topn is redirected to this new node. Subsection 16.2 Removing Elements from Stack So far, this has been almost exactly the same as already seen for linked lists. We now also want to support the removal of elements from the top of the stack. Our first try looks as follows: void stack::pop() { assert(!empty()); topn = topn->next; } We are guaranteed that the stack is not empty, so topn->next is not dereferencing a null Memory Management 189 pointer. And setting topn = topn->next indeed leads to the previous top element being “removed” from the stack. From the point of view of the stack, all is good! We could test our program and not run into any issues for quite some while, but eventually, the program might crash. What is going on? When pushing a new element to the stack, the line topn = new lnode(value, topn) is executed: memory is allocated for the lnode object, a (fitting) constructor is called to initialize the object, and a pointer to the object is returned (and assigned to topn). These dynamically generated objects (generated with new, living on the heap) have a dy- namic lifetime. This means that they “live” until they are deleted explicitly. Note that this is in stark contrast to local variables (on the stack) that “live” until they go out of scope. Explicit deletion happens via a delete statement delete p; where p is a pointer to an object that previously has been generated using new. While new has the effect of allocating memory and constructing the object, delete has the effect of destructing 61 the object and freeing the memory. Due to this duality, it is important to never have a new without a matching delete: Guideline about Dynamic Memory For each new, there has to be a matching delete! Ignoring this guideline leads to memory leaks: memory is allocated but never released, leading to the heap getting fuller and fuller with unused objects, eventually resulting in heap overflow once all memory is used up. On the other hand, we have to be careful about when and where to use delete. Things become tricky once there are several pointers pointing to the same object, as the following example illustrates. rational* t = new rational; rational* s = t; delete s; int nominator = t->denominator; Here we have two pointers t and s that both point to the same (dynamically generated) rational object. Line 3 deletes this objects using one of the pointers, thus destructs the object and frees the memory. After this, both pointers, t and s, still point to the same address as before, which is now an invalid memory location. Note that delete s in particular does not set the pointer s to nullptr. We call pointers pointing to deleted objects (and hence freed memory) dangling pointers. In Line 4, the dangling pointer t is dereferenced (recalling that t->denominator is equivalent to (*t).denominator), resulting in undefined behavior. Another danger, besides dereferencing dangling pointers, is to delete an object more than once, also leading to undefined behavior: 61 More about this in a second! Memory Management 190 rational* t = new rational; rational* s = t; delete s; delete t; So for our stack, where do we put the delete for the new in the function push? A node is created when the element is added to the stack and is deleted when the element is removed from the stack. Hence, the matching delete should be in the function pop: void stack::pop() { assert(!empty()); lnode* old_topn = topn; topn = topn->next; delete old_topn; } Note that we have to temporarily store the pointer to the top node in an auxiliary pointer old_topn so that after redirecting the pointer topn we still have access to the previous top node (see Figure 16.4). Otherwise, without a pointer to the to-be-deleted object, we could not delete it, resulting in a memory leak! topn 1 5 6 old topn Figure 16.4: Removing the top element from the stack by redirecting the top pointer to the second element and deleting the previous top node using an auxiliary pointer old_topn. Subsection 16.3 Destructors Now the new in push has its matching delete in pop. We therefore do not produce a memory leak by adding and removing elements from a stack. Great! We should be all set now, right? { stack s; s.push(1); s.push(2); Memory Management 191 s.push(3); std::cout next; delete old_topn; } } Memory Management 192 This indeed frees all its dynamic memory as soon as a stack is destructed (e.g., when its scope ends). Subsection 16.4 Copy Assignment Our stack class now seems to follow the guideline for dynamic memory: when we pop an element from the stack, we delete the element and when the stack is destructed, all its elements are deleted. But wait, there’s more! stack s1; s1.push(1); s1.push(2); s1.push(3); // s1: 3 -> 2 -> 1 stack s2 = s1; // s2: 3 -> 2 -> 1 s1.pop(); // s1: 2 -> 1 s2.pop(); Code 16.1: A non-working example. When running this program, the program crashes or some other weird things might happen! Why? Undefined behavior! Why? The interesting part happens on the line with the statement stack s2 = s1. It might look innocent, but it most definitely is not! This copy construction (here) means that a member-wise copy is created, i.e., a copy of the address of the pointer topn. After this line, s1.topn and s2.topn thus point to the same node. This node is deleted when s1.pop() is called, leaving s2 with a dangling pointer s2.topn. The call s2.pop() then dereferences that dangling pointer. s1 3 2 1 dangling pointer! s2 Figure 16.6: When the copy constructor is used to construct a stack s2 from stack s1, then s1 and s2 essentially “are” the same stack. When s1 removes its top element (and hence deletes it), s2 is left with a dangling pointer. A similar problem also occurs here: Memory Management 193 { stack s1; s1.push(1); stack s2 = s1; } Code 16.2: A minimum non-working example. Again, after the copy construction stack s2 = s1, the stacks s1 and s2 contain the same elements. When the block ends, both variables go out of scope, meaning their destructors are called (in reverse order of their declaration). Once the destructor of s2 is done, all elements have been deleted. The pointer s1.topn is dangling. The destructor of s1 thus dereferences a dangling pointer. The problem can be summarized as follows: Since we do not actually create a copy of all the data but only of the pointer, the two stacks use the same data. At the end of their lifetime, both stacks thus try to delete the same data. There are three different directions of a solution to this problem: 1. Create an actual copy of all data (deep copy). 2. Disallow copies altogether! 3. Implement a shared data structure (not further discussed here). Subsection 16.5 Copy Constructor The first approach is to create a copy of all data so that both stacks operate on their separate data. Removing elements on one stack does not have an influence on the other stack; they are completely independent. See Figure 16.7. The operations on s1 and on s2 are completely independent. Memory Management 194 s1 3 2 1 3 2 1 s2 Figure 16.7: The result of deep copying a stack s1 with the elements 3, 2, 1 (from top to bottom) to s2 and then calling pop on both stacks once. But how do we achieve this? For that, let us take a closer look at the copy construction stack s2 = s1. When an object of a class type T is initialized with another object of type T, this is called copy construction. The copy constructor of a class T is the unique constructor with declaration T (const T& t). It is called automatically when values of type T are initialized with values of type T, e.g., in one of the following cases (for a t of type T): T x = t; T x(t); If we have not declared our own copy constructor, the automatically-generated copy con- structor is called, which leads to member-wise application of their copy constructor. For fundamental types (e.g., int or pointers), this just means a copy of the bit pattern. If we want anything more interesting to happen, we have to provide our own copy constructor. For a deep copy for our class stack, we can define the copy constructor as follows: // POST: *this is initialized with a copy of s stack::stack(const stack& s) : topn (nullptr) { if (s.topn == nullptr) return; topn = new lnode(s.topn->value, nullptr); lnode* last = topn; for (lnode* n = s.topn->next; n != nullptr; n = n->next) { lnode* copy = new lnode(n->value, nullptr); last->next = copy; last = copy; } } We loop through the nodes of the stack s and create a copy of its current node n to build a new stack with topn (which is short for this->topn) pointing to its top element. Memory Management 195 With this, Codes 16.1 and 16.2 now indeed work! Subsection 16.6 Assignment Let us now make a subtle change to Codes 16.1 and 16.2: instead of stack s2 = s1, we write s2 = s1 for an already-declared stack s2. In other words, instead of copy construction, we use the assignment operator = (often also referred to as copy assignment in that context). The assignment operator of a class T is the overloaded function operator= as a member function of T with the signature T& T::operator=(const T& t) that has the current object *this as the left-hand side and the object t as the right-hand side. By C++ convention, it should return a reference to the left-hand side. If no assignment operator is declared, the automatically-generated assignment operator is called, which corresponds to a member-wise assignment. If we want anything more interest- ing to happen, we have to provide our own implementation. In particular, the assignment operator should have almost the same behavior as the copy constructor, with three small differences: First, since the to-be-assigned-to object is already initialized, the assignment operator does not need any initialization of the left-hand object. Second, since the object on the left-hand side is “overwritten”, data associated with this old object has to “cleaned up”. Third, there needs to be a check for the special case of a self assignment (t = t) that should not have any effect! For the stack example, the automatically-generated assignment operator essentially assigns s2.topn = s1.topn, again leading to the two stacks s1 and s2 sharing their nodes. If we want a deep copy to be made, we have to reflect that in our own assignment operator overload with signature stack& stack::operator=(const stack& s). We want to first check whether it is a self assignment. We can do that by checking whether the two objects live at the same address. The current object (*this) lives at the address this and the object s lives at the address &s. If this == &s, we do nothing. Otherwise, we want to create a deep copy of s, assign this copy to *this, and properly clean up the previous content of *this. There are two different ways how to implement this: from scratch and using the copy-and-swap idiom. We will present both! 16.6.1 Variant 1: From Scratch We first introduce some auxiliary member functions. The member function lnode* stack::copy_nodes() creates a (deep) copy of the nodes of *this and returns a pointer to the top-most node of this copy. We can essentially copy-paste this functionality from the copy constructor: Memory Management 196 // POST: returns a pointer to a copy of the nodes of *this lnode* stack::copy_nodes() const { if (topn == nullptr) return nullptr; lnode* topn_copy = new lnode(topn->value, nullptr); lnode* last = topn_copy; for (lnode* n = topn->next; n != nullptr; n = n->next) { lnode* copy = new lnode(n->value, nullptr); last->next = copy; last = copy; } return topn_copy; } In particular, with copy_nodes at hand, we could now rewrite our copy constructor as follows // POST: *this is initialized with a copy of s stack::stack(const stack& s) : topn (s.copy_nodes()) {} setting topn to the returned pointer of s.copy_nodes(). The second auxiliary member function helps us cleaning up the nodes of a stack (copy- pasting the implementation from the destructor): // POST: cleans up the nodes of *this, setting topn to nullptr void stack::clean_up_nodes() { while (topn != nullptr) { lnode* old_topn = topn; topn = topn->next; delete old_topn; } } With this, we can write the destructor in a single line: // POST: the dynamic memory of *this is deleted stack::~stack() { clean_up_nodes(); } We are now ready to implement the assignment operator! Memory Management 197 // POST: *this (left operand) becomes a copy of s (right operand) stack& stack::operator=(const stack& s) { if (this != &s) { // no self assignment clean_up_nodes(); // clean up old data topn = s.copy_nodes(); // copy data from s } return *this; // convention } Note that while it might be tempting, it would not be valid to directly call the destructor ~stack() instead of clean_up_nodes() to clean up the data: directly after the destructor call, the object *this would becomes invalid and could not be used anymore! Put differently, it is almost always a bad idea (and not what you want) to explicitly call a destructor. 16.6.2 Variant 2: Copy-and-Swap Idiom As you can imagine62 , it is a quite common situation that we want to implement the assign- ment operator after we have already implemented a destructor and a copy constructor. And as Variant 1 above shows, a lot of code from those two are reused in the definition of the assignment operator. There is a very elegant strategy to implement the copy assignment operator with calls to the other two functions (instead of code reuse!) called copy-and-swap idiom. The idea is to first call the copy constructor to construct a local copy copy of the right operand. Then to use the function std::swap(topn, copy.topn) to swap the top-node pointers63 of the left operand *this and copy. After this swap, this->topn points to a copy of the right operand and copy.topn contains the old content of *this. When the end of the function is reached, copy goes out of scope, so its destructor is called. This destructor call cleans up the data of copy, hence the old data of *this. // POST: *this (left operand) becomes a copy of s (right operand) stack& stack::operator=(const stack& s) { if (this != &s) { // no self assignment stack copy = s; // copy constructor std::swap(topn, copy.topn); // copy now has old data of *this } // destructor of copy called return *this; // convention } This is illustrated in Figure 16.8. 62 and more justification follows in the subsequent section 63 Usually, it is done slightly differently: One would implement a swap function defining how two stack objects are swapped (by swapping all member variables), and then call this swap function, rather than call swap directly on the member variable(s)). Memory Management 198 s.topn 3 2 1 this->topn 6 7 copy.topn 3 2 1 Figure 16.8: Consider an assignment with *this (a stack with elements 6 -> 7) as left operand and s (a stack with elements 3 -> 2 -> 1 as right operand using the copy-and- swap idiom. A local variable copy containing a copy of s is created. Then the pointers topn of copy and *this are swapped. This situation right after the swap is depicted above. When now the local variable copy goes out of scope, the stack 6 -> 7 is cleand up and *this remains with a copy of s, as desired. Subsection 16.7 Rule of Three We have seen that for proper memory management, a class needs constructors (to create new instances), a destructor (to destruct instances that are not used anymore), a copy constructor (to initialize a new instance as a copy of another instance), and an assignment operator (to assign a copy of an instance to another one). All these member functions are automatically-generated by C++. If we want a special functionality of these functions beyond the one provided by the automatically-generated versions, we have to implement our custom versions. Due to the close connection between destructor, copy constructor, and assignment operator (as illustrated before), there is the Rule of Three that states that if one of these three receives a special treatment, then all of them should. Rule of Three If a class declares one of the special member functions destructor, copy constructor, and assignment operator (hence overwriting the automatically-generated versions), all three should be declared. Note that one special way of declaring a copy constructor or an assignment operator is by deleting them, i.e., not allowing this function to be called at all! This can be done by adding =delete to the declaration. For instance, we can write T(const T& s)=delete; to delete the copy constructor of T. Note that while the keyword delete to delete a member function is the same as the one to deallocate memory (with delete p for a pointer p), these are two completely different things without any connection! Also note that it is not allowed to delete the destructor, and you would not want to anyway! For the example of the stack, this would correspond to the second solution of disallowing any copies. We could implement this as follows: Memory Management 199 class stack { public: stack(); // default constructor, creating empty stack ~stack(); // destructor, cleaning up all data stack(const stack& s)=delete; // no copy constructor stack& operator=(const stack& s)=delete; // no assignment operator... }; If after deleting the copy constructor and assignment operator, you access them, this leads to a compiler error: stack s1; stack s2; stack s2 = s1; // compiler error: use of deleted function stack s3; s3 = s1; // compiler error: use of deleted function Subsection 16.8 Shared Pointers Smart pointers are pointers with additional functionality that take care of the memory management for us, thus in some sense allow us to “outsource” proper memory management. There are two (main) types of smart pointers: shared pointers (std::shared_ptr) and unique pointers (std::unique_ptr). Unique pointers make sure that at most one pointer points to the an object. This pointer can be thought of as the owner of the object. As soon as the owner stops pointing to its object, the object is deleted. We do not discuss unique pointers further here. A shared pointer counts the number of pointers pointing to an object and deletes the object only when that number goes down to 0. For a type T, a shared pointer to T can be created using the function std::make_shared that takes the same arguments as a constructor of T. #include std::shared_ptr sp1 = std::make_shared(3, 4); We can use shared pointers exactly the same as normal64 pointers: 64 often referred to as raw or naked Memory Management 200 // dereferencing rational r = *sp1; // assignment std::shared_ptr sp2 = sp1; // member access std::cout n