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:

  • Add_Terminal: Create and add a new terminal
  • Remove_Terminal: Remove and delete a terminal
  • Find_Terminal: Find a terminal from its terminal_Id
  • Handle_Message: Route the received message to the Terminal object

Terminal Manager

#include <map> // Header file include for map
using namespace std;// STL containers are defined in std namespace
class Terminal_Message
{
public:
int Get_Terminal_Id() const;
};
class Terminal
{
public:
Terminal(int terminal_Id, int type);
void Handle_Message(const Terminal_Message *pMsg);
int Get_Terminal_Id() const;
};
class Terminal_Manager
{
typedef map<int, Terminal *> Terminal_Map;
Terminal_Map m_terminal_Map;
public:
enum Status {FAILURE, SUCCESS};
Status Add_Terminal(int terminal_Id, int type)
{
Status status;
// Check if the terminal is already present in the map. count()
// returns the total number of entries that are keyed by terminal_Id
if(m_terminal_Map.count(terminal_Id) == 0)
{
// count() returned zero, so no entries are present in the map
Terminal *pTerm = new Terminal(terminal_Id, type);
// Since map overloads the array operator [ ], it gives
// the illusion of indexing into an array. The following
// line makes an entry into the map
m_terminal_Map[terminal_Id] = pTerm;
status = SUCCESS;
}
else
{
// count() returned a non zero value, so the terminal is already
// present.
status = FAILURE;
}
return status;
}
Status Remove_Terminal(int terminal_Id)
{
Status status;
// Check if the terminal is present
if (m_terminal_Map.count(terminal_Id) == 1)
{
// Save the pointer that is being deleted from the map
Terminal *pTerm = m_terminal_Map[terminal_Id];
// Erase the entry from the map. This just frees up the memory for
// the pointer. The actual object is freed up using delete
m_terminal_Map.erase(terminal_Id);
delete pTerm;
status = SUCCESS;
}
else
{
status = FAILURE;
}
return status;
}
Terminal *Find_Terminal(int terminal_Id)
{
Terminal *pTerm;
if (m_terminal_Map.count(terminal_Id) == 1)
{
pTerm = m_terminal_Map[terminal_Id];
}
else
{
pTerm = NULL;
}
return pTerm;
}
void Handle_Message(const Terminal_Message *pMsg)
{
int terminal_Id = pMsg->Get_Terminal_Id();
Terminal *pTerm;
pTerm = Find_Terminal(terminal_Id);
if (pTerm)
{
pTerm->Handle_Message(pMsg);
}
}
};
view raw Terminal_Manager.cpp hosted with ❤ by GitHub

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:

  • Print: Prints out all the entries in the routing table.
  • Add_Routing_Entry: Adds a new entry into the routing table
  • Remove_Routing_Entry: Removes an entry from the routing table
  • Route: Provides the Node Id to Link Id mapping

Routing Table

#include <map> // Header file include for map
using namespace std; // STL containers are defined in std namespace
typedef int Node_Id;
typedef int Link_Id;
#define INVALID_LINK_ID (-1)
class Routing_Table
{
typedef map<Node_Id, Link_Id> Routing_Map;
Routing_Map m_routing_Map;
public:
enum Status {FAILURE, SUCCESS};
void Print()
{
// STL defines a nested type iterator. Here we have declared an instance
// of this nested type.
Routing_Map::iterator it;
// Iterator it "points" to a structure defined as:
// struct Pair
// {
// Node_Id first;
// Link_Id second;
// };
// map supports predefined begin() and end() markers. begin() "points"
// to the first entry in the map. end() points BEYOND the last entry
// in the map (i.e. the last entry is the entry just before end()
// STL provides pointer like symantics to iterators, thus it++ moves
// the iterator to the next entry in the map.
for (it = m_routing_Map.begin(); it != m_routing_Map.end(); it++)
{
printf ("Node_Id = %d, Link_Id = %d\n", it->first, it->second);
}
}
Status Add_Routing_Entry(Node_Id node_Id, Link_Id link_Id)
{
Status status;
// First check if the entry already exists
if (m_routing_Map.find(node_Id) != m_routing_Map.end())
{
// Iterator returns a value other than end, thus this
// is a duplicate addition, return failure
status = FAILURE;
}
else
{
// The end iterator was returned, signifying that
// no entry currently exists, so a new one can be added.
m_routing_Map[node_Id] = link_Id;
status = SUCCESS;
}
}
Status Remove_Routing_Entry(Node_Id node_Id)
{
Status status;
// Check if the terminal is present
if (m_routing_Map.find(node_Id) != m_routing_Map.end())
{
// Erase the entry from the map.
m_routing_Map.erase(node_Id);
status = SUCCESS;
}
else
{
status = FAILURE;
}
return status;
}
Link_Id Route(Node_Id node_Id)
{
Link_Id link_Id = INVALID_LINK_ID;
// Check if the route entry is present
if (m_routing_Map.find(node_Id) != m_routing_Map.end())
{
link_Id = m_routing_Map[node_Id];
}
return link_Id;
}
};
view raw Routing_Table.cpp hosted with ❤ by GitHub

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

