#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

    template <class V0, class V1>
    class CRefPair { // overrides copy semantics of std::pair
    protected:
        V0 &m_v0;
        V1 &m_v1;

    public:
        CRefPair(V0 &v0, V1 &v1)
            :m_v0(v0), m_v1(v1)
        {}

        void swap(CRefPair &other)
        {
            std::swap(m_v0, other.m_v0);
            std::swap(m_v1, other.m_v1);
        }

        operator std::pair<V0, V1>() const // both g++ and msvc sort requires this (to get a pivot)
        {
            return std::pair<V0, V1>(m_v0, m_v1);
        }

        CRefPair &operator =(std::pair<V0, V1> v) // both g++ and msvc sort requires this (for insertion sort)
        {
            m_v0 = v.first;
            m_v1 = v.second;
            return *this;
        }

        CRefPair &operator =(const CRefPair &other) // required by g++ (for _GLIBCXX_MOVE)
        {
            m_v0 = other.m_v0;
            m_v1 = other.m_v1;
            return *this;
        }
    };

    template <class V0, class V1>
    inline bool operator <(std::pair<V0, V1> a, CRefPair<V0, V1> b) // required by both g++ and msvc
    {
        return a < std::pair<V0, V1>(b); // default pairwise lexicographical comparison
    }
    
    template <class V0, class V1>
    inline bool operator <(CRefPair<V0, V1> a, std::pair<V0, V1> b) // required by both g++ and msvc
    {
        return std::pair<V0, V1>(a) < b; // default pairwise lexicographical comparison
    }
    
    template <class V0, class V1>
    inline bool operator <(CRefPair<V0, V1> a, CRefPair<V0, V1> b) // required by both g++ and msvc
    {
        return std::pair<V0, V1>(a) < std::pair<V0, V1>(b); // default pairwise lexicographical comparison
    }

    namespace std {

    template <class V0, class V1>
    inline void swap(CRefPair<V0, V1> &a, CRefPair<V0, V1> &b)
    {
        a.swap(b);
    }

    } // ~std

    template <class It0, class It1>
    class CPairIterator : public std::random_access_iterator_tag {
    public:
        typedef typename std::iterator_traits<It0>::value_type value_type0;
        typedef typename std::iterator_traits<It1>::value_type value_type1;
        typedef std::pair<value_type0, value_type1> value_type;
        typedef typename std::iterator_traits<It0>::difference_type difference_type;
        typedef /*typename std::iterator_traits<It0>::distance_type*/difference_type distance_type; // no distance_type in g++, only in msvc
        typedef typename std::iterator_traits<It0>::iterator_category iterator_category;
        typedef CRefPair<value_type0, value_type1> reference;
        typedef reference *pointer; // not so sure about this, probably can't be implemented in a meaningful way, won't be able to overload ->
        // keep the iterator traits happy

    protected:
        It0 m_it0;
        It1 m_it1;

    public:
        CPairIterator(const CPairIterator &r_other)
            :m_it0(r_other.m_it0), m_it1(r_other.m_it1)
        {}

        CPairIterator(It0 it0 = It0(), It1 it1 = It1())
            :m_it0(it0), m_it1(it1)
        {}

        reference operator *()
        {
            return reference(*m_it0, *m_it1);
        }

        value_type operator *() const
        {
            return value_type(*m_it0, *m_it1);
        }

        difference_type operator -(const CPairIterator &other) const
        {
            assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
            // the iterators always need to have the same position
            // (incomplete check but the best we can do without having also begin / end in either vector)

            return m_it0 - other.m_it0;
        }

        bool operator ==(const CPairIterator &other) const
        {
            assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
            return m_it0 == other.m_it0;
        }

        bool operator !=(const CPairIterator &other) const
        {
            return !(*this == other);
        }

        bool operator <(const CPairIterator &other) const
        {
            assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
            return m_it0 < other.m_it0;
        }

        bool operator >=(const CPairIterator &other) const
        {
            return !(*this < other);
        }

        bool operator <=(const CPairIterator &other) const
        {
            return !(other < *this);
        }

        bool operator >(const CPairIterator &other) const
        {
            return other < *this;
        }

        CPairIterator operator +(distance_type d) const
        {
            return CPairIterator(m_it0 + d, m_it1 + d);
        }

        CPairIterator operator -(distance_type d) const
        {
            return *this + -d;
        }

        CPairIterator &operator +=(distance_type d)
        {
            return *this = *this + d;
        }

        CPairIterator &operator -=(distance_type d)
        {
            return *this = *this + -d;
        }

        CPairIterator &operator ++()
        {
            return *this += 1;
        }

        CPairIterator &operator --()
        {
            return *this += -1;
        }

        CPairIterator operator ++(int) // msvc sort actually needs this, g++ does not
        {
            CPairIterator old = *this;
            ++ (*this);
            return old;
        }

        CPairIterator operator --(int)
        {
            CPairIterator old = *this;
            -- (*this);
            return old;
        }
    };

    template <class It0, class It1>
    inline CPairIterator<It0, It1> make_pair_iterator(It0 it0, It1 it1)
    {
        return CPairIterator<It0, It1>(it0, it1);
    }
    
    struct CompareByFirst {
    	bool operator ()(std::pair<size_t, char> a, std::pair<size_t, char> b) const
    	{
            return a.first < b.first;
    	}
    };
    
int main()
{
    size_t keys[] = {5, 2, 3, 1, 4};
    char values[] = {'e', 'b', 'd', 'c', 'a'};

    std::vector<char> vv(values, values + 5); // fill by values
    std::vector<size_t> kv(keys, keys + 5); // fill by keys

    std::sort(make_pair_iterator(kv.begin(), vv.begin()),
        make_pair_iterator(kv.end(), vv.end()), CompareByFirst());
    // nice

    for(int i = 0; i < 5; ++ i)
        std::cout << kv[i] << " ";
    std::cout << std::endl;
    for(int i = 0; i < 5; ++ i)
        std::cout << vv[i] << " ";
    std::cout << std::endl;
    // could have used for_each and lambdas
    
	return 0;
}