CSE333(15-16): C++ STL and Smart Pointers

language

Lecture 15 - C++ Standard Template Library

four major pieces

  • The entire C standard library
  • C++’s input/output stream library
    • std::cin, std::cout, stringstreams, fstreams, etc.
  • C++’s standard template library (STL) +Containers, iterators, algorithms (sort, find, etc.), numerics
  • C++’s miscellaneous library
    • Strings, exceptions, memory allocation, localization

STL Containers

A container is an object that stores (in memory) a collection of other objects (elements).

Several different classes of container:

  • Sequence containers (vector, deque, list, …)
  • Associative containers (set, map, multiset, multimap, bitset, …)
  • Differ in algorithmic cost and supported operations

STL containers store by value, not by reference:

  • When you insert an object, the container makes a copy
  • If the container needs to rearrange objects, it makes copies
    • e.g. if you sort a vector, it will make many, many copies
    • e.g. if you insert into a map, that may trigger several copies
  • What if you don’t want this (disabled copy constructor or copying is expensive)?
    • You can insert a wrapper object with a pointer to the object (use smart pointer)

STL vector

Vector, A generic, dynamically resizable array.

  • Elements are stored in contiguous memory locations
    • Elements can be accessed using pointer arithmetic if you’d like
    • Random access is O(1) time
  • Adding/removing from the end is cheap (amortized constant time)
  • Inserting/deleting from the middle or start is expensive (linear time)

Each container class has an associated iterator class (e.g. vector::iterator) used to iterate through elements of the container.

Lecture 16 - C++ Smart Pointers

Intro and toy_ptr

We noticed that STL was doing an enormous amount of copying

  • solution: store pointers in containers instead of objects

But who’s responsible for deleting and when???

A smart pointer is an object that stores a pointer to a heap-allocated object

  • A smart pointer looks and behaves like a regular C++ pointer
    • By overloading * , ->, [], etc.
  • These can help you manage memory
    • The smart pointer will delete the pointed-to object at the right time including invoking the object’s destructor, When that is depends on what kind of smart pointer you use
    • With correct use of smart pointers, you no longer have to remember when to delete new’d memory!

A Toy Smart Pointer

We can implement a simple one with:

  • A constructor that accepts a pointer
  • A destructor that frees the pointer
  • Overloaded * and -> operators that access the pointer

ToyPtr.cc

#ifndef _TOYPTR_H_
#define _TOYPTR_H_
template <typename T> class ToyPtr {
	public:
		ToyPtr(T *ptr) : ptr_(ptr) { } // constructor
		~ToyPtr() { // destructor
			if (ptr_ != nullptr) {
				delete ptr_;
				ptr_ = nullptr;
			}
		}
		T &operator*() { return *ptr_; } // * operator
		T *operator->() { return ptr_; } // -> operator
	private:
		T *ptr_; // the pointer itself
};
#endif // _TOYPTR_H_

usetoy.cc:

#include <iostream>
#include "ToyPtr.h"
// simply struct to use
typedef struct { int x = 1, y = 2; } Point;
std::ostream &operator<<(std::ostream &out, const Point &rhs) {
	return out << "(" << rhs.x << "," << rhs.y << ")";
}
int main(int argc, char **argv) {
	// Create a dumb pointer
	Point *leak = new Point;

	// Create a "smart" pointer (OK, it's still pretty dumb)
	ToyPtr<Point> notleak(new Point);
	std::cout << " *leak: " << *leak << std::endl;
	std::cout << " leak->x: " << leak->x << std::endl;
	std::cout << " *notleak: " << *notleak << std::endl;
	std::cout << "notleak->x: " << notleak->x << std::endl;
	return 0;
}

std::unique_ptr

A unique_ptr takes ownership of a pointer:

  • A template: template parameter is the type that the “owned” pointer references (i.e., the T in pointer type T*)
  • Part of C++’s standard library (C++11)
  • Its destructor invokes delete on the owned pointer
    • Invoked when unique_ptr object is delete’d or falls out of scope

unique1.cc:

#include <iostream> // for std::cout, std::endl
#include <memory> // for std::unique_ptr
#include <cstdlib> // for EXIT_SUCCESS
void Leaky() {
	int *x = new int(5); // heap-allocated
	(*x)++;
	std::cout << *x << std::endl;
} // never use delete, therefore leak

