Sorting one array based on the values of another array?
I have an array of pointers to objects that are instances of a class from external code that I would not change.
I also have a vector of ints that was called by a function call on each object. So I
A: [pointerToObj1, pointerToObj2, ... pointerToObjN]
and
B: [obj1Int, obj2Int, ..... objNInt]
How easy is it to sort A so that it sorts by B values. I have access to boost.
That is, if B were
[3, 1, 2]
I want to sort A so that it is in order
[pointerToObj2, pointerToObj3, pointerToObj1]
In javascript you can do this like
B.sort(function(a,b){return A[B.indexOf(a)] < A[B.indexOf(b)];});
source to share
-
Make a paired vector containing both A and B.
vector<pair<pointerToObjType, int>> order(N); for (int i=0; i<N; ++i){ order[i] = make_pair(A[i], B[i]); }
-
Create your custom comparator to sort the vector of a pair.
struct ordering { bool operator ()(pair<pointerToObjType, int> const& a, pair<pointerToObjType, int> const& b) { return a.second < b.second; } };
-
Sorting a pair vector.
sort(order.begin(), order.end(), ordering());
-
All sorted A can be accessed with
order[i].first
.
source to share
One option is to store an array of "scores" in std::map<MyObject, int> scores
. Now you can create a comparator
bool compare(const MyObject* lhs, const MyObject* rhs) {
return scores[*lhs] < scores[*rhs];
}
Now you just do
std::sort(vectorOfObjects.begin(), vectorOfObjects.end(), compare);
Unfortunately, this requires that either scores
has a global variable, either scores
, and compare
packaged into a single class.
Perhaps the best 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 write it to the lambda.
One of the drawbacks of this solution is that in order to use a class MyObject
as a key for, std::map
you must implement operator<()
for the class (or a comparator to go to a constructor std::map
). Fortunately, you can write this as a global function and you must not modify the class itself. However, this requires direct object mapping.
source to share