Week 4: Building a better Python-like List type

Advantages and Disadvantages of arrays

Advantages:

• easy to declare and use
• indexing is very efficient.

Disadvantages:

• compiler/code does not stop you from indexing out of bounds.
• fixed size
• cannot do nice operations like appending, extending, printing, comparing, slicing, etc.

Let's implement a better array -- a Dynamic Array.

PyList class

• constructor
• getItem(index)
• setItem(index, item)
• append(item)
• copy constructor
• using [] to index
• slicing
• outputting array contents with <<
• Idea: adding 2 arrays together (creates new array with all items from each).

How this will differ from Vec class

In lab, you will create a Vec class -- also a dynamic array.

• Vec: capacity must be changed explicitly with call to setSize().
• PyList: capacity grows as items are added.

​

Dynamic allocation

Problem: you need space to store an array, but you don't know how big the array should be until runtime… What do you do?

1. Make the array bigger than most user will ever need.
2. Get new memory as needed… but how?

new operator

new gets memory from the operating system.

​

Syntax:

int *arr = new int[capacity];

"argument" to new is a type, from which the number of bytes required can be computed

returns an address of (a pointer to) new memory, allocated from the heap

Stack vs. Heap

Local variables and parameters in a function are allocated on the stack.

• each time a function is called, the stack frame has enough space for the local variables and parameters.
• when a function returns, that frame goes away.

Heap: other memory, allocated to the process by the operating system.

• Memory can be allocated from it using new and given back with delete and delete[].

Implementing PyList

constructors

getSize() -- const method

append(const Item &it)

operator<<

destructor

​

When is a destructor called?

A class destructor is called when:

• delete obj is called (obj is an instance of the class)
• an object of the class goes out of scope.
• end of a function where it is a local variable.
• inside of a for loop or if statement where it was defined.

When do you need to implement a destructor?

C++ will create a destructor for you if you don't define it explicitly.

Q: When do you need to define it yourself?

A: If your code uses new to dynamically allocate memory from the heap, you need to implement the destructor to delete or delete[] that memory.

Implementing PyList (2)

copy constructor -- with deep copy

getItemAt()

operator[] -- two versions

• return Item &

removeAt() -- changes size but not capacity

When is a copy constructor called?

3 cases:

1. An explicit call:

Pair p;

… put values in p …

Pair p2(p); // copy values from p to p2

​

When is a copy constructor called? (continued)

2. When object is passed to function using pass-by-value:

void f(Pair aPair) { … }

Pair p;

… snip …

f(p);

​

When is a copy constructor called? (continued)

3. When object is returned from a function:

Pair f() {

Pair p; // local variable

…

return p;

}

​

// in main

Pair p2 = f();

​

New Stuff

typedef

dynamic allocation

calling array ctor to initialize whole array

returning a reference (operator[])

overriding/defining operator overload.

const methods

overriding global << function.

destructor

copy constructor

​

implement removeAt()

changes mySize, but not myCapacity.

​

this pointer

Remember how in python each method had self as its first parameter:

class JumboShrimp:

def __init__(self, param):

…etc…

In C++, self is this -- a pointer to the object being read or modified or created. It is an implicit parameter (whereas self was an explicit parameter in python).

more about this

You can use this:

void setFirst(Item newVal) {

this->myFirst = newVal;

}

​

this-> means same as *(this).

​

You can call a method on this:

​

Item operator[](int idx) {

return this->getValueAt(idx); // instead of just getValueAt(idx);

}

​

Some people like to use this-> to emphasize they are using an instance variable or calling a method in the object itself.