Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Differences with standard maps

Insertion
iterator::value_type
operator[] and at()
Complexity of operations

Remember that a map can be interpreted as a relation between two collections. In bimaps we have the freedom to change both collection types, imposing constrains in each of them. Some insertions that we give for granted to success in standard maps fails with bimaps. For example:

bimap<int,std::string> bm;

bm.left.insert(1,"orange");
bm.left.insert(2,"orange"); // No effect! returns make_pair(iter,false)

The insertion will only succeed if it is allowed by all views of the bimap. In the next snippet we define the right collection as a multiset, when we try to insert the same two elements the second insertion is allowed by the left map view because both values are different and it is allowed by the right map view because it is a non-unique collection type.

bimap<int, multiset_of<std::string> > bm;

bm.left.insert(1,"orange");
bm.left.insert(2,"orange"); // Insertion succeed!

If we use a custom collection of relation type, the insertion has to be allowed by it too.

The relations stored in the Bimap will not be in most cases modifiable directly by iterators because both sides are used as keys of key-based sets. When a bimap<A,B> left view iterator is dereferenced the return type is signature-compatible with a std::pair< const A, const B >. However there are some collection types that are not key_based, for example list_of. If a Bimap uses one of these collection types there is no problem with modifying the data of that side. The following code is valid:

typedef bimap< int, list_of< std::string > > bm_type;
bm_type bm;
bm.insert( bm_type::relation( 1, "one" ) );
...
bm.left.find(1)->second = "1"; // Valid

In this case, when the iterator is dereferenced the return type is signature-compatible with a std::pair<const int, std::string>.

The following table shows the constness of the dereferenced data of each collection type of:

Side collection type

Dereferenced data

set_of

constant

multiset_of

constant

unordered_set_of

constant

unordered_multiset_of

constant

list_of

mutable

vector_of

mutable

unconstrained_set_of

mutable

Here are some examples. When dereferenced the iterators returns a type that is signature-compatible with these types.

Bimap type

Signature-compatible types

bimap<A,B>

iterator -> relation<const A,const B>

left_iterator -> pair<const A,const B>

right_iterator -> pair<const B,const A>

bimap<multiset_of<A>,unordered_set_of<B> >

iterator -> relation<const A,const B>

left_iterator -> pair<const A,const B>

right_iterator -> pair<const B,const A>

bimap<set_of<A>,list_of<B> >

iterator -> relation<const A,B>

left_iterator -> pair<const A,B>

right_iterator -> pair<B,const A>

bimap<vector_of<A>,set_of<B> >

iterator -> relation<A,const B>

left_iterator -> pair<A,const B>

right_iterator -> pair<const B,A>

bimap<list_of<A>,unconstrained_set_of<B> >

iterator -> relation<A,B>

left_iterator -> pair<A,B>

right_iterator -> pair<B,A>

set_of and unordered_set_of map views overload operator[] to retrieve the associated data of a given key only when the other collection type is a mutable one. In these cases it works in the same way as the standard.

bimap< unorderd_set_of< std::string>, list_of<int> > bm;

bm.left["one"] = 1; // Ok

The standard defines an access function for map and unordered_map:

const data_type & at(const key_type & k) const;
      data_type & at(const key_type & k);

These functions look for a key and returns the associated data value, but throws a std::out_of_range exception if the key is not found.

In bimaps the constant version of these functions is given for set_of and unorderd_set_of map views independently of the other collection type. The mutable version is only provided when the other collection type is mutable.

The following examples shows the behaviour of at(key)

Go to source code

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

try
{
    bm.left.at("one") = 1; // throws std::out_of_range
}
catch( std::out_of_range & e ) {}

assert( bm.empty() );

bm.left["one"] = 1; // Ok

assert( bm.left.at("one") == 1 ); // Ok

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

bm.right[1] = "one"; // compilation error

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

assert( bm.right.at(1) == "one" ); // Ok

try
{
    std::cout << bm.right.at(2); // throws std::out_of_range
}
catch( std::out_of_range & e ) {}

bm.right.at(1) = "1"; // compilation error

The complexity of some operations is different in bimaps. Read the reference to find the complexity of each function.


PrevUpHomeNext