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

    template <class KeyType, class ValueVectorType>
    struct MyKeyWrapper { // all is public to save getters
        KeyType k;
        bool operator <(const MyKeyWrapper &other) const { return k < other.k; }
    };

    template <class KeyType, class ValueVectorType>
    struct ValueVectorSingleton { // all is public to save getters, but kv and vv should be only accessible by getters
        static std::vector<MyKeyWrapper<KeyType, ValueVectorType> > *kv;
        static ValueVectorType *vv;

        static void StartSort(std::vector<MyKeyWrapper<KeyType, ValueVectorType> > &_kv, ValueVectorType &_vv)
        {
            assert(!kv && !vv); // can't sort two at once (if multithreading)
            assert(_kv.size() == _vv.size());
            kv = &_kv, vv = &_vv; // not an attempt for atomic operation
        }

        static void EndSort()
        {
            kv = 0, vv = 0;
        }
    };

    template <class KeyType, class ValueVectorType>
    std::vector<MyKeyWrapper<KeyType, ValueVectorType> >
        *ValueVectorSingleton<KeyType, ValueVectorType>::kv = 0;
    template <class KeyType, class ValueVectorType>
    ValueVectorType *ValueVectorSingleton<KeyType, ValueVectorType>::vv = 0;

    namespace std {

    template <class KeyType, class ValueVectorType>
    void swap(MyKeyWrapper<KeyType, ValueVectorType> &a, MyKeyWrapper<KeyType, ValueVectorType> &b)
    {
        assert((ValueVectorSingleton<KeyType, ValueVectorType>::vv &&
            ValueVectorSingleton<KeyType, ValueVectorType>::kv)); // if this triggers, someone forgot to call StartSort()
        ValueVectorType &vv = *ValueVectorSingleton<KeyType, ValueVectorType>::vv;
        std::vector<MyKeyWrapper<KeyType, ValueVectorType> > &kv =
            *ValueVectorSingleton<KeyType, ValueVectorType>::kv;
        size_t ai = &kv.front() - &a, bi = &kv.front() - &b; // get indices in key vector
        std::swap(a, b); // swap keys
        std::swap(vv[ai], vv[bi]); // and any associated values
    }

    } // ~std

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
    typedef MyKeyWrapper<size_t, std::vector<char> > KV;
    assert(sizeof(KV) == sizeof(size_t)); // otherwise this will crash
    std::vector<KV> kv((KV*)keys, (KV*)keys + 5); // fill by keys, casted to MyKeyWrapper

    ValueVectorSingleton<size_t, std::vector<char> >::StartSort(kv, vv);
    std::sort(kv.begin(), kv.end());
    ValueVectorSingleton<size_t, std::vector<char> >::EndSort();
    // trick std::sort into using the custom std::swap which also swaps the other vectors

    for(int i = 0; i < 5; ++ i)
        std::cout << kv[i].k << " ";
    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;
}