Tag Archives: C++

C++

How to use the C++ STL Priority Queue

This article was originally posted at Gigi’s Computer Corner on 19th January 2013.

Overview

A priority queue is a queue data structure that has the particular property of being sorted by priority. You can decide what priority to give items depending on the data type – more on this in a minute.

The C++ Standard Template Library (STL) includes a convenient std::priority_queue class template in the queue header file.

A simple priority queue of integers

The following code sample illustrates how to implement a priority queue of integers. The integer value is used by default as a priority. The queue is sorted automatically as new entries are added.

#include <iostream>
#include <queue>

int main(int argc, char ** argv)
{
	std::priority_queue<int> queue;

	queue.push(100);
	queue.push(300);
	queue.push(50);
	queue.push(150);

	while (!queue.empty())
	{
		std::cout << queue.top() << std::endl;
		queue.pop();
	}

	system("pause");

	return 0;
}

The output of the above program is as follows:

300
150
100
50
Press any key to continue . . .

A priority queue with a custom class

In practical situations, it is often not very useful to simply maintain a priority queue of just integers. We often have some particular class, and we want to give each instance a priority (computed based on some internal state).

Let’s say we have a class called Toast, composed of a certain amount of bread and butter:

class Toast
{
public:
	int bread;
	int butter;

	Toast(int bread, int butter)
		: bread(bread), butter(butter)
	{

	}
};

It is easy to sort integers, but how do you sort Toast? We need to offer C++ a way to compare one Toast instance to another. This is done by creating a structure implementing an operator() and effectively doing a less-than comparison. A StackOverflow question and answer shows how it’s done, and the code needed for sorting our Toast is below.

struct ToastCompare
{
	bool operator()(const Toast &t1, const Toast &t2) const
	{
		int t1value = t1.bread * 1000 + t1.butter;
		int t2value = t2.bread * 1000 + t2.butter;
		return t1value < t2value;
	}
};

We can now pass the TestCompare class to the priority_queue to tell it how to sort the Toast. Sample code is below.

#include <iostream>
#include <queue>
#include <vector>

#include "Toast.h"

using std::priority_queue;
using std::vector;
using std::cout;
using std::endl;

int main(int argc, char ** argv)
{
	Toast toast1(2, 200);
	Toast toast2(1, 30);
	Toast toast3(1, 10);
	Toast toast4(3, 1);
	
	//priority_queue<Toast> queue;
	priority_queue<Toast, vector<Toast>, ToastCompare> queue;

	queue.push(toast1);
	queue.push(toast2);
	queue.push(toast3);
	queue.push(toast4);

	while (!queue.empty())
	{
		Toast t = queue.top();
		cout << "bread " << t.bread << " butter " << t.butter << std::endl;
		queue.pop();
	}

	system("pause");

	return 0;
}

If we used the simple priority_queue declaration (the line that is commented out), we would end up with a bunch of errors because of C++ not knowing how to compare theToast instances.

Instead, we pass three template arguments: the Toast itself, a vector of Toast, and theToastCompare class to tell C++ how to compare Toast instances. The second template argument (the vector) is there because the C++ STL priority queue is actually a container adapter – it uses an underlying data structure to store elements, and the default is a vector.

The output for the above program is given below:

bread 3 butter 1
bread 2 butter 200
bread 1 butter 30
bread 1 butter 10
Press any key to continue . . .

Further reading

Scope Bound Resource Management in C#

This article explains how we can use scope to localize resource lifetime as well as other arbitrary user code effects within a method. The article starts with background from C++, because that’s where this technique comes from.

Update 5th November 2016: Some of the utility classes described here have been incorporated in my Dandago.Utilities NuGet package.

The RAII Pattern

Despite their power, pointers in C/C++ have been the cause of much outrage. Using them incorrectly typically leads to disastrous effects, from memory leaks to segmentation faults. While newer languages such as Java and C# have imposed damage control by taking control of the lifetime of objects allocated on the heap (via garbage collection), there are techniques even in C++ that make pointers a lot less messy to use.

In fact, the problem here is not even about pointers. Pointers belong to a family of resources, along with file handles, sockets, and many other things. These are typically allocated on the heap and must be released after use; otherwise bad things happen.

Scott Meyers’ excellent book Effective C++: 55 Specific Ways to Improve Your Programs and Designs has an entire section dedicated to safely working with resources. One of the first things he suggests in that section is to encapsulate a resource within an object. For example:

class MyResource
{
public:
    MyResource() // constructor
    {
        this->ptr = new int[1000]; // allocate memory on heap
    }

    ~MyResource() // destructor
    {
        delete this->ptr; // free memory
    }

private:
    int * ptr; // pointer encapsulated within class
};

This encapsulation is called Resource Acquisition Is Initialization (RAII), or Scope-Bound Resource Management. Apart from constructors, C++ classes can have destructors. These get called either explicitly from application code, or automatically when an object allocated on the stack goes out of scope. Let’s see how this works in practice:

