#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/ref.hpp>
#include <iostream>
#include <utility>
#include <sstream>

using namespace boost::multi_index;

template<class T1, class T2>
struct pair_container_impl
{
	typedef std::pair<T1, T2> value_type;

	typedef multi_index_container
	<
		value_type,
		indexed_by
		<
			ordered_non_unique
			<
				composite_key
				<
					value_type,
					member<value_type, T1, &value_type::first>,
					member<value_type, T2, &value_type::second>
				>
			>,
			ordered_non_unique
			<
				member<value_type, T2, &value_type::second>
			>
		>
	> type;
};

template<class T1, class T2>
struct pair_container
{
private:
	typedef typename pair_container_impl<T1, T2>::type impl_type;

public:
	typedef typename impl_type::value_type		value_type;
	typedef typename impl_type::iterator		iterator;
	typedef typename impl_type::const_iterator	const_iterator;

	iterator		begin() { return impl.begin(); }
	const_iterator	begin()const { return impl.begin(); }
	iterator		end() { return impl.end(); }
	const_iterator	end()const { return impl.end(); }

	std::pair<iterator, bool> insert(const value_type& x)
	{
		iterator it0 = impl.find(boost::make_tuple(x.first));
		if ( it0 != impl.end() )
		{
			typename impl_type::nth_index_iterator<1>::type it1 = impl.template get<1>().find(x.second);
			if ( it1 != impl.template get<1>().end() )
			{
				return std::make_pair(it0, false);
			}
		}
		return impl.insert(x);
	}

	std::pair<iterator, bool> insert(T1 const& t1, T2 const& t2)
	{
		iterator it0 = impl.find(boost::make_tuple(t1));
		if ( it0 != impl.end() )
		{
			typename impl_type::nth_index_iterator<1>::type it1 = impl.template get<1>().find(t2);
			if ( it1 != impl.template get<1>().end() )
			{
				return std::make_pair(it0, false);
			}
		}
		return impl.insert(std::make_pair(t1, t2));
	}

	iterator find(value_type const& x) const
	{
		return impl.find(boost::make_tuple(boost::cref(x.first), boost::cref(x.second)));
	}

	iterator find(T1 const& t1, T2 const& t2) const
	{
		return impl.find(boost::make_tuple(boost::cref(t1), boost::cref(t2)));
	}

private:
	impl_type impl;
};

int main()
{
  typedef pair_container<int, int> PairContainer;
  PairContainer container;

  const int TOTAL_PAIRS = 100l;

  for ( int i = 0; i < TOTAL_PAIRS; i++ )
  {
	  for ( int j = 0; j < TOTAL_PAIRS; j++ )
	  {
		  if ( !container.insert(std::make_pair(i, j)).second )
		  {
			  std::cout << "Cannot Insert Pair (" << i << ", " << j << ")" << std::endl;
		  }
	  }
  }

  return 0;
}