Boost C++ Libraries

Iterators can be projected to any of the three views of the bimap. A bimap provides three member functions to cope with projection: project_left, project_right and project_up, with projects iterators to the left map view, the right map view and the collection of relations view. These functions take any iterator from the bimap and retrieve an iterator over the projected view pointing to the same element.

Here is an example that uses projection:

Go to source code

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

bm_type bm;
bm.insert( bm_type::value_type("John" ,34) );
bm.insert( bm_type::value_type("Peter",24) );
bm.insert( bm_type::value_type("Mary" ,12) );

// Find the name of the next younger person after Peter

bm_type::left_const_iterator name_iter = bm.left.find("Peter");

bm_type::right_const_iterator years_iter = bm.project_right(name_iter);

++years_iter;

std::cout << "The next younger person after Peter is " << years_iter->second;

These functions are members of the views of a bimap that are not founded in their standard counterparts.

The replace family member functions performs in-place replacement of a given element as the following example shows:

Go to source code

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

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

// Replace (1,"one") with (1,"1") using the right map view
{
    bm_type::right_iterator it = bm.right.find("one");

    bool successful_replace = bm.right.replace_key( it, "1" );

    assert( successful_replace );
}

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

// Fail to replace (1,"1") with (1,"two") using the left map view
{
    assert( bm.size() == 2 );

    bm_type::left_iterator it = bm.left.find(1);

    bool successful_replace = bm.left.replace_data( it, "two" );

    assert( ! successful_replace );
    assert( bm.size() == 2 );
}

replace functions performs this substitution in such a manner that:

replace functions are powerful operations not provided by standard STL containers, and one that is specially handy when strong exception-safety is required.

The observant reader might have noticed that the convenience of replace comes at a cost: namely the whole element has to be copied twice to do the updating (when retrieving it and inside replace). If elements are expensive to copy, this may be quite a computational cost for the modification of just a tiny part of the object. To cope with this situation, Boost.Bimap provides an alternative updating mechanism: modify functions.

modify functions accepts a functor (or pointer to function) taking a reference to the data to be changed, thus eliminating the need for spurious copies. Like replace functions, modify functions does preserve the internal orderings of all the indices of the bimap. However, the semantics of modify functions are not entirely equivalent to replace functions. Consider what happens if a collision occurs as a result of modifying the element, i.e. the modified element clashes with another with respect to some unique view. In the case of replace functions, the original value is kept and the method returns without altering the container, but modify functions cannot afford such an approach, since the modifying functor leaves no trace of the previous value of the element. Integrity constraints thus lead to the following policy: when a collision happens in the process of calling a modify functions, the element is erased and the method returns false. This difference in behavior between replace and modify functions has to be considered by the programmer on a case-by-case basis.

Boost.Bimap defines new placeholders named _key and _data to allow a sounder solution. You have to include <boost/bimap/support/lambda.hpp> to use them.

Go to source code

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

// Modify (1,"one") to (1,"1") using the right map view
{
    bm_type::right_iterator it = bm.right.find("one");

    bool successful_modify = bm.right.modify_key( it , _key = "1" );

    assert( successful_modify );
}

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

// Fail to modify (1,"1") to (1,"two") using the left map view
{
    assert( bm.size() == 2 );

    bm_type::left_iterator it = bm.left.find(1);

    bool successful_modify = bm.left.modify_data( it, _data = "two" );

    assert( ! successful_modify );
    assert( bm.size() == 1 );
}

Standard lower_bound and upper_bound functions can be used to lookup for all the elements in a given range.

Suppose we want to retrieve the elements from a bimap<int,std::string> where the left value is in the range [20,50]

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

// ...

bm_type::left_iterator iter_first  = bm.left.lower_bound(20);
bm_type::left_iterator iter_second = bm.left.upper_bound(50);

// range [iter_first,iter_second) contains the elements in [20,50]

Subtle changes to the code are required when strict inequalities are considered. To retrieve the elements greater than 20 and less than 50, the code has to be rewritten as

bm_type::left_iterator iter_first  = bm.left.upper_bound(20);
bm_type::left_iterator iter_second = bm.left.lower_bound(50);

// range [iter_first,iter_second) contains the elements in (20,50)

To add to this complexity, the careful programmer has to take into account that the lower and upper bounds of the interval searched be compatible: for instance, if the lower bound is 50 and the upper bound is 20, the iterators iter_first and iter_second produced by the code above will be in reverse order, with possibly catastrophic results if a traversal from iter_first to iter_second is tried. All these details make range searching a tedious and error prone task.

The range member function, often in combination with lambda expressions, can greatly help alleviate this situation:

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

// ...

bm_type::left_range_type r;

r = bm.left.range( 20 <= _key, _key <= 50 ); // [20,50]

r = bm.left.range( 20 <  _key, _key <  50 ); // (20,50)

r = bm.left.range( 20 <= _key, _key <  50 ); // [20,50)

range simply accepts predicates specifying the lower and upper bounds of the interval searched. Please consult the reference for a detailed explanation of the permissible predicates passed to range.

One or both bounds can be omitted with the special unbounded marker:

r = bm.left.range( 20 <= _key, unbounded ); // [20,inf)

r = bm.left.range( unbounded , _key < 50 ); // (-inf,50)

r = bm.left.range( unbounded , unbounded ); // (-inf,inf)

Go to source code