C++使用sort对容器排序的实现

本文主要解决以下问题

STL中sort的使用方法
使用sort对vector的排序
使用sort对map排序
使用sort对list排序

STL中sort的使用方法

C++ STL 标准库中的 sort() 函数，本质就是一个模板函数。该函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认以元素值的大小做升序排序，除此之外我们也可以选择标准库提供的其它排序规则（比如std::greater降序排序规则），甚至还可以自定义排序规则。

值得一提的是，sort() 函数位于头文件中，因此在使用该函数前，程序中应包含如下语句：

				?

									#include <algorithm>

sort() 函数有 2 种用法，其语法格式分别为：

				?

									//对 [first, last) 区域内的元素做默认的升序排序

									void sort (RandomAccessIterator first, RandomAccessIterator last);

									//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序

									void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

其中，first 和 last 都为随机访问迭代器，它们的组合 [first, last) 用来指定要排序的目标区域；另外在第 2 种格式中，comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater），也可以是自定义的排序规则。

数组排序样例：

				?

									#include <algorithm>

									#include <algorithm>

									using namespace std;

									int main(){

									    int arr[] = {2,6,3,5,4,8,1,0,9,10};

									    sort(arr, arr+10);

									    for(int i = 0;i < 10;i++)

									        cout << arr[i] << " ";

									}

									// out

									/*

									0 1 2 3 4 5 6 8 9 10

									*/

使用 STL 标准库提供的排序规则

				?

									int main(){

									    int arr[] = {2,6,3,5,4,8,1,0,9,10};

									    sort(arr, arr+10, std::greater<int>());

									    for(int i = 0;i < 10;i++)

									        cout << arr[i] << " ";

									    cout << endl;

									    sort(arr, arr+10, std::less<int>());

									    for(int i = 0;i < 10;i++)

									        cout << arr[i] << " ";

									}

									// out

									/*

									10 9 8 6 5 4 3 2 1 0

									0 1 2 3 4 5 6 8 9 10

									*/

使用自定义比较器

				?

									bool cmp(const int a, const int b){

									    return a < b;

									}

									int main(){

									    int arr[] = {2,6,3,5,4,8,1,0,9,10};

									    sort(arr, arr+10, cmp);

									    for(int i = 0;i < 10;i++)

									        cout << arr[i] << " ";

									}

									// out

									/*

									0 1 2 3 4 5 6 8 9 10

									*/

使用 lambda 表达式自定义比较器

				?

									int main(){

									    int arr[] = {2,6,3,5,4,8,1,0,9,10};

									    sort(arr, arr+10, [](const int a, const int b){

									         return a < b;

									         });

									    for(int i = 0;i < 10;i++)

									        cout << arr[i] << " ";

									}

									// out

									/*

									0 1 2 3 4 5 6 8 9 10

									*/

使用sort对vector的排序

在 C++ 中几乎操作vector时，几乎可以视作是在操作数组，可以将vector看作对数组的封装。因此，使用sort对vector进行排序时完全可以遵循上面使用sort对数组的排序方法。

一维vector排序

				?

									int main(){

									    vector<int> vec = {2,6,3,5,4,8,1,0,9,10};

									    sort(vec.begin(), vec.end());

									    for(int item: vec)

									        cout << item << " ";

									    return 0;

									}

									// out

									/*

									0 1 2 3 4 5 6 8 9 10

									*/

二维vector排序。数组保存一系列的坐标，先按照第二维进行升序排列，再按照第一维升序排列

				?

									int main(){

									    vector<vector<int>> vvi = {{9,1}, {2,3}, {8,7}, {6,2}, {5,2}};

									    sort(vvi.begin(), vvi.end(), [](const vector<int>& v1, const vector<int>& v2){

									         if(v1[1] < v2[1]) return true;

									         else if(v1[1] == v2[1]) return v1[0] < v2[0];

									         else return false;

									         });

									    for(vector<int> v: vvi){

									        for(int item: v){

									            cout << item << " ";

									        }

									        cout << endl;

									    }

									    return 0;

									}

									// out

									/*

									9 1

									5 2

									6 2

									2 3

									8 7

									*/

使用sort对map排序

map是用来存放<key, value>键值对的数据结构，可以很方便快速的根据key查到相应的value，map本身的实现方式内含了比较器的设置，只要我们在map初始化的时候传入比较器，即可完成对应的排序。

定义包含水果及其个数的map，按照水果名称字典序进行排序（按key排序）

				?

									#include<map>

									using namespace std;

									int main(){

									    map<string, int, less<string>> msi;

									    msi["apple"] = 5;

									    msi["watermelon"] = 2;

									    msi["pear"] = 3;

									    msi["peach"] = 6;

									    msi["cherry"] = 10;

									    for(auto item: msi)

									        cout << item.first << " " << item.second << endl;

									    return 0;

									}

									// out

									/*

									apple 5

									cherry 10

									peach 6

									pear 3

									watermelon 2

									*/

定义包含水果及其个数的map，按照水果个数进行排序，当水果个数相同时，按照水果名称字典序排序（将map转为vector进行排序）

				?

									bool cmp(const pair<string, int>& a, const pair<string, int>& b){

									    if(a.second < b.second) return true;

									    else if(a.second == b.second) return a.first < b.first;

									    else return false;

									}

									int main(){

									    map<string, int> msi;

									    msi["apple"] = 5;

									    msi["watermelon"] = 2;

									    msi["pear"] = 3;

									    msi["peach"] = 5;

									    msi["cherry"] = 10;

									    vector<pair<string, int>> vpi(msi.begin(), msi.end());

									    sort(vpi.begin(), vpi.end(), cmp);

									    for(auto item: vpi){

									        cout << item.first << " " << item.second << endl;

									    }

									    return 0;

									}

									// out

									/*

									watermelon 2

									pear 3

									apple 5

									peach 5

									cherry 10

									*/

使用sort对list排序

sort() 函数模板定义在头文件 algorithm 中，要求使用随机访问迭代器。但 list 容器并不提供随机访问迭代器，只提供双向迭代器，因此不能对 list 中的元素使用 sort() 算法。但是，还是可以进行元素排序，因为 list 模板定义了自己的 sort() 函数。sort() 有两个版本：无参 sort() 函数将所有元素升序排列。第二个版本的 sort() 接受一个函数对象或 lambda 表达式作为参数，这两种参数都定义一个断言用来比较两个元素。

list排序示例

				?

									int main(){

									    list<string> ls = {"one", "two", "three"};

									    ls.sort([](const string& a, const string& b){

									                return a < b;

									            });

									    for(string item: ls) cout << item << " ";

									    return 0;

									}

									// out

									/*

									one three two

									*/