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

Question

给定两个容器:std::list< int > a;和 std::list< int > b; , — a.size() == b.size() .需要对容器进行分类a和 b同步，即 a 中元素的每次交换应该导致交换 b 中的相应元素(位置索引意义上的对应关系)。假设 a 中的元素和 b非常重量级。 IE。你不能复制它。

完美的 STL 方法是什么？如何使用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 的类型要求功能。只有 MoveConstructible 和 MoveAssignable 是。因此the code更合适(但仍然不完整)。有一个真正困难的问题:交换提供给 std::sort 范围内的元素被(显然)分成一系列一致的操作:T tmp(std::move(lhs)); lhs = std::move(rhs); rhs = std::move(tmp); .因此，我不能(在 std::sort 期间)交换容器本身的引用元素，只能交换它们的迭代器。

Answer 1

一个相当简单的解决方案是在您的列表中构建一个迭代器 vector v，然后对其进行排序。然后，v 的第 i 个元素指向列表中应该占据排序列表中第 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);
}