Pointers and Dynamic Memory

CSCI 362: Data Structures

Prof. William Killian

View of Memory

  • Memory is byte addressable
  • If we had to declare memory
// pointer size in bits
size_t ptrSize = 8 * sizeof(void*);
// pointer size in bytes
size_t numBytes = 1 << ptrSize;

unsigned char memory[numBytes];
// memory is large enough to store ONE pointer

Pointer and Reference Declarations

  • Declaring a pointer requires us to add * to the type:
    int* ptr;
  • Declaring a reference requires us to add & to the type:
    int& ptr;
  • We don't often declare references inside functions, but we do declare references as parameters

Bonus: type aliases

Sometimes pointers and references can look confusing...

using IntPtr = int*;
using IntRef = int&;
// now we can use IntPtr instead of int* or IntRef instead of int&

Advanced Type Aliases

See: std::vector::value_type, std::vector::const_reference

Also, templated type aliases:

In [1]:
template <typename T>
using Ptr = T*;

template <typename T>
using Ref = T&;

template <typename T>
using CPtr = Ptr<T const>;

template <typename T>
using CRef = Ref<T const>;

Pointers and References -- oh my!

  • References look like values but act like pointers

  • There are two built-in operators in C++.

    1. Pointer dereference operator *

      T& operator* (T* ptr);

      Always takes a pointer and returns a reference

    2. Reference "addressof" operator &

      T* operator& (T& ptr);

      Always takes a reference and returns a pointer

In [1]:
int  a    = 4;
int& refA = a;     // refA is a reference to a
int* ptrA = &a;    // ptrA is a pointer to a
int& ref  = *ptrA; // ref is a reference to *ptrA (and therefore also a)

Data Addresses in Memory

0x80  0x81  0x82  0x83  0x84  0x85  0x86  0x87
+-----+-----+-----+-----+-----+-----+-----+----+
|                       |     |                |   
+-----+-----+-----+-----+-----+-----+-----+----+
^                       ^
myInt                   myChar
int  myInt;  // &myInt == 0x80
char myChar; // &myChar == 0x84
In [5]:
&a == &refA
Out[5]:
true
In [6]:
&refA == ptrA
Out[6]:
true

Pointers

Pointers hold addresses of objects

int* intPtr = nullptr;
Fish* fishPtr; // uninitialized -- COULD BE ANYTHING

// Note: C++ does NOT have a Scanner class...
Scanner* input = new Scanner (System::in);

int x;
// Get address of an object with operator&
int* xp = &x;

// Update 'x' indirectly through 'xp'
*xp = 8;

Creating "new" Pointers

Currently, we can only get a pointer by taking the address of a reference...

  • How did we create new instances of Objects in Java?
// Java
Scanner scanner = new Scanner(System.in);
  • In C++, it's almost the same!
// C++ -- note: Scanner and System doesn't exist
Scanner* scanner = new Scanner(System::in);

Cleaning up?

  • new asks the system to give us (the program) some memory (and constructs the object)
  • We need to tell the system we are done with memory we previously requested
  • When we don't do this, we hold onto the memory forever, resulting in a memory leak

Idea: delete

In [8]:
int* ptr = new int;
*ptr = 4;
delete ptr;

Pointer Manipulations

In [1]:
int m = 10;
int* intPtr = &m;

// *intPtr and m are aliases now
*intPtr = 3;
m
Out[1]:
3
In [2]:
#include <string>
#include <iostream>

std::string* sPtr; // uninitialized -- could be anything!
std::cout << sPtr;

0
In [3]:
sPtr = nullptr;
std::cout << sPtr;

0
In [3]:
sPtr = new std::string("jeb!"); // calls constructor
std::cout << sPtr;

0x5556418c0870
In [4]:
sPtr->size()
Out[4]:
4
In [5]:
delete sPtr

Arrays and Pointers

  • Really aren't so different from one another!
  • Array name evaluates to a const pointer to the first element
    int arr[7];
arr; // type of arr is 'int* const'
arr == &arr[0];
  • Hint: read types from right to left
    • int*
    • int const
    • int const *
    • int const * const

When to new

  • Use new sparingly (more costly and must match delete)
    • Low-level data structure implementation
    • More control over object lifetime
    • If you must use it, look into smart pointers
  • Use delete operator to release storage allocated with new
    • Otherwise, you have a memory leak
    • Uncessary in Java (because of garbage collection)

Constructors and Destructors

Constructor

  • Called during new
  • Initializes the object to some defined state