int main(int argc, char ** argv)
{
    // create instance of MyResource on stack
    MyResource resource;

    return 0;
} // we went out of scope; destructor gets called

Just like declaring an int variable allocates it on the stack, the same thing happens with class types. When that object goes out of scope (i.e. reaches the next } brace), its destructor gets called. This is great because you can’t really forget to dispose of the encapsulated resource. If you return early, throw an exception, etc, the destructor will get called when control leaves the current execution block.

The IDisposable Pattern

In C#, objects allocated on the heap (via the new keyword) are typically killed by the garbage collector when it determines that they are no longer in use. While C# code typically doesn’t face the problems C++ code has with pointers, managing resources is no less important. Just like C++, C# has to deal with file handles, databases, sockets, unmanaged libraries and other stuff that must be disposed as carefully as they are initialized.

For this reason, C# provides two tools to essentially do the work of C++ destructors: the IDisposable pattern, and finalizers. Using these correctly is non-trivial and depends on the situation, but they are also pretty standard and well-documented. Check out this CodeProject article for an in-depth treatment of the topic.

For convenience, C# also provides an overloaded using keyword that works hand-in-hand with the IDisposable pattern:

            using (var fs = File.OpenWrite("file.txt"))
            using (var sw = new StreamWriter(fs))
            {
                sw.WriteLine("Hello!");
            } // automatically calls Dispose() for both

A using block, wrapping an object that implements IDisposable, will automatically call that object’s Dispose() method when it goes out of scope (and using blocks can be stacked, as above). This is essentially equivapent to:

            FileStream fs = null;
            StreamWriter sw = null;
            try
            {
                fs = File.OpenWrite("file.txt");
                sw = new StreamWriter(fs);

                sw.WriteLine("Hello!");
            }
            finally
            {
                sw.Dispose();
                fs.Dispose();
            }

Abusing the IDisposable Pattern

While IDisposable is meant to be used to safely dispose of resources, we can extend its usefulness to other scenarios that relate to a particular scope.

One example where I’ve used this idea before is to log the beginning and end of a method:

    public class ScopedLog : IDisposable
    {
        private string name;

        public ScopedLog(string name)
        {
            this.name = name;
            Console.WriteLine("Begin {0}", name);
        }

        public void Dispose()
        {
            Console.WriteLine("End {0}", this.name);
        }
    }

This pattern doesn’t really add anything, but gives you an elegant way to do scope-related stuff without that getting in the way of your application logic:

        static void Main(string[] args)
        {
            using (var log = new ScopedLog("Main"))
            {
                Console.WriteLine("Hello!");
            }

            Console.ReadLine();
        }

Here’s the output:

scope-logging

Another example is when you want to benchmark your code. Code can get really messy when you’re doing logging, benchmarking and other stuff in the same method. Instead, we can make a dedicated class:

    public class ScopedTimer : IDisposable
    {
        private string name;
        private DateTime startTime;

        public ScopedTimer(string name)
        {
            this.name = name;
            this.startTime = DateTime.Now;
        }

        public void Dispose()
        {
            var endTime = DateTime.Now;
            var elapsed = endTime - this.startTime;

            Console.WriteLine("{0} took {1}", this.name, elapsed);
        }
    }

…and then put it neatly in a using block:

        static void Main(string[] args)
        {
            using (var timer = new ScopedTimer("Main"))
            using (var log = new ScopedLog("Main"))
            {
                Console.WriteLine("Hello!");
            }

            Console.ReadLine();
        }

Here’s the output:

scope-benchmarking

A final example is changing the console colour. It’s very easy to save the old colour, set a new one, and then revert back to the old colour when going out of scope:

    public class ScopedConsoleColour : IDisposable
    {
        private ConsoleColor oldColour;

        public ScopedConsoleColour(ConsoleColor newColour)
        {
            this.oldColour = Console.ForegroundColor;

            Console.ForegroundColor = newColour;
        }

        public void Dispose()
        {
            Console.ForegroundColor = this.oldColour;
        }
    }

Note: you could use Console.ResetColor(), but then you can’t nest colour changes.

Here’s the updated Main() code for this example:

        static void Main(string[] args)
        {
            using (var timer = new ScopedTimer("Main"))
            using (var log = new ScopedLog("Main"))
            {
                Console.WriteLine("Hello!");

                using (var colour = new ScopedConsoleColour(ConsoleColor.Yellow))
                {
                    Console.WriteLine("Howdy?");
                }

                Console.WriteLine("Bye!");
            }

            Console.ReadLine();
        }

Here’s the output:

scope-colour

Other Applications in C++

The RAII pattern is awesome. Not only does it allow you to safely manage the lifetime of resources, but it enables a whole class of scope-based applications. Aside from the C# examples in the previous section, RAII enables things like smart pointers in C++ (e.g. unique_ptr) and scoped locks.