void NotLeaky() {
	std::unique_ptr<int> x(new int(5)); // wrapped, heap-allocated
	(*x)++;
	std::cout << *x << std::endl;
} // never used delete, but no leak
int main(int argc, char **argv) {
	Leaky();
	NotLeaky();
	return EXIT_SUCCESS;
}

If you have many potential exits out of a function, it’s easy to forget to call delete on all of them

  • unique_ptr will delete its pointer when it falls out of scope
  • Thus, a unique_ptr also helps with exception safety

unique2.cc:

#include <memory> // for std::unique_ptr
#include <cstdlib> // for EXIT_SUCCESS
using namespace std;
typedef struct { int a, b; } IntPair;

int main(int argc, char **argv) {
	unique_ptr<int> x(new int(5));
	
	int *ptr = x.get(); // Return a pointer to pointed-to object
	int val = *x; // Return the value of pointed-to object
	
	// Access a field or function of a pointed-to object
	unique_ptr<IntPair> ip(new IntPair);
	ip->a = 100;
	
	// Deallocate current pointed-to object and store new pointer
	x.reset(new int(1));
	ptr = x.release(); // Release responsibility for freeing
	
	delete ptr;
	return EXIT_SUCCESS;
}

Transferring Ownership

Use reset() and release() to transfer ownership:

  • release returns the pointer, sets wrapped pointer to nullptr
  • reset delete’s the current pointer and stores a new one
int main(int argc, char **argv) {
	unique_ptr<int> x(new int(5));
	cout << "x: " << x.get() << endl;
	unique_ptr<int> y(x.release()); // x abdicates ownership to y
	cout << "x: " << x.get() << endl;
	cout << "y: " << y.get() << endl;
	unique_ptr<int> z(new int(10));
	// y transfers ownership of its pointer to z.
	// z's old pointer was delete'd in the process.
	z.reset(y.release());
	return EXIT_SUCCESS;
}

unique_ptrs Cannot Be Copied

  • std::unique_ptr has disabled its copy constructor and assignment operator
  • You cannot copy a unique_ptr, helping maintain “uniqueness” or “ownership”
#include <memory> // for std::unique_ptr
#include <cstdlib> // for EXIT_SUCCESS
int main(int argc, char **argv) {
	std::unique_ptr<int> x(new int(5)); // OK
	std::unique_ptr<int> y(x); // fail – no copy ctor
	std::unique_ptr<int> z; // OK – z is nullptr
	z = x; // fail – no assignment op
	return EXIT_SUCCESS;
}

Copy Semantics

Assigning values typically means making a copy

  • Sometimes this is what you want
    • e.g. assigning a string to another makes a copy of its value
  • Sometimes this is wasteful
    • e.g. assigning a returned string goes through a temporary copy
std::string ReturnFoo(void) {
	std::string x("foo");
	return x; // this return might copy
}
int main(int argc, char **argv) {
	std::string a("hello");
	std::string b(a); // copy a into b
	b = ReturnFoo(); // copy return value into b
	return EXIT_SUCCESS;
}

Move Semantics

Move semantics move values from one object to another without copying (“stealing”)

  • Useful for optimizing away temporary copies
  • A complex topic that uses things called “rvalue references”
std::string ReturnFoo(void) {
	std::string x("foo");
	// this return might copy
	return x;
}

int main(int argc, char **argv) {
	std::string a("hello");
	
	// moves a to b
	std::string b = std::move(a);
	std::cout << "a: " << a << std::endl;
	std::cout << "b: " << b << std::endl;
	
	// moves the returned value into b
	b = std::move(ReturnFoo());
	std::cout << "b: " << b << std::endl;
	return EXIT_SUCCESS;
}

unique_ptr and STL Containers

unique_ptrs can be stored in STL containers by using move semantics.

Transferring Ownership via Move:

  • Can move ownership from one unique_ptr to another
  • Behavior is equivalent to the ‘release-and-reset’ combination
  • unique_ptr<int> y = std::move(x);, x release, y reset?
  • Smart pointer can’t be copied…

unique_ptr and Vector

