Wrapper iterator class for STL associative containers and tuple sequence containers

• Download source code - 2.79 KB
• Download demo - 41 KB

Context

Modern C++ programming relies heavily on the STL and boost libraries, parts of which are now in the standard. STL separates algorithms from the container, thanks to the iterator pattern. The use of ready made algorithms is encouraged over a crafted for loop. Containers are themselves presented as sequence containers and associative containers. One of the sequence containers is the std::vector<T> class, and an associative one is the std::map<T,V> class. Associative containers are basically sequence containers on std::pair<T,V> with extra search capabilities. Unlike their .NET counterparts, they give no straight access to the underlying key collection or the values collection. A tuple container iterator adaptor has been added on a later revision.

Presentation

Motivation: the BOOST_MACRO

The BOOST_FOREACH macro conveniently mimics the foreach keyword in C# except for the associative containers. For example:

using namespace codeproject ;
using namespace std ;
vector< int >  avector ;
//...
BOOST_FOREACH( int ival , avector )
{
    // do something with ival
}

BOOST_FOREACH is quite versatile in the way it supports container, iterator pairs, native array; unfortunately, BOOST_FOREACH doesn't work quite as well with associative containers due to its sensibility to extra commas. For example:

using namespace std ;
map< int , int >  amap  ;
//...
BOOST_FOREACH( pair< int , int >& valcur , amap )
// doesn't compile

Motivation: using algorithms

Most of the time, boost::bind and boost::lambda provide the necessary glue to adapt STL algorithms to our containers, but sometimes they don't. Considering the following code fragment:

using namespace std ;
using namespace boost ;

typedef vector< tuple< int , const char* > >  tuple_coll_t ;
typedef pair< tuple_coll_t::iterator , tuple_coll_t::iterator >  tuple_iter_pair_t ;
tuple_coll_t  acoll ; 
// insert sorted elements
    
// would provide log search time (doesn't compile)
tuple_iter_pair_t find_number_3_label = equal_range( acoll.begin() ... );

The preferred way to find the label attached to integer 3 in a sorted container would be to use the std::equal_range algorithm, but this algorithm doesn't provide a functor variant; the std::find_if algorithm can be used instead, but requires to write an adaptor function and has linear search time. The tuple feature doesn't get as handy as it should be.

Usage

The provided library resides in a single header file: container_util.h (no lib required). It provides three template iterator classes that expose key sequences, value sequences, and a tuple field sequence, along with the creator make_.. functions. The code resides in the codeproject namespace. The iterator classes are:

• key_iterator: an iterator class on the const key of an associative container
• value_iterator: an iterator class on the values (or const values) of an associative container
• tuple_iter: an iterator class on the tuple member field (or the const member field) of a tuple sequence container

The helper template functions are:

• make_key_iterator: create an instance of key_iterator
• make_val_iterator: create an instance of val_iterator
• make_key_range: create a pair of key_iterators pointing at the beginning and end of an associative container
• make_val_range: create a pair of value_iterators pointing at the beginning and end of an associative container
• make_tuple_iterator: functor creating an instance of tuple_iter pointing at a tuple N^th element in a sequence tuple container
• make_tuple_range: functor creating a pair of tuple_iters pointing at a tuple N^th element at the beginning and end of a sequence tuple container

These helper functions are the most helpful. Example: iterate over the value part of a map:

map< int , std::string >  amap ;
// ...
BOOST_FOREACH( string& sval , make_val_range( amap ) )
{
    // do something with sval
}

The same example with a vector of tuple:

vector< tuple< int , string > >  acoll ; 
//...
BOOST_FOREACH( int ival , make_tuple_range<0>()( acoll ) )
{
    // do something with ival
}

Example: calculate the sum of all keys with an STL numeric algorithm:

map< int , string >  amap ;
// ...
int valsum = accumulate( make_key_iterator( amap.begin() ) , 
                         make_key_iterator( amap.end() ) , 0 ) ;

The same example with a vector of tuple:

vector< tuple< int , string > >  acoll ; 
// ...
int valsum = accumulate( make_tuple_iterator<0>()( acoll.begin() ) , 
                         make_tuple_iterator<0>()( acoll.end() ) , 0 ) ;

Example: applying a user defined function on a map using an STL algorithm:

string format_str_copy( const string& ref );
//...
map< int , string >  amap ;
// ...
transform( make_val_iterator( amap.begin() ) , make_val_iterator( amap.end() ) , 
           make_val_iterator( amap.begin() ) , format_str_copy );

The same example with a list of tuple:

list< tuple< int , string > >  acoll ;
// ...
transform( make_tuple_iterator<1>()( acoll.begin() ) , 
           make_tuple_iterator<1>()( acoll.end() )   , 
           make_tuple_iterator<1>()( acoll.begin() ) , format_str_copy );

Implementation notes

• Constantness is supported, i.e., make_.. return const iterators of the given const_iterator or const collection.
• The tuple_iter name has been chosen instead of tuple_iterator to prevent a possible name clash with boost fusion.
• The methods make_tuple_iterator and make_tuple_range are now implemented as a functor (class implementing the () operator ). This removes the use of the macros MK_TUPLE_ITER and MK_TUPLE_RANGE implemented in the previous version.
• tuple_iter reproduces the original iterator beheavior: bidirectional or random access, const or non-const.

More examples reside in container_util_demo.cpp provided with the source code.

Compatibility

The code requires a reasonably recent version of boost and the C++ compiler. It has been tested under VC8 (Visual Studio 2005), VC9 (Visual Studio 2008) with boost version 1.41, VC9 Express edition (Visual Studio 2008) with boost version 1.39, and under GCC version 4.4.1 with boost 1.42.

Revisions

• 19 April 2010: Changed the namespace to codeproject.
• 28 April 2010: Changed the project name to container_util, added tuple collection adapter.
• 1 May 2010: Improved the tuple collection adapter make_.. functions.

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)