如何通过不同 std::vector 的值对 std::vector 进行排序?

2021-12-10 00:00:00 sorting vector c++ stl boost

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

I have several std::vector, all of the same length. I want to sort one of these vectors, and apply the same transformation to all of the other vectors. Is there a neat way of doing this? (preferably using the STL or Boost)? Some of the vectors hold ints and some of them 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" };

推荐答案

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

friol's approach is good when coupled with yours. First, build a vector consisting of the numbers 1…n, along with the elements from the vector dictating the sorting order:

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

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

Now you can sort this array using a custom sorter:

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 中的重新排列顺序(更准确地说，在项目的第一个组件中).您现在可以使用此顺序对其他向量进行排序.可能有一个非常聪明的就地变体同时运行，但在其他人提出它之前，这里有一个不是就地变体.它使用 order 作为每个元素新索引的查找表.

Now you've captured the order of rearrangement inside order (more precisely, in the first component of the items). You can now use this ordering to sort your other vectors. There's probably a very clever in-place variant running in the same time, but until someone else comes up with it, here's one variant that isn't in-place. It uses order as a look-up table for the new index of each element.

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

相关文章