服务器之家

服务器之家 > 正文

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

时间:2021-11-09 13:21     来源/作者:范中豪

本文主要解决以下问题

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

STL中sort的使用方法

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

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

?
1
#include <algorithm>

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

?
1
2
3
4
//对 [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),也可以是自定义的排序规则。

数组排序样例:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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 标准库提供的排序规则

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
*/

使用自定义比较器

?
1
2
3
4
5
6
7
8
9
10
11
12
13
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 表达式自定义比较器

?
1
2
3
4
5
6
7
8
9
10
11
12
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排序

?
1
2
3
4
5
6
7
8
9
10
11
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排序。数组保存一系列的坐标,先按照第二维进行升序排列,再按照第一维升序排列

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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排序)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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进行排序)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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排序示例

?
1
2
3
4
5
6
7
8
9
10
11
12
13
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
*/

参考文献

C++中SORT函数使用方法

C++ sort()排序函数用法详解

C++ Lambda表达式详解

STL-map的简单用法

C++ STL中Map的按Key排序和按Value排序

C++ list(STL list)排序及合并元素方法详解

到此这篇关于C++使用sort对容器排序的实现的文章就介绍到这了,更多相关C++ sort对容器排序 内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://www.cnblogs.com/zhhfan/p/14789325.html

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部