Iterator Concept

Associative Arrays

In many places, STL containers are used, mainly the STL map template, see http://www.sgi.com/tech/stl/Map.html . A map in the Standard Template library is an associative array, which maps input objects to output objects. Elements are accessed very conveniently via the [] operator. For instance, it allows to map strings to numbers.

std::map<string, int>  MapStringToInt;

   MapStringToInt[ "one" ] = 1;
   MapStringToInt[ "two" ] = 2;
   MapStringToInt[ "three" ] = 3;

int value =  MapStringToInt[ "one" ];
    assert( value == 1 );   

To find all objects in a map, there is the STL way of using iterators:

std::map<string, int>  MapStringToInt;
for(std::map<string, int>::const_iterator it = MapStringToInt.begin(); it != MapStringToInt.end(); it++)
{
const string&text = it->first;
int           value = it->second;
        //...
}

Vish Coding Convention

In VISH, wherever an STL container template is used, it will be done via some typedef that has an "_t" appended:

typedef std::map<string, int>  MapStringToInt_t;

MapStringToInt_t MapStringToInt;

for(MapStringToInt_t::const_iterator it = MapStringToInt.begin(); it != MapStringToInt.end(); it++)
{
   ...
}

This allows to possibly change the type of the container without need to change the type in all following cases and iterations.

Read-only access

One must be aware that the [] operator will always return a result, which means if there is no entry yet, then one will be created. In order to just look for an object, STL provides the find() member function. It will return the maps end() element if no such object is found. It's usage is more effortsome than just using the [] operator:

MapStringToInt_t MapStringToInt;

MapStringToInt_t::const_iterator it = MapStringToInt.find("four");
        if (it == MapStringToInt.end() )
        {
                puts(" element not found ");
        }

There is no other way for read-only access to an element, since the the operator [] has no way to tell that an entry was not found.

For stored objects that are pointers, we may however return an null pointer. STL does not support this, but in VISH we are using a convention that does. For readonly access we overload the () operator, and derive out own class that implements this feature. In particular, reference counted objects (see Reference Pointers ) are used frequently as mapped objects, so we may return a NullPtr() when objects are not found.

struct  MapStringToValuePtr : map<string, RefPtr<Value> >
{
        RefPtr<Value> operator()(const string&s) const
        {
        const_iterator it = find(s);
                if (it == end() )
                        return NullPtr()
                return it->second;
        }
};

Usage (we assume a reference-countable class Value exists that has a construct accepting an integer):

MapStringToValuePtr myMap;
        myMap[ "one" ] = new Value(1);
        myMap[ "two" ] = new Value(2);
        myMap[ "three" ] = new Value(3);

        if (RefPtr<Value> Four = myMap("four") )
        {
                //... yes, entry "four" was found ...
        }

Note that MapStringToValuePtr inherits all members from the instantiated map, and can be used like a map itself. In addition, it now provides the convenient () operator for read-only access.

Container Encapsulation

