4

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)];});
herohuyongtao
  • 49,413
  • 29
  • 133
  • 174
asutherland
  • 2,849
  • 4
  • 32
  • 50

2 Answers2

4

  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
  • 49,413
  • 29
  • 133
  • 174
3

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.

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268