#include <queue> // STL header file for queue
#include <list>
using namespace std; // Specify that we are using the std namespace
class Message;
class Message_Queue
{
typedef queue<Message *, list<Message > > MsgQueType;
MsgQueType m_msgQueue;
public:
void Add(Message *pMsg)
{
// Insert the element at the end of the queue
m_msgQueue.push(pMsg);
}
Message *Remove()
{
Message *pMsg = NULL;
// Check if the message queue is not empty
if (!m_msgQueue.empty())
{
// Queue is not empty so get a pointer to the
// first message in the queue
pMsg = m_msgQueue.front();
// Now remove the pointer from the message queue
m_msgQueue.pop();
}
return pMsg;
}
int GetLength() const
{
return m_msgQueue.size();
}
};
view raw message-queue.cpp hosted with ❤ by GitHub

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 sepcified 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:

  • Function Objects are efficient, as they can even be inline. On the other hand, a function pointer will always have the overhead of a function call.
  • Function Objects provide a type safe implementation, there are no void pointers in this design.

Priority Message Queue

#include <queue> // STL header file for queue
#include <list>
using namespace std; // Specify that we are using the std namespace
class Message;
class Priority_Message_Queue
{
struct Entry
{
Message *pMsg;
int priority;
};
struct Compare_Messages
{
bool operator () (const Entry& left , const Entry& right)
{
return (left.priority < right.priority);
}
};
typedef priority_queue<Entry, vector<Entry>, Compare_Messages >
Message_Queue_Type;
Message_Queue_Type m_message_Queue;
public:
void Add(Message *pMsg, int priority)
{
// Make an entry
Entry entry;
entry.pMsg = pMsg;
entry.priority = priority;
// Insert the element according to its priority
m_message_Queue.push(entry);
}
Message *Remove()
{
Message *pMsg = NULL;
// Check if the message queue is not empty
if (!m_message_Queue.empty())
{
// Queue is not empty so get a pointer to the
// first message in the queue
pMsg = (m_message_Queue.top()).pMsg;
// Now remove the pointer from the message queue
m_message_Queue.pop();
}
return (pMsg);
}
size_t Get_Length() const
{
return m_message_Queue.size();
}
};
view raw priority-message-queue.cpp hosted with ❤ by GitHub

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:

  • Construction: When the Resource Allocator is constructed, it is a given a list of free resources. These resources are added to the free resource queue.
  • Allocate: When a resource is requested, it is removed from the free resource queue and the pointer to the resource is passed to the caller.
  • Free: When a resource is freed, it is added back to the free queue.
  • GetFreeResourceCount: Returns the total number of free resources currently available.

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)

#include <queue> // STL header file for queue
#include <list>
using namespace std; // Specify that we are using the std namespace
class Resource;
class Cold_Resource_Allocator
{
typedef queue<Resource *, list<Resource *> > Free_Queue_Type;
Free_Queue_Type m_free_Resource_Queue;
public:
Cold_Resource_Allocator(int resource_Count,
Resource *resource_Array[])
{
for (int i = 0; i < resource_Count; i++)
{
m_free_Resource_Queue.push(resource_Array[i]);
}
}
Resource * Allocate()
{
Resource *pResource = NULL;
// Check if any free resources are available.
if (!m_free_Resource_Queue.empty())
{
// Queue is not empty so get a pointer to the
// first resource in the queue
pResource = m_free_Resource_Queue.front();
// Now remove the pointer from the free resource queue
m_free_Resource_Queue.pop();
}
return pResource;
}
void Free(Resource *pResource)
{
// Insert the resource at the end of the free queue
m_free_Resource_Queue.push(pResource);
}
size_t GetFreeResourceCount()
{
return m_free_Resource_Queue.size();
}
};
view raw Cold_Resource_Allocator.cpp hosted with ❤ by GitHub

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)

#include <stack> // STL header file for stack
#include <deque>
using namespace std; // Specify that we are using the std namespace
class Resource;
class Hot_Resource_Allocator
{
typedef stack <Resource *, deque <Resource *> >
Free_Stack_Type;
Free_Stack_Type m_free_Resource_Stack;
public:
Hot_Resource_Allocator(int resource_Count,
Resource *resource_Array[])
{
for (int i = 0; i < resource_Count; i++)
{
m_free_Resource_Stack.push(resource_Array[i]);
}
}
Resource * Allocate()
{
Resource *pResource = NULL;
// Check if any free resources are available.
if (!m_free_Resource_Stack.empty())
{
// Queue is not empty so get a pointer to the
// first resource in the stack
pResource = m_free_Resource_Stack.top();
// Now remove the pointer from the free resource stack
m_free_Resource_Stack.pop();
}
return pResource;
}
void Free(Resource *pResource)
{
// Insert the resource at the end of the free stack
m_free_Resource_Stack.push(pResource);
}
size_t GetFreeResourceCount()
{
return m_free_Resource_Stack.size();
}
};
view raw Hot_Resource_Allocator.cpp hosted with ❤ by GitHub