## Contents

`std::map`

is a container that manages (`const key`

, `value`

) pairs and allows for O(log *n*) lookup based on the key. Maps impose the restriction that keys be unique - values, on the other hand, can be repeated.

Sometimes it is desirable to have unicity of values, as well as fast lookups for either type. This kind of container can be modeled as a *bidirectional map* which is entirely symmetric with respect to the two types that compose pairs. In what follows, we'll refer to these types as `from_type`

and `to_type`

.

`bimap`

implements a bidirectional map in the spirit of STL containers. In many respects, `bimap`

behaves as a normal `std::map`

of (`const from_type`

, `const to_type`

) pairs, with the added constraint that unicity of `to_type`

values is preserved. Additionally, the whole set of methods provided by maps (insertion, removal, fast lookup, `operator []`

) is replicated for use with `to_type`

values.

As a small tribute to this superb site, and in order to avoid name clashing, `bimap`

lives in the namespace `codeproject`

. For brevity, we will take the `codeproject::`

prefix for granted in this article.

Using `bimap`

is extremely simple, as this sample shows:

#pragma warning(disable:4503)
#include "bimap.h"
#include <iostream>
#include <string>
using codeproject::bimap;
int main(void)
{
bimap<int,std::string> bm;
bm[1]="Monday";
bm[2]="Tuesday";
bm[3]="Wednesday";
bm[4]="Thursday";
bm[5]="Friday";
bm[6]="Saturday";
bm[7]="Sunday";
std::cout<<"Thursday occupies place #"<<bm["Thursday"]<<
" in the week (european style)"<<std::endl;
return 0;
}

#### Output

Thursday occupies place #4 in the week (european style)

This looks as if a common `std::map`

could have been used until one notices the call `bm["Thursday"]`

, which performs fast access through a `to_type`

value.

The symmetry of `bimap`

imposes some constraints that are not found in `std::maps`

:

bimap<string,int> ranking;
ranking["Tom"]=2;
ranking["Bob"]=3;
ranking["Joe"]=2;
cout<<"First scorer: "<<ranking[1]<<endl;

`bimap_base::duplicate_value`

is thrown whenever an assignment is attempted to a value already present in the `bimap`

: this a consequence of the unicity of values in either side of the container. As for `bimap_base::value_not_found`

, this exception is thrown while trying to access a non-existent key: this behavior differs from that of `std::map`

, which automatically assigns a default value to non-existent keys referred to by `operator []`

; `bimap`

cannot afford this approach since it violates the unicity constraint.

Consider this example:

bimap <int,int> bm;
bm[1]=5;

Since in this case `from_type`

and `to_type`

are the same, we face an ambiguity problem: how can we refer to one or another side of the `bimap`

? The solution is provided by *memberspaces* `from`

and `to`

. We will discuss later in detail the memberspace concept, but the following should make it clear how they can be used to resolve the ambiguity:

bimap <int,int> bm;
bm.from[1]=5;
bm.to[4]=2;

Memberspaces `from`

and `to`

in fact can be used to label all the methods and types of `bimap`

:

bimap <int,int> bm;
bimap <int,int>::from::const_iterator it;
for(it=bm.from.begin();it!=bm.from.end();++it){
cout<<it->first<<"="<<it->second;<<endl;
}

It doesn't hurt to use the memberspaces even when there's no ambiguity. By default, all types and methods with no explicit memberspace declaration are assumed to belong to the `from`

memberspace, which allows to treat a `bimap`

as a regular `std::map`

(save the unicity constraints imposed by bidirectionality). Unlabeled calls are automatically resolved to the `to`

memberspace if no ambiguity exists, as in this example:

bimap<int,string> bm;
bm.find("Hello");

Another interesting aspect of memberspaces `from`

and `to`

is the possibility of passing them around wherever an associative container is expected, as this example shows:

template <typename container>
void dump(const container& c)
{
for(container::const_iterator it=c.begin();it!=c.end();++it){
cout<<it->first<<""<<it->last<<endl;
}
}
bimap<string,string> bm;
dump(bm.from);
dump(bm.to);

Along with *bimap.h*, a test suite is provided that thoroughly checks the correctness of implementation. This suite also serves as a brief guide to the various uses of `bimap`

which are not explained in detail here. It is advisable that you read the suite code and learn how to use `bimap`

using the example. *Note for VC++ users: make sure you set the compiler options /GX and /EHa while building the program.*

`bimap`

has been successfully tested in the following compilers:

- VC++ 6.0sp5
- VC++ 7.0 (aka .NET 2002)
- VC++ 7.1 (aka .NET 2003)
- GNU GCC 3.2, 3.3, 3.4, 3.4.2
- Metrowerks CodeWarrior 8.3

A good deal of effort has been put into making the code as standard-conformant as possible, so chances are it will work for other compilers with no modifications. I'd be most grateful if you try the test suite in your favorite environment and report the results. If only minor tweaks are needed to make `bimap`

