Differences with standard maps

| Home | Libraries | People | FAQ | More

### Differences with standard maps

#### Insertion

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.

#### iterator::value_type

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

#### operator[] and at()

`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

#### Complexity of operations

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