STL Design Patterns

Standard Template Library (STL) has been a part of C++ for a very long time but many people who have embraced C++ still hesitate in using STL in their projects. There is a feeling that STL is difficult and hard to learn. Nothing could be further from truth. STL is simple to use, debugged and efficient code. STL  can reduce the amount on mundane repetitive code that takes up so much of project time.

In this series of articles we will consider some real life design patterns from Embedded and Real-time systems and develop them using STL. These examples will illustrate how easy it is to implement complex design patterns with very little coding.

map

Our examples in this article focus on the STL map. Map allows you to store data so that it can be quickly accessed via a key. For example consider a phone number of circuit mapping in a switching system. The phone numbers have such a wide range that an array cannot be defined to provide a quick access from the phone number to the circuit. Searching through all entries is not an option as it would be too expensive. Map addresses this problem by providing a quick access mechanism. This mechanism is implemented using red-black trees. Fortunately using map does not require understanding its internal operations. The following examples show two embedded system patterns implemented using maps:

Terminal Manager

Terminal Manager exemplifies a typical design pattern seen in embedded systems. Here a collection of terminals is being managed by the Terminal Manager. Management involves routing messages, creating and deleting terminals. (We more details about this design pattern refer to Manager Design Pattern).

The Terminal Manager implements the following methods:

Terminal Manager

Routing Table

Routing Table is another pattern that can easily be implemented using map. In this routing table, a mapping is maintained from the Node Id to the Link Id. Each routing table entry is specified as a pair of Node Id and Link Id. Given a Node Id, the Routing Table returns the Link Id. We can write pretty much the same code as the previous example to implement it, but we will take a different route to implement the same functionality. This time we will use another feature of STL, the iterator.

Think of iterators as pointers on steroids. Iterators are special types defined by the map that give the appearance of a pointer. Iterators allow you to iterate through the complete data structure. For example the iterator in a map allows you to iterate through the complete map. The iterator points to a structure containing the key (marked as first) and the actual value stored in the as second. If this sounds confusing, the following example of the Routing Table pattern should clarify things.

The Routing Table implements the following methods:

Routing Table

We will discuss queuing and resource management patterns that can be implemented with ease using the STL queue and priority queue adaptors. A simple implementation of the following design patterns will be covered in this article:

Container Adaptors

We will be using the following container adaptors to implement our classes:

queue queue container adaptor supports the standard queue operations, viz. add to queue, remove from queue. STL allows you to specify the underlying container used for implementing the queue. By changing one line of code you could change from a linked list implementation to an array like double ended queue!
priority_queue Standard queue adds new arrivals at the tail of the queue. Priority queue however adds a new arrival according to its "priority". A higher priority entry is added before a lower priority entry in the queue. The "priority" for an entry is determined by invoking a user specified function.
stack Stack implements the standard LIFO (Last In First Out) operations. Just like the other container adaptors you can choose the underlying container to be a vector or a linked list.

Message Queue Pattern

Message Queues are a very important design pattern in embedded and real-time systems. Here we implement the Message Queue class as a very thin wrapper over the STL queue container adaptor.

Message Queue

Priority Message Queue Pattern

The Message Queue class always adds the message to the end of the queue. In many applications, the messages need to be queued according to the priority specified at the time of addition i.e. when a high priority message arrives, it is enqueued before any previously present low priority messages.

We will be using the priority_queue container adaptor to implement the Priority Message Queue class.

Function Objects (Functors)

The implementation of the Priority Message Queue is quite similar to the Message Queue. The most important change here is the introduction of a struct called CompareMessages. This struct is a function object (functor), i.e. the sole purpose of this struct is to define a method for comparing the priorities of the two messages.

If you look closely you will see that the struct CompareMessages just overloads the "()" operator, i.e. the method to be invoked when CompareMessages struct is used along with the "()" operator. This provides an extremely efficient mechanism for passing function code as a parameter. This mechanism has the following advantages over passing a function pointer:

Priority Message Queue

Resource Allocator Pattern

A simple Resource Allocator can be implemented by using the queue and the stack container adaptors. The container adaptors are used to maintain the free list of resources.

The Resource Allocator supports the following interfaces:

Coldest First

In coldest first resource allocation, the resource not allocated for maximum time is allocated first. To implement this first in first out, FIFO type of allocation, the resource allocating entity keeps the free resources in a queue. A resource allocation request is serviced by removing a resource from the head of the queue. A freed resource is returned to the free list by adding it to the tail of the queue.

The following code defines a simple "coldest first" resource allocator:

Resource Allocator (Coldest First)

Hottest First

In hottest first resource allocation, the resource last released is allocated on next resource request. To implement this last in first out, LIFO type of allocation, the list of free resources is maintained as a stack. An allocation request is serviced by popping a free resource from the stack. When a resource is freed, it is pushed on the free resource list.

The "coldest first" resource allocator can be changed to "hottest first" resource allocator by simply replacing the queue with a stack. The following code illustrates the code for hottest first resource allocator:

Resource Allocator (Hottest First)