按第一个元素的元素同步对两个容器进行排序

Question

鉴于两个容器:std::list< int > a;和std::list< int > b;- a.size() == b.size().需要对容器a进行b同步排序,即每个元素a交换应该导致交换相应的元素b(位置索引意义上的对应关系).假设,元素中a和b非常重量级.即你无法复制它.

什么是完美的STL- way呢？如何使用std::sort来执行操作？做什么,如果a是const？

我目前做了什么:

#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;
}

但我无法提供免费swap(基于P::swap)功能struct P.它是不可避免的语言限制(我不能在函数范围内定义非lambda函数,但可以定义非模板类)？

额外:

我发现存在swap自由函数重载不是函数的类型要求std::sort.Just MoveConstructible和MoveAssignable都是.因此代码更合适(但仍然不完整).存在一个非常std::sort棘手的问题:提供的范围内的元素交换(显然)被分成一系列的合并操作:T tmp(std::move(lhs)); lhs = std::move(rhs); rhs = std::move(tmp);.因此,我不能交换(期间std::sort)容器本身的引用元素,而只交换它们的迭代器.

Answer 1

v一个相当简单的解决方案是在列表中构建一个迭代器向量，然后对其进行排序。然后，第 i 个元素v指向列表中应占据排序列表中第 i 个位置的元素，您可以重建该列表。由于使用了辅助容器，性能可能不是最佳的，但它很容易理解。

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);
}