基于另一个数组的值对一个数组进行排序？

Question

我有一个指向外部代码类的对象实例的指针数组，而这些对象都是已创建好的，我不希望改变它们。

同时，我还有一个int类型的向量，是通过对每个对象调用函数生成的。所以我的数据结构如下：

A:  [pointerToObj1, pointerToObj2, ... pointerToObjN]

并且

B:  [obj1Int, obj2Int, ..... objNInt]

如何轻松地对A进行排序，使其按B的值排序。我有可用的boost函数库。

如果B是这样的

[3, 1, 2]

我希望将A排序，使其按照特定顺序排列。

[pointerToObj2, pointerToObj3, pointerToObj1]

在JavaScript中，你可以这样做：

B.sort(function(a,b){return A[B.indexOf(a)] < A[B.indexOf(b)];});

- asutherland

---

你不会碰巧在做遗传编程吧？ - Code-Apprentice

Answer 1

1. Make a pair vector that contains both A & B.

   vector<pair<pointerToObjType, int>> order(N);
   for (int i=0; i<N; ++i){
       order[i] = make_pair(A[i], B[i]);
   }
   

2. Create your custom comparator to sort the pair vector.

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

3. Sort the pair vector.

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

4. All sorted A's can be accessed using order[i].first.

- herohuyongtao

Answer 2

一种选择是将你的"分数"数组存储在一个std::map<MyObject, int> scores中。现在你可以创建一个比较器。

bool compare(const MyObject* lhs, const MyObject* rhs) {
    return scores[*lhs] < scores[*rhs];
}

现在，您只需要执行以下操作。

std::sort(vectorOfObjects.begin(), vectorOfObjects.end(), compare);

很不幸，这要求scores是全局变量或将scores和compare打包到同一个类中。

也许更好的方法是使用lambda表达式：

std::sort(vectorOfObjects.begin(), vectorOfObjects.end(),
    [&scores] (const MyObject* lhs, const MyObject* rhs) {scores[*lhs] < scores[*rhs];});

这允许你将scores声明为一个局部变量，并在lambda中捕获它。

这种解决方案的一个缺点是，为了将MyObject类作为std::map的键使用，你必须为该类实现operator<()（或者传递给std::map构造函数的比较器）。幸运的是，你可以编写这个函数作为全局函数，而不必更改类本身。但是，这需要以某种方式直接比较对象。

- Code-Apprentice

---

这似乎是一个不错的干净的答案，我在看到它之前就让herohuyongtao的方法起作用了。谢谢。 - asutherland

@asutherland 我在原始的lambda实现中遇到了一个错误。我决定恢复我的原始答案，然后展示一个带有lambda的简化版本。 - Code-Apprentice

我的王国要一个zip迭代器。 - emsr