http://stackoverflow.com/questions/18320566/

#!/usr/bin/env bash -vex
# cls ; bash self.bash 2>&1 | tee self.log | less
WARN="-W -Wall -Wextra -Werror"
g++ -x c++ - -std=gnu++1y $WARN -Og -g -o a <<__EOF && ./a && echo -e "\e[1;32msucceeded\e[0m" || echo -e "\e[1;31mfailed\e[0m"
#include <list>
#include <tuple>
#include <map>
#include <functional>

#include <string>

#include <cstdlib>
#include <cassert>

template< typename A, typename B >
class bijection
{

    using data_type = std::list< std::tuple< A const, B const > >;

public :

    using iterator = typename data_type::iterator;
    using const_iterator = typename data_type::const_iterator;

private :

    using direct_mapping_type = std::map< std::reference_wrapper< A const >, iterator, std::less< A const & > > ;
    using inverse_mapping_type = std::map< std::reference_wrapper< B const >, iterator, std::less< B const & > >;
    using direct_iterator = typename direct_mapping_type::iterator;
    using inverse_iterator = typename inverse_mapping_type::iterator;

public :

    auto size() const { return data_.size(); }

    auto begin() { return data_.begin(); }
    auto cbegin() const { return data_.cbegin(); }
    auto end() { return data_.end(); }
    auto cend() const { return data_.cend(); }

    auto find(A const & a)
    {
        auto const direct = direct_mapping_.find(a);
        if (direct == direct_mapping_.end()) {
            return data_.end();
        } else {
            return direct->second;
        }
    }

    auto find(B const & b)
    {
        auto const inverse = inverse_mapping_.find(b);
        if (inverse == inverse_mapping_.end()) {
            return data_.end();
        } else {
            return inverse->second;
        }
    }

    auto erase(iterator pos)
    {
        auto const & element = *pos;
        direct_mapping_.erase(std::get< 0 >(element));
        inverse_mapping_.erase(std::get< 1 >(element));
        return data_.erase(pos);
    }

    template< typename X, typename Y >
    std::tuple< iterator, bool, bool > insert(X && x, Y && y)
    {
        direct_iterator direct = direct_mapping_.find(x);
        inverse_iterator inverse = inverse_mapping_.find(y);
        bool const d = (direct != direct_mapping_.end());
        bool const i = (inverse != inverse_mapping_.end());
        if (d && i) {
            iterator ix = inverse->second;
            iterator iy = direct->second;
            inverse_mapping_.erase(inverse);
            direct_mapping_.erase(direct);
            if (ix != iy) {
                inverse_mapping_.erase(std::get< 1 >(*iy));
                direct_mapping_.erase(std::get< 0 >(*ix));
                data_.erase(iy);
                data_.erase(ix);
            } else {
                data_.erase(ix); // iy
            }
        } else if (d) {
            iterator iy = direct->second;
            direct_mapping_.erase(direct);
            inverse_mapping_.erase(std::get< 1 >(*iy));
            data_.erase(iy);
        } else if (i) {
            iterator ix = inverse->second;
            inverse_mapping_.erase(inverse);
            direct_mapping_.erase(std::get< 0 >(*ix));
            data_.erase(ix);
        }
        data_.emplace_back(std::forward< X >(x), std::forward< Y >(y));
        auto const & element = data_.back();
        iterator it = --data_.end();
        direct_mapping_.emplace(std::get< 0 >(element), it);
        inverse_mapping_.emplace(std::get< 1 >(element), it);
        return std::make_tuple(it, d, i);
    }

private :

    data_type data_;
    direct_mapping_type direct_mapping_;
    inverse_mapping_type inverse_mapping_;

};

int main()
{
    using A = std::size_t;
    using B = std::string;
    using M = bijection< A, B >;
    M m;
    assert(1 == (m.insert(A(111), B("111")), m.size()));
    assert(1 == (m.insert(A(111), B("111")), m.size()));
    assert(2 == (m.insert(A(222), B("222")), m.size()));
    assert(3 == (m.insert(A(333), B("333")), m.size()));
    assert(2 == (m.insert(A(222), B("111")), m.size()));
    assert(3 == (m.insert(A(111), B("222")), m.size()));
    assert(2 == (m.insert(A(111), B("111")), m.size()));
    assert(1 == (m.insert(A(333), B("111")), m.size()));
    assert(1 == (m.insert(A(333), B("333")), m.size()));
    assert(1 == (m.insert(A(111), B("333")), m.size()));
    assert(0 == (m.erase(m.find(A(111))), m.size()));
    return EXIT_SUCCESS;
}
__EOF