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:

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

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

&a == &refA

true

&refA == ptrA

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

int* ptr = new int;
*ptr = 4;
delete ptr;

Pointer Manipulations

int m = 10;
int* intPtr = &m;

// *intPtr and m are aliases now
*intPtr = 3;
m

3

#include <string>
#include <iostream>

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

0

sPtr = nullptr;
std::cout << sPtr;

0

sPtr = new std::string("jeb!"); // calls constructor
std::cout << sPtr;

0x5556418c0870

sPtr->size()

4

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

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;
    }
};

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

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)

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&&);

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
};

#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;
}

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 |
  +---+---+---+---+---+