Easier Usage of the STL Algorithms with Pair Associative Containers (map, hash_map, etc.)

• Download source files - 2.09 Kb

Introduction

Scott Meyers, an acknowledged C++ expert, has advised against using loops and encouraged the use of the STL algorithms in their place, especially when using the STL containers¹. Normally, this makes the purpose of a loop clearer, but sometimes using the algorithms with certain functors and containers can lead to statements that are long and convoluted, with nested functors and templates creating a difficult to read statement.

Using specialized function adaptors can lead to significantly cleaner code while not sacrificing the generic quality of the algorithm. This article presents two specialized function adaptors that work with pair associative containers defined in the STL. These adaptors are an improvement over the fully generic algorithm statement and retain the benefits of algorithms vs. hand written loops.

This article assumes a working knowledge of C++ and some experience with the use of functors, STL algorithms and STL containers. Unless otherwise stated, all types are assumed to be in the std namespace.

STL Algorithm Magic

STL provides what it calls algorithms, essentially specialized loops that allow traversal over generic containers using iterators. Each of these specialized loops is named based on what it does to individual elements of the container it traverses, e.g., for_each simply calls a function, transform outputs the result of a function into another collection, and accumulate adds all the results together. Container types, such as vector or list, provide iterators that allow access to the individual elements, while the algorithm then performs a particular operation to the element.

Each algorithm takes at least one function argument. This function must be defined to take one parameter, the element type contained in the container being iterated over.

// highly simplified example of STL container/iterator/

// algorithm relationship

template <typename Element>
class container {
    typedef iterator<element /> iterator;
    iterator begin();
    iterator end();
    ...
};

// emulates pointer syntax

template <typename Element>
class iterator {
   typedef Element value_type;
   typedef Element* pointer;
   typedef Element& reference;

   value_type operator*()();
   reference operator*()();
   pointer operator->()();
   ...
};

template <typename Iter, typename Func>
void algorithm( Iter begin, Iter end, Func func )
{
  ...
  // every algorithm has a similar function call inside.

  func( *begin ); 
  ...
}

The algorithm dereferences the iterator which has the return type of the element in the container. This finds the function overload that takes either a reference or a value of the element type used in the container.

There is no real magic, just a convention decided upon by the library designers that allows a number of different containers and algorithms to interoperate almost seamlessly.

Function Adaptors

Functions passed to algorithms may only take one parameter. What do you do if you need more information passed to a function, or the operation to be performed is to invoke a method on the objects in a collection? You code a wrapper function. Say you want to add 2 to each element in a vector of ints.

vector<int> my_vec;

void add2( int& number )
{
   number += 2;
}

void some_func( vector<int>& vec )
{
    for_each( vec.begin(), vec.end(), add2 );
}

Now what if you want to add 3 to each integer in the vector? Another wrapper. Even if you had a variable that an addn function referred to, it would be still only useful for integers. What about adding 0.5 to doubles? Another wrapper, but then another variable, etc. You can probably see where this is headed.

Function adaptors are functors that act as normal function calls from a syntactic standpoint but behave semantically identical to some other language construct, such as a method call (mem_fun) or expression (plus). For example, through the use of the mem_fun function adaptor, it is easy enough to call a member function on each element in a container as seen here:

#include <iostream>

#include <list>

#include <algorithm>


using namespace std;

class MyType {
    static int instance_count;
    int instance_id;
public:
    MyType(void) { instance_id = instance_count++; }
    void do_something(void) 
    { 
         cout <<
             "Doing something on instance " 
             << instance_id << endl;
    }
};

int MyType::instance_count = 0;

list<MyType*> my_list;

int main(void)
{
    for( int i = 0; i < 10; ++i ) 
        my_list.push_back( new MyType());

    for_each( my_list.begin(), my_list.end(), 
        mem_fun( &MyType::do_something ));

    return 0;
}

There are function adaptors to accomplish almost anything, such as calling a function with two parameters (bind2nd), and for function composition f(g()) (compose1).

Pair Associative Containers

Pair associative containers such as map and hash_map are containers that have keys and data. Keys of arbitrary type may be used to reference data within the container. Because they use arbitrary keys to reference data, they require two mandatory template parameters, the key and the data types.

