C++ Getline Explained

Start Learning

Are you looking to learn more about the getline function in C++? We’ve got you covered. In this article, we walk through a few usage examples for getline and explain how it differs from the commonly used operator.

C++ Getline
Programmer working On Computer In IT Office Typing Data Coding in software and checking code on computer screen


Continue Reading

C++ Linked Lists Explained

Start Learning

A list is an essential data structure used for storing elements of the same type. In C++, it differs from a vector in that its data is not stored in contiguous memory. This has some major implications for basic operations like finding or inserting elements. So if you’d like to learn about these differences while becoming more familiar with some fundamental programming concepts, let‘s dive right in!

Some background on C++ linked lists

In order to understand the features of a linked list in C++, we first have to look at a closely related data structure: the vector. A vector is a collection of elements that are stored in contiguous memory addresses. This means that accessing the data is extremely fast. For instance, computing the length of a vector is as simple as subtracting the first element’s address from the last. However, the adjacency-in-memory constraint also implies that whenever one part of the vector is manipulated in any way, other elements must be moved, too. This can be an unnecessarily costly operation. And that is where the linked list comes in.

C++ Linked Lists


Continue Reading

C++ Queues Explained

Start Learning

Imagine you’re in line at a lemonade stand on a hot summer day, waiting to reach the front so you can enjoy a refreshing drink. Without having to think about it, you know that the first person to join the line will be the first person to leave it, and the last person to join will be the last to receive a drink.  

The same concept exists in programming—in C++, this built-in data structure is called a queue. In this article, we’ll touch on what queues are and how to use them, and we’ll discuss some circumstances in which you might use and avoid queues. 

C++ Queues
Photo of administrator responsible for cyber security of large corporation searching for safety gaps debugging existant operating system to reduce hacker attacks success probability

What is a queue in C++?

A queue is a data structure that is optimized for a specific access pattern: the “first in, first out” (FIFO) pattern that describes lines as we know them in everyday life. 

In addition to a garden-variety queue, C++ also has the concept of a priority queue, which you can think of as a structured or organized queue. The top element (largest, greatest, etc.) is always moved to the front of the queue, the bottom element is moved to the back, and each element in between has a priority in relation to all other elements. 
C++ has built-in queue and priority_queue data structures.

How to use a C++ queue

The basic operations available to you when working with queues include creating a new queue, adding elements to it and retrieving elements. Let’s look at how this works with both a FIFO queue and a priority queue.

FIFO Queues

First, let’s create a queue:

#include <iostream>       // std::cout
#include <queue>          // std::queue
using namespace std;

int main () 
{
  queue<int> my_queue;
}

This creates an empty queue, which we have illustratively named my_queue. Now, how can we add an element to this queue? Since we initialized our queue to contain integers, let’s add one using the push member function. Keep in mind that we need to do this using the same scope in which we declared our queue:

my_queue.push(7);

Since our queue is empty, the integer 7 will be the only element. But say we push another element—where will it stand in the queue? The answer is that adding an element assigns it the last index, as the newest member of the queue.

As far as retrieving elements goes, the front and back functions will return references to those respective elements in the queue. Let’s push another integer into our queue so that the front and back functions will return different integers.

my_queue.push(3);
my_queue.front(); // returns 7
my_queue.back(); // returns 3

It’s important to note that while we have operations that retrieve elements from the front and back, we don’t have a way to get an element from the middle of a queue. If we push another integer—say, 4—to our queue, we have no way of accessing 3, now in the middle of our queue.

Priority Queues

Now that you’ve grasped the foundations of C++ queues, let’s look at the same operations in priority queues. Creating a priority queue (and then populating it with a for-loop) looks like this: 

#include <iostream>       // std::cout
#include <queue>          // std::queue
using namespace std;

int main () 
{
  priority_queue<int> my_priority_queue;

  for (int i = 5; i > 0; --i)
    my_priority_queue.push(i); // adds 5, 4, 3, 2, 1
}

Priority queues have most of the same operations as queues have, with a few additions like  top(). The top member function replaces the front member function used for FIFO queues. Note that there is no priority-queue equivalent to the back function. 

Say we add this line right after our for-loop:

cout << my_priority_queue.top() << endl;

What do you think this will print out? If you said 5, you are correct.  What if we changed the order in which elements were pushed into the priority queue, so that the smallest elements are added first?

#include <iostream>       // std::cout
#include <queue>          // std::queue

int main () 
{
  priority_queue<int> my_priority_queue;

  for (int i = 0; i < 5; ++i)
    my_priority_queue.push(i + 1); // adds 1, 2, 3, 4, 5

  cout << my_priority_queue.top() << endl;
}