work for a particular compiler, porting may be considered in the next version.

### Allocator support

Allocator treatment is not as smooth as it should be. Two difficulties arise:

- VC++ 6.0 does not support
`rebind`

in allocators: This forces some type discrepancies and occasional default assumptions about the actual type of `allocator_type`

. The problem does not show for other compilers.
`swap`

functions assume allocator equivalence (i.e. two allocators of the same type are assumed to be able to manage data allocated by each other): No solution has been found to treat allocator non-equivalence in an exception-safe manner.

When using `std::allocator`

, which is by far the most usual situation, no problems will happen.

### Explicit reference to types from and to

The following sentence does not compile:

codeproject::bimap<int,int>::from* f;

This is not a compiler bug, but a subtlety stemming from the way memberspaces `from`

and `to`

are defined. The correct expression needs the `class`

keyword:

class codeproject::bimap<int,int>::from* f;

The problem appears only when referring to the types `from`

and `to`

: no extra `class`

keyword is needed when using types embedded into those:

codeproject::bimap<int,int>::from::iterator it;

### Hint-driven insertion

For `std::map`

s and other associative containers, the standard requires that hint-driven insertion perform amortized constant time if the hint iterator is immediately before the point where the insertion occurs. Due to a bug in the STL implementation for VC++ 6.0 on which `bimap`

relies internally, a deviant policy is taken: amortized constant time happens when the hint is immediately *after* the insertion point.

The problem is corrected in the STL implementation for VC++ 7.0. Here, `bimap`

guarantees amortized constant-time when the hint is either immediately before or after the insertion point.

In other compilers, the standard rule is followed that the hint should precede the insertion point.

### Global swap functions

This problem only applies to VC++ 6.0 and 7.0. Global `swap`

functions are provided to interchange the contents of two `bimap`

s, optionally through their `from`

or `to`

memberspaces. These functions live in the namespace `codeproject`

. By C++ Koenig lookup rules, the following should be OK:

bimap<int,int> bm1,bm2;
swap(bm1,bm2);

Unfortunately, VC++ does not implement Koenig lookup for non-operator functions, so it is `std::swap`

that is called instead of the piece of code above. Overloading `std::swap`

for `bimap`

s is prohibited by the standard, so the only option is to explicitly qualify `swap`

:

bimap<int,int> bm1,bm2;
codeproject::swap(bm1,bm2);

bimap<
typename from_type, typename to_type,
typename from_compare=std::less<from_type>,
typename to_compare=std::less<to_type>,
typename allocator_type=
std::allocator<direct_pair<const from_type,const to_type> > >

Specifies a bidirectional map of types `from_type`

and `to_type`

. These must be copy-able types, but unlike `std::map`

they don't need to be default constructible. Ordering of values in both sides of the `bimap`

are made according to the predicates of type `from_compare`

and `to_compare`

respectively.

key_type, from::key_type

Synonyms of `from_type`

.

to::key_type

Synonym of `to_type`

.

mapped_type, from::mapped_type, referent_type,
from::referent_type, data_type, from::data_type

Synonyms of `to_type`

.

to::mapped_type, to::referent_type, to::data_type

Synonyms of `from_type`

.

key_compare, from::key_compare

Synonyms of `from_compare`

.

to::key_compare

Synonym of `to_compare`

.

allocator_type, from::allocator_type, to::allocator_type

Synonyms of `allocator_type`

.

value_type, from::value_type

Implementation-specific type convertible to `std::pair<const from_type, const to_type>`

.

to::value_type

Implementation-specific type convertible to `std::pair<const to_type, const from_type>`

.

value_compare, from::value_compare

Implementation-specific functor type that lexicographically compares `value_type`

objects based on `from_compare`

and `to_compare`

(in this order).

to::value_compare

Implementation-specific functor type that lexicographically compares `to::value_type`

objects based on `to_compare`

and `from_compare`

(in this order).

size_type, from::size_type, to::size_type

Synonyms of `allocator_type::size_type`

.

difference_type, from::difference_type, to::difference_type

Synonyms of `allocator_type::difference_type`

.

pointer, from::pointer

Synonyms of `value_type *`

.

to::pointer

Synonym of `to::value_type *`

.

const_pointer, from::const_pointer

Synonyms of `const value_type *`

.

to::const_pointer

Synonym of `const to::value_type *`

.

reference, from::reference

Synonyms of `value_type&`

.

to::reference

Synonym of `to::value_type&`

.

const_reference, from::const_reference

Synonyms of `const value_type&`

.

to::const_reference

Synonym of `const to::value_type&`

.

iterator, from::iterator

Bidirectional iterator to elements of type `value_type`

.

to::iterator

Bidirectional iterator to elements of type `to::value_type`

.

const_iterator, from::const_iterator

Bidirectional iterator to elements of type `const value_type`

.

to::const_iterator

Bidirectional iterator to elements of type `const to::value_type`

.

reverse_iterator, from::reverse_iterator