It turns out that it is problematic to do iterations and alterations of STL maps across boundaries of shared and dynamically linked libraries (DLL's). For instance, one would want to create a map in one shared library, and iterate over its entries in another one. This may badly fail in particular under Windows with segmentation faults, read this official article http://support.microsoft.com/kb/172396 about the cause of this problem.

The recommended solution is to provide methods to wrap the required functionality of the STL object.

Therefore we need to hide the maps, and iterators, within one compilation unit (i.e. a shared library). It is fine to have maps in a header file, but they must not be accessed from the outside. An object's header file .hpp with a class definition (including the Windows API statement) therefore looks like this:

class   MY_API MapStringToValuePtr
{
        typedef map<string, RefPtr<Value> > MapStringToValuePtr_t;

        MapStringToValuePtr_t myMap;

public:
        ~MapStringToValuePtr();

        RefPtr<Value> operator[](const string&s);
        RefPtr<Value> operator()(const string&s) const;
};

This class definition fully capsules the STL map and its iterator function. The corresponding .cpp file contains the definitions of these functions:

MapStringToValuePtr::~MapStringToValuePtr()
{}

RefPtr<Value> MapStringToValuePtr::operator[](const string&s)
{
        return myMap[ s ];
}

RefPtr<Value> MapStringToValuePtr::operator()(const string&s) const
{
MapStringToValuePtr_t::const_iterator it = find(s);
        if (it == end() )
                return NullPtr()
        return it->second;
}

Iterator Concept

With an encapsuled STL container, we can't directly use these nifty STL iterators outside the shared library where the map was defined. The alternative are Iterator Objects that provide virtual callback functions. This is slower than using STL iterators, but safe to do accross shared library and DLL boundaries.

The iteration over all elements of a map (or general STL container) also needs to be capsuled, which is done by introducing abstract iterator objects in the class:

class   MY_API MapStringToValuePtr
{
        typedef map<string, RefPtr<Value> > MapStringToValuePtr_t;

        MapStringToValuePtr_t myMap;

public:
        ~MapStringToValuePtr();

        struct  iterator
        {
                virtual ~iterator() = 0;

                bool apply(const string&key, const RefPtr<Value>&value) = 0;
        };

        int iterate(iterator&it);
};

The iterate() member function will (usually) count the number of successful iterations:

int MapStringToValuePtr::iterate(iterator&IteratorObject)
{
int     Count = 0;
        for(MapStringToValuePtr_t::iterator it = myMap.begin(); it != myMap.end(); it++)
        {
                if (!IteratorObject.apply( it->first, it->second) )
                        break;

                Count++;
        }
        return Count;
}

Note that in this example the iterator object may modify the elements of a map. There may also be a constant, read-only version of such an iterator object, as well as other operations. However, modifyable iteration is the most frequent operation, and it is usually just this iteration that is available for most objects.

Upon usage, the user needs to define a class to be derived for iteration, with the abstract member function apply() to be overloaded. Such a class may well be defined just locally within a function, a not very much known C++ feature:

void    myfunction(MapStringToValuePtr&MyMap)
{
        struct It : MapStringToValuePtr::iterator
        {
                bool apply(const string&key, const RefPtr<Value>&value)
                {
                        //... do something with key and value ...
                        return true;
                }
        };
It      MyLocalIterator;
        MyMap.iterate( MyLocalIterator );       
}

This is the dll-safe encapsulated version of the aforementioned STL iteration over all members of the object. It is slightly more effortsome than using STL iterators directly, and slower as it uses virtual functions, but solves the problem of segmentation faults when used accross shared libraries. In some cases, the definition of the map may be completely removed from the class definition, which then becomes independent from the STL header files via an opaque pointer http://en.wikipedia.org/wiki/Opaque_pointer , following the PIMPL idiom.

Note that additional arguments can be passed to the iterator object as data members:

void    myfunction(MapStringToValuePtr&MyMap, int param)
{
        struct It : MapStringToValuePtr::iterator
        {
                int     param;

                bool apply(const string&key, const RefPtr<Value>&value)
                {
                        //... do something with param, key and value ...
                        return true;
                }
        };
It      MyLocalIterator;
        MyLocalIterator.param = param;
        MyMap.iterate( MyLocalIterator );       
}

Also, the iterator object may provide results;

string myfunction(MapStringToValuePtr&MyMap, int param)
{
        struct It : MapStringToValuePtr::iterator
        {
                int     param;
                string output;

                bool apply(const string&key, const RefPtr<Value>&value)
                {
                        //
                        //... do something with param, key and value ...
                        //    like concatenating all keys that have a value
                        //
                        if (value)
                                output += key;

                        return true;
                }
        };
It      MyLocalIterator;
        MyLocalIterator.param = param;
        MyMap.iterate( MyLocalIterator );
        return MyLocalIterator.output;
}

It is also possible to derive a child iterator object from more than one iterator object by multiple inheritance. The iterate() member function of more than one iteratable object may then be applied to the same iterator object.

---