C++刷题实践--排序总结

2023-12-13 06:43:47

STL容器的排序场景

在STL中,容器需要用到排序的场景,按照使用方法,可以分为如下四类:

  • STL自动排序的关联型容器(底层结构采取红黑树),如set、map等
  • stack、queue和priority-queue都有特定的出入口,不允许用户对元素进行排序访问。
  • 使用sort算法的支持随机访问的容器:vector,deque,string
  • list的迭代器属于双向迭代,需要使用自己sort成员函数。

重点:vector和map

vector

一维?vector:
vector<int> vec{1,2,3,4};

//默认从小到大排序  1234
sort(vec.begin(),vec.end());
//从大到小排序 4321
sort(vec.begin(),vec.end(),greater<int>());

二维?vector + cmp:

?vector<vector< int >>

//默认优先对第一元素进行从小到大排序,第一元素相同的,按照第二元素从小到大排序

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

//默认优先对第一元素进行从小到大排序,第一元素相同的,按照第二元素从小到大排序
sort(vec.begin(),vec.end()); //[0,2],[1,5],[1,9],[4,6],[5,9],[8,10]

static bool cmp(const vector<int>& v1, const vector<int>& v2){
    //如果第一元素相等,则比较第二元素
    if (v1[0] == v2[0])
        return v1[1] < v2[1];
    return v1[0] > v2[0];
}

vector<vector<int>> vec{{0,2},{1,5},{1,9},{4,6},{5,9},{8,10}};
sort(vec.begin(),vec.end(),cmp);
//[8,10],[5,9],[4,6],[1,5],[1,9],[0,2]

匿名函数Lambda :

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

sort(vec.begin(),vec.end(),[&](const vector<int> &v1, const vector<int> &v2){
    //如果第一元素相等,则比较第二元素
    if (v1[0] == v2[0])
        return v1[1] < v2[1];
    return v1[0] > v2[0];
});
//[8,10],[5,9],[4,6],[1,5],[1,9],[0,2]

map

  • map容器默认排序规则为 按照key值进行 从小到大排序(不能按照value排序),利用仿函数,可以改变排序规则
  • 对于自定义数据类型,map必须要指定排序规则
map中的按key的默认排序
class MyCompare {
public:
	bool operator()(int v1, int v2) { //v1和v2是两个pair的key
		return v1 > v2;
	}
};

void test01() 
{
	//默认从小到大排序
    //map<int, int, MyCompare> m;
	//利用仿函数实现从大到小排序
	map<int, int, MyCompare> m;

	m.insert(make_pair(1, 10));
	m.insert(make_pair(2, 20));
	m.insert(make_pair(3, 30));
	m.insert(make_pair(4, 40));
	m.insert(make_pair(5, 50));

	for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
}
map希望按value排序-解决方法

????????虽然不能直接用sort对map进行排序,但因为map中所有元素都是pair 。可以把map中的pair元素放到序列容器(如vector)中,然后再对这些元素进行排序。

bool compare(const pair<string,int>& a,const pair<string,int>& b){
	if(a.second==b.second)return a.first<b.first;
        else return a.second>b.second;
}
map<string,int> m{{"a",1},{"b",2},{"c",3}};

vector<pair<string,int>> v(m.begin(),m.end());//将map中的元素拷贝到vector中

sort(v.begin(),v.end(),compare);//实现value的排序

set

内置数据类型:
//set 容器默认的存储的是升序。
set<int> S = {1,3,2};

//可改为降序
set<int, greater<int>> S = {1,3,2};

自定义数据类型:
#include <set>
#include <string>
?
class Person
{
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }
?
    string m_Name;
    int m_Age;
?
};
class comparePerson
{
public:
    bool operator()(const Person& p1, const Person &p2)//注意const
    {
        //按照年龄进行排序  降序
        return p1.m_Age > p2.m_Age;
    }
};
?
void test01()
{
    set<Person, comparePerson> s;
?
    Person p1("刘备", 23);
    Person p2("关羽", 27);
    Person p3("张飞", 25);
    Person p4("赵云", 21);
?
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);
?
    for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "姓名: " << it->m_Name << " 年龄: " << it->m_Age << endl;
    }
}
int main() {
?
    test01();
?
    system("pause");
?
    return 0;
}

注意:对于自定义数据类型,set必须指定排序规则才可以插入数据

参考

C++,自定义sort排序算法,map(key和value分别如何排序),set,priority_queue 自定义存储顺序_c++ map key sort-CSDN博客

C++ vector 自定义排序规则(vector<vector<int>>、vector<pair<int,int>>)_vector自定义排序-CSDN博客

C++:map自定义排序_c++ map排序-CSDN博客

文章来源:https://blog.csdn.net/weixin_46697509/article/details/134878149
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。