Bidirectional reverse iterator to elements of type `value_type`

.

to::reverse_iterator

Bidirectional reverse iterator to elements of type `to::value_type`

.

const_reverse_iterator, from::const_reverse_iterator

Bidirectional reverse iterator to elements of type `const value_type`

.

to::const_reverse_iterator

Bidirectional reverse iterator to elements of type `const to::value_type`

.

inv_bimap

This member `typedef`

identifies a `bimap`

type with `from_type`

and `to_type`

reversed. For example, `codeproject::bimap<int,double>::inv_bimap`

is equivalent to `codeproject::bimap<double,int>`

.

**VC++ 6.0**: Due to limitations in allocator support in VC++ 6.0, `inv_bimap`

assumes a `std::allocator`

as the allocator type, rather than rebinding from the allocator type of the `bimap`

where it is defined.

codeproject::bimap_base::duplicate_value: public std::logic_error

Thrown by certain methods when an insertion is attempted that violates the unicity of `from_type`

and `to_type`

values.

codeproject::bimap_base::value_not_found: public std::logic_error

Thrown by the various forms of `operator[]`

when the element specified is not present in the `bimap`

.

explicit bimap(
const from_compare& from_comp=from_compare(),
const to_compare& to_comp=to_compare(),
const allocator_type& al=allocator_type())

Constructs an empty `bimap`

with the parameters supplied for comparison and allocation, or the default values if not provided.

**Complexity** constant time.

bimap(const bimap& r)

Constructs a copy of a given `bimap`

. Comparison and allocation objects are copied from the given `bimap`

as well.

**Complexity** O(*n* log *n*) in general, O(*n*) if `r`

is monotonous (i.e. `x<y`

implies `r[x]<r[y]`

for every (`x`

, `r[x]`

), (`y`

, `r[y]`

) in `r`

).

explicit bimap(const inv_bimap& r)

Constructs a map from a given `inv_bimap`

.

**Complexity** O(*n* log *n*) in general, O(*n*) if `r`

is monotonous (i.e. `x<y`

implies `r[x]<r[y]`

for every (`x`

, `r[x]`

), (`y`

, `r[y]`

) in `r`

).

template <typename it_type> bimap(
it_type first,it_type last,
const from_compare& from_comp=from_compare(),
const to_compare& to_comp=to_compare(),
const allocator_type& al=allocator_type())

Constructs a map and fills it with the values in the range [`first`

, `last`

). Comparison and allocator objects can additionally be specified.

#### Throws

`duplicate_value`

when an insertion is attempted where either the `from_type`

or the `to_type`

value were already present in the `bimap`

.

**Complexity** O(*n* log *n*) in general, half the time if [`first`

, `last`

) is ordered with respect to their `first`

values, O(*n*) if additionally the interval is monotonous (i.e. `it1->first<it2->first`

implies `it1->second<it2->second`

for every `it1`

, `it2`

in [`first`

, `last`

)).

~bimap()

Destructs the `bimap`

.

**Complexity** O(*n*)

bimap& operator=(const bimap& r)

Assigns the given `bimap`

to the current `bimap`

. The original comparison and allocator objects are preserved. *Note: allocator equivalence is assumed*.

**Complexity** O(*n* log *n*) in general, O(*n*) if `r`

is monotonous (i.e. `x<y`

implies `r[x]<r[y]`

for every (`x`

, `r[x]`

), (`y`

, `r[y]`

) in `r`

).

class from& from.operator=(const from& r)

This is equivalent to calling `operator=(owner)`

, where `owner`

is the `bimap`

to which `r`

belongs.

**Complexity** O(

*n* log

*n*) in general, O(

*n*) if

`r`

is monotonous (i.e.

`x<y`

implies

`r[x]<r[y]`

for every (

`x`

,

`r[x]`

), (

`y`

,

`r[y]`

) in

`r`

).

class to& to.operator=(const to& r)

This is equivalent to calling `operator=(owner)`

, where `owner`

is the `bimap`

to which `r`

belongs.

**Complexity** O(

*n* log

*n*) in general, O(

*n*) if

`r`

is monotonous (i.e.

`x<y`

implies

`r[x]<r[y]`

for every (

`x`

,

`r[x]`

), (

`y`

,

`r[y]`

) in

`r`

).

bool operator==(const bimap& r) const
bool operator!=(const bimap& r) const
bool operator< (const bimap& r) const
bool operator> (const bimap& r) const
bool operator<=(const bimap& r) const
bool operator>=(const bimap& r) const
bool from.operator==(const from& r) const
bool from.operator!=(const from& r) const
bool from.operator< (const from& r) const
bool from.operator> (const from& r) const
bool from.operator<=(const from& r) const
bool from.operator>=(const from& r) const

Comparison of `bimap`

s is done lexicographically with respect to the `from_type`

values of their elements.

**Complexity** O(*n*), where *n* is the minimum of the lengths of the `bimap`

s being compared.

