STL Design Patterns

Terminal Manager Documentation Routing Table Documentation STL Design Patterns Source Code

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
• Routing Table

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

00009 #include <map>      // Header file include for map
00010 using namespace std;// STL containers are defined in std namespace
00011 
00012 
00013 class Terminal_Message
00014 {
00015 public:
00016     int Get_Terminal_Id() const;
00017 };
00018 
00022 
00023 class Terminal
00024 {
00025 public:
00026 
00030 
00031     Terminal(int terminal_Id, int type);
00032 
00035     void Handle_Message(const Terminal_Message *pMsg);
00036 
00039     int Get_Terminal_Id() const;
00040 };
00041 
00045 
00046 class Terminal_Manager
00047 {
00051    typedef map<int, Terminal *> Terminal_Map;
00052 
00055    Terminal_Map m_terminal_Map;
00056 
00057 public:
00058 
00059    enum Status {FAILURE, SUCCESS};
00060 
00074 
00075    Status Add_Terminal(int terminal_Id, int type)
00076    {
00077       Status status;
00078       
00079       // Check if the terminal is already present in the map. count()
00080       // returns the total number of entries that are keyed by terminal_Id
00081       if(m_terminal_Map.count(terminal_Id) == 0)
00082       {
00083          // count() returned zero, so no entries are present in the map
00084          Terminal *pTerm = new Terminal(terminal_Id, type);
00085  
00086          // Since map overloads the array operator [ ], it gives 
00087          // the illusion of indexing into an array. The following
00088          // line makes an entry into the map
00089          m_terminal_Map[terminal_Id] = pTerm;
00090          
00091          status = SUCCESS;
00092       }
00093       else
00094       {
00095          // count() returned a non zero value, so the terminal is already
00096          // present.
00097          status = FAILURE;
00098       }
00099       
00100       return status;
00101    }
00102    
00116 
00117    Status Remove_Terminal(int terminal_Id)
00118    {
00119       Status status;
00120       // Check if the terminal is present
00121       if (m_terminal_Map.count(terminal_Id) == 1)
00122       {
00123          // Save the pointer that is being deleted from the map
00124          Terminal *pTerm = m_terminal_Map[terminal_Id]; 
00125          
00126          // Erase the entry from the map. This just frees up the memory for
00127          // the pointer. The actual object is freed up using delete
00128          m_terminal_Map.erase(terminal_Id);
00129          delete pTerm;
00130          
00131          status = SUCCESS;
00132       }
00133       else
00134       {
00135          status = FAILURE;
00136       }
00137       
00138       return status;
00139    }
00140   
00147 
00148   Terminal *Find_Terminal(int terminal_Id)
00149   {
00150      Terminal *pTerm;
00151      if (m_terminal_Map.count(terminal_Id) == 1)
00152      {
00153         pTerm = m_terminal_Map[terminal_Id];
00154      }
00155      else
00156      {
00157          pTerm = NULL;
00158      }
00159      
00160      return pTerm;
00161   } 
00162   
00168 
00169   void Handle_Message(const Terminal_Message *pMsg)
00170   {
00171      int terminal_Id = pMsg->Get_Terminal_Id();
00172      
00173      Terminal *pTerm;
00174      
00175      pTerm = Find_Terminal(terminal_Id);
00176      
00177      if (pTerm)
00178      {
00179         pTerm->Handle_Message(pMsg);
00180      }
00181   }
00182 };

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

00007 
00008 #include <map>       // Header file include for map
00009 using namespace std; // STL containers are defined in std namespace
00010 
00011 typedef int Node_Id;
00012 typedef int Link_Id;
00013 
00014 #define INVALID_LINK_ID (-1)
00015 
00027 
00028 class Routing_Table
00029 {
00041    typedef map<Node_Id, Link_Id> Routing_Map;
00042 
00045    Routing_Map m_routing_Map;
00046 
00047 public:
00048    enum Status {FAILURE, SUCCESS};
00049 
00062   
00063    void Print()
00064    {
00065       // STL defines a nested type iterator. Here we have declared an instance
00066       // of this nested type.
00067       Routing_Map::iterator it;
00068       
00069       // Iterator it "points" to a structure defined as:
00070       // struct Pair
00071       // {
00072       //     Node_Id first;
00073       //     Link_Id second;
00074       // }; 
00075       
00076       // map supports predefined begin() and end() markers. begin() "points"
00077       // to the first entry in the map. end() points BEYOND the last entry
00078       // in the map (i.e. the last entry is the entry just before end()
00079       
00080       // STL provides pointer like symantics to iterators, thus it++ moves
00081       // the iterator to the next entry in the map.
00082       
00083       for (it = m_routing_Map.begin(); it != m_routing_Map.end(); it++)
00084       {
00085           printf ("Node_Id = %d, Link_Id = %d\n", it->first, it->second); 
00086       }
00087    }
00088 
00098 
00099    Status Add_Routing_Entry(Node_Id node_Id, Link_Id link_Id)
00100    {
00101       Status status;
00102       
00103       // First check if the entry already exists
00104       if (m_routing_Map.find(node_Id) != m_routing_Map.end())
00105       {
00106           // Iterator returns a value other than end, thus this
00107           // is a duplicate addition, return failure
00108          status = FAILURE;
00109       }
00110       else
00111       {
00112          // The end iterator was returned, signifying that
00113          // no entry currently exists, so a new one can be added.
00114          m_routing_Map[node_Id] = link_Id;
00115          
00116          status = SUCCESS;      
00117       }
00118    }
00119    
00126 
00127    Status Remove_Routing_Entry(Node_Id node_Id)
00128    {
00129       Status status;
00130       // Check if the terminal is present
00131       if (m_routing_Map.find(node_Id) != m_routing_Map.end())
00132       {         
00133          // Erase the entry from the map.
00134          m_routing_Map.erase(node_Id);                  
00135          status = SUCCESS;
00136       }
00137       else
00138       {
00139          status = FAILURE;
00140       }
00141       
00142       return status;
00143    }
00144   
00152 
00153   Link_Id Route(Node_Id node_Id)
00154   {
00155       Link_Id link_Id = INVALID_LINK_ID;
00156       // Check if the route entry is present
00157       if (m_routing_Map.find(node_Id) != m_routing_Map.end())
00158       {         
00159          link_Id = m_routing_Map[node_Id];
00160       }
00161       return link_Id;      
00162   }   
00163 };

Explore More ...

Terminal Manager Documentation Routing Table Documentation STL Design Patterns Source Code