Click here to Skip to main content
Click here to Skip to main content

Wrapper iterator class for STL associative containers and tuple sequence containers

, 2 May 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
A C++ librairy to facilitate the usage of STL algorithms and BOOST_FOREACH with Pair Associative Containers (map, unordered_map) and tuple sequence containers.

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 Nth element in a sequence tuple container
  • make_tuple_range: functor creating a pair of tuple_iters pointing at a tuple Nth 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.

License

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

Share

About the Author

Nicolas Witczak
Software Developer (Senior) self employed
France France
I am an electronic/software engineer.
I work as a self employed developer contracting since 1998 on C++ and .NET technologies mostly in finance / banking environments.

Comments and Discussions

 
Generaliterator for associative containers Pinmembergeoyar6-Apr-10 12:59 
GeneralMy vote of 2 PinmemberJon Summers5-Apr-10 22:31 
Generalmacro error PinmemberNicolas Witczak5-Apr-10 22:30 
Generaltry avoiding commas Pinmemberemilio_grv5-Apr-10 21:23 
GeneralRe: try avoiding commas PinmemberAjay Vijayvargiya30-Apr-10 2:38 
GeneralRe: try avoiding commas Pinmemberemilio_grv30-Apr-10 5:25 
GeneralRe: try avoiding commas PinmemberAjay Vijayvargiya30-Apr-10 7:21 
GeneralAbout BOOST_FOREACH and associative containers PinmemberAionlyl5-Apr-10 18:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141223.1 | Last Updated 3 May 2010
Article Copyright 2010 by Nicolas Witczak
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid