Boost Libraries that work well with Boost.Bimap

| Home | Libraries | People | FAQ | More

### Boost Libraries that work well with Boost.Bimap

#### Introduction

Name | Description | author | Purpose
--- | --- | --- | ---
Boost.Serialization | Serialization for persistence and marshalling | Robert Ramey | Serialization support for bimap containers and iterators
Boost.Assign | Filling containers with constant or generated data has never been easier | Thorsten Ottosen | Help to fill a bimap or views of it
Boost.Hash | A TR1 hash function object that can be extended to hash user defined types | Daniel James | Default hashing function
Boost.Lambda | Define small unnamed function objects at the actual call site, and more | from Jaakko Järvi, Gary Powell | Functors for modify, range, lower_bound and upper_bound
Boost.Range | A new infrastructure for generic algorithms that builds on top of the new iterator concepts | Thorsten Ottosen | Range based algorithms
Boost.Foreach | BOOST_FOREACH macro for easily iterating over the elements of a sequence | Eric Niebler | Iteration
Boost.Typeof | Typeof operator emulation | Arkadiy Vertleyb, Peder Holt | Using BOOST_AUTO while we wait for C++0x
Boost.Xpressive | Regular expressions that can be written as strings or as expression templates | Eric Niebler | Help to fill a bimap from a string
Boost.PropertyMap | Concepts defining interfaces which map key objects to value objects | Jeremy Siek | Integration with BGL

#### Boost.Serialization

A bimap can be archived and retrieved by means of the Boost.Serialization Library. Both regular and XML archives are supported. The usage is straightforward and does not differ from that of any other serializable type. For instance:

Go to source code

    typedef bimap< std::string, int > bm_type;

    // Create a bimap and serialize it to a file
    {
        bm_type bm;
        bm.insert( bm_type::value_type("one",1) );
        bm.insert( bm_type::value_type("two",2) );

        std::ofstream ofs("data");
        boost::archive::text_oarchive oa(ofs);

        oa << const_cast<const bm_type&>(bm);

        const bm_type::left_iterator left_iter = bm.left.find("two");
        oa << left_iter;

        const bm_type::right_iterator right_iter = bm.right.find(1);
        oa << right_iter;
    }

    // Load the bimap back
    {
        bm_type bm;

        std::ifstream ifs("data", std::ios::binary);
        boost::archive::text_iarchive ia(ifs);

        ia >> bm;

        assert( bm.size() == 2 );

        bm_type::left_iterator left_iter;
        ia >> left_iter;

        assert( left_iter->first == "two" );

        bm_type::right_iterator right_iter;
        ia >> right_iter;

        assert( right_iter->first == 1 );
    }

| We must do a const cast because Boost.Serialization archives only save const objects. Read Boost.Serializartion docs for the rationale behind this decision
| We can only serialize iterators if the bimap was serialized first. Note that the const cast is not requiered here because we create our iterators as const.

Serialization capabilities are automatically provided by just linking with the appropriate Boost.Serialization library module: it is not necessary to explicitly include any header from Boost.Serialization, apart from those declaring the type of archive used in the process. If not used, however, serialization support can be disabled by globally defining the macro BOOST_BIMAP_DISABLE_SERIALIZATION. Disabling serialization for Boost.MultiIndex can yield a small improvement in build times, and may be necessary in those defective compilers that fail to correctly process Boost.Serialization headers.

| Warning
Boost.Bimap and Boost.MultiIndex share a lot of serialization code. The macro `BOOST_BIMAP_DISABLE_SERIALIZATION` disables serialization in both libraries. The same happens when `BOOST_MULTI_INDEX_DISABLE_SERIALIZATION` is defined.

Retrieving an archived bimap restores not only the elements, but also the order they were arranged in the views of the container. There is an exception to this rule, though: for unordered sets, no guarantee is made about the order in which elements will be iterated in the restored container; in general, it is unwise to rely on the ordering of elements of a hashed view, since it can change in arbitrary ways during insertion or rehashing --this is precisely the reason why hashed indices and TR1 unordered associative containers do not define an equality operator.

Iterators of a bimap can also be serialized. Serialization of an iterator must be done only after serializing its corresponding container.

#### Boost.Assign

The purpose of this library is to make it easy to fill containers with data by overloading operator,() and operator()(). These two operators make it possible to construct lists of values that are then copied into a container.

These lists are particularly useful in learning, testing, and prototyping situations, but can also be handy otherwise. The library comes with predefined operators for the containers of the standard library, but most functionality will work with any standard compliant container. The library also makes it possible to extend user defined types so for example a member function can be called for a list of values instead of its normal arguments.

Boost.Assign can be used with bimap containers. The views of a bimap are signature-compatible with their standard counterparts, so we can use other Boost.Assign utilities with them.

Go to source code

     typedef bimap< multiset_of< int >, list_of< std::string > > bm_type;

     // We can use assign::list_of to initialize the container.

     bm_type bm = assign::list_of< bm_type::relation >
         ( 1, "one"   )
         ( 2, "two"   )
         ( 3, "three" );

     // The left map view is a multiset, again we use insert

     assign::insert( bm.left )
         ( 4, "four" )
         ( 5, "five" )
         ( 6, "six"  );

     // The right map view is a list so we use push_back here
     // Note the order of the elements in the list!

     assign::push_back( bm.right )
         ( "seven" , 7 )
         ( "eight" , 8 );

     assign::push_front( bm.right )
         ( "nine"  ,  9 )
         ( "ten"   , 10 )
         ( "eleven", 11 );

    // Since it is left_based the main view is a multiset, so we use insert

     assign::insert( bm )
         ( 12, "twelve"   )
         ( 13, "thirteen" );

| Note that `bm_type::relation` has to be used instead of `bm_type::value_type`. Contrary to `value_type`, `relation` type stores the elements as non const, a requirement of `assign::list_of`

#### Boost.Hash

The hash function is the very core of the fast lookup capabilities of the unordered sets: a hasher is just a Unary Function returning an std::size_t value for any given key. In general, it is impossible that every key map to a different hash value, for the space of keys can be greater than the number of permissible hash codes: what makes for a good hasher is that the probability of a collision (two different keys with the same hash value) is as close to zero as possible.

This is a statistical property depending on the typical distribution of keys in a given application, so it is not feasible to have a general-purpose hash function with excellent results in every possible scenario; the default value for this parameter uses Boost.Hash, which often provides good enough results.

Boost.Hash can be extended for custom data types, enabling to use the default parameter of the unordered set types with any user types.

#### Boost.Lambda

The Boost Lambda Library (BLL in the sequel) is a C++ template library, which implements form of lambda abstractions for C++. The term originates from functional programming and lambda calculus, where a lambda abstraction defines an unnamed function. Lambda expressions are very useful to construct the function objects required by some of the functions in a bimap view.

Boost.Bimap defines new placeholders in `<boost/bimap/support/lambda.hpp>` to allow a sounder solution. The placeholders are named _key and _data and both are equivalent to boost::lambda::_1. There are two reasons to include this placeholders: the code looks better with them and they avoid the clash problem between lambda::_1 and boost::_1 from Boost.Bind.

Go to source code

    typedef bimap< std::string, int > bm_type;

    bm_type bm;
    bm.insert( bm_type::value_type("one",1) );
    bm.insert( bm_type::value_type("two",2) );

    bm.right.range( 5 < _key, _key < 10 );

    bm.left.modify_key( bm.left.find("one"), _key = "1" );

    bm.left.modify_data( bm.left.begin(), _data *= 10 );

#### Boost.Range

Boost.Range is a collection of concepts and utilities that are particularly useful for specifying and implementing generic algorithms. Generic algorithms have so far been specified in terms of two or more iterators. Two iterators would together form a range of values that the algorithm could work on. This leads to a very general interface, but also to a somewhat clumsy use of the algorithms with redundant specification of container names. Therefore we would like to raise the abstraction level for algorithms so they specify their interface in terms of Ranges as much as possible.

