About C++Summary of three methods to define comparison functions

C++One of the reasons why programming is better than Pascal is C++There is STL (Standard Template Library) present. STL has many useful methods.

C++Many methods in the template library require the parameters to be ordered, such as Sort(). It is obvious that if you want to sort a collection, you must know the objects in the collection, which one comes first and which one comes last. Therefore, it is very important to learn how to define comparison methods.

C++template library, many containers need related types to be ordered, such as set<T> and priority_queue<T>.

This article aims to tell you how to define a sorting method for a class so that it can be used in STL containers or methods. As a C++Programmers, you should know these methods.

How to define sorting?

In short, defining sorting for a class allows us to know the order of any two objects of the class during the sorting process. We can implement this with a method that returns a bool value indicating who comes first. Clearly, we hope to implement a method similar to f(x, y), which takes two objects of the same type as parameters and returns a value indicating who will appear in front of whom.

Strict anti-symmetry

Almost all methods or containers need to be sorted to meet the mathematical standard of strict anti-symmetry, otherwise the behavior of these methods or containers will be unpredictable.

Assuming f(x, y) is a comparison function. If this function meets the following conditions, it is strictly anti-symmetric.

1. f(x, x) = false;

2. if f(x, y) then !f(y, x)

3. if f(x, y) and f(y, z) then f(x, z)

4. if !f(x, y) && !f(y, x) then x == y; if x == y and y == z then x == z;

It may seem a bit confusing, but don't worry, as long as your comparison method always returns false for equal elements, your method meets the requirements.

Three implementation methods:

1. Define < operator.

　Using this method, our custom class can naturally have the ability to be sorted. For example, if there is such a class:

struct Edge
{
int from, to, weight;
};

Since you want to implement Kruskal's algorithm, you hope that all edges in the graph are sorted in descending order by weight. Define operator< like this:

struct Edge
{
    int from, to, weight;
    bool operator<(Edge other) const
    {
        return weight > other.weight;
    }   
};  

The method you define must be declared in the following way:

bool operator<(T other) const

Note: The const keyword is required.

If you don't like this way, for example, you want to compare two objects, but the method only has one parameter. You can choose the following way:

　

struct Edge
{
　　int from, to, weight;
　　friend bool operator<(Edge a, Edge b)
　　{
　　　　return a.weight > b.weight;
　　}
};

STL的pair<T1, T}}2> has inherent sorting capabilities. The comparison of two pair objects is as follows: first compare the first parameter, and then compare the second parameter if the first parameter is the same.

All built-in types have inherent sorting capabilities, which are given by the compiler.

2. Custom sorting method.

This method is often used in the following situations:

a. Comparison of built-in types

b. Cannot modify the type to be compared

c. Comparison methods other than type-defined comparison methods

In simple terms, a comparison method takes two objects of the same type as parameters and returns a bool value, the prototype is as follows:

bool name(T a, T b);
　
3. Overload the () operator

We can pass the comparison function as the first parameter of the STL container constructor, and the function type as the template parameter. For example:

set<int, bool (*)(int, int)> s(cmp);

This may be somewhat confusing. Let's see how to use functors to eliminate your doubts.

We need to define a new class and overload the () operator.

vector<int> occurrences; 
struct cmp 
{ 
  bool operator()(int a, int b) 
  { 
    return occurrences[a] < occurrences[b];
  } 
};

Now we can pass this class as a template parameter to STL containers.

set<int, cmp> s;
priority_queue<int, vector<int>, cmp> pq;

STL also has some built-in functors, such as less<T>, greater<T> and so on.

Functors can be initialized and used like ordinary functions. The simplest way is to add parentheses () at the end of the functor.

sort(data.begin(), data.end(), greater<int>());

That's all the information brought to you by the editor about C++Here is a summary of three methods for defining comparison functions in the middle, I hope everyone will support and cheer for the tutorial!