bool to.operator==(const to& r) const
bool to.operator!=(const to& r) const
bool to.operator< (const to& r) const
bool to.operator> (const to& r) const
bool to.operator<=(const to& r) const
bool to.operator>=(const to& r) const

Comparison of `bimap`

s is done lexicographically with respect to the `to_type`

values of their elements. This is in general not equivalent to the comparisons performed according to `from_type`

values.

**Complexity** O(*n*), where *n* is the minimum of the lengths of the `bimap`

s being compared.

iterator begin()
from::iterator from.begin()

Return an `iterator`

pointing to the beginning of the `bimap`

(as seen from the `from_type`

side). `const`

versions are provided returning the corresponding `const_iterator`

.

**Complexity** constant time

to::iterator to.begin()

Returns a `to::iterator`

pointing to the beginning of the `bimap`

(as seen from the `to_type`

side). A `const`

version is provided returning the corresponding `to::const_iterator`

.

**Complexity** constant time

iterator end()
from::iterator from.end()

Return an `iterator`

pointing to the end of the `bimap`

(as seen from the `from_type`

side). `const`

versions are provided returning the corresponding `const_iterator`

.

**Complexity** constant time

to::iterator to.end()

Returns a `to::iterator`

pointing to the end of the `bimap`

(as seen from the `to_type`

side). A `const`

version is provided returning the corresponding `to::const_iterator`

.

**Complexity** constant time

reverse_iterator rbegin()
from::reverse_iterator from.rbegin()

Returns a `reverse_iterator`

pointing just beyond the end of the `bimap`

(as seen from the `from_type`

side). `const`

versions are provided returning the corresponding `const_reverse_iterator`

.

**Complexity** constant time

to::reverse_iterator to.rbegin()

Returns a `to::reverse_iterator`

pointing just beyond the end of the `bimap`

(as seen from the `to_type`

side). A `const`

versions is provided returning the corresponding `to::const_reverse_iterator`

.

**Complexity** constant time

reverse_iterator rend()
from::reverse_iterator from.rend()

Returns a `reverse_iterator`

pointing to the first element of the `bimap`

(as seen from the `from_type`

side). `const`

versions are provided returning the corresponding `const_reverse_iterator`

.

**Complexity** constant time

to::reverse_iterator to.rend()

Returns a `to::reverse_iterator`

pointing to the first element of the `bimap`

(as seen from the `to_type`

side). A `const`

versions is provided returning the corresponding `to::const_reverse_iterator`

.

**Complexity** constant time

size_type size() const
from::size_type from.size() const
to::size_type to.size() const

Returns the number of elements in the map.

**Complexity** constant time

size_type max_size() const
from::size_type from.max_size() const
to::size_type to.max_size() const

Return the length of the longest `bimap`

possible.

**Complexity** constant time

bool empty() const
bool from.empty() const
bool to.empty() const

Indicate whether the map is empty.

**Complexity** constant time

allocator_type get_allocator() const
from::allocator_type from.get_allocator() const
to::allocator_type to.get_allocator() const

Returns a copy of the `allocator_type`

object kept by the `bimap`

.

**Complexity** constant time

*(implementation specific return type)*
operator[](const key_type& key)
*(implementation specific return type)*
from.operator[](const from::key_type& key)

`operator[]`

behaves like it does for `std::map`

s. The object returned is implementation-specific, but it provides an assignment operator and automatic conversion to `to_type&`

so that the following sentences can be written:

bimap<int,string> bm;
bm[1]="Hello";
string s=bm[1];

`const`

versions of this operator are provided.

In some situations, the compiler is unable to automatically perform the conversion to `to_type&`

: in such cases, an auxiliary `get()`

method can be resorted to:

bimap<int,string> bm;
string s=bm[1].get();

#### Throws

`duplicate_value`

when an assignment is attempted to a `to_type`

already contained in the `bimap`

. No throws occur in the exceptional case when a `from_type`

value is reassigned the same `to_type`

value that is was bound to.
`value_not_found`

when the `to_type`

value is consulted of a `from_type`

value not present in the `bimap`

.

**Complexity of lookup** O(log *n*)

**Complexity of assignment** O(log *n*) (twice the time of lookup)

*(implementation specific return type)*
operator[](const to::key_type& key)*
*(implementation specific return type)*
to.operator[](const to::key_type& key)

^{*}Only available if `from_type!=to_type`

.

`operator[]`

behaves like it does for `std::map`

s. The object returned is implementation-specific, but it provides an assignment operator and automatic conversion to `from_type&`

so that the following sentences can be written:

bimap<int,string> bm;
bm["Hello"]=1;
int i=bm["Hello"];

`const`

versions of this operator are provided.

In some situations, the compiler is unable to automatically perform the conversion to `from_type&`

: in such cases, an auxiliar `get()`

method can be resorted to:

bimap<int,string> bm;
int i=bm["Hello"].get();

#### Throws

`duplicate_value`

when an assignment is attempted to a `from_type`

already contained in the `bimap`

. No throws occur in the exceptional case when a `to_type`

value is reassigned the same `from_type`

value that is was bound to.
`value_not_found`

when the `from_type`

value is consulted of a `to_type`

value not present in the `bimap`

.

**Complexity of lookup** O(log *n*)

**Complexity of assignment** O(log *n*) (twice the time of lookup)

std::pair<iterator, bool> insert(const value_type& x)
std::pair<from::iterator, bool>
from.insert(const from::value_type& x)

Insert the given `value_type`

into the `bimap`

if and only if there is no element already present with an equivalent `from_type`

value. In either case, the `iterator`

part of the pair returned points to the element in the `bimap`

with equivalent `from_type`

value. The `bool`

member indicates whether an insertion really occurred.

#### Throws

`duplicate_value`

when no previous element with equivalent `from_type`

value existed, but the `to_type`

part was already present in the `bimap`

.

**Complexity** O(log *n*)

std::pair<to::iterator, bool> insert(const to::value_type& x)
std::pair<to::iterator, bool> to.insert(const to::value_type& x)

Insert the given `to::value_type`

into the `bimap`

if and only if there is no element already present with an equivalent `to_type`

value. In either case, the `to::iterator`

part of the pair returned points to the element in the `bimap`

with equivalent `to_type`

value. The `bool`

member indicates whether an insertion really occurred.

#### Throws

`duplicate_value`

when no previous element with equivalent `to_type`

value existed, but the `from_type`

part was already present in the `bimap`

.

**Complexity** O(log *n*)

iterator insert(iterator it, const value_type& x)
from::iterator from.insert(from::iterator it,
const from::value_type& x)

Insert `x`

into the `bimap`

, using `it`

as a hint about where to locate the insertion point. Return an iterator to the inserted element (or the preexisting one if an element with equivalent `from_type`

value was already contained).

#### Throws

`duplicate_value`

when no previous element with equivalent `from_type`

value existed, but the `to_type`

part was already present in the `bimap`

.

**Complexity** O(log *n*), but half the time if `it`

immediately precedes the insertion point.

**Complexity for VC++ 6.0** O(log *n*), but half the time if `it`

immediately follows the insertion point.

**Complexity for VC++ 7.0** O(log *n*), but half the time if `it`

immediately precedes or follows the insertion point.

to::iterator insert(to::iterator it, const to::value_type& x)
to::iterator to.insert(to::iterator it, const to::value_type& x)

Insert `x`

into the `bimap`

, using `it`

as a hint about where to locate the insertion point. Return an iterator to the inserted element (or the preexisting one if an element with equivalent `to_type`

value was already contained).

#### Throws

`duplicate_value`

when no previous element with equivalent `to_type`

value existed, but the `from_type`

part was already present in the `bimap`

.

**Complexity** O(log *n*), but half the time if `it`

immediately precedes the insertion point.

**Complexity for VC++ 6.0** O(log *n*), but half the time if `it`

immediately follows the insertion point.

**Complexity for VC++ 7.0** O(log *n*), but half the time if `it`

immediately precedes or follows the insertion point.

std::pair<from::iterator,to::iterator>
insert(from::iterator fit,to::iterator tit, const value_type& x)

Insert `x`

into the `bimap`

, using `fit`

and `tit`

as hints about where to locate the insertion point in the `from`

and `two`

parts, respectively. Return a pair with `from`

and `to`

iterators to the inserted element (or the preexisting one if the value was already contained).

#### Throws

`duplicate_value`

if either the `from_type`

or the `to_type`

of `x`

were already present in the `bimap`

.

**Complexity** O(log *n*) in general, half the time if one of the hints immediately precedes the insertion point, amortized constant time if both hints immediately precede the corresponding insertion points.

**Complexity for VC++ 6.0** O(log *n*) in general, half the time if one of the hints immediately follows the insertion point, amortized constant time if both hints immediately follow the corresponding insertion points.

**Complexity for VC++ 7.0** O(log *n*) in general, half the time if one of the hints immediately precedes or follows the insertion point, amortized constant time if both hints immediately precede or follow the corresponding insertion points.

template<typename it_type> void insert(it_type first,
it_type last)
template<typename it_type> void from.insert(it_type first,
it_type last)

Insert the `value_type`

elements in the range [`first`

, `last`

). The insertion policy is the same as it is for the insertion of a single value.

#### Throws

`duplicate_value`

in the same situations explained for the insertion of a single value.

**Complexity** O(*m* log *m*+*n*) where *m* is the length of [`first`

, `last`

).

void insert(const to::value_type * first,const to::value_type * last)
template<typename it_type> void to.insert(it_type first,it_type last)

Insert the `to::value_type`

elements in the range [`first`

, `last`

). The insertion policy is the same as it is for the insertion of a single value.

#### Throws

`duplicate_value`

in the same situations explained for the insertion of a single value.