int main(int argc, char **argv) {
	std::vector<std::unique_ptr<int> > vec;  //a vector array of smart pointers
	vec.push_back(std::unique_ptr<int>(new int(9)));  // push back a smart pointer
	vec.push_back(std::unique_ptr<int>(new int(5)));
	vec.push_back(std::unique_ptr<int>(new int(7)));

	// z gets a copy of int value pointed to by vec[1]
	int z = *vec[1];
	std::cout << "z is: " << z << std::endl;
	// won’t compile! Cannot copy unique_ptr
	std::unique_ptr<int> copied = vec[1]; // hmmm... failed
	// Works! vec[1] after the statement below will wrap a nullptr
	std::unique_ptr<int> moved = std::move(vec[1]);
	std::cout << "*moved: " << *moved << std::endl;
	std::cout << "vec[1].get(): " << vec[1].get() << std::endl;
	return EXIT_SUCCESS;
}

unique_ptr and ‘<’

A unique_ptr implements some comparison operators, including operator <

  • However, it doesn’t invoke operator < on the pointed-to objects.
  • Instead, it just promises a stable, strict ordering (probably based on the pointer address, not the pointed-to-value)
  • So to use sort() on vectors, you want to provide it with a comparison function
using namespace std;
bool sortfunction(const unique_ptr<int> &x,
				  const unique_ptr<int> &y) { return *x < *y; }
void printfunction(unique_ptr<int> &x) { cout << *x << endl; }

int main(int argc, char **argv) {
	vector<unique_ptr<int> > vec;
	vec.push_back(unique_ptr<int>(new int(9)));
	vec.push_back(unique_ptr<int>(new int(5)));
	vec.push_back(unique_ptr<int>(new int(7)));
	
	// buggy: sorts based on the values of the ptrs
	sort(vec.begin(), vec.end());
	cout << "Sorted:" << endl;
	for_each(vec.begin(), vec.end(), &printfunction);
	
	// better: sorts based on the pointed-to values
	sort(vec.begin(), vec.end(), &sortfunction);
	cout << "Sorted:" << endl;
	for_each(vec.begin(), vec.end(), &printfunction);
	return EXIT_SUCCESS;
}

unique_ptr, “<”, and maps

  • Similarly, you can use unique_ptrs as keys in a map
  • A map internally stores keys in a sorted order, iterating through the map iterates through the keys in order
  • By default, “<” is used to enforce ordering
  • You must specify a comparator when constructing the map to get a meaningful sorted order using “<” of unique_ptrs

Example:

struct MapComp {
	bool operator()(const unique_ptr<int> &lhs,
		const unique_ptr<int> &rhs) const { return *lhs < *rhs; }
};

int main(int argc, char **argv) {
	map<unique_ptr<int>, int, MapComp> a_map; // Create the map
	
	unique_ptr<int> a(new int(5)); // unique_ptr for key
	unique_ptr<int> b(new int(9));
	unique_ptr<int> c(new int(7));
	
	a_map[std::move(a)] = 25; // move semantics to get ownership
	a_map[std::move(b)] = 81; // of unique_ptrs into the map.
	a_map[std::move(c)] = 49; // a, b, c hold NULL after this.
	
	map<unique_ptr<int>,int>::iterator it;
	for (it = a_map.begin(); it != a_map.end(); it++) {
		std::cout << "key: " << *(it->first);
		std::cout << " value: " << it->second << std::endl;
	}
	return EXIT_SUCCESS;
}

unique_ptr and Arrays

unique_ptr can store arrays as well, will call delete[] on destruction.

#include <memory> // for std::unique_ptr
#include <cstdlib> // for EXIT_SUCCESS

using namespace std;

int main(int argc, char **argv) {
	unique_ptr<int[]> x(new int[5]);
	x[0] = 1;
	x[2] = 2;
	return EXIT_SUCCESS;
}

Reference counting

Idea: associate a reference count with each object

  • Reference count holds number of references (pointers) to the object
  • Adjusted whenever pointers are changed:
    • Increase by 1 each time we have a new pointer to an object
    • Decrease by 1 each time a pointer to an object is removed
  • When reference counter decreased to 0, no more pointers to the object, so delete it (automatically)
  • Used by C++ shared_ptr, not used in general for C++ memory management

Noted that:

  • Bunch of extra overhead on every pointer operation
  • Cannot reclaim linked objects with circular references
  • Not general enough for automatic memory management (need automatic garbage collection as in Java), but when it’s appropriate it’s a clean solution for resource management and cleanup
    • directory links to files in Linux – delete file when link count = 0!

std::shared_ptr and std::weak_ptr

std::shared_ptr

