Share

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);
     }
  }
};

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;      
  }   
};