**Complexity** O(*m* log *m*+*n*) where *m* is the length of [`first`

, `last`

).

void erase(iterator it)
void from.erase(from::iterator it)

#### Replaced in VC++ for

iterator erase(iterator it)
from::iterator from.erase(from::iterator it)

Erase the element pointed to by `it`

.

**VC++**: The return `iterator`

points to the following element in the `bimap`

, or `end()`

if no such element exists.

**Complexity** O(log *n*)

void erase(to::iterator it)
void to.erase(to::iterator it)

#### Replaced in VC++ for

iterator erase(to::iterator it)
to::iterator to.erase(to::iterator it)

Erase the element pointed to by `it`

.

**VC++**: The return `to::iterator`

points to the following element in the `bimap`

, or `to.end()`

if no such element exists.

**Complexity** O(log *n*)

void erase(iterator first,iterator last)
void from.erase(from::iterator first,from::iterator last)

Erase the elements in the range [`first`

, `last`

).

**Complexity** O(*m* log *n*) where *m* is the length of [`first`

, `last`

).

void erase(to::iterator first,to::iterator last)
void to.erase(to::iterator first,to::iterator last)

Erase the elements in the range [`first`

, `last`

).

**Complexity** O(*m* log *n*) where *m* is the length of [`first`

, `last`

).

size_type erase(const key_type& key)
from::size_type from.erase(const from::key_type& key)

Erase the element whose `from_type`

part is equal to `key`

, if any. Return 1 or 0 depending or whether a deletion has occurred or not.

**Complexity** O(log *n*) (twice the time of an insertion based on an iterator).

size_type erase(const to::key_type& key)*
to::size_type to.erase(const to::key_type& key)

^{*}Only available if `from_type!=to_type`

.

Erase the element whose `to_type`

part is equal to `key`

, if any. Return 1 or 0 depending or whether a deletion has occurred or not.

**Complexity** O(log *n*) (twice the time of an insertion based on an iterator).

void clear()
void from.clear()
void to.clear()

These member functions resolve to a call to `erase(begin(),end())`

**Complexity** O(*n* log *n*)

void swap(bimap& x)
void from.swap(bimap::from x)
void to.swap(bimap::to x)

Swap the elements of the `bimap`

with those of `x`

. *Note: allocator equivalence is assumed.*

**Complexity** constant time

void codeproject::swap(bimap& x,bimap& y)
void codeproject::swap(bimap::from& x,bimap::from& y)
void codeproject::swap(bimap::from& x,bimap::from& y)

These are global functions. They swap the elements of `x`

and `y`

. *Note: allocator equivalence is assumed.*

**Complexity** constant time

key_compare key_comp() const
from::key_compare from.key_comp() const

Return a copy of the internal `key_compare`

object used for comparison of `from_type`

keys.

**Complexity** constant time

to::key_compare to.key_comp() const

Returns a copy of the internal `to::key_compare`

object used for comparison of `to_type`

keys.

**Complexity** constant time

value_compare value_comp() const
from::value_compare from.value_comp() const

Return an object of type `value_compare`

consistent with the lexicographical order induced by `from.key_comp()`

and `to.key_comp()`

.

**Complexity** constant time

to::value_compare to.value_comp() const

Returns an object of type `to::value_compare`

consistent with the lexicographical order induced by `to.key_comp()`

and `from.key_comp()`

.

**Complexity** constant time

iterator find(const key_type& key)
from::iterator from.find(const from::key_type& key)

Return an iterator pointing to the element whose `from_type`

value equals `key`

, or `end()`

if no such element exists. `const`

versions are provided returning a `const_iterator`

.

**Complexity** O(log *n*)

to::iterator find(const to::key_type& key)*
to::iterator to.find(const to::key_type& key)

^{*}Only available if `from_type!=to_type`

.

Return an iterator pointing to the element whose `to_type`

value equals `key`

, or `to.end()`

if no such element exists. `const`

versions are provided returning a `to::const_iterator`

.

**Complexity** O(log *n*)

size_type count(const key_type& key) const
from::size_type from.count(const from::key_type& key) const

Return 1 if the `bimap`

contains an element whose `from_type`

part equals `key`

, 0 otherwise.

**Complexity** O(log *n*)

size_type count(const to::key_type& key) const*
to::size_type to.count(const to::key_type& key) const

^{*}Only available if `from_type!=to_type`

.

Return 1 if the `bimap`

contains an element whose `to_type`

part equals `key`

, 0 otherwise.

**Complexity** O(log *n*)

iterator lower_bound(const key_type& key)
from::iterator from.lower_bound(const from::key_type& key)

Return an iterator to the first element of the `bimap`

(as seen from the `from`

memberspace) with `from_type`

value not less than `key`

. `const`

versions are provided returning a `const_iterator`

.

**Complexity** O(log *n*)

to::iterator lower_bound(const to::key_type& key)*
to::iterator to.lower_bound(const to::key_type& key)

^{*}Only available if `from_type!=to_type`

.

