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::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);
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);
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 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 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::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";
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::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;
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_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)
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::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:
- 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.
- 9th Oct, 2002 - 1.0.
- Initial release. Watch for frequent updates!
- 6th 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.
- 10th 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.
- 26th 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.
