Synchronously sort two containers by elements of first of them

Question

Given a two containers: std::list< int > a; and std::list< int > b;, — a.size() == b.size(). Need to sort containers a and b synchronously, i.e. each swap of elements in a should cause a swapping corresponding elements in b (correspondence in sense of positional indices). Assume, that elements in a and b are very heavyweight. I.e. you can't make its copies.

What is the perfect STL-way to do it? How to use std::sort to perform the operation? What to do if a is const?

What I do currently:

#include <iostream>
#include <iomanip>
#include <type_traits>
#include <utility>
#include <iterator>
#include <algorithm>
#include <list>
#include <vector>

#include <cstdlib>
#include <cassert>

template< typename first, typename second > 
void
sort_synchronously(first & f, second & s)
{
    std::size_t sz = f.size();
    assert(sz == s.size());
    struct P
    {
        typename first::iterator pfirst;
        typename second::iterator psecond;
        bool operator < (P const & p) const { return (*pfirst < *p.pfirst); }
        void swap(P & p) noexcept { std::iter_swap(pfirst, p.pfirst); std::swap(pfirst, p.pfirst); std::iter_swap(psecond, p.psecond); std::swap(psecond, p.psecond);  }
    };
    std::vector< P > p;
    p.reserve(sz); // O(N) additional memory
    auto fi = std::begin(f);
    auto si = std::begin(s);
    for (std::size_t i = 0; i < sz; ++i) {
        p.push_back({fi, si});
        ++fi;
        ++si;
    }
    std::sort(std::begin(p), std::end(p)); // O(N * log N) time
} 

int
main()
{
    std::list< int > a{5, 4, 3, 2, 1};
    std::list< int > b{1, 2, 3, 4, 5};
    std::copy(std::cbegin(a), std::cend(a), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    std::copy(std::cbegin(b), std::cend(b), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    sort_synchronously(a, b);
    std::copy(std::cbegin(a), std::cend(a), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    std::copy(std::cbegin(b), std::cend(b), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    return EXIT_SUCCESS;
}

But I can't provide free swap (based on P::swap) function for struct P. Is it unavoidable limitation of the language (I can't define non-lambda function inside function scope, but can define non-template class)?

ADDITIONAL:

I found that presence the swap free function overloading is not the type requirement for std::sort function. Just MoveConstructible and MoveAssignable are. Therefore the code is more appropriate (but still incomplete). There is the really hard issue: swap of elements in range provided to std::sort is (evidently) splitted into series of consistuent operations: T tmp(std::move(lhs)); lhs = std::move(rhs); rhs = std::move(tmp);. Therefore I can't swap (during std::sort) referenced elements of containers itself but only the iterators to them.

Answer 1

One reasonably simple solution is to build a vector v of iterators into your lists, and sort that. Then, the ith element of v points to the elements in the lists that should occupy the ith position in the sorted lists, which you can rebuild. Performance might not be optimal, due to the use of the auxiliary containers, but it's easy to understand.

void ZippedSort(std::list<A>& a, std::list<B>& b) {

    using PairOfIts = pair<decltype(a.begin()), decltype(b.begin())>;

    vector<PairOfIts> v;
    auto i = a.begin();
    auto j = b.begin();
    for (; i != a.end(); ++i, ++j)
        v.push_back(make_pair(i, j));

    std::sort(v.begin(), v.end(), [](PairOfIts const& i, PairOfIts const& j) { return *i.first < *j.first; } );

    list<A> sortedA;
    list<B> sortedB;
    for (auto& x : v) {
        sortedA.splice(sortedA.end(), a, x.first);
        sortedB.splice(sortedB.end(), b, x.second);
    }

    swap(sortedA, a);
    swap(sortedB, b);
}

Answer 2

The perfect STL-way to do it is to fill vector with std::pair and create custom comparator which compares only first element in pair. Then you will have sorted vector of pairs.