Sort vector pointers

Sorting

What the comparison function looks like - this is known only to you, you do not provide data on the structure of MyClassScan .

How to sort? Very simple, you need to use std::sort or a similar algorithm. Signature call can be found on the link.

Comparison function

Now, how to write the correct comparator (comparison function). Such a function accepts two objects as input and returns true if one is greater than / less than the other (binary relation). For example, std::less sets the “less” relationship:

 auto less = std::less<int>(); std::cout << less(1, 0) << "\n"; // 0 std::cout << less(1, 1) << "\n"; // 0 std::cout << less(0, 1) << "\n"; // 1 

How to write such a function, I think, is understandable. It is only necessary to take into account that you work with pointers that may be null. What to do if the input filed such a pointer - you decide.

Example:

 struct Test { int val = 0; }; bool cmp_test(const Test* a, const Test* b) { return !a || !b ? 0 : a->val < b->val; } int main() { Test a, b; a.val = 0; b.val = 1; std::cout << cmp_test(b, a) << "\n"; // 0 std::cout << cmp_test(b, b) << "\n"; // 0 std::cout << cmp_test(a, b) << "\n"; // 1 return 0; } 

Or using lambda:

 struct Test { int val = 0; }; int main() { auto cmp_test = [](const Test* a, const Test* b) { return !a || !b ? 0 : a->val < b->val; }; Test a, b; a.val = 0; b.val = 1; std::cout << cmp_test(b, a) << "\n"; // 0 std::cout << cmp_test(b, b) << "\n"; // 0 std::cout << cmp_test(a, b) << "\n"; // 1 return 0; } 

Comparison functor

At this point you need to ask the question: why did we write auto less = std::less<int>(); ? Namely, why are parentheses and what is std :: less?

Consider a typical function using a comparator. For example, at least:

 template<typename T, class CMP> T min(const T a, const T b, CMP cmp) { return cmp(a, b) ? a : b; } 

Our function takes as input two objects and a comparator for them and returns a smaller object. For example:

 Test a, b; a.val = -1; b.val = 1; auto m = min(&a, &b, cmp_test); std::cout << m->val << "\n"; // -1 

What is cmp inside the min function? In our code, this is a function pointer. Our min takes a pointer to a function and calls it.

But if there are a lot of comparisons (and there are a lot of them in sorting), we will lose some time to call the function. So we want to make our function inline.

The problem is that we do not know the function pointer in advance, which means we cannot inline the implementation. For example, we can have two comparators with the same signature, and we can pass a link to any of them:

 auto cmp_test1 = [](const Test* a, const Test* b) { return !a || !b ? 0 : a->val < b->val; }; auto cmp_test2 = [](const Test* a, const Test* b) { return !a || !b ? 0 : a->val > b->val; }; ... Test a, b; a.val = -1; b.val = 1; auto m1 = min(&a, &b, cmp_test1); auto m2 = min(&a, &b, cmp_test2); std::cout << m1->val << "\n"; // -1 std::cout << m2->val << "\n"; // 1 

In the code above, the template engine output one specification of the template min , which takes a pointer to a function.

Therefore a trick in the form of a functor is applied. A functor is a structure with a specific operator() . Such a structure looks like a function, but in fact it is a class. Consider std::less :

 template <class T> struct less : binary_function <T, T, bool> { bool operator() (const T& x, const T& y) const { return x < y; } }; 

So, we have created a less structure (inheritance from binary_function , in general, is not necessary, see the comment @alexolut). Instances of a structure behave in a manner similar to a function - they can be “invoked”:

 auto cmp = less<int>(); // Создаем экземпляр структуры std::cout << cmp(1, 0) << "\n"; // 0 // Используем operator() std::cout << cmp(1, 1) << "\n"; // 0 std::cout << cmp(0, 1) << "\n"; // 1 

How is this completely different from the function pointer? And by the fact that for each such structure the template engine will display its own specification. We can use such structures in the same way as functions:

 Test a, b; a.val = -1; b.val = 1; auto m = min(&a, &b, less<int>()); std::cout << m->val << "\n"; // -1 

However, now we are passing inside not a pointer to a certain function, but an instance of a particular class. So, the implementation of operator() known for each specification and it can be zainlaynit.

For our Test such a functor will look like this:

 struct cmp_test3 : binary_function <Test*, Test*, bool> { bool operator() (const Test* a, const Test* b) const { return !a || !b ? 0 : a->val < b->val; } }; 

Tldr

 #include <iostream> #include <algorithm> #include <functional> #include <vector> struct Test { int val = 0; Test(int a): val(a) {}; }; struct cmp_test : std::binary_function <Test*, Test*, bool> { bool operator() (const Test* a, const Test* b) const { return !a || !b ? 0 : a->val < b->val; } }; int main() { Test a(1), b(3), c(2), d(4); std::vector<Test*> v {&a, &b, &c, &d}; std::sort(v.begin(), v.end(), cmp_test()); for (auto i: v) std::cout << i->val << " "; // 1 2 3 4 return 0; } 

 #include <vector> #include <algorithm> struct MyClassScan { int sortedField; int otherField; MyClassScan(int _sortedField, int _otherField) : sortedField(_sortedField) , otherField(_otherField) {} }; bool ComparatorFunction(const MyClassScan* left, const MyClassScan* right) { return left->sortedField < right->sortedField; } struct ComparatorClass { bool operator () (const MyClassScan* left, const MyClassScan* right) const { return left->sortedField < right->sortedField; } }; int main() { std::vector<MyClassScan*> pointersVector = { new MyClassScan(5, 1), new MyClassScan(4, 2), new MyClassScan(3, 3), new MyClassScan(2, 4), new MyClassScan(1, 5) }; // способ 1 std::sort(pointersVector.begin(), pointersVector.end(), [](const MyClassScan* left, const MyClassScan* right){ return left->sortedField < right->sortedField; }); // способ 2 std::sort(pointersVector.begin(), pointersVector.end(), ComparatorFunction); // способ 3 std::sort(pointersVector.begin(), pointersVector.end(), ComparatorClass()); for (auto it = pointersVector.begin(); it != pointersVector.end();) { delete *(it++); } } 

If necessary, add checks to nullptr .

If there is a need to create multiple classes of the class at once, use std::tie in the appropriate places:

 std::tie(left->sortedField, left->otherField) < std::tie(right->sortedField, right->otherField) 

instead

 left->sortedField < right->sortedField 

Simply:

 std::sort(begin(scanArray), end(scanArray), [](const MyClassScan* a, const MyClassScan *b) { return a->someField < b->someField; }); 

If it’s more general: just pass your comparator to the std::sort algorithm: http://www.cplusplus.com/reference/algorithm/sort