template <typename Key, typename Data>
class PairAssociativeContainer {
...
};

Function arguments to algorithms take only one parameter. To allow for this, the pair associative containers define their element type to be a pair of the key and the data type, which means that a function argument to an algorithm using a pair associative container must look like this:

// the declaration for a function argument compatible with

// algorithms and pair associative containers.


template <typename A, typename B>
void some_func( std::pair<A,B> pair );

Needless to say, this is not often expected and therefore makes most potential algorithm function arguments useless.

// familiar month example used 

// mandatory contrived example to show a simple point

// compiled using MinGW gcc 3.2.3 with gcc -c -o file.o 

// file.cpp


#include <string>

#include <ext/hash_map>

#include <iostream>


using namespace std;
// some STL implementations do not put hash_map in std

using namespace __gnu_cxx; 

hash_map<const char*, int> days_in_month;

class MyClass {
    static int totalDaysInYear;
public:
    void add_days( int days ) { totalDaysInYear += days; }
    static void printTotalDaysInYear(void) 
    { 
        cout << "Total Days in a year are " 
            << totalDaysInYear << endl; 
    }
};

int MyClass::totalDaysInYear = 0;

int main(void)
{
    days_in_month["january"] = 31;
    days_in_month["february"] = 28;
    days_in_month["march"] = 31;
    days_in_month["april"] = 30;
    days_in_month["may"] = 31;
    days_in_month["june"] = 30;
    days_in_month["july"] = 31;
    days_in_month["august"] = 31;
    days_in_month["september"] = 30;
    days_in_month["october"] = 31;
    days_in_month["november"] = 30;
    days_in_month["december"] = 31;

    // ERROR: This line doesn't compile.

    accumulate( days_in_month.begin(), days_in_month.end(),
        mem_fun( &MyClass::add_days ));

    MyClass::printTotalDaysInYear();

    return 0;
}

Standard C++ Solutions

The Standard C++ Library defines certain function adaptors, select1st, select2nd and compose1, that can be used to call a single parameter function with either the key or the data element of a pair associative container.

select1st and select2nd do pretty much what their respective names say they do. They return either the first or second parameter from a pair.

compose1 allows the use of functional composition, such that the return value of one function can be used as the argument to another. compose1(f,g) is the same as f(g(x)).

Using these function adaptors, we can use for_each to call our function.

hash_map<string, MyType> my_map;
for_each( my_map.begin(), my_map.end(), 
          compose1( mem_fun( &MyType::do_something ), 
                    select2nd<hash_map<string, 
                    MyType>::value_type>()));

Certainly, this is much better than having to define helper functions for each pair, but it still seems a bit cumbersome, especially when compared with the clarity that a comparable for loop has.

for( hash_map<string, MyType>::iterator i = 
         my_map.begin();
     i != my_map.end(), ++i ) {

     i->second.do_something();
}

Considering it was avoiding the for loop for clarity's sake that inspired the use of the STL algorithms in the first place, it doesn't help the case of algorithms vs. hand written loops that the for loop is more clear and concise.

with_data and with_key

with_data and with_key are function adaptors that strive for clarity while allowing the easy use of the STL algorithms with pair associative containers. They have been parameterized much the same way mem_fun has been. This is not exactly rocket science, but it is quickly easy to see that they are much cleaner than the standard function adaptor expansion using compose1 and select2nd.

Using with_data and with_key, any function can be called and will use the data_type or key_type as the function's argument respectively. This allows hash_map, map, and any other pair associative containers in the STL to be used easily with the standard algorithms. It is even possible to use it with other function adaptors, such as mem_fun.

hash_map<string, IDirect3DVertexBuffer* /> my_vert_buffers;

void ReleaseBuffers(void)
{
    // release the vertex buffers created so far.

    std::for_each( my_vert_buffers.begin(), 
        my_vert_buffers.end(), 
        with_data( boost::mem_fn( 
            &IDirect3DVertexBuffer9::Release )));
}

Here boost::mem_fn is used instead of mem_fun since it recognizes the __stdcall methods used by COM, if the BOOST_MEM_FN_ENABLE_STDCALL macro is defined.

