Introduction to Computer Science PDF

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 Dynamic Data Structures II...

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 Dynamic Data Structures II 205 Section 17 Dynamic Data Structures II We have already seen how to allocate memory for an object using new. In this section, we want to learn how to allocate whole blocks of memory, not just memory for a single object. To this end, we will implement our own version our_vector of a vector, corresponding to std::vector. Recall that what we know about a vector std::vector. It can be initialized with an arbitrary size n (especially also for values that are only known at runtime), and it supports various operations, as summarized here: e = v[i]; // get element v[i] = e; // set element l = v.size(); // get size v.push_back(e); // append element... In particular, a vector is a dynamic data structure whose size can change during runtime! Its elements thus have to live on the heap. It there occupies a contiguous part of the memory (see Figure 17.1) to allow random access! Figure 17.1: The elements of a vector are stored contiguously in one piece in the memory. Now let us say we want to create a vector of size 100. How do we allocate the memory for it? Allocating every element separately would not only be tedious, it would lead to these elements being spread all over the heap memory. We want to instead dynamically allocate a chunk of memory of arbitrary size during runtime. We can do that with new for arrays! Subsection 17.1 Dynamic Arrays We can use the new operator together with [] to allocate a chunk of consecutive memory: The statement new T[n] allocates memory to store n many consecutive objects of type T (see Figure 17.2). This chunk of memory is called an array65 of type T of length n. Here, n has to be an expression of type int. 65 It is called dynamic array since it lives on the heap. There are also static arrays, but their size needs to be known at compile-time, so it could not have the size of a user input! Dynamic Data Structures II 206 size s of a T Figure 17.2: An array of 7 elements of type T in memory. The new T[] operator has type T* and as its value the starting address of the memory chunk (i.e., the address of the first element). Thus, for instance, after int* p = new int[n], the pointer p points to the first of n integers, and the value of the first integer can be read by dereferencing the pointer, i.e., with *p. But how do we access later elements? For instance, the second or the last element? For that, we have to use pointer arithmetic. 17.1.1 Pointer Arithmetic Pointer plus Integer We can add a positive number i with 0 ≤ i ≤ n to a pointer66. p + i then contains the address of the (i + 1)th element (at index i), and *(p + i) its value. The address p + n denotes the end of the array (one beyond the last element). p p+3 p+n Figure 17.3: The pointer returned by new T[n] is the address of the first element. The fourth element can be found at address p + 3, and the last element at p + (n - 1). The pointer p + n points right behind the array. Here is an example and the corresponding illustration in Figure 17.4 int* p0 = new int{1,2,3,4,5,6,7}; // p0 points to 1st element int* p3 = p0 + 3; // p3 points to 4th element *(p3 + 2) = 600; // set value of 6th element to 600 std::cout