Level: Introductory Hemang Subramanian (shemang@in.ibm.com), Software Engineer, IBM India
11 Apr 2003 In many application programs, the need for standard data structures, or collection structures, is critical. This article compares the features of the IBM Open Collection Classes and Standard Template Library (STL) Collection Classes. If you need to port applications that use STL Collection Classes to applications that use the IBM Open Class Library, or vice versa, then you might find this article useful.
Introduction
If you migrate a C++ application to Linux written with a VisualAge C++ tool, which in turn uses the IBM Open Class (IOC) Library, you would need to find the equivalents for the various classes used in the GNU-stdlibc++ provided on Linux. Similarly, if you need to migrate any application that uses STL classes to a platform that supports IOC, how would you do it?
This article discusses the nuances of a subset of the IOC Library called the collection classes. It addresses certain classes and gives a general direction for finding the functional equivalent for the collection classes. The STL classes and methods have an equivalent for most of the IBM Open Classes.
Collection classes in the IOC Library
The IOC Library has various class templates for providing things like application control, runtime storage of data, and user interface programming. The collection classes of the IOC library are used to store data in a particular data structure. The collection classes can be classified as:
- Flat collection
- Bags, sets, queues, lists, and so on
- Tree collection
- n-nary tree implementation, methods for traversal
- Auxilliary collection
- Cursor, tree cursor, iterators
- Abstract collection
- Consist of most of the base classes from which the first three are derived.
The most commonly used data structures are: queues, stacks, lists, sets, maps, bags, trees, and tables. Each of these categories have several variations. For example, the queue can be represented many ways in the library, such as IAProrityQueue, Iqueue, IqueueonTabularSequence, IqueueonSortedTabularSequence, and so on.
Most of the methods used for all the classes are unique to the data structure, but there are several methods that are common across the various classes. This article discusses the implementation of those methods and gives a source code example of the STL equivalent in Linux for a simple Queue data structure.
One of the caveats of the Open classes is the presence of a generic class called ICursor that can point to any &element in a collection object. The ICursor can point to any &element in the collection, and is similar to a pointer to an &element in a list.
STL organization and container classes
The STL is a generic C++ library of container classes, algorithms, and iterators. It provides many of the known basic algorithms and data structures. Its components have many parameters, and almost every component in the STL is a template.
The STL's main components are:
- Algorithms
- Computational procedures that are able to work on different containers
- Containers
- Objects that are able to keep and administer objects
- Iterators
- Abstractions of the algorithm access to containers so that an algorithm is able to work on different containers
- Function objects
- Classes that have the function-call operator (operator ()) defined
- Adaptors
- Encapsulate a component to provide another interface, such as making a stack out of a list
See Resources for more details about STL and C++.
You can consider an object of type Iterator as being similar to a cursor that points to a particular member of a particular collection. All the data structures that are present and defined are present as a part of the container classes provided by STL.
Common methods used by collection classes
Several methods and functions are commonly defined as members to the several classes in the IOC Library. Some of the commonly used methods of these classes are:
-
Add
- Adds the element to the collection and sets the cursor to the added element. In sorted collections, the element is added at a position determined by the element or key value.
-
AllElementsDo
- Calls the given function for all elements in the collection until the given function returns False. The elements are visited in iteration order. Additional arguments can be passed to the given function using
additionalArgument. The additional argument defaults to zero if no additional argument is given.
Note: For the non-const version of allElementsDo(), the given function must not manipulate the element in the collection in a way that changes the positioning property of the element.
retcode = Data.allElementsDo(WriteRecord, rLog)
rLog is the parameter to the WriteRec function
|
-
RemoveAll
- Deletes all the elements in the Queue.
-
key
- Cannot be used by the Visual Age class to notify the particular collection of the value to be used for each element in the collection for performing a certain operation.
For example, I have structure "abc" with elements a,b,c, and I have a QueueonSortedTabularSequence collection, where each member is of type "abc." The element used to sort the elements of the Queue could be the element "a." The function key would return "a."
-
elementAt
- Returns the element pointed to by the cursor.
 |