with_data and with_key are defined as follows:

template <typename Result, typename Arg>
struct call_func_with_data_t {

    typedef Result (*Func)(Arg);
    Func f_;

    explicit call_func_with_data_t( Func f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const 
    {
        // to enforce the equality of the data with the 

        //argument type instantiated

        const Arg value = v.second;     

        return f_( value );
    }
};

template <typename Functor>
struct call_class_with_data_t {

    Functor f_;
    typedef typename Functor::result_type Result;
    typedef typename Functor::argument_type Arg;

    explicit call_class_with_data_t( Functor f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const 
    {
        // to enforce the equality of the data with the 

        // argument type instantiated

        const Arg value = v.second;

        return f_( value );
    }
};

template <typename Result, typename Arg>
call_func_with_data_t<Result, Arg> with_data( Result (*f)(Arg) )
{
    return call_func_with_data_t<Result, Arg>( f );
}

template <typename Functor>
call_class_with_data_t<Functor> with_data( Functor f )
{
    return call_class_with_data_t<Functor>( f );
}

template <typename Result, typename Arg>
struct call_func_with_key_t {

    typedef Result (*Func)(Arg);
    Func f_;

    explicit call_func_with_key_t( Func f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const
    {
        // to enforce the equality of the data with the 

        // argument type instantiated

        const Arg value = v.first;

        return f_( value );
    }
};

template <typename Functor>
struct call_class_with_key_t {

    Functor f_;
    typedef typename Functor::result_type Result;
    typedef typename Functor::argument_type Arg;

    explicit call_class_with_key_t( Functor f ) : f_(f) {}
    
    template <typename A, typename B>
    Result operator()( const std::pair<A,B>& v ) const
    {
        // to enforce the equality of the data with the 

        // argument type instantiated

        const Arg value = v.first;

        return f_( value );
    }
};

template <typename Result, typename Arg>
call_func_with_key_t<Result, Arg> with_key( Result (*f)(Arg))
{
    return call_func_with_key_t<Result, Arg>( f );
}

template <typename Functor>
call_class_with_key_t<Functor> with_key( Functor f )
{
    return call_class_with_key_t<Functor>( f );
}

How it works

with_key and with_data have only one difference between them, the element of the pair they extract before calling the function. For this reason, only with_data is explained.

There are two with_data functions, one for function pointers and the other for functors. The compiler overloads which one is called based on the parameter. These each return a specific functor that does the same thing, the difference being the types returned by the operator() function. The one for function pointers (call_func_with_data_t) is able to extract the return type from the template parameters. The functor specific one (call_class_with_data_t) uses the unary_function convention typedefs to determine the argument type (unary_function::argument_type) and return type (unary_function::result_type) of the function passed in.

The operator() method in each functor extracts the second member and calls the function with it. The additional line creating the temporary value is used to make sure that the B type is compatible with the Arg type, since member functions may not be partially specialized.

// this is illegal. Member functions may not be 

// partially specialized.


template <typename Functor>
struct call_class_with_key_t {

    Functor f_;
    typedef typename Functor::result_type Result;
    typedef typename Functor::argument_type Arg;

    explicit call_class_with_key_t( Functor f ) : f_(f) {}
    
    // illegally specialized member function

    template <typename A>
    Result operator()<Arg>( 
        const std::pair<A,Arg>& v ) const
    {
        return f_( v.first );
    }
};

Using the code

Included in the accompanying zip file is the header file call_with.hpp that defines the two function adaptors. The code is released into the public domain and may be used as however seen fit. It is known to compile on Visual C++ 7.1, gcc 3.2.3, and Comeau 4.3.3.

Conclusion

The with_* function adaptors are not revolutionary, but do help clarify the usage of an algorithm with one of the pair associative containers. Their names state their purpose more clearly than the compose1/select2nd combination. Sometimes, in an effort to be more generic, it pays to be a little more specific.

The author would like to thank Eric Dixon, John Olsen and Nate Robins for their comments and corrections.

References

[1] Meyers, Scott. STL Algorithms vs Hand Written Loops.

History

• 12/21/03 - Initial writing.
• 1/18/04 - Initial posting.