Sort one array based on values of another array?

Question

I have an array of pointers to objects that are instances of a class from external code that I would rather not change.

I also have a vector of ints that was generated by calling a function on each object. So I have

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

And

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

How do I easily sort A such that it is sorted in by the values of B. I have boost available.

That is if B were

[3, 1, 2]

I want to sort A such that it is in the order

[pointerToObj2, pointerToObj3, pointerToObj1]

In javascript you could do this like

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

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.

Answer 2

One option is to store your array of "scores" in a std::map<MyObject, int> scores instead. Now you can create a comparator

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

Now you simply do

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

Unfortunately, this requires that either scores is a global variable or scores and compare are packaged into the same class.

Perhaps a better approach is to use a lambda:

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

This allows you to declare scores as a local variable and capture it in the lambda.

One drawback to this solution is that, in order to use the MyObject class as a key for std::map, you must implement operator<() for the class (or a comparator to pass to the std::map constructor). Fortunately, you can write this as a global function and don't have to change the class itself. However, this requires comparing the objects directly in some way.