shared_ptr is similar to unique_ptr but we allow shared objects to have multiple owners:

  • The copy/assign operators are not disabled and increment or decrement reference counts as needed
    • After a copy/assign, the two shared_ptr objects point to the same pointed-to object and the (shared) reference count is 2
  • When a shared_ptr is destroyed, the reference count is decremented
    • When the reference count hits 0, we delete the pointed-to object!
  • Allows us to create complex linked structures (double-linked lists, graphs, etc.) at the cost of maintaining reference counts
  • A loop(cycle) of linked list may cause memory leak!

Memory Leak Example:

Node * q = new Node();
Node * r = new Node();
q->next = r;
r->next = q;
r = nullptr;
q = nullptr;

Shared Pointer Example:

#include <cstdlib> // for EXIT_SUCCESS
#include <iostream> // for std::cout, std::endl
#include <memory> // for std::shared_ptr
int main(int argc, char **argv) {
	std::shared_ptr<int> x(new int(10)); // ref count: 1
	// temporary inner scope with local y (!)
	{
	std::shared_ptr<int> y = x; // ref count: 2
	std::cout << *y << std::endl;
	} // exit scope, y deleted
	std::cout << *x << std::endl; // ref count: 1
	return EXIT_SUCCESS;
} // ref count: 0

std::shared_ptr and STL Containers

Even simpler than unique_ptrs, Safe to store shared_ptrs in containers, since copy & assign maintain a shared reference count.

vector<std::shared_ptr<int> > vec;

vec.push_back(std::shared_ptr<int>(new int(9)));
vec.push_back(std::shared_ptr<int>(new int(5)));
vec.push_back(std::shared_ptr<int>(new int(7)));

int &z = *vec[1];
std::cout << "z is: " << z << std::endl;

std::shared_ptr<int> copied = vec[1]; // works!
std::cout << "*copied: " << *copied << std::endl;

std::shared_ptr<int> moved = std::move(vec[1]); // works!
std::cout << "*moved: " << *moved << std::endl;
std::cout << "vec[1].get(): " << vec[1].get() << std::endl;

std::weak_ptr

To solve the Cycle of shared_ptrs problem. weak_ptr is similar to a shared_ptr but doesn’t affect the reference count

  • Can only “point to” an object that is managed by a shared_ptr
  • Not really a pointer, we can’t actually dereference using * unless you “get” its associated shared_ptr
  • Because it doesn’t influence the reference count, weak_ptrs can become “dangling”
    • Object referenced may have been delete’d
    • But you can check to see if the object still exists

Breaking the Cycle with weak_ptr:

#include <cstdlib>
#include <memory>

using std::shared_ptr;
using std::weak_ptr;

struct A {
	shared_ptr<A> next;
	weak_ptr<A> prev;
};

int main(int argc, char **argv) {
	shared_ptr<A> head(new A());
	head->next = shared_ptr<A>(new A());
	head->next->prev = head;
	return EXIT_SUCCESS;
}

Now what happens when we delete head? Ref counts go to 0 and nodes deleted!

#include <cstdlib> // for EXIT_SUCCESS
#include <iostream> // for std::cout, std::endl
#include <memory> // for std::shared_ptr, std::weak_ptr
int main(int argc, char **argv) {
	std::weak_ptr<int> w;
	{ // temporary inner scope with local x
		std::shared_ptr<int> x;
		{ // temporary inner-inner scope with local y
			std::shared_ptr<int> y(new int(10));
			w = y; // weak ref; ref count for “10” node is same
			x = w.lock(); // get "promoted" shared_ptr, ref cnt = 2
			std::cout << *x << std::endl;
		} // y deleted; ref count now 1
		std::cout << *x << std::endl;
	} // x deleted; ref count now 0; mem freed
	std::shared_ptr<int> a = w.lock(); // nullptr
	std::cout << a << std::endl; // output is 0 (null)
	return EXIT_SUCCESS;
}

Summary

  1. A unique_ptr takes ownership of a pointer
  • Cannot be copied, but can be moved
  • get() returns a copy of the pointer, but is dangerous to use; better to use release() instead
  • reset() deletes old pointer value and stores a new one
  1. A shared_ptr allows shared objects to have multiple owners by doing reference counting
  • deletes an object once its reference count reaches zero
  1. A weak_ptr works with a shared object but doesn’t affect the reference count
  • Can’t actually be dereferenced, but can check if the object still exists and can get a shared_ptr from the weak_ptr if it does

Hope that I can be as smart as the smart pointer…

References