Return an iterator to the first element of the `bimap`

(as seen from the `to`

memberspace) with `to_type`

value not less than `key`

. `const`

versions are provided returning a `to::const_iterator`

.

**Complexity** O(log *n*)

iterator upper_bound(const key_type& key)
from::iterator from.upper_bound(const from::key_type& key)

Return an iterator to the first element of the `bimap`

(as seen from the `from`

memberspace) with `from_type`

value greater than `key`

. `const`

versions are provided returning a `const_iterator`

.

**Complexity** O(log *n*)

to::iterator upper_bound(const to::key_type& key)*
to::iterator to.upper_bound(const to::key_type& key)

^{*}Only available if `from_type!=to_type`

.

Return an iterator to the first element of the `bimap`

(as seen from the `to`

memberspace) with `to_type`

value greater than `key`

. `const`

versions are provided returning a `to::const_iterator`

.

**Complexity** O(log *n*)

std::pair<iterator, iterator> equal_range(const key_type& key)
std::pair<from::iterator, from::iterator>
from.equal_range(const from::key_type& key

Return a pair of iterators with its first member being `lower_bound(key)`

and its second member `upper_bound(key)`

. `const`

versions are provided returning the corresponding `const_iterator`

s.

**Complexity** O(log *n*)

std::pair<to::iterator, to::iterator>
equal_range(const to::key_type& key)*
std::pair<to::iterator, to::iterator>
to.equal_range(const to::key_type& key)

^{*}Only available if `from_type!=to_type`

.

Return a pair of iterators with its first member being `to.lower_bound(key)`

and its second member `to.upper_bound(key)`

. `const`

versions are provided returning the corresponding `to::const_iterator`

s.

**Complexity** O(log *n*)

`bimap`

uses a kind of constructs that I call *memberspaces*. Memberspaces bear some similarities with namespaces, but they are not exactly the same, and they are not natively supported by C++. This annex briefly introduces member spaces and some situations where they prove useful, along with a sketch of how they can be simulated in standard C++.

Suppose we are defining a two-way queue holding integers. Such a queue presents two ends, say `head`

and `tail`

, providing the usual `push`

and `pull`

operations. As a class cannot hold two member functions with the same name and arguments, the problem arises as to how to name the corresponding member functions for each end of the queue. A naive approach is to simply adorn the names of the member functions with some disambiguating prefix:

class twoway_queue
{
public:
void head_push(int n);
int head_pull();
void tail_push(int n);
int tail_pull();
...
};

This simple solution suffers from several limitations:

- It is aesthetically unpleasant.
- It does not extend to operators, like
`operator []`

.
- Sometimes, one wants to use the class with preexistent generic code that assumes certain names for member functions, like in this example:
template<typename queue_type> void fill_n(
queue_type& q,int n)
{
for(int i=1;i<n;++i)q.push(i);
}

In these situations, name adorning breaks the "interface" expected by the generic code, rendering it unusable.

Memberspaces solve all these problems by introducing an additional level of scope into the class being defined:

class twoway_queue
{
public:
memberspace head
{
public:
void push(int n);
int pull();
}
memberspace tail
{
public:
void push(int n);
int pull();
}
...
};

The use of memberspaces is straightforward:

twoway_queue q;
q.head.push(1);
cout<<q.tail.pull()<<endl;
fill_n(q.head,100);

The additional level of scope brought by member spaces is not restricted to members alone (called with `operator .`

), but it also serves to define local types (referred to with `::`

):

class int2string_queue
{
public:
memberspace int_end
{
public:
typedef int type;
void push(int n);
int pull();
}
memberspace str_end
{
public:
typedef string type;
void push(string str);
string pull();
}
...
};
int2string_queue q;
int2string_queue::str_end::type a;
a=q.str_end.pull();
cout<<a<<endl;

So, memberspaces can be viewed as dual constructs playing the role of both an embedded object and an in-class namespace.

### Implementation

Although memberspaces are not directly supported by C++, they can be efficiently simulated to a little-known syntax rule dating back from the C language, which allows an object and a class to be given the same name:

class A
{
...
};
class A A;

We can take advantage of this rule to lay the grounds for an implementation of memberspaces:

class twoway_queue
{
public:
class head
{
public:
void push(int n);
int pull();
}head;
...
};

Such an artifact imposes no or minimum penalty on the memory layout of the nesting class. To grant inter-accessibility between `private`

members of the enclosing class and those of the memberspace we just arrange the necessary `friend`

declarations:

class twoway_queue
{
public:
class head
{
**friend twoway_queue;**
public:
void push(int n);
int pull();
}head;
**friend class head;**
...
};

There is only one brick left to complete this building: when the code inside the member space needs to access some member of the enclosing class, it has to find out the object where it is embedded. This can be solved at compile-time if we note that it is known in advance the exact location inside the enclosing class of the member space object, so that we can just force the "upcasting" to the whole class like this:

class twoway_queue
{
class head
{
public:
void push(int n)
{
...
**owner().length++;
**
}
...
private:
**twoway_queue& owner()
{
return *reinterpret_cast<twoway_queue*>(
reinterpret_cast<char*>(this)-offsetof(
twoway_queue,head));
}**
}head;
...
}

There are still some uninteresting details to round up, like defining a `const`

version of `owner`

and enforcing the fact that the memberspace object should not live outside the location where it is defined inside the class by declaring the copy constructor and assignment operator `private`

.

In order to provide `std::map`

-like capabilities for both `from_type`

and `to_type`

keys, `bimap`

maintains two `std::set`

s of pointers to the elements. The figure shows the data layout of a `bimap<int,char>`

with elements (1,'c'), (3,'a') and (2,'b'):

One problem remains, though: STL associative containers are supposed to hold pairs of (key, value) elements. From the point of view of the `to_type`

part, this requirement is not met, since `two_type`

values come the second in the pairs. The following trick has been used to workaround the problem: Two template classes have been defined, named `direct_pair`

and `inv_pair`

; `direct_pair`

behaves as regular `std::pair`

s, whereas `inv_pair`

s have their `first`

and `second`

members arranged in the opposite order, `first`

being the second in the object layout. So, a `direct_pair<A,B>`

can be `reinterpret_cast`

'ed to a `inv_pair<B,A>`

and vice-versa. `from::iterator`

s and `to::iterator`

s are set to point to `direct_pair`

s and `inv_pair`

s, respectively, though actually they're pointing to the same pieces of memory. From the perspective of generic algorithms as those of STL, both `from::iterator`

s and `to::iterator`

s behave as expected, pointing to an object whose member named `first`

is the key and `second`

is the value. The following UML diagram shows the relationships between the different types:

- Thanks go to Alexandru Savescu, who tested some beta releases of the library in VC++ 7.0 and pinpointed various bugs.
- Manuel Prieto Martín tested the final version 1.0 in VC++ 7.0. Jorge Munuera Andreo checked the final version 1.1 against this compiler.
- The motivation for trying to make
`bimap`

run under compilers other than VC++ came from Bala Swaminathan, who did an initial port to GCC from which version 1.1 has been written. He has also tested the final version 1.1 for different flavors of GCC.
- Andrew Pollard provided a workaround to suppress some annoying warnings in GCC relating to the use of
`offsetof`

.
- David Phillip Oster provided the fixes to port
`bimap`

to CodeWarrior 8.3. He, Dmitry Markman and Herb Davis tested the final version 1.1 for this compiler.
- Big thanks to Steve Robb for finding (and sharing) a way to make VC++ 7.1 compile the library without crashing, at a time when it seemed this couldn't be done without changing the public interface of
`bimap`

.
- Gregoire Banderet tested version 1.3 against GCC 3.3, GCC 3.4 and VC++ 7.1.

The implementation code is rather messy and takes advantage of several smart techniques to simulate partial template specialization. Ideas are taken from the following sources:

- Alexandrescu, A.:
*Modern C++ Design: Generic Programming and Design Patterns Applied*, ch. 2, Addison-Wesley, February 2001.,
- Boost,
`type_traits`

library, `boost::is_same<T,U>`

template, April 2001, boost.org.
- Czarnecki, K., Eisenecker, U.:
*Generative Programming - Methods, Tools, and Applications*, Addison-Wesley, June 2000.
- Marcus, M., Jones, J.: "Simulated partial Specialization for C++", September 2000, original link no longer available, article stored in web.archive.org.

- 9
^{th} Oct, 2002 - 1.0.
- Initial release. Watch for frequent updates!

- 6
^{th} Feb, 2003 - 1.1.
`bimap::erase(to::iterator,to::iterator)`

incorrectly returned an iterator. Documentation was also erroneous about this point.
- Incorrect use of
`allocator::allocate`

and `allocator::deallocate`

was causing much more memory to be used than necessary.
- Improved language conformance with respect to missing
`typename`

and `template`

keywords, faulty `friend`

declarations and broken implementation of some features of `<iterator>`

in VC++.
`allocator::rebind`

used if compiler supports it.
- Fixed some non-conformances about construction of allocator and comparison objects in copy constructors.
- The allocator object used to be
`protected`

for no good reason: changed to `private`

as the rest of the internal objects.
- Some tweaks to make the thing compile under GNU GCC and Metrowerks CodeWarrior.
- GCC didn't like a template parameter and a defined type to have the same name: I don't know if this is actually standard conformant.

- 10
^{th} Jan, 2006 - 1.2.
`bimap`

now works for VC 7.1. This long-requested upgrade has been made possible by Steve Robb, who found a workaround for avoiding the internal compiler errors triggered by the previous versions of the library.

- 26
^{th} Oct, 2006 - 1.3.
- The code has been updated so as to correctly cope with a (mandatory) template mechanism known as two-phase name lookup. As a result,
`bimap`

now works for modern versions of GCC.