To watch the youtube video explaining this topic, click here.
Prerequisite: You Should Know About Pointers And References
Make sure you check out the blogpost on pointers and references, because this topic will be a continuation of that.
In this blog post, we'll be going over what R-Values (and L-Values) are, what R-Value References are, and what Move Semantics are. We'll also look at std::move. If you're a good, modern C++ programmer, then you should know this. Note: It's possible to get more technical (and accurate) about the concepts I'll mention, but we'll keep it simple to start out with. What Are L-Values and R-Values
L-Values and R-Values are category types that describe variables, function returns, and objects in C++.
An L-value is stored in memory and will exist on the next line of code. An R-Value is temporary and won't exist (in memory) on the next line of code. Let's go through some code examples.
A simple rule of thumb (that isn't entirely accurate) is "if it can be on the left side of an equal sign, it's an L-Value. Otherwise, it's an R-Value."
R-Value References
Okay, so remember references from the last blog post? The & sign that means a variable refers to something that already exists in memory (instead of making a copy)? Well, the & sign only works with L-Value references. If you use the && sign, then you mean you want an R-Value reference, specifically.
Let's look at some code to see how this works.
Make sure you compile with C++ version 11 or higher.
The copy way works like this:
The R-Value reference way works like this:
NOTE: Line 13 won't actually do a real "copy" because of Return Value Optimization (which basically means the compiler will just put the value into a directly, because the compiler is smart, and the thing that function srcString() returns is very clear to the compiler (with no chance of something else being returned). That line is mostly meant as a simple example.
This type of reference is powerful: we no longer have to spend time and space with copies, we can just keep the same variables (or objects) in memory that would have been removed.
std::move
std::move is a standard library function that takes an L-Value or R-Value, and casts it to an R-Value.
In the following code, move will convert the L-Value to an R-Value, which means that the R-Value will go into the overloaded function meant for R-Values.
So why use std::move? Use it when you want to convert an L-Value to an R-Value (presumably to call an overloaded function). The primary use case is when you don't care about what happens to the value of the variable/object after you use it, as seen in move semantics.
Move Semantics
Move Semantics is a simple concept, but you need to understand and use the stuff from the previous sections to really make use of it: Copying is expensive. If we don't care about what happens to the value of a variable/object after using it, then use R-Value References.
The way you actually use move semantics is through a special move constructor/assignment operator, that will be called instead of a copy constructor/assignment operator. The difference will be that the move constructor/assignment operator will have a && sign.
(This is also what makes the Rule of 3 into the Rule of 5.)
It's also possible to have special move functions in a class implemented depending on certain situations.
One very easy example to see who move semantics is good is with a swap function. With a normal "copy" version of swap, there's an extra copy being used.
What's really going on is something like this:
You see that an extra T (which could be a variable, an object, a container, etc.) named tmp must be generated in RAM for the swap to occur. If we're dealing with a large container like a vector, this is bad. Move semantics is better.
The following code will be more efficient (assuming that class T has a move constructor defined).
The following code is explained in the following picture:
The above code generally changes depending on what T's move constructor will do, but in a simple case, we can see that tmp temporarily points to the exact place in memory for item a, let's a point to b's item, and then let's b point to a's item.
This is much more efficient, as we don't need to allocate memory for an extra temporary variable/container/object. Conclusion
In this blog post, we covered the topic of R-Values, R-Value Reference, std::move, and the concept of Move Semantics in C++. However, it's a bit hard to really grasp the concept without actually writing code and thinking about how to define a move constructor and a move assignment operator.
In a future blog post, we're going to implement the Rule of 5 by making our own Vector class, and it'll teach us how to actually make and code with Move Semantics in mind.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Introduction - Memory Management is kind of a Big Deal
Controlled memory management is one of the most important features that C++ (and C) have that other other famous programming languages (like Java, C#, Python) don't have. Although the other languages often give you what you need to work with data, C++ allows for very fine-tuned control of data because of the use of pointers.
We'll define what pointers and references are, and go over all of the possible code examples you'd use them in. (It's especially important to know for function parameters, since it saves a LOT of time if you pass by pointer or reference.)
Note: This topic is a bit difficult for beginner programmers, and if you learn Java first, you'll never really even learn about pointers since the language doesn't use them (although Java does use references) Still, learning about it is worthwhile.
What Are Pointers and References?
To start out with, remember that in programming, our data (variables, objects, everything) lives in memory (RAM, specifically), and so each variable in our program has a specific address corresponding to it's specific location in memory.
A pointer is a C++ variable that stores the address of some other variable.
Note that pointer syntax is to declare a variable with an asterisk * next to it, accessing the address of a variable with with an ampersand &, and dereferencing a pointer (accessing whatever is inside the address of a pointer) is also with an asterisk *.
Think of a pointer like knowing a specific index in an array: if you know the direct index, you can just look directly to find the variable you want.
A reference is when two variables refer to the same data in memory. You'll know because references use the & sign.
In C++, references are very helpful in function calls, either to update an external variable value inside the function, or to make sure you don't need to copy a large data structure like a vector unnecessarily.
(Note: We're using lvalue references specifically. rvalue references are an advanced topic that we'll talk about in another tutorial. (If that doesn't make sense, don't worry.)) Pass By Copy To Function
Passing a copy of a variable does not change the original variable. When the function PassByCopy is called, a new variable named srcmake2 is created in memory, and the value of srcmake2 is set to whatever was in srcmake1's value was at the time.
Output: 10 5
Pass By Reference To Function
Passing a variable by reference means that the function's variable (srcmake2) is actually the same data in memory as the original. That means any changes to the referenced variable will affect the original (and any other function calls using that reference).
Output: 10 10
Note the only real difference is the & sign next to the function parameter, srcmake2, where we declare that we're passing the variable by reference. Pass By Pointer To Function
Passing a pointer to a function is really dumb, and you should only really do it if you're working with linked lists or trees.
Notice the three changes: 1) When we call the function, we need to pass the address of the variable, instead of the variable itself. 2) In the functions parameters, we have to use a * to indicate the variable is a pointer. 3) Whenever we actually want to use the variable in the function, we have to reference it.
Output: 10 10
Pass by reference if you can. Passing by pointers (for the sake of updating the variables outside of function scope) is annoying. Pass A Pointer By Reference
Sometimes you need to update a pointer using a function, and so you can pass a pointer by reference. It works the same way as passing a variable by reference: updating the pointer inside of the function will update the pointer in memory (so it's a global change).
Output: 5 10 10
Pass A Pointer By Pointer
A really convoluted way to change the value of a pointer after using a function is to pass a pointer to the pointer, and then dereferencing the pointer to the pointer to change the actual pointer value. Sound confusing? That's because it's dumb. Pass a pointer by reference, like in the last section, if you need too. Still, if you see someone use a ** in the function parameter and don't know what it means, then check this code out.
Output: 5 10
Bonus: Pass A String As Const Char*
Sometimes you'll see people pass a string as "const char*". It's a little weird, but it's just a pointer to a string. Here's some code explaining how it works.
Output: Size is: 7
Word is: srcmake String version: srcmake s r c m a k e Conclusion
This is a lot of information to take in, but understanding the fundamentals of memory, pointers, and references will help you write more efficient code (and understand what other people's code). It might seem like this code isn't necessary, but even using fundamental data structures likes trees and linked lists require using pointers, so you need to know them.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Intro - Binary Trees and Doubly Linked Lists
A popular interview question is converting a Binary Tree to a Doubly Linked List.
A Binary Tree (BT) is a hierachical graph data structure. Here's a blog post on Trees if you've never seen one before. (Note: We don't care if it's a Binary Search Tree, it just needs to be a binary tree.) A Doubly Linked List is a data structure where nodes that hold information are sequentially chained: each node holds a pointer to the next node in the chain. Here's a blog post on Linked Lists if you're new to them. BST To Doubly Linked List: Our Algorithm
Our algorithm to convert a Binary Tree to a Double Linked List is pretty simple. We'll do an In-Order Traversal of the tree (which ends up visiting the nodes in the order: 25 12 30 100 (which is the order we want our DLL to be), and we'll keep track of the current node that we're looking at, and the previous node that we've visited.
At each step, we'll make the currentNode's left pointer point to the previousNode, and we'll make the previousNode's right pointer point to the currentNode. Simple, right? (We'll also cover one specific case where our first node becomes the "prevNode", and we have a head pointer for our linked list point to that node.) See the diagram below to see how this works. The Code (In C++)
Our code will implement the algorithm described above as one In-Order Traversal recursive function. I've also borrowed some code from previous blog posts to create/add nodes to a binary tree, and to print a linked list, so view those blog posts if you want too.
The time complexity is O(N), as we visit each node exactly once, and the space complexity is O(1), since we use no extra space (since we don't create new nodes, we just update the pointers).
Conclusion
This is a popular interview question, and tests your knowledge of two fundamental data structured (binary trees and linked lists), as well as your recursive and pointer (and reference) skill, so make sure you can write this code yourself.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake |
AuthorHi, I'm srcmake. I play video games and develop software. Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.
|