If this were a FIFO queue, we would expect 1 to be the first item, since it was pushed first. However, the code prints out 5 when we call top(). As expected, our priority queue has ordered the elements for us.

To check if this is really how priority queues work, let’s now call pop(), a function (also available in FIFO queues) that removes the topmost element and returns its value. With a priority queue, we should see that the numbers returned by pop are ordered, so let’s try it and see: 

priority_queue.pop(); // returns 5
priority_queue.pop(); // returns 4
priority_queue.pop(); // returns 3
priority_queue.pop(); // returns 2
priority_queue.pop(); // returns 1

And so we see that this priority queue really is ordered. 
Now that we have an understanding of both types of queues, let’s move on to some use cases for these data structures.

When to use queues in C++

Queues are great at keeping track of tasks to process and are the right choice if you need to track the order in which items need to be processed. If, for example, a movie studio has a number of scenes to render on its server farm, a queue will effectively keep track of which task came in first and handles it first.
Perhaps you don’t need to keep track of the order elements are inserted, but you do need to order tasks according to a certain metric. In this case queues can still be a great fit—priority queues, that is. Back in our movie studio example, some projects will have a higher priority, and a priority queue will help those get taken care of first.

When to avoid using queues in C++

As previously noted, we can’t reference queue elements outside of the first and last ones, so if you’re looking for access to, say, the sixth element of a 12-element list, a queue is not the right data structure for you. You might find an array better suited to this purpose.

Underlying containers in C++

So far we have only touched on the first argument used in FIFO queues and priority queues. As you know, this first argument specifies the type of elements in the queue, but you can also specify an optional second argument. 
A priority queue is a container adapter, which changes the functionality of a given container type by imposing limitations on it. The optional second argument specifies the underlying container that actually stores the elements.  
Let’s look at our previous example and add in a second argument:

priority_queue<int, vector<int> > my_priority_queue

Here, a vector is the underlying container—that is, the priority queue uses a vector container to store its values. It is worthwhile to note that the elements in the underlying container are accessed by the member functions of the container adapter (the priority queue), and not by those of the container (the vector) itself.
Remember, the second argument is optional. If none is provided, a FIFO queue defaults to a deque as its container adapter, and a priority queue defaults to a vector. Other underlying container options include a list (for a FIFO queue) and a deque (for a priority queue).

Further reading and resources

This is a comprehensive overview of member functions available to FIFO queues and priority queues. Here is a great overview of FIFO queues and another for priority queues.

Conclusion

In this article, we covered what C++ FIFO queues and priority queues are, and we walked through the code for instantiating, adding to and retrieving from these data structures. We went over some ideal circumstances for using queues and talked about when other data structures might be more appropriate.

Start Learning

C++ Maps Explained

Start Learning

Looking to learn more about maps in C++ and how to use them? Then this article is for you. We cover the details on how exactly to use maps, present some use cases for them and explain when to avoid them entirely. Let’s dive in.

What is a map in C++?

A C++ map is a way to store a key-value pair. A map can be declared as follows:

#include <iostream>
#include <map>

map<int, int> sample_map;

Each map entry consists of a pair: a key and a value. In this case, both the key and the value are defined as integers, but you can use other types as well: strings, vectors, types you define yourself, and more.



Continue Reading

Microsoft Visual C++ Review

Start Learning

Looking to learn what Microsoft Visual C++ is and why organizations use it? Then this article is for you. We’ll explain the difference between C++ and Visual C++, cover which versions of Visual C++ are currently supported (and which one you should pick for a new project) and talk about what the Visual C++ Redistributable actually is. Scroll to the bottom for a list of resources that will help you learn even more about Visual C++ development.



Continue Reading

C++ Compilers Explained

Start Learning

As a C++ developer, you’ve mastered a high-performance programming language used to create applications in the world’s most exciting fields—from data mining and big data to self-driving cars and robotics to gaming and video. By this point you may have tackled topics like multi-threading and parallel programming. But have you ever taken a look behind the scenes to find out what happens during compilation?
The topic is worth learning about, and this article contains some of the most important details that you’ll want to know. The inner workings of the compiler can provide deep insights and improve your programming skills by helping you avoid common errors.

C++ Compilers Explained


Continue Reading

C++ Strings Explained

Start Learning

As a programmer, you’re likely familiar with the concept of a string, but did you know there are three ways to build a string in C++? Do you understand their behavior in particular? In this article, we’ll go over what a C++ string is, how it differs from strings in C, and show some examples of how to use strings in everyday programming. We’ll also touch briefly on methods that can be invoked when working with C++ strings.



Continue Reading