Exception handling and thread safety in the IOC and STL
All methods associated with any particular collection class have several exceptions that are thrown by the various methods in the classes. The exceptions that arise are:
- IOutOfMemory
- ICursorInvalidException
- IFullException, if the collection is bounded
This is a feature unique to the IBM Open Classes. Most of the exceptions are thrown by the method itself, and actions can be taken based on these exceptions.
STL methods internally do not throw out any such exceptions. Take extra care to avoid errors here, since they cannot be automatically detected by the IOC library.
Both classes are not thread-safe. For example, if I have two threads, one of which adds a member to an object and the other deletes it, I would have to use a method to lock either. See Resources for information about achieving this in STL.
IQueue collection class
A queue is a sequence with restricted access. It is an ordered collection of elements with no key and no element equality. The elements are arranged so that each collection has a first and a last element. Each element except the last has a next element, and each element except the first has a previous element. The type and value of the elements are irrelevant and have no effect on the behavior of the collection. One can only add an element as the last element, and can only remove the first element. Consequently, the elements of a queue are in chronological order. A queue is characterized by first-in, first-out (FIFO) behavior.
void enqueue ( Element const &element )
Adds the element to the collection and sets the cursor to the added element. For ordinary queues, the given element is added as the last element.
Exceptions:
- IOutOfMemory
- ICursorInvalidException
- IFullException, if the collection is bounded
IBoolean add ( Element const &element )
Adds an element to the queue and points the cursor to the element that has been added.
Exceptions:
- IOutOfMemory
- ICursorInvalidException
- IFullException, if the collection is bounded
INumber numberOfElements ( ) const
Returns the number of elements the collection contains.
void dequeue ( Element &element )
Copies the first element of the collection to the given element and removes it from the collection.
Exception:
IBoolean isEmpty ( ) const
Returns True if the collection is empty.
IBoolean allElementsDo (IBoolean (*function) (Element , void*),void* additionalArgument = 0 )
ls the given function for all elements in the collection until the given function returns False. The elements are visited in iteration order. Additional arguments can be passed to the given function using additionalArgument. The additional argument defaults to zero if no additional argument is given.
Note: For the non-const version of allElementsDo(), the given function must not manipulate the element in the collection in a way that changes the positioning property of the element.
ibGood = Data. allElementsDo(WriteRecord, amprLogampamp;);
rLog is the parameter to the WriteRecord function
|
void removeFirst ( )
Removes the first element from the collection. Element destructors are called as described in RemoveAt.
Exception:
void addAllFrom ( CLASS_NAME &constamp collection )
Adds or copies all elements of the given collection to the collection. The elements are added in the iteration order of the given collection. The contents of the elements, not the pointers to the elements, are copied. The elements are added according to the definition of add for this collection. The given collection is not changed.
Exception:
- IOutOfMemory
- IIdenticalCollectionException
- IFullException, if the collection is bounded
Cursor* newCursor ( ) const
Creates a cursor for the collection and returns a pointer to the cursor. The cursor is initially not valid.
Exception:
removeAll()
Deletes all the elements in the Queue.
IQueue Collection Class
Equivalent STL class for the IQueue being used as a List.
There could be different ways of representing the equivalent class for the Open Class Queue, such as creating a class that inherits from List, but this example just shows the basics. Because the queue class on Linux does not return an iterator, which is needed for simulation of several functions given by the VAC++ classes, the IQueue is implemented as a List.
The List also cannot be used instead of a queue class directly available in the STL library because there is no equivalent for the forAllElementsDo method. The for_each algorithm cannot be considered equivalent to forAllElementsDo because it does not stop performing the operations on the elements if the callback function returns a false for even one element.
A List is a doubly linked list. It is a sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning, end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements. Even removal invalidates only the iterators that point to the elements that are removed.
- Equivalent to
Enqueue
-
void push_back(const T&) - Inserts a new element at the end.
- Equivalent to
Add
void push_back(const T&) - Inserts a new element at the end.- Equivalent to
NumberOfElements
size_type size() const - Returns the size of the list. Do not assume that this function is constant time.- Equivalent to
Dequeue
- A combination of two methods:
void front() – returns the last element
void pop_front() - Removes the last element
- Equivalent to
IsEmpty
- Bool empty - returns True if the queue is empty.
- Equivalent to
allElementsDo
-
A simple for loop achieves the equivalence to the allElementsDo method:
for (itt=object.begin();itt!=object.end();itt++)
if(!print(*itt)) break;
|
This traverses the whole list from the first element to the last element in the list. Each element in the list is passed as a parameter to the function print as a pointer to the iterator itt. The prototype of the function print would remain the same as on OS/2, as it would return a data of type Boolean.
- Equivalent to
RemoveFirst
- void pop_front() - Removes the last element.
- Equivalent to
addAllFrom
- The following code achieves the merging of two queues -- mergelist and the abc.
for (itt =mergelist.begin();itt != mergelist.end();itt++)
abc.push_front(*itt);
|
Here, itt is an object of type Iterator.
Note that this section of the code has to be locked with a Mutex in order to be thread-safe.
- Equivalent to
newCursor
-
The class
Iterator is used instead of a cursor to point to a particular object's contained element. A new iterator is declared and assigned the first element in the list.
ListClass::iterator itt;
itt = list.begin(); //itt |
- Equivalent to
RemoveAll
- void clear() - Erases all of the elements.
Source code for the IBM Open Class
Queue Implmentation using Open Classes */
#include <iostream.h>
//#define INO_CHECKS // to omit run-time precondition checks
#include <iset.h> // for ISet
//#pragma info (nocmp, nopor) // to omit comparison and non-portable
conversion
#include <iqueue.h>
#include <iglobals.h>
#include <os2.h>
typedef IQueue<int> WordSet;
WordSet abc;
WordSet def;
IBoolean printit(int const &abc, void *bcd)//not used
{
cout<< abc <<endl;
return TRUE;
}
void main(void)
{
int remark;
int temp;
abc.enqueue(1);
abc.enqueue(2);
abc.enqueue(3);
abc.enqueue(4);
//Creation of the second list of items
def.enqueue(99);
def.enqueue(100);
def.enqueue(101);
// abc.allElementsDo(Mult,&remark);
abc.dequeue(temp);
//if list abc is Empty donot print
if (!abc.isEmpty())
cout<<"element " <<temp <<" number of elements
"<<abc.numberOfElements()<<"\n";
//Merger with the second list
abc.addAllFrom(def);
//if list abc is Empty donot print
if (!abc.isEmpty())
cout<<"number of elements "<<abc.numberOfElements()<<"\n";
//All Elements do
abc.allElementsDo(printit); //print all elements
//removeAll elements
abc.removeAll();
if (abc.isEmpty())
cout<<"number of elements "<<abc.numberOfElements()<<"\n";
}
|
Source code for the STL classes
Equivalent Queue Listing */
#include<iostream.h>
#include<list>
#include<iterator>
#include<string>
#include<algorithm>
typedef struct _abc{
int a;
int b;
}sabc;
typedef list<sabc> WordSet;
//Queue is a first in First out mechanism
//(END)D C B A(FRONT)
WordSet abc;
WordSet mergelist;
WordSet::iterator itt;//Equivalent for Cursor
bool print(sabc elem)
{
if(elem.a == 8)
return 0;
else {
cout<<elem.a <<" "<< elem.b<<' '<<'\n';
return 1;
}
}//code needed for returning a TRUE Value
void main(void) {
sabc temp;
sabc temp1;
sabc temp2;
sabc temp3[3];
sabc temp4;
int size;
temp1.a = 1;
temp1.b = 2;
temp2.a = 3;
temp2.b = 4;
temp3[0].a = 5;
temp3[0].b = 6;
temp3[1].a = 6;
temp3[1].b = 7;
temp3[2].a = 8;
temp3[2].b = 9;
//Method for add
abc.push_back(temp1);//1 2
abc.push_back(temp2);//3 4
abc.push_back(*(temp3 + 2));//8 9
abc.push_back(*(temp3 + 1));//6 7
//new list for merging with abc
mergelist.push_back(temp3[0]);// 5 6
mergelist.push_back(temp3[1]);//6 7
//for allElementsDo method
for(itt=abc.begin();itt!=abc.end();itt++)
{
if (!print(*itt))
break;
}
// for IsEmpty
if (!abc.empty())
{
cout<<"list is not empty"<<endl;
}
//Method for dequeue
temp4 = abc.front();
cout <<"DEQUEUE " <<temp4.a<<" "<<temp4.b<<endl;
abc.pop_front();
//End Method for dequeue
temp4 = abc.front();
cout <<"After popping:BACK " <<temp4.a<<" "<<temp4.b<<endl;
if (!abc.empty())
size = abc.size();//Method for numberofElements
cout<<"Size of the Queue is:- "<< size <<endl;
//Method for addAllFrom
for(itt=mergelist.begin();itt!=mergelist.end();itt++)
abc.push_back(*itt);
cout<<"The new merged list is as follows" << endl;
//displaying the merged list
for_each(abc.begin(), abc.end(),print);
//Method for removeAll
abc.clear();
if (!abc.empty())
cout<<"List has not been cleared \n";
else cout<<"List is empty \n";
}
|
Resources
- Review VisualAge C++ 5.0 manuals to learn more about equivalence.
- Read the IBM Open Class Library Transition Guide to learn more about the transition of Open Classes to STL.
- The VisualAge C++ v3.0 Help manual provides the references for the various methods.
- Review the specifiications for STL classes.
- Review this electronic textbook about C++, written by Bruce Eckel.
- Visit the C++ User's Journal to view
for_each of the STL classes.
- Get exception handling information and help about the GPP compiler.
- View this Web site for more information about the standard C++ library that comes with Linux.
- Go to this Web site for information about thread safety.
- The Toolbox subscription is your one-stop access to over 1000 IBM tools, middleware, and technologies from WebSphere, WebSphere Studio, DB2, Tivoli, and Lotus for open standards-based Web services and application development. Visit the online catalog today to view all the products and tools available.
About the author  | | | Hemang holds a B.Tech in Computer Science from KREC, Surathkal (now known as the National Institute of Technology, Surathkal). He has been with IBM India working on wired and wireless networking for more than three years. He has a U.S. patent pending, and two publications (one in the IBM technical disclosure bulletin, and the other on the developerWorks Wireless Zone). You can contact Hemang at shemang@in.ibm.com.
|
Rate this page
| 
