Basic introductory tutorial for C++ sort functions

preface

STL consists of containers, iterators, and algorithms. Users can perform a series of operations on the container, such as traversal and calculation. The iterators and containers provided by STL provide a perfect interface for this. std::vector is one of the most commonly used containers. vector is a template class defined under the namespace namespace. Using vector requires the inclusion of header files. Today we will focus on the use of vector sorting.

sort class functions:

函数名	功能描述
sort	对给定区间所有元素进行排序
stable_sort	对给定区间所有元素进行稳定排序
partial_sort	对给定区间所有元素部分排序
partial_sort_copy	对给定区间复制并排序
nth_element	找出给定区间的某个位置对应的元素
is_sorted	判断1个区间是否已经排好序
partition	使得符合某个条件的元素放在前面
stable_partition	相对稳定的使得符合某个条件的元素放在前面

Need a header file < algorithm >

sort (begin, end, cmp), cmp parameter can not be if there is no default non-descending sort.

Common sorting algorithms are quick sort, bubble sort, merge sort, etc. The implementation of the sort function in STL is related to the version of STL, which is often a mix of sorting algorithms.

1. The vector element is a built-in data type

The sort function in STL is used as follows, with the container sorted from small to large by default.

#include <vector> // std::vector
#include <algorithm> // std::sort

int main(){

 std::vector<int> vi{2, 0, 1, 8, 1, 2, 1, 5};
 std::sort(vi.begin(), vi.end());　　 //  The equivalent of  std::sort(vi.begin(), vi.end(), std::less<int>());

 for (int i = 0; i < vi.size(); ++i) {
  printf("%d ", vi[i]);
 }

 printf("\n");

// output: 0 1 1 1 2 2 5 8

Of course, you can also specify sorting containers from large to small:

#include <vector> // std::vector
#include <algorithm> // std::sort

int main(){

 std::vector<int> vi{2, 0, 1, 8, 1, 2, 1, 5};
 std::sort(vi.begin(), vi.end(), std::greater<int>());

 for (int i = 0; i < vi.size(); ++i) {
  printf("%d ", vi[i]);
 }

 printf("\n");

// output: 8 5 2 2 1 1 1 0

2. The vector element customizes the data type for the user

If the elements in vector are of a user-defined type and the user wants to sort by some combination of features of the custom type. Let's look at the definition of the sort function:

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

The first two arguments are iterator types, and the third argument is a comparison function. In the following example, class Character has two attributes, age_ and name_, where the variables are public for simplicity. Now you need to sort an vector of element type Character by age_ of Character from small to small.

class Character {
public:
 Character(int n, string s) : age_(n), name_(s) {}
 int age_;
 string name_;
};

class Compare {
public:
 bool operator() (Character* ca, Character* cb) {
  return ca->age_ < cb->age_;
 }
};


int main(){
 vector<Character*> vc{new Character(1, "sasaki"), new Character(2, "nozomi"), new Character(1, "satchel"), new Character(6, "qingtian")};

 sort(vc.begin(), vc.end(), Compare());

 for (int i = 0; i < vc.size(); ++i) {
  printf("%s ", vc[i]->name_.c_str());
 }

 return 0;
}// output: sasaki satchel nozomi qingtian

For the third function of sort, users can define any kind of comparison by themselves, but they need to satisfy the conditions of strict weak ordering:

X a;
X b;

Condition:     Test    Result
a is equivalent to b:  Compare(a, b)  false       Compare(b, a)  false

a is less than b   Compare(a, b)  true              Compare(b, a)  false

b is less than a   Compare(a, b)  false              Compare(b, a)  true

The Compare function in the above example is compared based on the value of the age_ variable of the Character object. According to the conditions of strict weak ordering, it is easier to understand that vector is ordered according to certain conditions.

For the two elements of vector, a, b, if a must be ranked before b, the following conditions need to be met: Compare(a, b) = true, Compare(b, a) = false; If Compare(a, b) = false & Compare(b, a) = false, then the two elements are equal;

Extension: sort the elements in vector so that age_ 1 comes first, age_! = 1 comes after;

Analysis: In this case, Character is divided into two categories, age_ ==1 and age_! = 1; For any two Character objects a, b:

1. Equal (a == b) : a- > age_ == 1 & & b- > age_ ==1, or a- > age_ != 1 & & b- > age_! = 1;

Less than (a < b) : a - > age_ == 1 & & b- > age_! = 1;

class Compare {
public:
 bool operator() (Character* ca, Character* cb) {
  if (ca->age_ == 1 && cb->age_ == 1 ||
   ca->age_ != 1 && cb->age_ != 1) return false;
  return ca->age_ == 1;
 }
};

Complete test code:

class Character {
public:
 Character(int n, string s) : age_(n), name_(s) {}
 int age_;
 string name_;
};

class Compare {
public:
 bool operator() (Character* ca, Character* cb) {
  if (ca->age_ == 1 && cb->age_ == 1 ||
   ca->age_ != 1 && cb->age_ != 1) return false;
  return ca->age_ == 1;
 }
};


int main() {
 vector<Character*> vc{ new Character(1, "sasaki"), new Character(2, "nozomi"), new Character(1, "satchel"), new Character(6, "qingtian") };

 sort(vc.begin(), vc.end(), Compare());

 for (int i = 0; i < vc.size(); ++i) {
  printf("%s ", vc[i]->name_.c_str());
 }

 return 0;
}// output: sasaki satchel nozomi qingtian

Reference:

1. std::sort

2. comparator

3. strict weak order

conclusion