Destructor

  • Called during delete
  • Is supposed to relinquish any owned resources the of "deleted" object
In [4]:
class MyObject {
public:
    MyObject () {
        std::cout << "ctor" << std::endl;
    }
    MyObject (MyObject const&) {
        std::cout << "copy ctor" << std::endl;
    }
    MyObject (MyObject&&) {
        std::cout << "move ctor" << std::endl;
    }
    MyObject& operator= (MyObject const&) {
        std::cout << "copy assign" << std::endl;
        return *this;
    }
    MyObject& operator= (MyObject&&) {
        std::cout << "move assign" << std::endl;
        return *this;
    }
    ~MyObject () {
        std::cout << "dtor" << std::endl;
    }
};
In [5]:
MyObject* p;
{
    MyObject m;
    MyObject o(m);
    p = new MyObject(std::move(m));
    m = o;
    *p = std::move(o);
}

ctor
copy ctor
move ctor
copy assign
move assign
dtor
dtor
In [6]:
delete p

dtor

Operator new[] and delete[]

  • new and delete only allocated/deallocate a single instance
  • We need to dynamically allocate arrays
    • Used to implement std::vector
    • Allocated/deallocated at runtime
    • use new[] (array new)
    • use delete[] (array delete)
In [ ]:
int n = 100;
int* arr = new int[n];
// arr has space for n objects [0..n)
delete[] arr;
// dtor invoked on each object in arr

Vector class

  • What are some of the issues in implementing std::vector
  • insert() and friends...
    • push_back() can just call insert()
  • erase() and friends...
    • pop_back() can just call erase()
  • resize() / reserve() / trim_to_size()
  • iterator invalidation

Classes with Pointer Members

  • Recipe for classes that allocate memory dynamically

"If you implement any of the following five special functions, you must implement all of them"

--- The Rule of 5

  • Destructor ~Class();
  • Copy Constructor Class (Class const&);
  • Copy Assignment Class& operator= (Class const&);
  • Move Constructor Class (Class&&);
  • Move Assignment Class& operator= (Class&&);
In [1]:
class Class {
    // defaults to private visibility
    int m1;
    int* m2;
public:
    Class (int x, int y);            // ctor
    Class (Class const&);            // copy ctor
    Class (Class&&);                 // move ctor
    ~Class();                        // dtor
    Class& operator= (Class const&); // copy assign
    Class& operator= (Class&&);      // move assign
};
In [ ]:
#include <utility> // std::exchange, std::move

Class::Class (int x, int y)
: m1 (x)
, m2 (new int (y)) {
}

Class::Class (Class const& co)
: m1 (co.m1)
, m2 (new int(*(co.m2))) {
}

Class::Class (Class&& co)
: m1 (std::move(co.m1))
, m2 (std::exchange(co.m2, nullptr)) {
}

Class::~Class () {
    delete m2;
}
In [ ]:
Class& Class::operator= (Class const& co) {
    if (this != &co) {
        m1 = co.m1;
        *m2 = *(co.m2);
    }
    return *this;
}

Class& Class::operator= (Class&& co) {
    m1 = std::move(co.m1);
    delete std::exchange(m2, co.m2);
    return *this;
}

std::move and std::exchange

template <typename T>
using RValueRef = std::remove_reference_t<T>&&;

namespace std {

  template<typename T>
  constexpr RValueRef<T> move (T&& t) noexcept {
    return static_cast<RValueRef<T>>(t);
  }

  template <typename T, typename U = T>
  T exchange(T& obj, U&& new_value) {
    T old_value = std::move(obj);
    obj = std::forward<U>(new_value);
    return old_value;
  }
}

this pointer

Every non-static member function has a pointer to the invoking object

  • named this (similar to Java)
  • implicitly defined
  • is of type MyClass * const for non-const member functions
  • is of type MyClass const * const for const member functions
*this

is the invoking object

MyClass& operator=(...)

always returns *this so we can chain

  • a = b = c

Matrix

  • A matrix is a two-dimensional array

  • Easy to allocate statically

    int m[3][5];

  • First subscript is rows, second is columns

  • Question: how can we dynamically allocate an array?
+---+---+---+---+---+
| 8 | 1 | 7 |-2 | 5 |
+---+---+---+---+---+    m[0][3] is -2
| 0 |-3 | 4 | 6 |-2 |
+---+---+---+---+---+    m[1][2] is 4
| 10|-14| 1 | 0 | 9 |
+---+---+---+---+---+
In [ ]: