Example: Using Templated Functions

Sorting with a priority queue is a nice example of why you might want to use templates in C++.

Suppose we want to write a general-purpose sorting function that reads all the elements of a vector into a priority queue like this:

void pq_sort(vector<int>& v) {
    for(int x : v) {
        pq.insert(x);  // <--- Where does pq come from?
    }
    v.clear();
    while (!pq.empty()) {
        v.push_back(pq.pop_min());
    }
}

The question is this: how do we tell pq_sort which priority queue implementation to use for pq?

The most straightforward way is probably to just use cut-and-paste to create a new sorting function for each priority queue implementation.

But surely we can do better. Perhaps we can use an abstract base class defined something like this:

class Priority_queue_base {
public:
    virtual ~Priority_queue() { }
    virtual bool empty() const = 0;
    virtual void insert(int x) = 0;
    virtual int pop_min() = 0;
}; // class Priority_queue_base

This lets us write derived classes that implement empty, insert, and pop_min, e.g.:

class PQ_unordered : public Priority_queue_base {
private:
    vector<int> vec;
public:
    // ...
};


class PQ_ordered : public Priority_queue_base {
private:
    vector<int> vec;
public:
    // ...
};

// ...

Then we could write a general-purpose priority queue based sort function like this:

// Pre-condition:
//    pq is empty
// Post-condition:
//    v is re-arranged into ascending sorted order
void pq_sort(vector<int>& v, Priority_queue_base& pq) {
    for(int x : v) {
        pq.insert(x);
    }
    v.clear();
    while (!pq.empty()) {
        v.push_back(pq.pop_min());
    }
}

Somewhere before pq_sort is called the programmer must construct the priority queue they want to use, e.g.:

PQ_unordered pq;
pq_sort(v, pq);

Manually creating the priority queue before pq_sort is not ideal. The priority queue really should be a local variable inside pq_sort itself because it is only used by pq_sort. Defining it outside of pq_sort increases its scope, and leaves it up to the programmer to ensure pq is empty when it is passed to the sort, and is disposed of afterwards.

What we really want to do is to somehow tell pq_sort to use PQ_unordered for the local priority queue it needs. If we could pass just the type PQ_unordered to pq_sort instead of a value, then pq_sort could construct its own local priority queue.

C++ templates solve this problem quite nicely. C++ templates let us pass a type (as opposed to a value of that type) to a function, which allows that function to construct instances of that type.

Here is a templated version of pq_sort:

template<class PQ>
void pq_sort(vector<int>& v) {
    PQ pq;
    for(int x : v) {
        pq.insert(x);
    }
    v.clear();
    while (!pq.empty()) {
        v.push_back(pq.pop_min());
    }
}

You call it like this:

pq_sort<PQ_unordered>(v);

As you can see, the PQ type is not an ordinary parameter, but is instead passed using template syntax. Wherever PQ appears inside pq_sort, it gets replaced by PQ_unordered.

Notice that we don’t need the Priority_queue_base class any more. Instead, the C++ compiler scans through pq_sort to see which methods pq uses:

PQ pq;        // default constructor

// ...

pq.insert(x)  // void insert(int)

// ...

pq.pop_min()  // int pop_min()

PQ can be any class that provides these three methods. Determining the type of something in this way, i.e. without making a pre-defined list of methods that PQ must support, is sometimes called duck typing.