Useful functions

| Home | Libraries | People | FAQ | More

### Useful functions

#### Projection of iterators

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;

#### replace and modify

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 );
    }

| `it` is still valid here, and the bimap was left unchanged

`replace` functions performs this substitution in such a manner that:

- The complexity is constant time if the changed element retains its original order with respect to all views; it is logarithmic otherwise.
- Iterator and reference validity are preserved.
- The operation is strongly exception-safe, i.e. the `bimap` remains unchanged if some exception (originated by the system or the user's data types) is thrown.

`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 );
    }

| `it` is not longer valid and `(1,"1")` is removed from the bimap

#### Retrieval of ranges

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_type` is a handy typedef equal to `std::pair<iterator,iterator>`. `const_range_type` is provided too, and it is equal to `std::pair<const_iterator,const_iterator>`
| _key is a Boost.Lambda placeholder. To use it you have to include `<boost/bimap/support/lambda.hpp>`

`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)

| This is equivalent to std::make_pair(s.begin(),s.end())

Go to source code