As Boost.Bimap views are signature-compatible with their standard container counterparts, they are compatible with the concept of a range. As an additional feature, ordered bimap views offer a function named `range` that allows a range of values to be obtained.

If we have some generic functions that accepts ranges:

    template< class ForwardReadableRange, class UnaryFunctor >
    UnaryFunctor for_each(const ForwardReadableRange & r, UnaryFunctor func)
    {
        typedef typename
        boost::range_const_iterator<ForwardReadableRange>::type const_iterator;

        for(const_iterator i= boost::begin(r), iend= boost::end(r); i!=iend; ++i )
        {
            func(*i);
        }

        return func;
    }

    template< class ForwardReadableRange, class Predicate >
    typename boost::range_difference<ForwardReadableRange>::type
        count_if(const ForwardReadableRange & r, Predicate pred)
    {
        typedef typename
        boost::range_const_iterator<ForwardReadableRange>::type const_iterator;

        typename boost::range_difference<ForwardReadableRange>::type c = 0;

        for( const_iterator i = boost::begin(r), iend = boost::end(r); i != iend; ++i )
        {
            if( pred(*i) ) ++c;
        }

        return c;
    }

We can use them with Boost.Bimap with the help of the `range` function.

    struct pair_printer
    {
        pair_printer(std::ostream & o) : os(o) {}
        template< class Pair >
        void operator()(const Pair & p)
        {
            os << "(" << p.first << "," << p.second << ")";
        }
        private:
        std::ostream & os;
    };

    struct second_extractor
    {
        template< class Pair >
        const typename Pair::second_type & operator()(const Pair & p)
        {
            return p.second;
        }
    };

    int main()
    {
        typedef bimap< double, multiset_of<int> > bm_type;

        bm_type bm;
        bm.insert( bm_type::value_type(2.5 , 1) );
        bm.insert( bm_type::value_type(3.1 , 2) );
        //...
        bm.insert( bm_type::value_type(6.4 , 4) );
        bm.insert( bm_type::value_type(1.7 , 2) );

        // Print all the elements of the left map view

        for_each( bm.left, pair_printer(std::cout) );

        // Print a range of elements of the right map view

        for_each( bm.right.range( 2 <= _key, _key < 6 ), pair_printer(std::cout) );

        // Count the number of elements where the data is equal to 2 from a
        // range of elements of the left map view

        count_if( bm.left.range( 2.3 < _key, _key < 5.4 ),
                  bind<int>( second_extractor(), _1 ) == 2 );

        return 0;
    }

Go to source code

#### Boost.Foreach

In C++, writing a loop that iterates over a sequence is tedious. We can either use iterators, which requires a considerable amount of boiler-plate, or we can use the std::for_each() algorithm and move our loop body into a predicate, which requires no less boiler-plate and forces us to move our logic far from where it will be used. In contrast, some other languages, like Perl, provide a dedicated "foreach" construct that automates this process. BOOST_FOREACH is just such a construct for C++. It iterates over sequences for us, freeing us from having to deal directly with iterators or write predicates.

You can use BOOST_FOREACH macro with Boost.Bimap views. The generated code will be as efficient as a std::for_each iteration. Here are some examples:

    typedef bimap< std::string, list_of<int> > bm_type;

    bm_type bm;
    bm.insert( bm_type::value_type("1", 1) );
    bm.insert( bm_type::value_type("2", 2) );
    bm.insert( bm_type::value_type("3", 4) );
    bm.insert( bm_type::value_type("4", 2) );

    BOOST_FOREACH( bm_type::left_reference p, bm.left )
    {
        ++p.second;
    }

    BOOST_FOREACH( bm_type::right_const_reference p, bm.right )
    {
        std::cout << p.first << "-->" << p.second << std::endl;
    }

| We can modify the right element because we have use a mutable collection type in the right side.

You can use it directly with ranges too:

    BOOST_FOREACH( bm_type::left_reference p,
                 ( bm.left.range( std::string("1") <= _key, _key < std::string("3") ) ))
    {
        ++p.second;
    }

    BOOST_FOREACH( bm_type::left_const_reference p,
                 ( bm.left.range( std::string("1") <= _key, _key < std::string("3") ) ))
    {
        std::cout << p.first << "-->" << p.second << std::endl;
    }

Go to source code

#### Boost.Typeof

Once C++0x is out we are going to be able to write code like:

    auto iter = bm.by<name>().find("john");

instead of the more verbose

    bm_type::map_by<name>::iterator iter = bm.by<name>().find("john");

Boost.Typeof defines a macro BOOST_AUTO that can be used as a library solution to the auto keyword while we wait for the next standard.

If we have

    typedef bimap< tagged<std::string,name>, tagged<int,number> > bm_type;
    bm_type bm;
    bm.insert( bm_type::value_type("one"  ,1) );
    bm.insert( bm_type::value_type("two"  ,2) );

The following code snippet

    for( bm_type::map_by<name>::iterator iter = bm.by<name>().begin();
         iter!=bm.by<name>().end(); ++iter)
    {
        std::cout << iter->first << " --> " << iter->second << std::endl;
    }

    bm_type::map_by<number>::iterator iter = bm.by<number>().find(2);
    std::cout << "2: " << iter->get<name>();

can be rewrited as

    for( BOOST_AUTO(iter, bm.by<name>().begin()); iter!=bm.by<name>().end(); ++iter)
    {
        std::cout << iter->first << " --> " << iter->second << std::endl;
    }

    BOOST_AUTO( iter, bm.by<number>().find(2) );
    std::cout << "2: " << iter->get<name>();

Go to source code

#### Boost.Xpressive

Using Boost.Xpressive we can parse a file and insert the relations in a bimap in the same step. It is just amazing the power of four lines of code. Here is an example (it is just beatifull)

    typedef bimap< std::string, int > bm_type;
    bm_type bm;

    std::string rel_str("one <--> 1     two <--> 2      three <--> 3");

    sregex rel = ( (s1= +_w) >> " <--> " >> (s2= +_d) )
    [
        xp::ref(bm)->*insert( construct<bm_type::value_type>(s1, as<int>(s2)) )
    ];

    sregex relations = rel >> *(+_s >> rel);

    regex_match(rel_str, relations);

    assert( bm.size() == 3 );

Go to source code

#### Boost.Property_map

The Boost Property Map Library consists mainly of interface specifications in the form of concepts (similar to the iterator concepts in the STL). These interface specifications are intended for use by implementers of generic libraries in communicating requirements on template parameters to their users. In particular, the Boost Property Map concepts define a general purpose interface for mapping key objects to corresponding value objects, thereby hiding the details of how the mapping is implemented from algorithms.

The need for the property map interface came from the Boost Graph Library (BGL), which contains many examples of algorithms that use the property map concepts to specify their interface. For an example, note the ColorMap template parameter of the breadth_first_search. In addition, the BGL contains many examples of concrete types that implement the property map interface. The adjacency_list class implements property maps for accessing objects (properties) that are attached to vertices and edges of the graph.

The counterparts of two of the views of Boost.Bimap map, the `set` and `unordered_set`, are read-write property maps. In order to use these, you need to include one of the following headers:

    #include <boost/bimap/property_map/set_support.hpp>
    #include <boost/bimap/property_map/unordered_set_support.hpp>

The following is adapted from the example in the Boost.PropertyMap documentation.

Go to source code

    template <typename AddressMap>
    void foo(AddressMap & address_map)
    {
        typedef typename boost::property_traits<AddressMap>::value_type value_type;
        typedef typename boost::property_traits<AddressMap>::key_type key_type;

        value_type address;
        key_type fred = "Fred";
        std::cout << get(address_map, fred);
    }

    int main()
    {
        typedef bimap<std::string, multiset_of<std::string> > Name2Address;
        typedef Name2Address::value_type location;

        Name2Address name2address;
        name2address.insert( location("Fred", "710 West 13th Street") );
        name2address.insert( location( "Joe", "710 West 13th Street") );

        foo( name2address.left );

        return 0;
    }