83: Let's Learn About "Box" & "Rc" in Rust

[00:00:00]How's it going everyone? Today, we're going to learn about smart pointers in Rust. There are a few of them out there and they each solve a different problem.

[00:00:10]We're going to start with the simplest one, box, and then work our way up to the more complex stuff. Now, the most common reason you'd reach for box is to use trait objects. A trait object is basically a value where the concrete type gets erased at runtime. What you're left with is just the trait methods.

[00:00:33]Boxes are usually written as box dynamic trait and that lets you store different types in the same collection. So, next we're going to create a quick example.

[00:00:43]And here we're going to define a shape trait and implement it for a couple of types and then store all of them in the same vector. Now, this shape trait will contain one method, which gives us back the area as an F64. Below, we will create a struct called circle and this holds the radius of the circle. Next, we will implement the shape for the circle.

[00:01:07]Here, we need to compute the area of the circle and to get the area, we just need to use pi times the radius squared. And we're going to do the same thing for a square, which will contain a side of type F64.

[00:01:25]Then once again, we will implement the shape for the square and this requires us to implement the area method. And to get the area of a square, we just need to multiply the side by itself. Now, we can move on to the main function. Here, we're going to create some shapes, which will be of type vector box and pass in the dynamic shape and that will equal a vector, which contains the following shapes. One which is a circle and one which is a square. And we will be using the box constructor for both of these.

[00:02:01]The main idea here is that a vector which contains a box of dynamic shapes can hold any type that implements shape, even if those types are different sizes.

[00:02:13]This works because box contains a pointer to that object, and pointer sizes are known at compile time. So, even though a circle and a square take up different amounts of memory, this [snorts] box wrapping ensures that each one is always the same fixed size. So, once again, here we have a vector of boxed trait objects. Then inside we have a circle which is boxed, so it fits in the vector. And we did the same thing for the square. Now, if we wanted to, we could even iterate over each boxed shape.

[00:02:49]And inside here we could print the area.

[00:02:52]Now, when we run this, what we should end up with is 12.5 and 9 based on the information we provided here.

[00:03:00]But now let's look at another classic use case for box, which is recursive types. A recursive type is one that contains another value of the same type.

[00:03:11]Think of a tree where each node has more nodes inside it. The thing is, Rust needs to know the size of every type at compile time. So, if you try to make a recursive type naively, the size would be infinite.

[00:03:27]Box solves this because it gives us a fixed-size pointer. Now, below the binary tree we're going to create a leaf, and this is just a helper method which we will use to build a leaf node.

[00:03:40]So, inside we will return a node with no children. Now, we can build a small binary tree. So, here we will let our tree be of type binary tree, and that will equal a binary tree node. And the root node will have a value of one. Then we will create the left subtree. And finally, we will insert the right subtree. And let's format all of this so that you can see the data more clearly.

[00:04:09]At the bottom, we will print the tree.

[00:04:12]And now when we run this, we're going to get our tree back.

[00:04:16]So, as you can see, boxes are quite useful.

[00:04:20]So, in the last file, we used box to build a tree. Each node has one parent, but sometimes you need a graph instead.

[00:04:30]A node can have multiple parents, and the graph can even have loops.

[00:04:35]Now, box can't handle that because it only lets you have a single owner. If two nodes both pointed to the same child with box, the second assignment would move the child out of the first node, which is obviously not what we want. So, that's where RC comes in. It stands for reference counted. Every time you clone it, the count goes up. Every time it gets dropped, the count goes down. When the count hits zero, the data gets freed. Basically, it gives us shared ownership, and the only run time cost is the counter itself. So, for this example, we're going to create a node, which will be the node in our graph. And this will contain the value stored in the node. This node will also contain some neighbors, which will be a vector of type RC, which wraps a node. Inside main, we're going to build a small graph. So, let's do that by creating the shared node first, which is D. And D has no neighbors. And honestly, to make this easier to visualize, I'm going to leave this graph up here. So, right now we created D. Then below, we're going to create both B and C. Both B and C point to D, as you can see inside the vector, which we included inside our neighbors.

[00:05:57]So right now, B and C are pointing to D.

[00:06:01]Our C clone bumps the count each time.

[00:06:04]So D is shared, but it's not copied.

[00:06:07]Then we have one more node, which is node A, and A points to both B and C. As you can see inside the neighbors, we have an RC clone of B and an RC clone of C. And at the bottom, we will print these owners and the graph starting from A. What you should note here is that D has three owners, which are the original D binding, B's neighbors list, and C's neighbors list. And to prove that, we will run this so that you can see inside the console that D has three owners. And below, we get the graph printed.

[00:06:45]Now, this graph is what we call a DAG.

[00:06:48]That means no loops, but a graph can also have loops, where a node points back to one of its ancestors.

[00:06:55]When that happens, you get a reference cycle, and we'll learn how to handle that shortly. And one more thing, RC only works on a single thread, and you can't mutate data through it. For those cases, we've got something called RefCell and Arc, which we'll see in the next few videos.