c++ - 如何按不同 std::vector 的值对 std::vector 进行排序？

Question

这个问题在这里已经有了答案:

How can I sort two vectors in the same way, with criteria that uses only one of the vectors? (9 个回答)

关闭 6 个月前。

我有几个 std::vector，长度都一样。我想对这些 vector 之一进行排序，并将相同的转换应用于所有其他 vector 。有没有一种巧妙的方法来做到这一点？ (最好使用 STL 或 Boost)？一些 vector 包含 ints，其中一些包含 std::strings。

伪代码:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };

Transformation = sort(Index);
Index is now { 1, 2, 3};

... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };

Answer 1

friol 的方法与您的方法相结合时效果很好。首先，构建一个包含数字 1...n 的 vector ，以及指示排序顺序的 vector 中的元素:

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

现在您可以使用自定义排序器对该数组进行排序:

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

现在您已经在 order 中捕获了重新排列的顺序(更准确地说，在项目的第一个组件中)。您现在可以使用此排序来对其他 vector 进行排序。可能有一个非常聪明的就地变体同时运行，但在其他人想出它之前，这里有一个不是就地的变体。它使用 order 作为每个元素的新索引的查找表。

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}