Is there a more efficient implementation for a bidirectional map?

Boost Bimap makes use of Boost Mutant Idiom.

From the linked wikipedia page:

Boost mutant idiom makes use of reinterpret_cast and depends heavily on assumption that the memory layouts of two different structures with identical data members (types and order) are interchangeable. Although the C++ standard does not guarantee this property, virtually all the compilers satisfy it.

template <class Pair>
struct Reverse
{
    typedef typename Pair::first_type  second_type;
    typedef typename Pair::second_type first_type;
    second_type second;
    first_type first;
};

template <class Pair>
Reverse<Pair> & mutate(Pair & p)
{
  return reinterpret_cast<Reverse<Pair> &>(p);
}

int main(void)
{
  std::pair<double, int> p(1.34, 5);

  std::cout << "p.first = " << p.first << ", p.second = "  << p.second << std::endl;
  std::cout << "mutate(p).first = " << mutate(p).first << ", mutate(p).second = "  << mutate(p).second << std::endl;
}

The implementation in boost sources is of course fairly hairier.

If you create a set of pairs to your types std::set<std::pair<X,Y>> you pretty much have your functionallity implemented and rules about mutabillity and constness preset (OK maybe the settings aren't what you want but tweaks can be made). So here is the code :

#ifndef MYBIMAP_HPP
#define MYBIMAP_HPP

#include <set>
#include <utility>
#include <algorithm>

using std::make_pair;

template<typename X, typename Y, typename Xless = std::less<X>, 
                     typename Yless = std::less<Y>>
class bimap
{
    typedef std::pair<X, Y>                             key_type;
    typedef std::pair<X, Y>                             value_type;
    typedef typename std::set<key_type>::iterator       iterator;
    typedef typename std::set<key_type>::const_iterator const_iterator;

    struct Xcomp
    {
        bool operator()(X const &x1, X const &x2)
        {
            return !Xless()(x1, x2) && !Xless()(x2, x1);
        }
    };
    struct Ycomp
    {
        bool operator()(Y const &y1, Y const &y2)
        {
            return !Yless()(y1, y2) && !Yless()(y2, y1);
        }
    };
    struct Fless 
    { // prevents lexicographical comparison for std::pair, so that 
        // every .first value is unique as if it was in its own map
        bool operator()(key_type const &lhs, key_type const &rhs)
        {
            return Xless()(lhs.first, rhs.first);
        }
    };
    /// key and value type are interchangeable
    std::set<std::pair<X, Y>, Fless> _data;

public:
    std::pair<iterator, bool> insert(X const &x, Y const &y)
    {
        auto it = find_right(y);
        if (it == end()) { // every .second value is unique
            return _data.insert(make_pair(x, y));
        }
        return make_pair(it, false);
    }
    iterator find_left(X const &val)
    {
        return _data.find(make_pair(val,Y()));
    }
    iterator find_right(Y const &val)
    {
        return std::find_if(_data.begin(), _data.end(), 
            [&val](key_type const &kt)
        {
            return Ycomp()(kt.second, val);
        });
    }
    iterator end()   { return _data.end();   }
    iterator begin() { return _data.begin(); }
};

#endif

Example usage

template<typename X, typename Y, typename In>
void PrintBimapInsertion(X const &x, Y const &y, In const &in)
{
    if (in.second) {
        std::cout << "Inserted element (" 
              << in.first->first << ", " << in.first->second << ")\n";
    }
    else {
        std::cout << "Could not insert (" << x << ", " << y 
                      << ") because (" <<  in.first->first << ", " 
                      << in.first->second << ") already exists\n";
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    bimap<std::string, int> mb;
    PrintBimapInsertion("A", 1, mb.insert("A", 1) );
    PrintBimapInsertion("A", 2, mb.insert("A", 2) );
    PrintBimapInsertion("b", 2, mb.insert("b", 2));
    PrintBimapInsertion("z", 2, mb.insert("z", 2));

    auto it1 = mb.find_left("A");
    if (it1 != mb.end()) {
        std::cout << std::endl << it1->first << ", " 
                      << it1->second << std::endl;
    }

    auto it2 = mb.find_right(2);
    if (it2 != mb.end()) {
        std::cout << std::endl << it2->first << ", " 
                      << it2->second << std::endl;
    }

    return 0;
}

NOTE: All this is a rough code sketching of what a full implementation would be and even after polishing and extending the code I'm not implying that this would be an alternative to boost::bimap but merely a homemade way of having an associative container searchable by both the value and the key.

Live example

One possible implementation that uses an intermediate data structure and an indirection is:

int sz;  // total elements in the bimap

std::map<A, int> mapA;
std::map<B, int> mapB;

typedef typename std::map<A, int>::iterator iterA;
typedef typename std::map<B, int>::iterator iterB;

std::vector<pair<iterA, iterB>> register;  
// All the operations on bimap are indirected through it.

Insertion

Suppose you have to insert (X, Y) where X, Y are instances of A and B respectively, then:

Insert (X, sz) in mapA --- O(lg sz) Insert (Y, sz) in mapB --- O(lg sz) Then push_back (IterX, IterY) in register --- O(1). Here IterX and IterY are iterators to the corresponding element in mapA and mapB and are obtained from (1) and (2) respectively.

Lookup

Lookup for the image of an element, X, of type A:

Get the int mapped to X in mapA. --- O(lg n) Use the int to index into register and get corresponding IterY. --- O(1) Once you have IterY, you can get Y through IterY->first. --- O(1)

So both the operations are implemented in O(lg n).

Space: All the copies of the objects of A and B are required to be stored only once. There is, however, a lot of bookkeeping stuff. But when you have large objects, that would also be not much significant.

Note: This implementation relies on the fact that the iterators of a map are never invalidated. Hence, the contents of register are always valid.

A more elaborate version of this implementation can be found here

How about this?

Here, we avoid double storage of one type (T1). The other type (T2) is still double stored.

// Assume T1 is relatively heavier (e.g. string) than T2 (e.g. int family).
// If not, client should instantiate this the other way.
template <typename T1, typename T2>
class UnorderedBimap {

  typedef std::unordered_map<T1, T2> Map1;
  Map1 map1_;

  std::unordered_map<T2, Map1::iterator> map2_;
};