CS247 Lecture 4

This time: Linked List ADT continued. move ctor/assignment operator. Elision. Encapsulation.

Node n {"a", new Node{"b", new Node{"c", nullptr}}};

Issue: although n is freed, the rest of the Nodes in the list are on the heap, must also be freed.

We will write a dtor, which runs when stack allocated objects go out of scope, and when heap allocated objects are freed.

Node::~Node(){ delete nex; }

Complaint: Efficiency

Node getAlphabet(){
	return Node{"a", new Node{"b", new Node{"z",nullptr}}};
}
Node n{getAlphabet()};

In memory it lookes like the following: (upload pic from lecture)

Here, we’ve copied 2b nodes, then delete the originals immediately. We can observe that getAlphabet() is an rvalue. It’s going to be deleted by the next line. No one else will use that memory. We can steal it.

We’ll write a [move constructor] for rvalues, which will be faster. Takes in an rvalue. Called on temporary values

Node::Node(Node&& other): data{other.data}, next{other.next}{
	other.next = nullptr;
}

other: is a rvalue, but inside the function, other is an lvalue. One more slight optimization:

data{other.data}

other.data has an address, it’s an lvalue. This invokes the copy ctor for the data string. Even though other.data will die soon. We’d prefer to run the string move ctor.

data{std::move(other.data)}

std::move is included in <utility>, it forces an lvalue to be treated as an rvalue. So the move ctor runs. We still have data sharing :

Node n{"a", new Node{"b", new Node{"c", nullptr}}};
Node p{"d", new Node{"e", nullptr}};
p = n; // Runs the copy assignment operator, since both nodes exist (already initialized)

Compiler provided copy assignmnet operator which does shallow copies of pointers. We have data sharing, since p’s first node is changed to a and points to Node n’s b. (include picture) Data sharing again, leaked Node. We’ll implement our own copy assignment operator.

Attempt #1 :

Node& Node::operator=(const Node& other){
	delete next;
	data = other.data;
	next = other.next?new Node{*(other.next)}:nullptr;
	return *this;
}

Need to do some cleanup first when it is a assignment operator. Example of breaking:

Node n{"a", new Node{"b", new Node{"c", nullptr}}};
n = n;

(include picture) We start by deleting the rest of the linked list.

To protect against self-assignment, add the following to the beginning of the assignment operator:

if(this == &other) return *this;

other is an lvalue reference, we check if it’s the same thing in the memory location, then return *this. We’ll rearrange the copy assignment operator slightly: new has the posibility to reject our request for more memory, we’ll then quit the function. Call new first so if it fails, we haven’t deleted anything yet.

Working copy assignment operator:

Node& Node::operator=(const Node& other){
	if(this == &other) return *this;
	Node* tmp = other.next?new Node(*(other.next)):nullptr;
	data = other.data;
	delete next;
	next = tmp;
	return *this;
}

There is some code duplicating between copy ctor and coy assignment operator. Can address this using the copy and swap idiom.

Node& Node::operator=(const Node& other){
	Node tmp{other}; // complete recursive copy of n
	std::swap(data, tmp.data);
	std::swap(next, tmp.next);
	return *this;
	// swap is in <utility> swaps two values
}
 
p = n;

(picture example to include)

Exercise: Check what happens with self-assignment! Finally: Move asisgnment operator, for more efficiency:

Node& Node::operator=(Node&& other){
	std::swap(data, other.data);
	std::swap(next, other.next);
	return *this;
}
n = getAlphabet();

(include picture)

Exercise: write this without swapping.

If you don’t define a move ctor/assignment operator but you do define a copy ctor/assignment operator, compiler will use copies in all scenarios.

Rule of Five / Big Five If you write one of the following, should usually write all:

• Destructor
• Move constructor operator
• Move assignment operator
• Copy constructor operator
• Copy assignment operator

Elision:

Rational makeRational() {return Rational{1, 5}};
{
	Rational r = makeRational();
}

In g++, std = c++14, neither moe nor copy gets called! This is called elision. In certain cases, compiler can skip calling copy/move ctors, instead writing the objects’ values directly into its final location.

Another example:

void doMath(Rational r){
	...
}
doMath(makeRational());

Here, {1, 5} is writeen directly into r. Note: Elision is possible, even if it changes program output!

• Not expected to know all possible cases, just that it’s possible.

Disable with the flag —fno -elide -constructors (slow down program thoug)