An STL-like bidirectional map

• Download source files - 14.5 Kb

Contents

• Introduction
• Namespace
• Basic usage
• Memberspaces from and to
• Test suite
• Compiler status
• Issues
• Reference
  • Types
  • Exceptions
  • Constructors and assignment
  • Comparison
  • Iterator retrieval
  • Utility member functions
  • Insertion and erasing
  • Search
• Annex 1: Memberspaces
• Annex 2: Data structure
• Acknowledgements
• Bibliography
• Version history

Introduction

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.

Namespace

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.

Basic usage

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; // throws bimap_base::duplicate_value

// throws throws bimap_base::value_not_found

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.

Memberspaces from and to

Consider this example:

bimap <int,int> bm;
bm[1]=5; // which side of the bimap are we referring to?

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; // assigns 5 to the "from" value 1

bm.to[4]=2;   // assigns 4 to the "to" value 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){
  // lists pairs in (from,to) order

  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"); // equivalent to bm.to.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); // reverse order

Test suite

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.

Compiler status

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.

Issues

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; // OK, no 'class' needed

Hint-driven insertion

For std::maps 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 bimaps, 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); // should call codeproject::swap()

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 bimaps is prohibited by the standard, so the only option is to explicitly qualify swap:

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

Reference

Types

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.

Exceptions

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.

Constructors and assignment

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

Comparison

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 bimaps 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 bimaps 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 bimaps 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 bimaps being compared.

Iterator retrieval

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

Utility member functions

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

Insertion and erasing

(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::maps. 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"; //assignment

string s=bm[1]; // retrieval of a string&

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::maps. 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; // assignment

int i=bm["Hello"]; // retrieval of an int&

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

Search

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_iterators.

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_iterators.

Complexity O(log n)

Annex 1: Memberspaces

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 //warning, "memberspace" is not C++

  { 
  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 to convert between ints and their 

// string representations and viceversa

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 string

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; // legal C++! object A is of type 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; // head is both a nested 

         // class and an embedded object

  ...
};

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++; // access private member 

                        // length of twoway_queue

    }   
  ...
  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.

Annex 2: Data structure

In order to provide std::map-like capabilities for both from_type and to_type keys, bimap maintains two std::sets 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::pairs, whereas inv_pairs 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::iterators and to::iterators are set to point to direct_pairs and inv_pairs, respectively, though actually they're pointing to the same pieces of memory. From the perspective of generic algorithms as those of STL, both from::iterators and to::iterators 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:

Acknowledgements

• 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.

Bibliography

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.

Version history

• 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.

You must Sign In to use this message board.

FAQ  Noise Tolerance Very HighHighMediumLowVery Low  Search Messages    Layout Expand All MessagesThread ViewNo Javascript (slow)No Javascript Preview    Per page 102550

Msgs 1 to 25 of 145 (Total in Forum: 145) (Refresh) FirstPrevNext

Relationship to Boost.Bimap roel_ 5:30 24 Jun '08   I have seen that you are the author of Boost.MultiArray which I haven't used yet; although from the description it seems to be a generalisation which also covers the use case that Boost.Bimap seeks to cover. Are there any advantages over using this class or MultiArray over Boost.Bimap? Should I use MultiArray if I only need 'bimap-like' functionality? Thanks for the excellent article btw. Sign In·View Thread·PermaLink Re: Relationship to Boost.Bimap Joaquín M López Muñoz 8:48 24 Jun '08   I have seen that you are the author of Boost.MultiArray which I haven't used yet; I take you meant Boost.MultiIndex. Yes, I'm the author of that library. although from the description it seems to be a generalisation which also covers the use case that Boost.Bimap seeks to cover. Are there any advantages over using this class or MultiArray over Boost.Bimap? Should I use MultiArray if I only need 'bimap-like' functionality? The story is a little convoluted, but Matías Capeletto, the author of Boost.Bimap, sums it up here[^]. If you only need the bimap functionality, use Boost.Bimap as it is designed to make this precise functionality user friendlier. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo Want a Boost forum in Code Project? Vote here[^]! Sign In·View Thread·PermaLink Re: Relationship to Boost.Bimap roel_ 23:37 24 Jun '08   Joaquín M López Muñoz wrote: I take you meant Boost.MultiIndex. Yes, I'm the author of that library. Sorry about that - I even looked up the names on the boost website because I was confusing them and then I still mess up here Anyway, thanks for your answer, I'll stick with boost.bimap for now then. Sign In·View Thread·PermaLink 5.00/5 (1 vote) Can not compile in BCB 6 Dayang1000 7:54 20 Apr '07   I've tried to compile bimap in Borland C++ 6 Professional version, but I got a lot of error msgs. What do I need to do to get it to compile in BCB 6. Thanks Sign In·View Thread·PermaLink Re: Can not compile in BCB 6 Alexei Vinidiktov 6:50 16 Sep '07   Same here for BCB 5 Standard. [C++ Error] BIMAP.H(424): E2312 'logic_error' is not an unambiguous base class of 'bimap_base::value_not_found' [C++ Error] BIMAP.H(424): E2251 Cannot find default constructor to initialize base class 'std::logic_error' [C++ Error] BIMAP.H(431): E2312 'logic_error' is not an unambiguous base class of 'bimap_base::duplicate_value' [C++ Error] BIMAP.H(431): E2251 Cannot find default constructor to initialize base class 'std::